A Square Root and Division Free Givens Rotation for Solving Least Squares Problems on Systolic Arrays
- 1 July 1991
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Scientific and Statistical Computing
- Vol. 12 (4) , 800-807
- https://doi.org/10.1137/0912042
Abstract
This paper presents a square root and division free Givens rotation (SDFG) to be applied to the QR-decomposition (QRD) for solving linear least squares problems on systolic arrays. The SDFG is based on a special kind of number description of the matrix elements and can be executed by mere application of multiplications and additions. Therefore, it is highly suited for the VLSI-implementation of the QRD on systolic arrays. Roundofi error and stability analyses indicate that the SDFG is numerically as stable as known Givens rotation methods.Keywords
This publication has 11 references indexed in Scilit:
- Fast Parallel Algorithms for QR and Triangular FactorizationSIAM Journal on Scientific and Statistical Computing, 1987
- Scaled Givens Rotations for the Solution of Linear Least Squares Problems on Systolic ArraysSIAM Journal on Scientific and Statistical Computing, 1987
- A Rotation Method for Computing the QR-DecompositionSIAM Journal on Scientific and Statistical Computing, 1986
- Numerically Stable Solution of Dense Systems of Linear Equations Using Mesh-Connected ProcessorsSIAM Journal on Scientific and Statistical Computing, 1984
- Systolic Networks for Orthogonal DecompositionsSIAM Journal on Scientific and Statistical Computing, 1983
- A very fast multiplication algorithm for VLSI implementationIntegration, 1983
- Highly concurrent computing structures for matrix arithmetic and signal processingComputer, 1982
- Error analysis of QR decompositions by Givens transformationsLinear Algebra and its Applications, 1975
- A Note on Modifications to the Givens Plane RotationIMA Journal of Applied Mathematics, 1974
- Least Squares Computations by Givens Transformations Without Square RootsIMA Journal of Applied Mathematics, 1973