Evaluation of Orderings for Unsymmetric Sparse Matrices
Authors:
- A. M. ErismanAEA. M. Erisman
- R. G. GrimesRGR. G. Grimes
- J. G. LewisJLJ. G. Lewis
- Jr. W. G. PooleJPJr. W. G. Poole
- H. D. SimonHSH. D. Simon
- 1 July 1987
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Scientific and Statistical Computing
- Vol. 8 (4) , 600-624
Abstract
The computational complexity of obtaining optimal reorderings for performing sparse Gaussian elimination justifies the heuristic nature of all practical reordering algorithms. The concomitant lack of analytic results on heuristic orderings requires that any general comparisons between orderings must be empirical. We report our findings from an extensive investigation of the Markowitz, ${\text{P}}^4 $ and ${\text{P}}^5 $ ordering heuristics applied to a spectrum of sparse matrices. The ordering heuristics differ in overall effectiveness in reducing fill, particularly on certain problem classes, and in their ability to provide stable as well as low fill factorizations. Statistical analyses indicate that certain easily observed, general, structural parameters of the matrices are predictors for the amount of fill observed. Various estimates of the stability of the factorizations were compared for reliability and accuracy. We close with recommendations for use and for further investigation.
Keywords
This publication has 17 references indexed in Scilit:
- A Structurally Stable Modification of Hellerman–Rarick’s ${\text{P}}^4 $ Algorithm for Reordering Unsymmetric Sparse MatricesSIAM Journal on Numerical Analysis, 1985
- Some Extensions of an Algorithm for Sparse Linear Least Squares ProblemsSIAM Journal on Scientific and Statistical Computing, 1982
- Sparse matrix test problemsACM SIGNUM Newsletter, 1982
- An Implementation of Tarjan's Algorithm for the Block Triangularization of a MatrixACM Transactions on Mathematical Software, 1978
- Algorithm 529: Permutations To Block Triangular Form [F1]ACM Transactions on Mathematical Software, 1978
- Hierarchical partition—a new optimal pivoting algorithmMathematical Programming, 1977
- On Permutations to Block Triangular FormIMA Journal of Applied Mathematics, 1977
- Monitoring the stability of the triangular factorization of a sparse matrixNumerische Mathematik, 1974
- The Partitioned Preassigned Pivot Procedure (P4)1972
- Reinversion with the preassigned pivot procedureMathematical Programming, 1971