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).
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(n2)
processors and O(m + n log n)
units of time.
Comments
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