Numerical analysis Direct methods for linear systems Fact

Minimum degree algorithm

Builds on Positive definite matrix Sparse matrix Cholesky decomposition Graph Degree of a vertex Gaussian elimination Nested dissection Cuthill–McKee algorithm

Statement

Let $A$ be a real symmetric positive definite $n \times n$ sparse matrix. Let $G$ be its graph: the vertices are $1, \dots, n$ , and $i \ne j$ are adjacent when $a_{ij} \ne 0$ . To eliminate a vertex $v$ of a graph means to join every two neighbours of $v$ by an edge and then to delete $v$ . For an ordering $v_1, \dots, v_n$ of the vertices, let $G_0 = G$ and let $G_k$ be the graph obtained from $G_{k-1}$ by eliminating $v_k$ .

Let $P$ be the permutation matrix of the ordering, and let $L$ be the Cholesky factor of $P A P^T$ . If no numerical cancellation occurs, then for $i > j$ the entry $l_{ij}$ is nonzero exactly when $v_i$ and $v_j$ are adjacent in $G_{j-1}$ .
The minimum degree algorithm builds the ordering greedily: for $k = 1, \dots, n$ , it takes for $v_k$ a vertex of least degree in $G_{k-1}$ .

Remarks

Clause 1 holds because one step of symmetric Gaussian elimination with pivot $v$ subtracts a multiple of the row of $v$ from the row of each neighbour of $v$ . That update creates a nonzero at every pair of neighbours of $v$ , which is exactly the set of edges added when $v$ is eliminated. The new nonzeros are called fill-in. A vertex of degree $d$ creates at most $d(d-1)/2$ new edges when it is eliminated, so the greedy rule tries to keep the fill small. Example: take the star graph with centre $1$ and leaves $2, \dots, n$ . Eliminating the centre first fills the whole matrix. Eliminating the leaves first, each of degree $1$ , creates no fill at all. The rule is a heuristic and need not give an ordering of least fill; finding an ordering of least fill is NP-hard. Practical codes, such as approximate minimum degree, use quotient graphs and degree bounds to run fast.

Going deeper

For a student

The graph model turns a question about matrices into a question about graphs, and it predicts the sparsity of the Cholesky factor before any arithmetic. Minimum degree is one of the standard fill-reducing orderings, together with nested dissection and bandwidth-reducing orderings such as Cuthill–McKee. It works well on irregular problems, while nested dissection has better guarantees on grid-like and planar problems.

Reading path

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

Show the path as a graph

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

Band matrix concept
Degree of a vertex concept
Finite difference method concept
Gaussian elimination concept
Graph concept
Matrix definition
Permutation matrix concept
Planar graph concept
Positive definite matrix concept
Sparse matrix concept
Symmetric matrix concept
Square matrix definition
Transpose definition
Lower triangular matrix definition
Symmetric matrix definition
Conjugate transpose definition
Hermitian matrix definition
Positive definite matrix definition
Cholesky decomposition statement
Cuthill–McKee algorithm statement
Nested dissection statement
Minimum degree algorithm statement

Tag	`4135XQ4WHK`
URI	`m2://4135XQ4WHK`
Kind	statement, fact
Writing	W0 stub
MSC	65F50, 65F05, 05C85
Status	This copy of the site has no build data. Run `m2 status 4135XQ4WHK`.
About	Sparse matrix, Cholesky decomposition
Uses	Positive definite matrix, Sparse matrix, Cholesky decomposition, Graph, Degree of a vertex, Gaussian elimination, Nested dissection, Cuthill–McKee algorithm
Same as	Wikidata Q17098969 Wikipedia Minimum degree algorithm