Cuthill–McKee algorithm

In numerical linear algebra, the Cuthill–McKee algorithm (CM), named for Elizabeth Cuthill  and James McKee, 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. In practice this generally results in less fill-in  than the CM ordering when Gaussian elimination is applied.

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  for  until all nodes
are exhausted. The set  is created from set 
by listing all vertices adjacent to all nodes in . These 
nodes are listed in increasing degree. This last detail is the only difference
with the breadth-first search algorithm.

Algorithm

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

First we choose a peripheral vertex (the vertex with the lowest degree)  and set .

Then for  we iterate the following steps while 

Construct the adjacency set  of  (with  the i-th component of ) and exclude the vertices we already have in 

Sort  with ascending vertex order (vertex degree).
Append  to the Result set .

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.

See also
Graph bandwidth
Sparse matrix

References

 Cuthill–McKee documentation for the Boost C++ Libraries.
 A detailed description of the Cuthill–McKee algorithm.
 symrcm MATLAB's implementation of RCM.
 reverse_cuthill_mckee RCM routine from SciPy written in Cython.

Category:Matrix theory
Category:Graph algorithms
Category:Sparse matrices