Separators and structure prediction in sparse orthogonal factorization (Q1361831)

Let \(A\) be an \(m\times n\) matrix, \(m\geq n\), and let \(A=QR\), where \(Q\) is an \(m\times n\) matrix with orthogonal columns that span the range of \(A\) and \(R\) is an \(n \times n\) upper triangular matrix with positive diagonal elements. Then \(Q= H_1\cdots H_n\), where \(H_i\) is a Householder reflection with reflection vector \(h_i\). The matrix \(H\) with columns \(h_i\) is called a Householder matrix. The authors consider the \(QR\) factorization of a sparse matrix \(A\). They investigate when \(H\) is much sparser than \(A\) and related questions.