1
$\begingroup$

Is it necessary to reorder nodes (using Reverse Cuthill-Mckee algorithm, for example) if I am already using a CSR or CSC storing technique? Because, since CSR/CSC only stores non-zero elements I guess reorder wouldn't be much advantageous.

$\endgroup$
4
$\begingroup$

You should use a reordering. Although it's true that storing a sparse matrix requires the same amount of memory whether or not you reorder it using RCM, reordering it should lead to faster calculations (eg matrix-vector products) due to different/better utilization of cache.

Something to keep in mind is that the "best" reordering depends upon what you intend to do with the matrix. Bandwidth reduction reorderings (like RCM) help with matvec's, but if you're reordering a matrix for parallel distribution you should look into methods that minimize edge-cut/communication-volume (like METIS, others), and if you're looking into sparse direct methods you should consider unstructured nested-dissection (METIS/SCOTCH) or fill-minimization (minimum degree or appproximate MD).

$\endgroup$
  • $\begingroup$ Do you have any references, or even just a crude estimate based on your personal experience, on what kind of speedup one could expect when reordering a sparse MVP? I'm personally interested in sparse matrices arising from 3D FEM systems of size in the 100s of MBs to GBs. $\endgroup$ – LedHead Apr 30 at 17:15
  • $\begingroup$ Unfortunately I do not. On very large systems the reordering effect might be pretty subtle, since you can only squeeze the bandwidth so much on a matrix with 3D connectivity. I think a new question might be in order. For what it's worth, it's not too hard of an experiment to run for yourself in eg matlab or some other linear algebra platform. On the other hand, for direct solvers the effects of reordering are enormous, their asymptotic complexity (big-O) hinges on doing it properly. $\endgroup$ – rchilton1980 May 1 at 0:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.