Predicting Structure in Sparse Matrix Computations
- 1 January 1994
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Matrix Analysis and Applications
- Vol. 15 (1) , 62-79
- https://doi.org/10.1137/s0895479887139455
Abstract
Many sparse matrix algorithms—for example, solving a sparse system of linear equations—begin by predicting the nonzero structure of the output of a matrix computation from the nonzero structure of its input. This paper is a catalog of ways to predict nonzero structure. It contains known results for some problems, including various matrix factorizations, and new results for other problems, including some eigenvector computations.Keywords
This publication has 27 references indexed in Scilit:
- Optimal Parallel Solution of Sparse Triangular SystemsSIAM Journal on Scientific Computing, 1993
- Exploiting Structural Symmetry in Unsymmetric Sparse Symbolic FactorizationSIAM Journal on Matrix Analysis and Applications, 1992
- The Null Space Problem II. AlgorithmsSIAM Journal on Algebraic Discrete Methods, 1987
- Inherited Matrix Entries: Principal Submatrices of the InverseSIAM Journal on Algebraic Discrete Methods, 1987
- The Null Space Problem I. ComplexitySIAM Journal on Algebraic Discrete Methods, 1986
- Predicting fill for sparse orthogonal factorizationJournal of the ACM, 1986
- On Algorithms for Obtaining a Maximum TransversalACM Transactions on Mathematical Software, 1981
- Algorithms and Data Structures for Sparse Symmetric Gaussian EliminationSIAM Journal on Scientific and Statistical Computing, 1981
- Some Design Features of a Sparse Matrix CodeACM Transactions on Mathematical Software, 1979
- Some results on sparse matricesMathematics of Computation, 1970