On Finding Supernodes for Sparse Matrix Computations
- 1 January 1993
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Matrix Analysis and Applications
- Vol. 14 (1) , 242-252
- https://doi.org/10.1137/0614019
Abstract
A simple characterization of fundamental supernodes is given in terms of the row subtrees of sparse Cholesky factors in the elimination tree. Using this characterization, an efficient algorithm is presented that determines the set of such supernodes in time proportional to the number of nonzeros and equations in the original matrix. Experimental results verify the practical efficiency of this algorithm.Keywords
This publication has 10 references indexed in Scilit:
- Efficient sparse matrix factorization on high performance workstations—exploiting the memory hierarchyACM Transactions on Mathematical Software, 1991
- The Role of Elimination Trees in Sparse FactorizationSIAM Journal on Matrix Analysis and Applications, 1990
- The influence of relaxed supernode partitions on the multifrontal methodACM Transactions on Mathematical Software, 1989
- A Fast Algorithm for Reordering Sparse Matrices for Parallel FactorizationSIAM Journal on Scientific and Statistical Computing, 1989
- The Evolution of the Minimum Degree Ordering AlgorithmSIAM Review, 1989
- Sparse matrix test problemsACM Transactions on Mathematical Software, 1989
- Progress in Sparse Matrix Methods for Large Linear Systems On Vector SupercomputersThe International Journal of Supercomputing Applications, 1987
- A compact row storage scheme for Cholesky factors using elimination treesACM Transactions on Mathematical Software, 1986
- The Multifrontal Solution of Indefinite Sparse Symmetric LinearACM Transactions on Mathematical Software, 1983
- A New Implementation of Sparse Gaussian EliminationACM Transactions on Mathematical Software, 1982