VLSI-suited orthogonal solution of systems of linear equations

Abstract

In this paper one- and two-dimensional processor arrays for the orthogonal solution of systems of linear equations are presented. Each processor cell of these processor arrays is able to carry out a Givens rotation. By using a modified Givens rotation algorithm only multiplications and additions must be executed in these processor cells. Compared to previous approaches for an orthogonal solution of systems of linear equations, the presented processor arrays have the following advantages: • -the hardware in an individual processor cell consists only of multipliers and adders. • -almost full utilization (asymptotically 100%) of these hardware components in an active processor cell can be achieved. • -the latency time for one GR, which determines the data pulse frequency of the processor arrays, can be reduced from O(b) to O(log2b), where b is the length of a dataword. © 1991.