Every full column rank matrix has a
unique factorization as a product of a matrix with orthogonal colums
(Q) and an upper triangular matrix with positive diagonal (R), the
famous QR factorization. When A is large and sparse, it is useful to
know how sparse Q and R will be, for purposes of allocating storage in
anticipation of calculation. It had been observed that Q (especially)
tended in certain circumstances to be sparser than was easily predicted
by the simple analysis then in use. We explain, based upon some
subtlety of orthogonality, why this happens and give a description of
the sparsity of Q and R. This is joint work with Pauline vanden
Driessche and Dale Olesky. |