Cuthill–McKee Algorithm

In numerical linear algebra, the Cuthill–McKee algorithm (CM), named after Elizabeth Cuthill and James McKee,E. Cuthill and J. McKee
the bandwidth of sparse symmetric matrices''
In Proc. 24th Nat. Conf. ACM, pages 157–172, 1969. 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 and Joseph Liu is the same algorithm but with the resulting index numbers reversed. In practice this generally results in less fill-in than the CM ordering when Gaussian elimination is applied.J. A. George and J. W-H. Liu, Computer Solution of Large Sparse Positive Definite Systems, Prentice-Hall, 1981

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 $R_i$ for $i=1, 2,..$ until all nodes
are exhausted. The set $R_$ is created from set $R_i$
by listing all vertices adjacent to all nodes in $R_i$. These
nodes are ordered according to predecessors and degree.

Algorithm

Given a symmetric $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 $R$ of vertices which is the new order of the vertices.

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

Then for $i = 1,2,\dots$ we iterate the following steps while $, R, < n$

*Construct the adjacency set $A_i$ of $R_i$ (with $R_i$ the ''i''-th component of $R$) and exclude the vertices we already have in $R$
:$A_i := \operatorname(R_i) \setminus R$
*Sort $A_i$ ascending by minimum predecessor (the already-visited neighbor with the earliest position in R), and as a tiebreak ascending by vertex degree.The Reverse Cuthill-McKee Algorithm in Distributed-Memor

slide 8, 2016
*Append $A_i$ to the Result set $R$.

In other words, number the vertices according to a particular level structure (computed by breadth-first search) where the vertices in each level are visited in order of their predecessor's numbering from lowest to highest. Where the predecessors are the same, vertices are distinguished by degree (again ordered from lowest to highest).

See also

*Graph bandwidth
*Sparse matrix

References

Cuthill–McKee documentation
for the Boost C++ Libraries.

A detailed description of the Cuthill–McKee algorithm



MATLAB's implementation of RCM.


RCM routine from SciPy written in Cython.

{{DEFAULTSORT:Cuthill-McKee algorithm
Matrix theory
Graph algorithms
Sparse matrices