The Evolution of the Minimum Degree Ordering Algorithm
Alan D. George, Joseph W. H. Liu · SIAM Review · 1989
Over the past fifteen years, the implementation of the minimum degree algorithm has received much study, and many important enhancements have been made to it. This paper describes these various enhancements, their historical development, and some experiments showing how very effective they are in improving the execution time of the algorithm. A shortcoming is also presented that exists in all of the widely used implementations of the algorithm, namely, that the quality of the ordering provided by the implementations is surprisingly sensitive to the initial ordering. For example, changing the input ordering can lead to an increase (or decrease) of as much as a factor of three in the cost of the subsequent numerical factorization. This sensitivity is caused by the lack of an effective tie-breaking strategy, and the authors’ experiments illustrate the importance of developing such a strategy
Cited by 383 works. doi:10.1137/1031001
Authors
References
- Direct solutions of sparse network equations by optimally ordered triangular factorization
- Algorithmic Graph Theory and Perfect Graphs
- Computer Solution of Large Sparse Positive Definite Systems.
- Direct Methods for Sparse Matrices
- Nested Dissection of a Regular Finite Element Mesh
- Algorithmic graph theory and perfect graphs
- 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
- The Multifrontal Solution of Indefinite Sparse Symmetric Linear
- Computing the Minimum Fill-In is NP-Complete