A complete
combinatorial/graph theoretic answer is given to the following question.
Given only the nonzero
pattern of an m-by-n matrix A with full column rank, which entries of Q
and
which entries of R in its Q-R factorization must be 0 and which may be
nonzero?
Recall that in the Q-R factorization, R is upper triangular and Q has
orthonormal columns. The motivation for knowing is to allocate storage
for
large sparse problems. Some of the ideas may transfer to other problems,
and
the answer requires careful thought about the implication of
orthogonality. |