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 ≥ n by QR factorization of A and transformation of the right-hand side vector 6 to Q^Tb. A multifrontal-based method for computing Q^Tb using Householder factorization is presented. A theoretical operation count for the K by K unbordered grid model problem and problems defined on graphs with √n-separators shows that the proposed method requires O(N_R) storage and multiplications to compute Q^Tb, 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)²). Some numerical results for the grid model problems as well as Harwell-Boeing problems are provided.