TY - JOUR
T1 - Multifrontal computation with the orthogonal factors of sparse matrices
AU - Lu, Szu Min
AU - Barlow, Jesse L.
PY - 1996/7
Y1 - 1996/7
N2 - 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 QTb. A multifrontal-based method for computing QTb 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(NR) storage and multiplications to compute QTb, where NR = 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 Qi of each frontal matrix Fi. 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.
AB - 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 QTb. A multifrontal-based method for computing QTb 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(NR) storage and multiplications to compute QTb, where NR = 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 Qi of each frontal matrix Fi. 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.
UR - http://www.scopus.com/inward/record.url?scp=0030514421&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0030514421&partnerID=8YFLogxK
U2 - 10.1137/S0895479893259509
DO - 10.1137/S0895479893259509
M3 - Article
AN - SCOPUS:0030514421
SN - 0895-4798
VL - 17
SP - 658
EP - 679
JO - SIAM Journal on Matrix Analysis and Applications
JF - SIAM Journal on Matrix Analysis and Applications
IS - 3
ER -