Editing Cuthill–McKee algorithm (section)

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

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