An Approximate Minimum Degree Ordering Algorithm
Patrick Amestoy, Timothy A. Davis, Iain Duff · SIAM Journal on Matrix Analysis and Applications · 1996
Abstract. An approximate minimum degree (AMD), ordering algorithm for preordering a symmetric sparse matrix prior to numerical factorization is presented. We use techniques based on the quotient graph for matrix factorization that allow us to obtain computationally cheap bounds for the minimum degree. We show that these bounds are often equal to the actual degree. The resulting algorithm is typically much faster than previous minimum degree ordering algorithms and produces results that are comparable in quality with the best orderings from other minimum degree algorithms.
Cited by 731 works. doi:10.1137/s0895479894278952
Authors
References
- Introduction to Algorithms
- Direct solutions of sparse network equations by optimally ordered triangular factorization
- Computer Solution of Large Sparse Positive Definite Systems.
- Direct Methods for Sparse Matrices
- The Elimination form of the Inverse and its Application to Linear Programming
- A GRAPH-THEORETIC STUDY OF THE NUMERICAL SOLUTION OF SPARSE POSITIVE DEFINITE SYSTEMS OF LINEAR EQUATIONS
- Sparse matrix test problems
- The Multifrontal Solution of Indefinite Sparse Symmetric Linear
- Computing the Minimum Fill-In is NP-Complete
- Modification of the minimum-degree algorithm by multiple elimination