## Numerically stable solution
of dense systems of linear equations using mesh-connected processors

65. A. W. Bojanczyk, R. P. Brent and
H. T. Kung,
Numerically stable solution
of dense systems of linear equations using mesh-connected processors,
* SIAM J. Scientific and Statistical Computing* 5 (1984), 95-104.
MR 85b:65026.
Also appeared as Technical Report TR-CS-81-01,
Department of Computer Science, ANU;
and as Technical Report TR-CS-81-119,
Department of Computer Science, CMU (May 1981), 23 pp.

Abstract:
dvi (3K),
pdf (90K),
ps (32K).

Paper: pdf (1038K).

## 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 order *n*^{2}
processors is employed to implement the first stage,
and (using a previously known scheme) a one-dimensional array of
order *n* processors is employed
to implement the second stage. 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.
## Comments

Although publication in *SISSC* was delayed,
the Technical Report
predated the well-known work of
Gentleman and Kung
[*Proc. SPIE, Volume 298, Real-Time Signal Processing IV*,
August 1981].
As shown in Brent [110],
the algorithm of the present paper
and that of Gentleman and Kung are in a certain sense dual.
The algorithm of Gentleman and Kung is preferable for
QR factorization of *m* × *n* matrices where
*m* >*n* (as in least squares problems) because the
size of the processor array depends on *n* but not on *m*.

Go to next publication

Return to Richard Brent's index page