A SQUARE ROOT AND DIVISION FREE GIVENS ROTATION FOR SOLVING LEAST-SQUARES PROBLEMS ON SYSTOLIC ARRAYS

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. Roundoff error and stability analyses indicate that the SDFG is numerically as stable as known Givens rotation methods.