A Fast Implementation of the Minimum Degree Algorithm Using Quotient Graphs
Alan D. George, Joseph W. H. Liu · ACM Transactions on Mathematical Software · 1980
This paper describes a very fast implementation of the m~n~mum degree algorithm, which is an effective heuristm scheme for fmding low-fill ordermgs for sparse positive definite matrices.This implementation has two important features: first, in terms of speed, it is competitive with other unplementations known to the authors, and, second, its storage requirements are independent of the amount of fill suffered by the matrix during its symbolic factorization.Some numerical experiments which compare the performance of this new scheme to some existing minimum degree programs are provided.
Cited by 59 works. doi:10.1145/355900.355906 Open-access PDF
Authors
References
- The Theory of Graphs and Its Applications
- The Theory of Graphs and its Applications.
- Algorithmic Aspects of Vertex Elimination on Graphs
- The Use of Linear Graphs in Gauss Elimination
- An Automatic Nested Dissection Algorithm for Irregular Finite Element Problems
- Sparse Matrix Proceedings 1978
- A Minimal Storage Implementation of the Minimum Degree Algorithm
- Algorithms for Matrix Partitioning and the Numerical Solution of Finite Element Systems