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