Systolic Networks for Orthogonal Decompositions

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² 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.