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.
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.
A symmetric version of 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.
A crucial aspect of such algorithms is a tie breaking strategy when there is a choice of renumbering resulting in the same degree.
This is confirmed by theoretical analysis, which shows that for graphs with n vertices and m edges, MMD has a tight upper bound of
Cummings, Fahrbach, and Fatehpuria designed an exact minimum degree algorithm with