Predicting structure in nonsymmetric sparse matrix factorizations. (English) Zbl 0792.05098
George, Alan (ed.) et al., Graph theory and sparse matrix computation. Proceedings of a workshop that was an integral part of the 1991-92 IMA program on ”Applied linear algebra”, Minneapolis, MN (USA). New York: Springer-Verlag. IMA Vol. Math. Appl. 56, 107-139 (1993).
Summary: Many computations on sparse matrices have a phase that predicts the nonzero structure of the output, followed by a phase that actually performs the numerical computation. We study structure prediction for computations that involve nonsymmetric row and column permutations and nonsymmetric or non-square matrices. Our tools are bipartite graphs, matchings, and alternating paths.
Our main new result concerns \(LU\) factorization with partial pivoting. We show that if a square matrix \(A\) has the strong Hall property (i.e., is fully indecomposable) then an upper bound due to George and Ng on the nonzero structure of \(L+U\) is as tight as possible. To show this, we prove a crucial result about alternating paths in strong Hall graphs. The alternating-paths theorem seems to be of independent interest: it can also be used to prove related results about structure prediction for \(QR\) factorization that are due to Coleman, Edenbrandt, Gilbert, Hare, Johnson, Olesky, Pothen, and van den Driessche.
For the entire collection see [Zbl 0785.00030].
Our main new result concerns \(LU\) factorization with partial pivoting. We show that if a square matrix \(A\) has the strong Hall property (i.e., is fully indecomposable) then an upper bound due to George and Ng on the nonzero structure of \(L+U\) is as tight as possible. To show this, we prove a crucial result about alternating paths in strong Hall graphs. The alternating-paths theorem seems to be of independent interest: it can also be used to prove related results about structure prediction for \(QR\) factorization that are due to Coleman, Edenbrandt, Gilbert, Hare, Johnson, Olesky, Pothen, and van den Driessche.
For the entire collection see [Zbl 0785.00030].
MSC:
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 65F50 | Computational methods for sparse matrices |
| 15A23 | Factorization of matrices |
| 65F05 | Direct numerical methods for linear systems and matrix inversion |
