`symrcm`

Reverse Cuthill-McKee ordering that reduces the bandwidth of a sparse matrix.

Syntax

p = symrcm(S)

Returns a permutation vector p so that S(p,p) has a smaller bandwidth.

Description

The method numbers the nodes of the matrix graph in breadth-first order, starting from a node far from the center, and then reverses the order. Rows and columns that are linked end up near each other, so the nonzeros gather near the diagonal. A narrower band means less fill-in in banded Cholesky or LU factorizations, and a more cache-friendly matrix-vector product.

Apply it symmetrically, S(p,p), to keep a symmetric matrix symmetric.

Input arguments

S: Square sparse matrix, treated as symmetric by its pattern.

Output arguments

p: Row vector, a permutation of 1:size(S,1).

Example

Reordering a matrix

S = sparse([1 0 0 1; 0 1 1 0; 0 1 1 0; 1 0 0 1]);
p = symrcm(S)
full(S(p, p))

Output

p = 1×4

     2     3     1     4
ans = 4×4

     1     1     0     0
     1     1     0     0
     0     0     1     1
     0     0     1     1

symrcm