A Note on the Column Elimination Tree
John R. Gilbert, Laura Grigori · SIAM Journal on Matrix Analysis and Applications · 2003
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 Gilbert and Ng [Graph Theory and Sparse Matrix Computation, A. George, J. R. Gilbert, and J. W. H. Liu, eds., Springer-Verlag, New York, 1994, pp. 107--139].