Evaluation of Orderings for Unsymmetric Sparse Matrices

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.