Re: [eigen] RFC: BasicSVD class

[ Thread Index | Date Index | More lists.tuxfamily.org/eigen Archives ]


I compared the speed of BasicSVD to two versions of LAPACK running the [scdz]gesdd functions: the netlib version that comes with ubuntu and the MKL (Composer version). They are pretty comparable. BasicSVD in "fast mode" beats either version for k<5. The mode based on SelfAdjointEigenSolver is slower than the MKL LAPACK.

-- Mark

On 12/05/2012 11:05 AM, Mark Borgerding wrote:
Attached is a draft of a faster SVD class.

Summary:
The BasicSVD is much faster and sufficiently accurate for many (most?) purposes.


excerpt from header:
 * Singular Value Decomposition by eigenanalysis of the Gramian
 *
* option 1: (default) Solves A=U*S*V' by finding the eigenvectors,values of A'A (or AA' if matrix is wide)
 *           This is done using the SelfAdjointEigenSolver
* option 2: "fastMode" uses power iteration to quickly strip off the dominant eigenvectors one at a time. * This may be useful when only a few of the singular dimensions are desired (e.g. k<5)
 *
* Currently limited to "Thin" or "Economy Sized" singular vectors. When decomposing a rectangular matrix, * either the U or V matrix will be an incomplete basis (tall). Any completion of this basis is valid and
 * is left as an exercise to the reader.
*
* The "fast" mode uses power iteration (plus feedback)
*    This can be several times faster than the default mode, but
*   with caveats:
* *) convergence is slow and accuracy suffers in the case of nearly identical strongest singular values * *) speed is linear with K, so if K> 5ish, fastMode may actually be slower.



Output from testBasicSVD.cc (attached)
compiled with: g++ -Wall -O -g -msse4.2 -I /path/to/inc/ testBasicSVD.cc
explanation of fields:
values: K strongest singular values (in this case K=2) ( all lesser dimensions have singular values around 1) vectorwise errors: singular vector errors left|right for each of the K strongest dimensions subspace error: residual error of the true rank-K subspace projected onto the found subspace

begin output :
############## Type: float Problem Size: 300x200
================ JacobiSVD ================
elapsed time 0.358115s
values = 3.00011 2.00006
vectorwise errors (dB):-87.5|-92.3 -87.8|-92.2
subspace error -114 dB
================ BasicSVD ================
elapsed time 0.0242s
values = 3 2
vectorwise errors (dB):-133|-125 -112|-106
subspace error -109 dB
================ BasicSVD (fast mode) ================
elapsed time 0.0046s
values = 3 2
vectorwise errors (dB):-89.8|-86.3 -78.5|-81.8
subspace error -97.3 dB
############## Type: complex<double> Problem Size: 300x200
================ JacobiSVD ================
elapsed time 5.91s
values = 3 2
vectorwise errors (dB):-259|-265 -266|-268
subspace error -284 dB
================ BasicSVD ================
elapsed time 0.216s
values = 3 2
vectorwise errors (dB):-241|-237 -231|-231
subspace error -235 dB
================ BasicSVD (fast mode) ================
elapsed time 0.0411s
values = 3 2
vectorwise errors (dB):-305|-306 -178|-175
subspace error -178 dB


-- Mark Borgerding




Mail converted by MHonArc 2.6.19+ http://listengine.tuxfamily.org/