Separators and structure prediction in sparse orthogonal factorization

Abstract In the factorization A = QR of a sparse matrix A , the orthogonal matrix Q can be represented either explicitly (as a matrix) or implicitly (as a sequence of Householder vectors). A folk theorem states that the Householder vectors are much sparser than Q in practice. In this paper we make this folk theorem precise: we prove tight upper and lower bounds on the nonzero counts of the two representations in terms of the quality of separators in the column intersection graph of A . We conclude that the folk theorem is true when A is nearly square, but not when A has many more rows than columns.