Computation of the SVD using mesh-connected processors

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

Abstract: dvi (3K), pdf (80K), ps (28K).

Paper: pdf (2385K).


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


The systolic array proposed here is similar to one proposed by Brent and Luk [84] for the symmetric eigenvalue problem, but to handle a rectangular SVD problem requires a preprocessing step in which a QR factorization is computed.

A closely related paper is [87]. For an extension to the generalized SVD, see [83].

Go to next publication

Return to Richard Brent's index page