Sparse Matrix Ordering
Reorder the rows and columns of a sparse matrix (represented as a graph) to reduce fill-in during factorization or to improve cache locality. Each vertex represents a row/column; edges represent nonzero entries.
| Algorithm | When to use |
|---|---|
Reduces bandwidth. The reverse Cuthill-McKee ordering (just reverse the output) is widely used for FEM and sparse linear solvers. |
|
Similar to Cuthill-McKee but minimizes the profile instead of bandwidth. |
|
Reduces fill-in during Cholesky factorization. Good for symmetric positive definite systems. |
|
Reduces both profile and wavefront simultaneously. |
|
Selects good starting and ending vertices for the Sloan algorithm. |
These orderings are evaluated using the metrics in Graph Metrics: bandwidth, profile, and wavefront.