# Cuthill–McKee algorithm

(Redirected from Reverse Cuthill-McKee algorithm)
Cuthill-McKee ordering of a matrix
RCM ordering of the same matrix

In numerical linear algebra, the Cuthill–McKee algorithm (CM), named for Elizabeth Cuthill and James[1] McKee,[2] is an algorithm to permute a sparse matrix that has a symmetric sparsity pattern into a band matrix form with a small bandwidth. The reverse Cuthill–McKee algorithm (RCM) due to Alan George is the same algorithm but with the resulting index numbers reversed.[3] In practice this generally results in less fill-in than the CM ordering when Gaussian elimination is applied.[4]

The Cuthill McKee algorithm is a variant of the standard breadth-first search algorithm used in graph algorithms. It starts with a peripheral node and then generates levels ${\displaystyle R_{i}}$ for ${\displaystyle i=1,2,..}$ until all nodes are exhausted. The set ${\displaystyle R_{i+1}}$ is created from set ${\displaystyle R_{i}}$ by listing all vertices adjacent to all nodes in ${\displaystyle R_{i}}$. These nodes are listed in increasing degree. This last detail is the only difference with the breadth-first search algorithm.

## Algorithm

Given a symmetric ${\displaystyle n\times n}$ matrix we visualize the matrix as the adjacency matrix of a graph. The Cuthill–McKee algorithm is then a relabeling of the vertices of the graph to reduce the bandwidth of the adjacency matrix.

The algorithm produces an ordered n-tuple ${\displaystyle R}$ of vertices which is the new order of the vertices.

First we choose a peripheral vertex (the vertex with the lowest degree) ${\displaystyle x}$ and set ${\displaystyle R:=(\{x\})}$.

Then for ${\displaystyle i=1,2,\dots }$ we iterate the following steps while ${\displaystyle |R|

• Construct the adjacency set ${\displaystyle A_{i}}$ of ${\displaystyle R_{i}}$ (with ${\displaystyle R_{i}}$ the i-th component of ${\displaystyle R}$) and exclude the vertices we already have in ${\displaystyle R}$
${\displaystyle A_{i}:=\operatorname {Adj} (R_{i})\setminus R}$
• Sort ${\displaystyle A_{i}}$ with ascending vertex order (vertex degree).
• Append ${\displaystyle A_{i}}$ to the Result set ${\displaystyle R}$.

In other words, number the vertices according to a particular breadth-first traversal where neighboring vertices are visited in order from lowest to highest vertex order.

## References

1. ^
2. ^ E. Cuthill and J. McKee. Reducing the bandwidth of sparse symmetric matrices In Proc. 24th Nat. Conf. ACM, pages 157–172, 1969.
3. ^ http://ciprian-zavoianu.blogspot.ch/2009/01/project-bandwidth-reduction.html
4. ^ J. A. George and J. W-H. Liu, Computer Solution of Large Sparse Positive Definite Systems, Prentice-Hall, 1981