Minimum degree algorithm

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, or sometimes an incomplete choleski factor used as a preconditioner (for example in the preconditioned conjugate gradient algorithm) can be appled with fewer aritmetic operations.

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 the coeficients in the partial differential equation, resulting in efficency savings when the same mesh is used for a variety of coefficient values.

References

Alan George and Joseph Liu. The evolution of the Minimum Degree Ordering Algorithm, SIAM Review, 31:1-19, 1989.