CuthillMoore

The Cuthill–Moore algorithm, also known as the Cuthill–Moore ordering, is a heuristic method for reducing the bandwidth of a sparse matrix by reordering its rows and columns. It interprets the sparsity pattern as a graph and seeks an ordering that places connected nodes close together in the sequence. This reordering can lead to sparser intermediate factors and improved numerical performance in subsequent computations.

The algorithm typically works with a BFS-like procedure. It starts from a vertex with a low degree in each connected component and visits neighboring vertices in order of increasing degree, producing a permutation of the indices. The resulting ordering tends to cluster nonzero entries near the diagonal, thereby reducing the matrix bandwidth and the profile. This reduction often translates into less fill-in during LU or Cholesky factorization and better cache efficiency.

A common variant is the Reverse Cuthill–Moore (RCM) ordering, which reverses the obtained sequence and frequently yields even smaller bandwidth. The method is widely used in finite element analysis and other applications involving large sparse linear systems, where a smaller bandwidth can significantly accelerate factorization and solve steps.

The Cuthill–Moore algorithm is heuristic and not guaranteed to be optimal. It is typically implemented with near-linear time relative to the number of nonzero entries, making it an efficient preprocessing step in many numerical linear algebra workflows. The approach remains a staple in sparse matrix preprocessing and graph-based reordering.