Systolic givens factorization of dense rectangular matrices
- 1 January 1988
- journal article
- research article
- Published by Taylor & Francis in International Journal of Computer Mathematics
- Vol. 25 (3-4) , 287-298
- https://doi.org/10.1080/00207168808803674
Abstract
Given an m by n dense matrix A(m≧n) we consider parallel algorithms to compute its orthogonal factorization via Givens rotations. First we describe an algorithm which is executed in m+n— 2 steps on a linear array of [m/2] processors, a step being the time necessary to achieve a Givens rotation. The pipelined version of the new algorithm leads to a systolic implementation whose area-time performances overcome those of the arrays of Bojanczyk, Brent and Kung [1] and Gentleman and Kung [5].Keywords
This publication has 10 references indexed in Scilit:
- Complexity of parallel QR factorizationJournal of the ACM, 1986
- Parallel QR decomposition of a rectangular matrixNumerische Mathematik, 1986
- An alternative givens orderingNumerische Mathematik, 1984
- Solving Linear Algebraic Equations on an MIMD ComputerJournal of the ACM, 1983
- Matrix Triangularization By Systolic ArraysPublished by SPIE-Intl Soc Optical Eng ,1982
- Why systolic architectures?Computer, 1982
- Large-scale geodetic least-squares adjustment by dissection and orthogonal decompositionLinear Algebra and its Applications, 1980
- A Survey of Parallel Algorithms in Numerical Linear AlgebraSIAM Review, 1978
- On Stable Parallel Linear System SolversJournal of the ACM, 1978
- Very high-speed computing systemsProceedings of the IEEE, 1966