Cuthill–McKee algorithm: Difference between revisions

Revision as of 20:55, 12 December 2011

Revision as of 21:17, 12 December 2011

Line 1:

In the [[mathematics|mathematical]] subfield of [[matrix theory]], the '''Cuthill–McKee algorithm''' (named for Elizabeth Cuthill and J. McKee)

<ref name="cm"> E. Cuthill and J. McKee. [http://portal.acm.org/citation.cfm?id=805928''Reducing the bandwidth of sparse symmetric matrices''] In Proc. 24th Nat. Conf. [[Association for Computing Machinery|ACM]], pages 157–172, 1969.</ref> is an [[algorithm]] to permute a matrix into a banded form with a small

[[bandwidth (matrix theory)|bandwidth]] of [[sparse matrix|sparse]] [[symmetric matrix|symmetric matrices]]. 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.<ref name="gl"> J. A. George and J. W-H. Liu, Computer Solution of Large Sparse Positive Definite Systems, Prentice-Hall, 1981 </ref>

[[File:can_73_orig.pdf|thumb|Original matrix from Harwell-Boeing collection]]

Line 8 ⟶ 6:

[[File:can_73_rcm.pdf|thumb|RCM ordering of the same matrix]]

In the [[mathematics|mathematical]] subfield of [[matrix theory]], the '''Cuthill–McKee algorithm''' (named for Elizabeth Cuthill and J. McKee)

<ref name="cm"> E. Cuthill and J. McKee. [[http://portal.acm.org/citation.cfm?id=805928''Reducing the bandwidth (matrixof theory)sparse symmetric matrices''] In Proc. 24th Nat. Conf. [[Association for Computing Machinery|bandwidthACM]], ofpages 157–172, 1969.</ref> is an [[algorithm]] to permute a [[sparse matrix|sparse]] that has a [[symmetric matrix|symmetric]] matricessparsity pattern into a [[band matrix]] form with a small [[bandwidth (matrix theory)|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.<ref name="gl"> J. A. George and J. W-H. Liu, Computer Solution of Large Sparse Positive Definite Systems, Prentice-Hall, 1981 </ref>

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 <math>R_i</math> for <math>i=1, 2,..</math> until all nodes

are exhausted. The set <math> R_{i+1} </math> is created from set <math> R_i</math>

by listing all vertices adjacent to all nodes in <math> R_i </math>. These

nodes are listed in increasing degree. This last detail is the only difference

with the breadth-first search algorithm.

==Algorithm==