Numerically Stable Solution of Dense Systems of Linear Equations Using Mesh-Connected Processors

Abstract

We propose a multiprocessor structure for solving a dense system of n linear equations. The solution is obtained in two stages. First, the matrix of coefficients is reduced to upper triangular form via Givens rotations. Second, a back substitution process is applied to the triangular system. A two-dimensional array of $\theta (n^2 )$ processors is employed to implement the first step, and (using a previously known scheme) a one-dimensional array of $\theta (n)$ processors is employed to implement the second step. These processor arrays allow both stages to be carried out in time $O(n)$, and they are well suited for VLSI implementation as identical processors with a simple and regular interconnection pattern are required.