Premium
Multifrontal QR Factorization in a Multiprocessor Environment
Author(s) -
Amestoy P. R.,
Duff I. S.,
Puglisi C.
Publication year - 1996
Publication title -
numerical linear algebra with applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.02
H-Index - 53
eISSN - 1099-1506
pISSN - 1070-5325
DOI - 10.1002/(sici)1099-1506(199607/08)3:4<275::aid-nla83>3.0.co;2-7
Subject(s) - uniprocessor system , qr decomposition , factorization , parallel computing , computer science , matrix decomposition , multiprocessing , lu decomposition , sparse matrix , matrix (chemical analysis) , algorithm , eigenvalues and eigenvectors , physics , materials science , quantum mechanics , composite material , gaussian
We describe the design and implementation of a parallel QR decomposition algorithm for a large sparse matrix A . The algorithm is based on the multifrontal approach and makes use of Householder transformations. The tasks are distributed among processors according to an assembly tree which is built from the symbolic factorization of the matrix A T A . We first address uniprocessor issues and then discuss the multiprocessor implementation of the method. We consider the parallelization of both the factorization phase and the solve phase. We use relaxation of the sparsity structure of both the original matrix and the frontal matrices to improve the performance. We show that, in this case, the use of Level 3 BLAS can lead to very significant gains in performance. We use the eight processor Alliant˜FX/80 at CERFACS to illustrate our discussion.