PATTERNS THAT PRESERVE SPARSITY IN ORTHOGONAL FACTORIZATION

An m X n zero-nonzero pattern A with the Hall property allows:a full r ank matrix A is an element of A with a QR factorization. The union of patterns occurring in Q over all such A is denoted by Q. By further re stricting A to have the strong Hall property, a Hasse diagram that is a forest is used to characterize patterns A that yield Q = A, thus pre serving the sparsity of A. For fixed n, the sparsest n X n such patter ns are characterized by a binary rooted tree. (C) 1998 Elsevier Scienc e Inc.