In
numerical linear algebra
Numerical linear algebra, sometimes called applied linear algebra, is the study of how matrix operations can be used to create computer algorithms which efficiently and accurately provide approximate answers to questions in continuous mathematic ...
, the Cuthill–McKee algorithm (CM), named after
Elizabeth Cuthill and James McKee,
[E. Cuthill and J. McKee]
the bandwidth of sparse symmetric matrices''
In Proc. 24th Nat. Conf. ACM, pages 157–172, 1969. is an
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
to permute a
sparse matrix
In numerical analysis and scientific computing, a sparse matrix or sparse array is a matrix in which most of the elements are zero. There is no strict definition regarding the proportion of zero-value elements for a matrix to qualify as sparse b ...
that has a
symmetric
Symmetry (from grc, συμμετρία "agreement in dimensions, due proportion, arrangement") in everyday language refers to a sense of harmonious and beautiful proportion and balance. In mathematics, "symmetry" has a more precise definiti ...
sparsity pattern into a
band matrix
Band or BAND may refer to:
Places
* Bánd, a village in Hungary
*Band, Iran, a village in Urmia County, West Azerbaijan Province, Iran
* Band, Mureș, a commune in Romania
*Band-e Majid Khan, a village in Bukan County, West Azerbaijan Province, ...
form with a small
bandwidth
Bandwidth commonly refers to:
* Bandwidth (signal processing) or ''analog bandwidth'', ''frequency bandwidth'', or ''radio bandwidth'', a measure of the width of a frequency range
* Bandwidth (computing), the rate of data transfer, bit rate or thr ...
. The reverse Cuthill–McKee algorithm (RCM) due to Alan George and Joseph Liu 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.
[J. A. George and J. W-H. Liu, Computer Solution of Large Sparse Positive Definite Systems, Prentice-Hall, 1981]
The Cuthill McKee algorithm is a variant of the standard
breadth-first search
Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next de ...
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 ordered according to predecessors and degree.
Algorithm
Given a symmetric
matrix we visualize the matrix as the
adjacency matrix
In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.
In the special case of a finite simp ...
of a
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
. 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 of vertices which is the new order of the vertices.
First we choose a
peripheral vertex (the vertex with the lowest
degree
Degree may refer to:
As a unit of measurement
* Degree (angle), a unit of angle measurement
** Degree of geographical latitude
** Degree of geographical longitude
* Degree symbol (°), a notation used in science, engineering, and mathematics
...
)
and set
.
Then for
we iterate the following steps while
*Construct the adjacency set
of
(with
the ''i''-th component of
) and exclude the vertices we already have in
:
*Sort
ascending by minimum predecessor (the already-visited neighbor with the earliest position in R), and as a tiebreak ascending by
vertex degree.
[The Reverse Cuthill-McKee Algorithm in Distributed-Memor]
slide 8, 2016
*Append
to the Result set
.
In other words, number the vertices according to a particular
level structure
In the mathematical subfield of graph theory a level structure of an undirected graph is a partition of the vertices into subsets that have the same distance from a given root vertex..
Definition and construction
Given a connected graph ''G'' ...
(computed by
breadth-first search
Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next de ...
) where the vertices in each level are visited in order of their predecessor's numbering from lowest to highest. Where the predecessors are the same, vertices are distinguished by degree (again ordered from lowest to highest).
See also
*
Graph bandwidth
In graph theory, the graph bandwidth problem is to label the vertices of a graph with distinct integers so that the quantity \max\ is minimized ( is the edge set of ).
The problem may be visualized as placing the vertices of a graph at disti ...
*
Sparse matrix
In numerical analysis and scientific computing, a sparse matrix or sparse array is a matrix in which most of the elements are zero. There is no strict definition regarding the proportion of zero-value elements for a matrix to qualify as sparse b ...
References
Cuthill–McKee documentationfor the
Boost C++ Libraries
Boost, boosted or boosting may refer to:
Science, technology and mathematics
* Boost, positive manifold pressure in turbocharged engines
* Boost (C++ libraries), a set of free peer-reviewed portable C++ libraries
* Boost (material), a material b ...
.
A detailed description of the Cuthill–McKee algorithm
MATLAB's implementation of RCM.
RCM routine from
SciPy
SciPy (pronounced "sigh pie") is a free and open-source Python library used for scientific computing and technical computing.
SciPy contains modules for optimization, linear algebra, integration, interpolation, special functions, FFT, ...
written in
Cython
Cython () is a programming language that aims to be a superset of the Python programming language, designed to give C-like performance with code that is written mostly in Python with optional additional C-inspired syntax.
Cython is a compiled ...
.
{{DEFAULTSORT:Cuthill-McKee algorithm
Matrix theory
Graph algorithms
Sparse matrices