A Stream Algorithm for the SVD
Author(s)
Strumpen, Volker; Hoffmann, Henry; Agarwal, Anant
DownloadMIT-CSAIL-TR-2003-024.ps (29.15Mb)
Additional downloads
Other Contributors
Computer Architecture
Metadata
Show full item recordAbstract
We present a stream algorithm for the Singular-Value Decomposition (SVD) of anM X N matrix A. Our algorithm trades speed of numerical convergence for parallelism,and derives from a one-sided, cyclic-by-rows Hestenes SVD. Experimental results showthat we can create O(M) parallelism, at the expense of increasing the computationalwork by less than a factor of about 2. Our algorithm qualifes as a stream algorithmin that it requires no more than a small, bounded amount of local storage per processor and its compute efficiency approaches an optimal 100% asymptotically for largenumbers of processors and appropriate problem sizes.
Date issued
2003-10-22Other identifiers
MIT-CSAIL-TR-2003-024
MIT-LCS-TM-641
Series/Report no.
Massachusetts Institute of Technology Computer Science and Artificial Intelligence Laboratory