THE SOLUTION OF SINGULAR-VALUE AND SYMMETRIC EIGENVALUE PROBLEMS ON MULTIPROCESSOR ARRAYS

R. P. BRENT AND F. T. LUK

Abstract

Parallel Jacobi-like algorithms are presented for computing a singular-value decomposition of an m × n matrix (m ≥ n) and an eigenvalue decomposition of an n × n symmetric matrix. A linear array of O(n) processors is proposed for the singular-value problem; the associated algorithm requires time O(mnS), where S is the number of sweeps (typically S ≤ 10). A square array of O(n^{2}) processors with nearest-neighbour communication is proposed for the eigenvalue problem; the associated algorithm requires time O(nS).

Comments

Only the Abstract is given here. The full paper appeared as [6], which combined results in the earlier reports [1, 2]. For related work and generalisations, see [3, 4, 5]. It is conjectured in [6, page 83] that S(n) = O(log n).

References

1. R. P. Brent and F. T. Luk, A systolic architecture for the singular value decomposition, Report TR-CS-82-09, DCS, ANU; Report TR 82-522, DCS, Cornell University; Report CMA-R02-82, ANU, August 1982, 12 pp. rpb075.

2. R. P. Brent and F. T. Luk, A systolic architecture for almost linear-time solution of the symmetric eigenvalue problem, Report TR-CS-82-10, DCS, ANU; Report TR 82-525, DCS, Cornell University; Report CMA-R03-82, CMA, ANU, August 1982, 23 pp. rpb076.

3. R. P. Brent, H. T. Kung and F. T. Luk, “Some linear-time algorithms for systolic arrays” (invited paper), in Information Processing 83 (edited by R. E. A. Mason), North-Holland, Amsterdam, 1983, 865–876. rpb079.

4. R. P. Brent, F. T. Luk and C. F. Van Loan, “Computation of the singular value decomposition using mesh-connected processors”, J. of VLSI and Computer Systems 1, 3 (1983–1985), 242–270. MR 86m:65033. rpb080.

1991 Mathematics Subject Classification. Primary 65Y10; Secondary 47B35, 65F15, 65H17, 65Y05, 68Q22, 68Q25, 68Q35.

Key words and phrases. Multiprocessor arrays, systolic arrays, singular-value decomposition, SVD, eigenvalue decomposition, real symmetric matrices, Hermitian matrices, Hestenes method, Jacobi method, VLSI, real-time computation, parallel algorithms.

Received by the editors November 12, 1982, and in revised form August 9, 1983.

The research of F. T. Luk was supported in part by the US Army Research Office under grant DAAG 29-79-C0124 and the National Science Foundation under grant MCS-8213718, and in part by the Mathematical Sciences Research Centre and the Centre for Mathematical Analysis, Australian National University.

Copyright \begin{matrix}c \\ ◯ \end{matrix} 1985, SIAM.

Comments \begin{matrix}c \\ ◯ \end{matrix} 1993, R. P. Brent. rpb084a typeset using AMS-L^{A}TEX 5. R. P. Brent, F. T. Luk and C. F. Van Loan, “Computation of the generalized singular value decompo-

sition using mesh-connected processors”, Proceedings SPIE, Volume 431, Real Time Signal Processing VI (edited by Keith Bromley), SPIE, Bellingham, Washington, 1983, 66–71. rpb083.

6. R. P. Brent and F. T. Luk, “The solution of singular-value and symmetric eigenvalue problems on multiprocessor arrays”, SIAM J. Scientific and Statistical Computing 6 (1985), 69–84. Also appeared as Report TR 83-562, Department of Computer Science, Cornell University, July 1983, 34 pp. MR 86i:65089. A preliminary version appeared in Proceedings of a Workshop on Mathematical Programming and Numerical Analysis (edited by S. Gustavson and R.S. Womersley), Centre for Mathematical Analysis, ANU, 1984, 38–64. MR 86k:65129. rpb084.

(Brent) Centre for Mathematical Analysis, Australian National University, Canberra

(Luk) Department of Computer Science, Cornell University, Ithaca, NY 14853, USA