An orthogonal method for solving systems of linear equations without square roots and with few divisions

摘要

An algorithm is presented that requires only multiplications, additions, and a single division for the orthogonal solution of a system of linear equations. For that purpose the QR-decomposition of an extended system matrix, called the orthogonal Faddeeva algorithm, is computed by a square-root- and division-free Givens rotation, called scaled standard Givens rotation (SSGR). A special kind of number description, which is tailored to the standard Givens rotation, allows the execution of the SSGR solely by application of multiplications and additions. Therefore, the SSGR is highly suited for VLSI implementation. The roundoff error of the SSGR is as stable as the roundoff error of any available square-root-free Givens rotation, and its deviation factor is better.