Cuthill–McKee algorithm


In numerical linear algebra, the Cuthill–McKee algorithm, 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 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 and set.
Then for we iterate the following steps while
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.