Suely Oliveira : July 8, 2002
Predicting QR Fill-In.
Tuesday, July 8, 2:30 a.m. at CERFACS
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 over-estimates the fill-in in general.
However, in my talk I present a fast and simple post-processing step for row-merge trees that predicts the exact fill-in for sparse QR factorization using Householder reflectors, for general matrices.