A Stream Algorithm for the SVD

We present a stream algorithm for the Singular-Value Decomposition (SVD) of an M ×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 show that we can create O(M) parallelism, at the expense of increasing the computational work by less than a factor of about 2. Our algorithm qualifies as a stream algorithm in 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 large numbers of processors and appropriate problem sizes