Multifrontal Computation with the Orthogonal Factors of Sparse Matrices

This paper studies the solution of the linear least squares problem for a large and sparse m by n matrix A with $m \geq n$ by $QR$ factorization of A and transformation of the right-hand side vector b to $Q^T b$. A multifrontal-based method for computing $Q^T b$ using Householder factorization is presented. A theoretical operation count for the K by K unbordered grid model problem and problems defined on graphs with $\sqrt n $-separators shows that the proposed method requires $O( N_R )$ storage and multiplications to compute $Q^T b$, where $N_R = O( n \log n )$ is the number of nonzeros of the upper triangular factor R of A. In order to introduce BLAS-2 operations, Schreiber and Van Loan’s storage-efficient WY representation [SIAM J. Sci. Stat. Comput., 10 (1989), pp. 53–57] is applied for the orthogonal factor $Q_i $ of each frontal matrix $F_i $. If this technique is used, the bound on storage increases to $O( ( n \log n )^2 )$. Some numerical results for the grid model problems as well as Harwell–Boeing problems are provided.