Cuthill-McKee algorithm

Cuthill-McKee sorting of the same matrix

Reverse Cuthill-McKee sorting of the same matrix

The Cuthill-McKee algorithm (named after Elizabeth Cuthill and James McKee) is an algorithm in numerical mathematics that transforms a symmetrical sparse matrix into a band matrix with a smaller bandwidth . Very efficient calculation algorithms exist for band matrices, for example for the solution of very large linear equation systems (see BLAS ).

The reverse Cuthill-McKee algorithm of Alan George is the same algorithm in reverse index order. In general, the reverse algorithm results in less fill-in when Gaussian elimination is performed. "Fill-in" means the creation of non-zero elements at positions that are occupied by zero in the original matrix.

The Cuthill-McKee algorithm differs from breadth-first search for graphs in its sequence, which is determined by numbering adjacent nodes based on their degree.

algorithm

Let it be an adjacency matrix , i.e. a symmetrical matrix with only zeros and ones as entries. The Cuthill-McKee algorithm is a renumbering of the nodes of the graph represented by the adjacency matrix in order to reduce the bandwidth of the adjacency matrix. The algorithm calculates a tuple of nodes representing the new order as follows: ${\displaystyle M\!}$ ${\displaystyle n\times n\!}$ ${\displaystyle n}$

• Choose a starting node and place . ${\displaystyle x\!}$ ${\displaystyle R:=(x)\!}$

• For while it is, do the following: ${\displaystyle i=1,2,\dots }$ ${\displaystyle |R|<n}$

• Construct the set of adjacent nodes of , where the -th component of is, and exclude all nodes that are already contained in: ${\displaystyle A_{i}}$ ${\displaystyle R_{i}}$ ${\displaystyle R_{i}}$ ${\displaystyle i}$ ${\displaystyle R}$ ${\displaystyle R}$ ${\displaystyle A_{i}:=\operatorname {Adj} (R_{i})\setminus R}$
• Sort by increasing knot degree . ${\displaystyle A_{i}}$
• Append to the result tuple . ${\displaystyle A_{i}}$ ${\displaystyle R}$

Choice of the starting node

The quality of the new numbering or permutation determined by the algorithm depends crucially on the choice of the starting node. Since the bandwidth minimization problem is NP-difficult , the choice of an optimal start node also falls into this complexity class. Instead, Cuthill and McKee suggest always choosing a knot of minimal degree, but this has not proven effective in practice. Alternatively, the choice of a peripheral node, i.e. a node in the edge of the graph, as the starting node is obvious. The determination of a peripheral node is only possible in quadratic runtime, which dominates the actual algorithm. Therefore, in practice one is content with choosing a pseudo-peripheral node that can be determined in the following way:

1. Choose any node . ${\displaystyle x\in X\!}$
2. Create the stratification with the root . ${\displaystyle \{L_{0}(x),...,L_{\varepsilon (x)}(x)\}\!}$ ${\displaystyle x\!}$
3. Choose any node of minimal degree . ${\displaystyle r\in L_{\varepsilon (x)}(x)\!}$
4. Create the stratification with the root . If so , replace with and go to 3. ${\displaystyle \{L_{0}(r),...,L_{\varepsilon (r)}(r)\}\!}$ ${\displaystyle r\!}$ ${\displaystyle \varepsilon (r)>\varepsilon (x)\!}$ ${\displaystyle x\!}$ ${\displaystyle r\!}$
5. ${\displaystyle r\!}$ is a pseudo-peripheral node.

The eccentricity of a node of a connected graph is the size ${\displaystyle \varepsilon (x)\!}$ ${\displaystyle x\!}$ ${\displaystyle \varepsilon (x):={\underset {y\in X}{\max }}{\text{ dist}}(x,y).\!}$

application

The algorithm is used to reduce the bandwidth of matrices and thus, for example, to drastically reduce the effort of Gaussian elimination when solving linear systems of equations.

Web links

• Documentation of the Cuthill – McKee algorithm for the Boost C ++ library (English)
• Description of Cuthill-McKee algorithm (English)
• A comparison of the quality and efficiency of various algorithms for selecting a pseudo-peripheral node (English)

Individual evidence

1. ^ Recommendations for ship hull surface representation , page 6
2. ↑ ^{a b} E. Cuthill and J. McKee. Reducing the bandwidth of sparse symmetric matrices In Proc. 24th Nat. Conf. ACM , pages 157-172, 1969.
3. ↑ JA George and J. WH. Liu, Computer Solution of Large Sparse Positive Definite Systems, Prentice-Hall, 1981
4. ↑ Uriel Feige: Coping with the NP-Hardness of the Graph Bandwidth Problem . In: Algorithm Theory - SWAT 2000 . tape 1851 . Springer Berlin Heidelberg, Berlin, Heidelberg 2000, ISBN 978-3-540-67690-4 , pp. 10–19 , doi : 10.1007 / 3-540-44985-x_2 ( springer.com [accessed March 23, 2020]).