Distributed Orthogonal Factorization: Givens and Householder Algorithms
Authors:
- Alex PothenAPAlex Pothen
- Padma RaghavanPRPadma Raghavan
- 1 November 1989
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Scientific and Statistical Computing
- Vol. 10 (6) , 1113-1134
Abstract
Several algorithms for orthogonal factorization on distributed memory multiprocessors are designed and implemented. Two of the algorithms employ Householder transformations, a third is based on Givens rotations, and a fourth hybrid algorithm uses Householder transformations and Givens rotations in different phases. The arithmetic and communication complexities of the algorithms are analyzed. The analyses show that the sequential arithmetic terms play a more important role than the communication terms in determining the running times and efficiencies of these algorithms. The hybrid algorithm is the fastest algorithm overall, since its arithmetic cost is lower than the Householder algorithms and its communication cost does not increase with the column length of the matrix. The observed execution times of the implementations on an iPSC-286 agree quite well with the complexity analyses. It is also shown that the efficiencies can be approximated using only the arithmetic costs of the algorithms.Keywords
This publication has 10 references indexed in Scilit:
- Householder reflections versus givens rotations in sparse orthogonal decompositionLinear Algebra and its Applications, 1987
- The WY Representation for Products of Householder MatricesSIAM Journal on Scientific and Statistical Computing, 1987
- Parallel Cholesky factorization on a shared-memory multiprocessorLinear Algebra and its Applications, 1986
- A Rotation Method for Computing the QR-DecompositionSIAM Journal on Scientific and Statistical Computing, 1986
- Parallel QR decomposition of a rectangular matrixNumerische Mathematik, 1986
- Implementation of some concurrent algorithms for matrix factorizationParallel Computing, 1986
- An alternative givens orderingNumerische Mathematik, 1984
- Solving Linear Algebraic Equations on an MIMD ComputerJournal of the ACM, 1983
- On Stable Parallel Linear System SolversJournal of the ACM, 1978
- Error analysis of QR decompositions by Givens transformationsLinear Algebra and its Applications, 1975