SOME RESULTS ON STRUCTURE PREDICTION IN SPARSE QR FACTORIZATION

In QR factorization of an m x n matrix A (m greater than or equal to n ), the orthogonal factor Q is often stored implicitly as an m x n lowe r trapezoidal matrix W, known as the Householder matrix. When the spar sity of A is to be exploited, the factorization is often preceded by a symbolic factorization step, which computes a data structure in which the nonzero entries of W and R are computed and stored. This is achie ved by computing an upper bound on the nonzero structure of these fact ors, based solely on the nonzero structure of A. In this paper we use a well-known upper bound on the nonzero structure of W to obtain an up per bound on the nonzero structure of Q. Let U be the matrix consistin g of the first n columns of Q. One interesting feature of the new boun d is that the bound on W's structure is identical to the lower trapezo idal part of the bound on U's structure. We show that if A is strong H all and has no zero entry on its main diagonal, then the bounds on the nonzero structures of W and U are the smallest possible based solely on the nonzero structure of A. We then use this result to obtain corre sponding smallest upper bounds in the case where A is weak Hall, is in block upper triangular form, and has no zero entry on its main diagon al. Finally, we show that one can always reorder a weak Hall matrix in to block upper triangular form so that there is no increase in the fil l incurred by the QR factorization.