Cuthill–McKee algorithm: Difference between revisions

Revision as of 20:04, 12 December 2011

Latest revision as of 04:43, 13 August 2025

(49 intermediate revisions by 35 users not shown)

Line 1:

[[File:Can 73 cm.svg|thumb|Cuthill-McKee ordering of a 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 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

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

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

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

algorithm used in graph algorithms. It starts with a peripheral node and then

generates [[Level structure|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 ordered according to predecessors and degree.

==Algorithm==

Given a symmetric <math>n\times n</math> matrix we visualize the matrix as the [[adjacency matrix]] of a [[graphGraph (discrete mathematics)|graph]]. The Cuthill–McKee algorithm is then a relabeling of the [[vertex (graph theory)|vertices]] of the graph to reduce the bandwidth of the adjacency matrix.

The algorithm produces an ordered [[n-tuple|''n''-tuple]] ''<math>R''</math> of vertices which is the new order of the vertices.

First we choose a [[peripheral vertex]] ''(the vertex with the lowest [[Degree (graph theory)|degree]]) <math>x''</math> and set ''<math>R'' := ( \{'' x'' \})</math>.

Then for <math>i = 1,2,\dots</math> we iterate the following steps while <math>|''R''| < ''n''</math>

*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> ascending by minimum 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>

*Sort <math>A_i</math> with ascending vertex order.

*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 26 ⟶ 35:

==References==

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

[[Category:Graph algorithms]]

[[Category:Sparse matrices]]

[[es:Algoritmo de Cuthill-McKee]]

[[ru:Алгоритм Катхилла-Макки]]