Content deleted Content added
Added a reference explaining what I asked to be explained before |
m WP:CHECKWIKI error fix for #61. Punctuation goes before References. Do general fixes if a problem exists. - |
||
Line 3:
[[File:can 73 rcm svg.svg|thumb|RCM ordering of the same matrix]]
In the [[mathematics|mathematical]] subfield of [[Matrix (mathematics)|matrix theory]], the '''Cuthill–McKee algorithm''' ('''CM'''), 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 [[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 is the same algorithm but with the resulting index numbers reversed.<ref>http://ciprian-zavoianu.blogspot.ch/2009/01/project-bandwidth-reduction.html</ref>
The Cuthill McKee algorithm is a variant of the standard [[breadth-first search]]
Line 40:
* [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]]
|