# Reordering sparse matrices in computational science

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.

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.