Suely Oliveira : July 8, 2002

Predicting QR Fill-In.

Abstract

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.