Cuthill–McKee algorithm: Difference between revisions

Revision as of 17:58, 16 January 2017

Revision as of 18:19, 16 January 2017

Line 3:

[[File:can 73 rcm svg.svg|thumb|RCM ordering of the same matrix]]

In the [[mathematics|mathematical]] subfield of [[Matrix (mathematics)|matrix theory]], the '''Cuthill–McKee algorithm''' ('''CM'''), 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 [[sparse matrix]] that has a [[symmetric matrix|symmetric]] sparsity 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{{clarify |date=January 2017 |reason= What exactly are these index numbers?}} reversed{{clarify |date=January 2017 |reason= What does "reserved" mean in this context?}}<ref>http://ciprian-zavoianu.blogspot.ch/2009/01/project-bandwidth-reduction.html</ref>. In practice this generally results in less [[Sparse_matrix#Reducing_fill-in|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]]