r = symrcm(S)
r = symrcm(S)
returns the symmetric reverse Cuthill-McKee ordering of S
. This is a permutation r
such that S(r,r)
tends 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 and asymmetric S
.
For a real, symmetric sparse matrix, S
, the eigenvalues of S(r,r)
are the same as those of S
, but eig(S(r,r))
probably takes less time to compute than eig(S)
.
B = bucky
uses an M-file 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
subplot(1,2,1), spy(B), title('B')
The reverse Cuthill-McKee ordering is obtained with
Thep = symrcm(B);
R = B(p,p);
spy
plot shows a much narrower bandwidth:
subplot(1,2,2), spy(R), title('B(p,p)')
This example is continued in the reference pages for symmmd
.The bandwidth can also be computed with
The bandwidths of[i,j] = find(B);
bw = max(i-j) + 1
B
and R
are 35 and 12, respectively.
\
,chol
,colmmd
,colperm
,eig
,lu
[2] John R. Gilbert, Cleve Moler, and Robert Schreiber, "Sparse Matrices in MATLAB: Design and Implementation," to appear in SIAM Journal on Matrix Analysis, 1992. A slightly expanded version is also available as a technical report from the Xerox Palo Alto Research Center.
(c) Copyright 1994 by The MathWorks, Inc.