Exact Prediction of QR Fill-In by Row-Merge Trees
Suely Oliveira · SIAM Journal on Scientific Computing · 2001
Row-merge trees for forming the QR factorization of a sparse matrix A are closely related to elimination trees for the Cholesky factorization of A T A. Row-merge trees predict the exact fill-in (assuming no numerical cancellation) provided A satisfies the strong Hall property, but overestimate the fill-in in general. However, here a fast and simple postprocessing step for row-merge trees is presented that predicts the exact fill-in for sparse QR factorization using Householder reflectors for general matrices.