COMPUTATION OF THE SINGULAR VALUE DECOMPOSITION USING MESH-CONNECTED PROCESSORS

R. P. BRENT, F. T. LUK, AND CHARLES VAN LOAN

Abstract

A cyclic Jacobi method for computing the singular value decomposition of an m × n matrix (m ≥ n) using systolic arrays is proposed. The algorithm requires O(n^{2}) processors and O(m + n log n) units of time.

Comments

Only the Abstract is given here. The full paper appeared as [2]. For related work and generalisations, see [1, 3, 4].

References

1. 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.

2. 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. Also appeared as Report TR 82-528, Department of Computer Science, Cornell University, November 1982; and as Report TR-CS-83-05, Department of Computer Science, ANU, January 1983, 34 pp. MR 86m:65033. rpb080.

3. R. P. Brent, F. T. Luk and C. F. Van Loan, “Computation of the generalized singular value decomposition using mesh-connected processors”, Proceedings SPIE, Volume 431, Real Time Signal Processing VI (edited by Keith Bromley), SPIE, Bellingham, Washington, 1983, 66–71. rpb083.

4. 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. MR 86i:65089. rpb084.

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

(Luk) School of Electrical Engineering, Cornell University, Ithaca, NY 14853

(Van Loan) Department of Computer Science, Cornell University, Ithaca, NY 14853

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

Key words and phrases. Systolic arrays, singular-value decomposition, SVD, cyclic Jacobi method, real-time computation, VLSI.

Copyright \begin{matrix}c \\ ◯ \end{matrix} 1985, Computer Science Press, Inc. Comments \begin{matrix}c \\ ◯ \end{matrix} 1993, R. P. Brent. rpb080a typeset using AMS-L^{A}TEX