Reordering sparse matrices in computational science

Question

On page 3 of this document, there are some matrix forms for sparse matrices. I wonder if there are other forms used in computational problems encountered in physics, chemistry, etc., so that reordering the matrix will speedup the computation phase. Preprocessing overhead for matrix reordering should be amortizable via the gain in computation step.

Answer 1

Matrix reordering is not only useful for speedup but often mandatory in order to obtain a code which runs in a reasonable amount of time, especially for sparse direct solvers. These aim to keep the number of extra entries that are filled in during LU-factorization small. For example, the reverse Cuthill-McKee ordering is a useful heuristic for obtaining a reordering with a much smaller bandwidth, thus giving fewer extra non-zero entries when you factor the matrix. Likewise, the approximate minimum degree ordering aims to reduce the fill-in directly using some ideas from graph theory. Both of these are implemented in Matlab as symrcm and symamd respectively if you want to try them yourself. If you want to know more, you should look at Davis's book Direct Methods for Sparse Linear Systems in chapter 7.

The same reorderings are also helpful if you are using an iterative solver but you're preconditioning with an incomplete LU-factorization. There are other orderings which you might choose instead if you are only using iterative methods. The independent set ordering and multicolor ordering (see Iterative Methods for Sparse Linear Systems, chapter 12) are useful for parallelizing Gauss-Seidel iteration and in turn obtaining a parallel implementation of the multigrid algorithm.

The initial cost of reordering your system can be amply paid back in speedup later. For a time-dependent or nonlinear PDE, where you solve not one but several linear systems, this is especially true. Often it is the case for a single linear system too, but you should make that judgment call based on what method you're using, the cost of applying the permutation to the matrix storage format you've chosen, etc. Finally, for discretizing a PDE on an unstructured mesh, you're more likely to wind up with one of the "other" formats, (j) and (k) in the page you linked, than a nice-looking one like banded diagonal.

Answer 2

In a moment of boredom, I compared a whole lot of reordering strategies with regard to their ability to speed up preconditioners. I put this comparison here (after the heading A comparison of reordering strategies):

http://www.dealii.org/developer/doxygen/deal.II/namespaceDoFRenumbering.html