Cuthill–McKee algorithm: Difference between revisions

Revision as of 02:22, 12 October 2024

Latest revision as of 04:43, 13 August 2025

(2 intermediate revisions by 2 users not shown)

Line 3:

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

In [[numerical linear algebra]], the '''Cuthill–McKee algorithm''' ('''CM'''), named after [[Elizabeth Cuthill]] and James 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 and Joseph Liu is the same algorithm but with the resulting index numbers reversed.<ref>{{cite web |url=http://ciprian-zavoianu.blogspot.ch/2009/01/project-bandwidth-reduction.html |title = Ciprian Zavoianu - weblog: Tutorial: Bandwidth reduction - The CutHill-McKee Algorithm| date=15 January 2009 }}</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]]

Line 36:

<references />

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

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

* [http://www.mathworks.com/help/matlab/ref/symrcm.html symrcm] MATLAB's implementation of RCM.

* [http://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.csgraph.reverse_cuthill_mckee.html reverse_cuthill_mckee] RCM routine from [[SciPy]] written in [[Cython]].

Line 42:

{{DEFAULTSORT:Cuthill-McKee algorithm}}

[[Category:Matrix theory]]

[[Category:AlgorithmsGraph in graph theoryalgorithms]]

[[Category:Sparse matrices]]