SEPARATORS AND STRUCTURE PREDICTION IN SPARSE ORTHOGONAL FACTORIZATION

In the factorization A = QR of a sparse matrix A, the orthogonal matri x Q can be represented either explicitly (as a matrix) pr 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 bou nds on the nonzero counts of the two representations in terms of the q uality of separators in the column intersection graph of A. We conclud e that the folk theorem is true when A is nearly square, but not when A has many more rows than columns. (C) Elsevier Science Inc., 1997.