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 n2
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