---
tag: 4135XQ4WHK
kind: statement
role: fact
name: Minimum degree algorithm
msc: [65F50, 65F05, 05C85]
uses: [0KX66CZMBB, JGACZYEEY7, 0WKG8CYY6A, 00C0BR7D7H, 0KS0KRDV4Y, 0JVJ2WCXZH, 9DTJ87P4R1, 1X0E3JHCH9]
about: [JGACZYEEY7, 0WKG8CYY6A]
sources:
  - url: https://en.wikipedia.org/wiki/Minimum_degree_algorithm
same_as:
  wikidata: Q17098969
  wikipedia: Minimum degree algorithm
---

## Statement

Let $A$ be a real symmetric [[positive definite|0KX66CZMBB]] $n \times n$ [[sparse matrix|JGACZYEEY7]].
Let $G$ be its [[graph|00C0BR7D7H]]: 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$.

1. Let $P$ be the permutation matrix of the ordering, and let $L$ be the [[Cholesky factor|0WKG8CYY6A]] 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}$.
2. The *minimum degree algorithm* builds the ordering greedily: for $k = 1, \dots, n$, it takes for $v_k$ a vertex of least [[degree|0KS0KRDV4Y]] in $G_{k-1}$.

## Remarks

Clause 1 holds because one step of symmetric [[Gaussian elimination|0JVJ2WCXZH]] 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.

## Explanations

### L1 human

Solving a large sparse linear system by elimination can turn many zeros into nonzeros, which costs memory and time.
The order in which the unknowns are eliminated decides how much of this fill appears.
The minimum degree algorithm always eliminates next the unknown that is linked to the fewest others.
It is a simple greedy rule that works well in practice.

### L2 human

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|9DTJ87P4R1]] and bandwidth-reducing orderings such as [[Cuthill–McKee|1X0E3JHCH9]].
It works well on irregular problems, while nested dissection has better guarantees on grid-like and planar problems.