Separators and Structure Prediction in Sparse Orthogonal Factorization

Résumé du livre

"In the factorization A=QR of a matrix A, the orthogonal matrix Q can be represented either explicitly (as a matrix) or implicitly (as a sequence of Householder vectors). We compare the nonzero counts of these two representations, for a class of matrices that arise in finite element analysis. We prove both upper and lower bounds on nonzero counts in terms of the quality of the separators in a particular graph, the column intersection graph of A. This extends earlier work of George and Ng, who proved upper bounds on the nonzero counts of the Householder vectors in the case that A is square and has good separators"--Abstract.