Modification of the minimum-degree algorithm by multiple elimination
Joseph W. H. Liu · ACM Transactions on Mathematical Software · 1985
The most widely used ordering scheme to reduce fills and operations in sparse matrix computation is the minimum-degree algorithm. The notion of multiple elimination is introduced here as a modification to the conventional scheme. The motivation is discussed using the k -by- k grid model problem. Experimental results indicate that the modified version retains the fill-reducing property of (and is often better than) the original ordering algorithm and yet requires less computer time. The reduction in ordering time is problem dependent, and for some problems the modified algorithm can run a few times faster than existing implementations of the minimum-degree algorithm. The use of external degree in the algorithm is also introduced.
Cited by 361 works. doi:10.1145/214392.214398 Open-access PDF
Authors
References
- Direct solutions of sparse network equations by optimally ordered triangular factorization
- Computer Solution of Large Sparse Positive Definite Systems.
- A GRAPH-THEORETIC STUDY OF THE NUMERICAL SOLUTION OF SPARSE POSITIVE DEFINITE SYSTEMS OF LINEAR EQUATIONS
- The Multifrontal Solution of Indefinite Sparse Symmetric Linear
- Computer Solution of Large Sparse Positive Definite
- Computing the Minimum Fill-In is NP-Complete
- Sparse matrix test problems
- Applications of an Element Model for Gaussian Elimination11This work was supported in part by NSF Grant GJ-43157 and ONR Grant N00014-67-A-0097-0016.
- A Fast Implementation of the Minimum Degree Algorithm Using Quotient Graphs
- Parallel pivoting algorithms for sparse symmetric matrices