A Stream Algorithm for the SVD
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...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Language: | en_US |
| Published: |
2005
|
| Online Access: | http://hdl.handle.net/1721.1/30429 |
| _version_ | 1811075419181416448 |
|---|---|
| author | Strumpen, Volker Hoffmann, Henry Agarwal, Anant |
| author2 | Computer Architecture |
| author_facet | Computer Architecture Strumpen, Volker Hoffmann, Henry Agarwal, Anant |
| author_sort | Strumpen, Volker |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T10:05:35Z |
| id | mit-1721.1/30429 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T10:05:35Z |
| publishDate | 2005 |
| record_format | dspace |
| spelling | mit-1721.1/304292019-04-12T13:39:27Z A Stream Algorithm for the SVD Strumpen, Volker Hoffmann, Henry Agarwal, Anant Computer Architecture 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. 2005-12-22T01:09:48Z 2005-12-22T01:09:48Z 2003-10-22 MIT-CSAIL-TR-2003-024 MIT-LCS-TM-641 http://hdl.handle.net/1721.1/30429 en_US Massachusetts Institute of Technology Computer Science and Artificial Intelligence Laboratory 31 p. 30567456 bytes 1124918 bytes application/postscript application/pdf application/postscript application/pdf |
| spellingShingle | Strumpen, Volker Hoffmann, Henry Agarwal, Anant A Stream Algorithm for the SVD |
| title | A Stream Algorithm for the SVD |
| title_full | A Stream Algorithm for the SVD |
| title_fullStr | A Stream Algorithm for the SVD |
| title_full_unstemmed | A Stream Algorithm for the SVD |
| title_short | A Stream Algorithm for the SVD |
| title_sort | stream algorithm for the svd |
| url | http://hdl.handle.net/1721.1/30429 |
| work_keys_str_mv | AT strumpenvolker astreamalgorithmforthesvd AT hoffmannhenry astreamalgorithmforthesvd AT agarwalanant astreamalgorithmforthesvd AT strumpenvolker streamalgorithmforthesvd AT hoffmannhenry streamalgorithmforthesvd AT agarwalanant streamalgorithmforthesvd |