Systolic Networks for Orthogonal Decompositions
Don E. Heller, Ilse C. F. Ipsen · SIAM Journal on Scientific and Statistical Computing · 1983
An orthogonally connected systolic array, consisting of a few types of simple processors, is constructed to perform the $QR$ decomposition of a matrix. Application is made to solution of linear systems and linear least squares problems as well as $QL$ and $LQ$ factorizations. For matrices A of bandwidth w the decomposition network requires less than $w^2 $ processors, independent of the order n of A. In terms of the operation time of the slowest processor, computation time varies between $2n$ and $4n$ subject to the number of codiagonals.