Cuthill–McKee algorithm - Alchetron, the free social encyclopedia

In the mathematical subfield of matrix theory, the Cuthill–McKee algorithm (CM), named for Elizabeth Cuthill and J. 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 R i for i = 1 , 2 , . . until all nodes are exhausted. The set R i + 1 is created from set R i by listing all vertices adjacent to all nodes in 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 n × 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 := ( { x } ) .

Then for i = 1 , 2 , … 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 := Adj ⁡ ( R i ) ∖ R

Sort A i with ascending vertex order (vertex degree).

Append A i to the Result set 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

Cuthill–McKee algorithm Wikipedia

(Text) CC BY-SA