Math 2.0

Numerical analysis Direct methods for linear systems Proposition

Cuthill–McKee algorithm

Builds on Sparse matrixBand matrixSymmetric matrixGraphDegree of a vertexPermutation matrixCholesky decomposition

Statement

Let AA be a symmetric n×nn \times n matrix. Its graph GG has vertices 1,…,n1, \dots, n and an edge between i≠ji \ne j when aij≠0a_{ij} \ne 0; assume GG is connected. The bandwidth of AA is max⁡{∣i−j∣:aij≠0}\max \set{\abs{i - j} : a_{ij} \ne 0}. The Cuthill–McKee algorithm orders the vertices as follows. It picks a start vertex v1v_1. For k=1,2,…k = 1, 2, \dots it appends to the list the neighbours of vkv_k not yet listed, in order of increasing degree. Let L0={v1}L_0 = \set{v_1} and, for d≥1d \ge 1, let LdL_d be the set of vertices at distance dd from v1v_1 in GG. Then:

  1. the algorithm lists every vertex exactly once, and each level LdL_d forms a contiguous block of the list, in the order L0,L1,L2,…L_0, L_1, L_2, \dots;
  2. if PP is the permutation matrix of this ordering, the bandwidth of PAPTP A P^T is at most max⁡d(∣Ld∣+∣Ld+1∣)−1\max_d \big(\abs{L_d} + \abs{L_{d+1}}\big) - 1;
  3. the reversed ordering, called reverse Cuthill–McKee, gives a matrix with the same bandwidth.

Remarks

The list is built exactly as a breadth-first search from v1v_1 would build its queue, which lists the vertices by nondecreasing distance from v1v_1; this gives clause 1. In a breadth-first level structure, every edge joins two vertices of the same level or of adjacent levels. Two adjacent levels occupy ∣Ld∣+∣Ld+1∣\abs{L_d} + \abs{L_{d+1}} consecutive positions, so the positions of the ends of an edge differ by at most ∣Ld∣+∣Ld+1∣−1\abs{L_d} + \abs{L_{d+1}} - 1; this gives clause 2. Clause 3 holds because reversing the order maps the positions p,qp, q to n+1−p,n+1−qn + 1 - p, n + 1 - q, which have the same difference. So a start vertex with many small levels, such as a vertex far from the rest of the graph, gives a narrow band. In practice one starts from a vertex of minimum degree or a pseudo-peripheral vertex. Example: for the path graph 2−1−32 - 1 - 3 (with a12,a13≠0a_{12}, a_{13} \ne 0), starting at v1=2v_1 = 2 gives the order 2,1,32, 1, 3, and the reordered matrix is tridiagonal, with bandwidth 11. The reverse ordering usually produces less fill-in in a Cholesky factorization, which is why it is the version used in sparse solvers.

Going deeper

For a student

The algorithm is a heuristic: it does not find the smallest possible bandwidth, which is an NP-hard problem, but it is fast and usually good. It runs in time roughly proportional to the number of nonzero entries, up to the sorting by degree. Reverse Cuthill–McKee is a standard preprocessing step before banded or envelope Cholesky factorization of symmetric sparse matrices.

Reading path

To understand this page from the ground up, read these 16 pages in order. The foundations come first.

Show the path as a graph
Band matrix, concept, no evidence levelBand matrixconceptDegree of a vertex, concept, no evidence levelDegree of a vertexconceptGraph, concept, no evidence levelGraphconceptMatrix, definition, no evidence levelMatrixdefinitionPermutation matrix, concept, no evidence levelPermutation matrixconceptSparse matrix, concept, no evidence levelSparse matrixconceptSymmetric matrix, concept, no evidence levelSymmetric matrixconceptSquare matrix, definition, no evidence levelSquare matrixdefinitionTranspose, definition, no evidence levelTransposedefinitionLower triangular matrix, definition, no evidence levelLower triangular matr…definitionSymmetric matrix, definition, no evidence levelSymmetric matrixdefinitionConjugate transpose, definition, no evidence levelConjugate transposedefinitionHermitian matrix, definition, no evidence levelHermitian matrixdefinitionPositive definite matrix, definition, no evidence levelPositive definite mat…definitionCholesky decomposition, statement, no evidence levelCholesky decompositionstatementCuthill–McKee algorithm, statement, no evidence levelCuthill–McKee algorit…statement
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Band matrix concept
  2. Degree of a vertex concept
  3. Graph concept
  4. Matrix definition
  5. Permutation matrix concept
  6. Sparse matrix concept
  7. Symmetric matrix concept
  8. Square matrix definition
  9. Transpose definition
  10. Lower triangular matrix definition
  11. Symmetric matrix definition
  12. Conjugate transpose definition
  13. Hermitian matrix definition
  14. Positive definite matrix definition
  15. Cholesky decomposition statement
  16. Cuthill–McKee algorithm statement

Where this leads

1 page builds on this one.

Further reading

  1. Web https://en.wikipedia.org/wiki/Cuthill–McKee_algorithm
About this page
Tag1X0E3JHCH9
URIm2://1X0E3JHCH9
Kindstatement, proposition
WritingW0 stub
MSC65F50, 05C85
StatusThis copy of the site has no build data. Run m2 status 1X0E3JHCH9.
AboutSparse matrix
UsesSparse matrix, Band matrix, Symmetric matrix, Graph, Degree of a vertex, Permutation matrix, Cholesky decomposition
Same as

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)
  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

Used by