Separators and structure prediction in sparse orthogonal factorization

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.