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.

References

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