Minimum degree algorithm explained
In numerical analysis, the minimum degree algorithm is an algorithm used to permute the rows and columns of a symmetric sparse matrix before applying the Cholesky decomposition, to reduce the number of non-zeros in the Cholesky factor.This results in reduced storage requirements and means that the Cholesky factor can be applied with fewer arithmetic operations. (Sometimes it may also pertain to an incomplete Cholesky factor used as a preconditioner—for example, in the preconditioned conjugate gradient algorithm.)
Minimum degree algorithms are often used in the finite element method where the reordering of nodes can be carried out depending only on the topology of the mesh, rather than on the coefficients in the partial differential equation, resulting in efficiency savings when the same mesh is used for a variety of coefficient values.
Given a linear system
where
A is an
real symmetric sparse square matrix. The Cholesky factor
L will typically suffer 'fill in', that is have more non-zeros than the upper triangle of
A. We seek a
permutation matrix P, so that the matrix
, which is also symmetric, has the least possible fill in its Cholesky factor. We solve the reordered system
\left(PTAP\right)\left(PTx\right)=PTb.
The problem of finding the best ordering is an
NP-complete problem and is thus intractable, so heuristic methods are used instead. The minimum degree algorithm is derived from a method first proposed by
Markowitz in 1959 for non-symmetric
linear programming problems, which is loosely described as follows. At each step in
Gaussian elimination row and column permutations are performed so as to minimize the number of off diagonal non-zeros in the pivot row and column. A symmetric versionof Markowitz method was described by Tinney and Walker in 1967 and Rose later derived a graph theoretic version of the algorithm where the factorization is only simulated, and this was named the minimum degree algorithm. The graph referred to is the graph with
n vertices, with vertices
i and
j connected by an edge when
, and the
degree is the degree of the vertices. A crucial aspect of such algorithms is a tie breaking strategy when there is a choice of renumbering resulting in the same degree.
A version of the minimum degree algorithm was implemented in the MATLAB function symmmd (where MMD stands for multiple minimum degree), but has now been superseded by a symmetric approximate multiple minimum degree function symamd, which is faster. This is confirmed by theoretical analysis, which shows that for graphs with n vertices and m edges, MMD has a tight upper bound of
on its running time, whereas for AMD a tight bound of
holds. Cummings, Fahrbach, and Fatehpuria designed an exact minimum degree algorithm with
running time, and showed that no such algorithm can exist that runs in time
, for any
, assuming the
strong exponential time hypothesis.
References
- Robert . Cummings . Matthew . Fahrbach . Animesh . Fatehpuria . A fast minimum degree algorithm and matching lower bound . Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms . 2021 . 724–734 . 10.1137/1.9781611976465.45 . 978-1-61197-646-5 . 198968052 . 1907.12119 .
- Alan . George . Joseph . Liu . The evolution of the minimum degree ordering algorithm . . 31 . 1 . 1–19 . 1989 . 2030845 . 10.1137/1031001. 5686483 .
- Book: Rose, D. J. . A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations . Graph Theory and Computing . Academic Press . 1972 . 183–217 . 0-12-583850-6 .
- W. F. . Tinney . J. W. . Walker . Direct solution of sparse network equations by optimally ordered triangular factorization . . 55 . 11 . 1801–1809 . 1967 . 10.1109/PROC.1967.6011 .
