A note on the column elimination tree. (English) Zbl 1063.65024
Summary: This short communication considers the \(LU\) factorization with partial pivoting and shows that an all-at-once result is possible for the structure prediction of the column dependencies in \(L\) and \(U\). Specifically, we prove that for every square strong Hall matrix \(A\) there exists a permutation \(P\) such that every edge of its column elimination tree corresponds to a symbolic nonzero in the upper triangular factor \(U\).
In the symbolic sense, this resolves a conjecture of J. R. Gilbert and E. G. Ng [Graph Theory and Sparse Matrix Computation, A. George, J. R. Gilbert, and J. W. H. Liu, eds., Springer-Verlag, New York, IMA Vol. Math. Appl. 56, 107–139 (1993; Zbl 0792.05098)].
In the symbolic sense, this resolves a conjecture of J. R. Gilbert and E. G. Ng [Graph Theory and Sparse Matrix Computation, A. George, J. R. Gilbert, and J. W. H. Liu, eds., Springer-Verlag, New York, IMA Vol. Math. Appl. 56, 107–139 (1993; Zbl 0792.05098)].
MSC:
| 65F05 | Direct numerical methods for linear systems and matrix inversion |
| 65F50 | Computational methods for sparse matrices |
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
