MATLAB Function Reference |

Sparse reverse Cuthill-McKee ordering

**Syntax**

**Description**

```
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 nonsymmetric `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)`

.

**Algorithm**

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.

**Examples**

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

The reverse Cuthill-McKee ordering is obtained with

The `spy`

plot shows a much narrower bandwidth.

This example is continued in the reference pages for `symmmd`

.

The bandwidth can also be computed with

The bandwidths of `B`

and `R`

are 35 and 12, respectively.

**See Also**

`colamd`

, `colmmd`

, `colperm`

, `symamd`

, `symmmd`

**References**

[1] George, Alan and Joseph Liu, *Computer Solution of Large Sparse Positive
Definite Systems*, Prentice-Hall, 1981.

[2] Gilbert, John R., 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.

symmmd | symvar |

© 1994-2005 The MathWorks, Inc.