Dirac measure: Difference between revisions
en>Helpful Pixie Bot m ISBNs (Build KH) |
en>DumbBOT removing a protection template from a non-protected page (info) |
||
Line 1: | Line 1: | ||
[[File:can 73 cm.pdf|thumb|Cuthill-McKee ordering of the same matrix]] | |||
[[File:can 73 rcm.pdf|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. 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 listed in increasing degree. This last detail is the only difference | |||
with the breadth-first search algorithm. | |||
==Algorithm== | |||
Given a symmetric <math>n\times n</math> matrix we visualize the matrix as the [[adjacency matrix]] of a [[graph (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]] ''R'' 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]]) ''x'' and set ''R'' := ({''x''}). | |||
Then for <math>i = 1,2,\dots</math> we iterate the following steps while |''R''| < ''n'' | |||
*Construct the adjacency set <math>A_i</math> of <math>R_i</math> (with <math>R_i</math> the ''i''-th component of ''R'') and exclude the vertices we already have in ''R'' | |||
:<math>A_i := \operatorname{Adj}(R_i) \setminus R</math> | |||
*Sort <math>A_i</math> with ascending vertex order ([[Degree (graph theory)|vertex degree]]). | |||
*Append <math>A_i</math> to the Result set ''R''. | |||
In other words, number the vertices according to a particular [[breadth-first search|breadth-first traversal]] where neighboring vertices are visited in order from lowest to highest vertex order. | |||
==See also== | |||
*[[Graph bandwidth]] | |||
*[[Sparse matrix]] | |||
==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]]. | |||
* [http://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. | |||
{{DEFAULTSORT:Cuthill-McKee algorithm}} | |||
[[Category:Matrix theory]] | |||
[[Category:Graph algorithms]] | |||
[[Category:Sparse matrices]] |
Revision as of 16:17, 14 November 2013
In the mathematical subfield of matrix theory, the Cuthill–McKee algorithm (CM), named for Elizabeth Cuthill and J. McKee ,[1] is an algorithm to permute a sparse matrix that has a symmetric sparsity pattern into a band matrix form with a small bandwidth. 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.[2]
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 levels for until all nodes are exhausted. The set is created from set by listing all vertices adjacent to all nodes in . These nodes are listed in increasing degree. This last detail is the only difference with the breadth-first search algorithm.
Algorithm
Given a symmetric matrix we visualize the matrix as the adjacency matrix of a graph. The Cuthill–McKee algorithm is then a relabeling of the vertices of the graph to reduce the bandwidth of the adjacency matrix.
The algorithm produces an ordered n-tuple R of vertices which is the new order of the vertices.
First we choose a peripheral vertex (the vertex with the lowest degree) x and set R := ({x}).
Then for we iterate the following steps while |R| < n
- Construct the adjacency set of (with the i-th component of R) and exclude the vertices we already have in R
- Sort with ascending vertex order (vertex degree).
- Append to the Result set R.
In other words, number the vertices according to a particular breadth-first traversal where neighboring vertices are visited in order from lowest to highest vertex order.
See also
References
- ↑ E. Cuthill and J. McKee. Reducing the bandwidth of sparse symmetric matrices In Proc. 24th Nat. Conf. ACM, pages 157–172, 1969.
- ↑ J. A. George and J. W-H. Liu, Computer Solution of Large Sparse Positive Definite Systems, Prentice-Hall, 1981
- Cuthill–McKee documentation for the Boost C++ Libraries.
- A detailed description of the Cuthill–McKee algorithm.
- symrcm MATLAB's implementation of RCM.