Cuthill–McKee algorithm: Difference between revisions

Browse history interactively

← Previous edit

Content deleted Content added

VisualWikitext

Revision as of 20:08, 30 November 2020 edit Desertrider12 (talk \| contribs) 2 edits It's important to say that level sets are sorted by predecessor. The code in the cited blogspot explores the next level one vertex at a time from a queue, so it's not made explicit there. But this code takes R_i all at once and sorts it, so predecessor must be used to compare. The slides I cite make this clearer. ← Previous edit		Latest revision as of 04:43, 13 August 2025 edit undo Bender the Bot (talk \| contribs) Bots 1,064,377 edits m →References: HTTP to HTTPS for Blogspot Tag: AWB
(8 intermediate revisions by 7 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 ~~for~~after [[Elizabeth Cuthill ]] and James~~<ref name="mckee">[http://calhoun.nps.edu/bitstream/handle/10945/30131/recommendationsf00fran.pdf''Recommendations for ship hull surface representation''], page 6</ref>~~ 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]]. * [~~http~~https://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]].