SPARSITY ANALYSIS OF THE QR FACTORIZATION

Given only the zero-nonzero pattern of an m x n matrix A of full colum n rank, which entries of Q and which entries of R in its QR factorizat ion must be zero, and which entries may be nonzero? A complete answer to this question is given, which involves an interesting interplay bet ween combinatorial structure and the algebra implicit in orthogonality . To this end some new sparse structural concepts are introduced, and an algorithm to determine the structure of Q is given. The structure o f R then follows immediately from that of Q and A. The computable zero /nonzero structures for the matrices Q and R are proven to be tight, a nd the conditions on the pattern for A are the weakest possible (namel y, that it allows matrices A with full column rank). This complements existing work that focussed upon R and then only under an additional c ombinatorial assumption (the strong Hall property).