A completecombinatorial/graph theoretic answer is given to the following question. Given only the nonzeropattern of an m-by-n matrix A with full column rank, which entries of Q andwhich 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 hasorthonormal columns. The motivation for knowing is to allocate storage forlarge sparse problems. Some of the ideas may transfer to other problems, andthe answer requires careful thought about the implication of orthogonality. |