Cuthill–McKee algorithm: Difference between revisions

Revision as of 17:55, 16 January 2017

Latest revision as of 04:43, 13 August 2025

(21 intermediate revisions by 16 users not shown)

Line 1:

[[File:canCan 73 cm svg.svg|thumb|Cuthill-McKee ordering of a matrix]]

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

In the [[mathematics|mathematical]]numerical subfieldlinear of [[Matrix (mathematics)|matrix theoryalgebra]], the '''Cuthill–McKee algorithm''' ('''CM'''), named forafter [[Elizabeth Cuthill ]] and J.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>{{clarifycite web |dateurl=January 2017http://ciprian-zavoianu.blogspot.ch/2009/01/project-bandwidth-reduction.html |reasontitle = whatCiprian isZavoianu it- meantweblog: byTutorial: "numbersBandwidth reserved"reduction in- thisThe CutHill-McKee Algorithm| date=15 January 2009 context?}}.</ref> In practice this generally results in less [[Sparse_matrixSparse matrix#Reducing_fillReducing 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 10:

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 listedordered inaccording increasingto predecessors and degree. This last detail is the only difference

with the breadth-first search algorithm.

==Algorithm==

Line 25 ⟶ 24:

*Construct the adjacency set <math>A_i</math> of <math>R_i</math> (with <math>R_i</math> the ''i''-th component of <math>R</math>) and exclude the vertices we already have in <math>R</math>

:<math>A_i := \operatorname{Adj}(R_i) \setminus R</math>

*Sort <math>A_i</math> with ascending vertexby orderminimum predecessor (the already-visited neighbor with the earliest position in R), and as a tiebreak ascending by [[Degree (graph theory)|vertex degree]]).<ref>The Reverse Cuthill-McKee Algorithm in Distributed-Memory [https://archive.siam.org/meetings/csc16/slides/ariful_azad_CSC16.pdf], slide 8, 2016</ref>

*Append <math>A_i</math> to the Result set <math>R</math>.

In other words, number the vertices according to a particular [[breadth-firstlevel search|structure]] (computed by [[breadth-first traversalsearch]]) where neighboringthe vertices in each level are visited in order of their predecessor's numbering from lowest to highest. vertexWhere orderthe predecessors are the same, vertices are distinguished by degree (again ordered from lowest to highest).

==See also==

Line 37 ⟶ 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]].

{{DEFAULTSORT:Cuthill-McKee algorithm}}

[[Category:Matrix theory]]