Sparse reverse Cuthill-McKee ordering
r = symrcm(S)
r = symrcm(S) returns
the symmetric reverse Cuthill-McKee ordering of
This is a permutation
r such that
to have its nonzero elements closer to the diagonal. This is a good
preordering for LU or Cholesky factorization of matrices that come
from long, skinny problems. The ordering works for both symmetric
For a real, symmetric sparse matrix,
S(r,r) are the same as those of
eig(S(r,r)) probably takes less time to compute
B = bucky;
uses a function in the
demos toolbox to generate the adjacency graph of a truncated icosahedron. This is better known as a soccer ball, a Buckminster Fuller geodesic dome (hence the name
bucky), or, more recently, as a 60-atom carbon molecule. There are 60 vertices. The vertices have been ordered by numbering half of them from one hemisphere, pentagon by pentagon; then reflecting into the other hemisphere and gluing the two halves together.
With this numbering, the matrix does not have a particularly narrow bandwidth, as the first spy plot shows:
The reverse Cuthill-McKee ordering is obtained with:
p = symrcm(B); R = B(p,p);
spy plot shows a much narrower bandwidth.
This example is continued in the reference page for
The bandwidth can also be computed with:
[i,j] = find(B); bw = max(i-j) + 1;
The bandwidths of
R are 35 and 12, respectively.
The algorithm first finds a pseudoperipheral vertex of the graph of the matrix. It then generates a level structure by breadth-first search and orders the vertices by decreasing distance from the pseudoperipheral vertex. The implementation is based closely on the SPARSPAK implementation described by George and Liu.
 George, Alan and Joseph Liu, Computer Solution of Large Sparse Positive Definite Systems, Prentice-Hall, 1981.
 Gilbert, John R., Cleve Moler, and Robert Schreiber, “Sparse Matrices in MATLAB: Design and Implementation,” SIAM Journal on Matrix Analysis, 1992. A slightly expanded version is also available as a technical report from the Xerox Palo Alto Research Center.