LAPACK Archives

[Lapack] multiprocessor, fast Singular Value Decomposition (SVD) solver.


By the way Jim, I forgot to mention, but DGESVD is only one way to get the 
singular value decomposition using LAPACK. 
DGESVD uses the Demmel and Kahan algorithm (based on the QR iteration method).
But we also have DGESDD which uses Divide and Conquer and can notably faster 
for large matrices and actually as a better opportunity to use a multithreaded 
BLAS beneath LAPACK.

And finally we have Jacobi based methods DGESVJ and DGEJVS, they are slower but 
provide the best accuracy for the singular values. 

(And soon ... we should have an MRRR based SVD algorithm! -- just to get users 
even more confused.)

And I am realizing that your email was for real arithmetic (sorry got confused 
with another support question in complex arithmetic), so
in this case, S = A^TA and is obtained with DSYRK, and the symmetric eigenvalue 
solvers that you might want to consider are
DSYEV, DSYEVD or DSYEVR. 

Cheers,
Julien.

On Sep 23, 2011, at 3:42 PM, Jim Brown wrote:

Julien:

Thank you for your help.

Jim

On 9/23/2011 8:09 AM, Langou, Julien wrote:
DGESVD can benefit of some multithreading at the BLAS level. (So if you use 
a multithreaded BLAS you can get some speedup. ) However this will not be 
"perfect". ( You would be lucky to observe any speedup at all actually ... )

If
1) your matrix is tall and skinny
2) and 2a) you have relatively well clustered singular values (say the ratio 
of the smallest on the largest is less than 1e4)
or 2b) you do not care about the accuracy of the smallest singular values 
(just want the largest ones)
then
you can compute S = A^H * A (ZHERK), then compute the symmetric eigenvalue 
decomposition of S (ZHEEV or ZHEEVR or ZHEEVD), then obtain the singular 
values from there.
(See a linear algebra textbook.)
This does not compute the smallest singular values accurately, this does not 
work if n is not<<  m, but otherwise, ZHERK dominates the operation count 
and ZHEERK does parallelize well.
Any multithreaded BLAS will give you great speedup.

Otherwise you can check out the PLASMA project. I know that they are working 
on the SVD for multicore platforms.
I think as of now they are able to compute the singular values. They have 
great speedup.

Julien.





On Sep 22, 2011, at 2:59 PM, Jim Brown wrote:

Lapack Team:

I am looking for a multiprocessor, fast Singular Value Decomposition
(SVD) solver.

I have down loaded netlibfiles\lapack\double and I found dgesvd.f.

Is this a multiprocessor, fast Singular Value Decomposition (SVD) solver?

Or can you recommend another such SVD solver?

Jim Brown



_______________________________________________
Lapack mailing list
Lapack@Domain.Removed
http://lists.eecs.utk.edu/mailman/listinfo/lapack




<Prev in Thread] Current Thread [Next in Thread>


For additional information you may use the LAPACK/ScaLAPACK Forum.
Or one of the mailing lists, or