The solution of linear systems by the QIF algorithms on a wavefront array processor (Q1101183)

The quadrant interlocking factorization (QIF) is especially well suited for computations with massive parallel arrays. It is a factorization of the form \(A=WZ\), where both W and Z are matrices whose nonzero elements appear in a `butterfly' form. The parallel algorithm for computing the QIF involves the recursive solution of 2-by-2 linear subsystems and updating of appropriate matrix elements. The present paper describes an implementation of the parallel QIF method on a wavefront array processor (WAP), i.e. a 2dim. mesh of processors (like a systolic array) that communicate without the synchronization by a global clock signal. I such a WAP, the data sweeps like a wavefront through the array, and many such computational wavefronts are usually pipelined through the WAP. The parallel QIF algorithm actually generates two wavefronts: a usual wavefront and a `dewavefront' sweeping in the opposite direction. This algorithm is described in details, and some comments are made on the timing and necessary delays required in a practical implementation of the algorithm.