Equivalent Sparse Matrix Reordering by Elimination Tree Rotations
Author:
- 1 May 1988
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Scientific and Statistical Computing
- Vol. 9 (3) , 424-444
Abstract
In this paper, we introduce a class of fill-preserving equivalent reorderings for sparse Cholesky factorization. This class is based on performing a special form of tree rotation on the elimination tree of the given sparse matrix. Some applications on the use of such elimination tree rotation are described: core storage reduction in a sparse out-of-core scheme, working storage reduction in the multifrontal method, and solution of a subset of unknowns. Some experimental results are also provided to demonstrate its effectiveness in some of these applications.Keywords
This publication has 14 references indexed in Scilit:
- An Adaptive General Sparse Out-Of-Core Cholesky Factorization SchemeSIAM Journal on Scientific and Statistical Computing, 1987
- An Application of Generalized Tree Pebbling to Sparse Matrix FactorizationSIAM Journal on Algebraic Discrete Methods, 1987
- Computational models and task scheduling for parallel sparse Cholesky factorizationParallel Computing, 1986
- On the storage requirement in the out-of-core multifrontal method for sparse factorizationACM Transactions on Mathematical Software, 1986
- A compact row storage scheme for Cholesky factors using elimination treesACM Transactions on Mathematical Software, 1986
- Modification of the minimum-degree algorithm by multiple eliminationACM Transactions on Mathematical Software, 1985
- The Multifrontal Solution of Indefinite Sparse Symmetric LinearACM Transactions on Mathematical Software, 1983
- The space complexity of pebble games on treesInformation Processing Letters, 1980
- Nested Dissection of a Regular Finite Element MeshSIAM Journal on Numerical Analysis, 1973
- A GRAPH-THEORETIC STUDY OF THE NUMERICAL SOLUTION OF SPARSE POSITIVE DEFINITE SYSTEMS OF LINEAR EQUATIONS1972