Cuthill–McKee algorithm: Difference between revisions

Revision as of 19:30, 12 December 2011

Revision as of 19:55, 12 December 2011

Line 1:

In the [[mathematics|mathematical]] subfield of [[matrix theory]], the '''Cuthill–McKee algorithm''' (named for Elizabeth Cuthill and J. McKee) is an [[algorithm]] to permute a matrix into a banded form with small

*<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>

==Algorithm==

Line 23 ⟶ 24:

==References==

<references />

*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.

== External links ==

* [http://www.boost.org/doc/libs/1_37_0/libs/graph/doc/cuthill_mckee_ordering.html Cuthill–McKee documentation] for the [[Boost C++ Libraries]].

* [http://ciprian-zavoianu.blogspot.com/2009/01/project-bandwidth-reduction.html A detailed description of the Cuthill–McKee algorithm].