Predicting the structure of sparse orthogonal factors (Q1318224)

Given the structure of an \(m \times n\) real or complex matrix \(A\), where \(m \geq n\) and \(A\) has full column rank, the author considers the problem of correctly predicting the structure of its orthogonal factors \(Q\) and \(R\). Recently, \textit{D. R. Hare, C. R. Johnson, D. D. Olesky}, and \textit{P. van den Driessche} [SIAM J. Matrix Anal. Appl. 14, No. 3, 655-669 (1993; Zbl 0783.65038)] have described a method to predict these structures, and they have shown that corresponding to any specified nonzero element in the predicted structures of \(Q\) or \(R\), there exists a matrix \(A\) with the given structure whose factor has a nonzero element in that position. In the paper under review, this method is shown to satisfy a stronger property: there exist matrices with the structure of \(A\) whose factors have exactly the predicted structures. Efficient algorithms for computing the structures of the factors are designed, and the relationship between the structure of \(Q\) and the Householder array is also described.