Re: [eigen] BDCSVD update
• To: eigen <eigen@xxxxxxxxxxxxxxxxxxx>
• Subject: Re: [eigen] BDCSVD update
• From: Gael Guennebaud <gael.guennebaud@xxxxxxxxx>
• Date: Wed, 21 Aug 2013 16:36:46 +0200

Hi,

some fresh numbers after last Jitse commit. Computation times in second for a 1000x1000 random matrix, compared to Lapack's D&C implementation:

BDCSVD:         4.49042
BDCSVD  U+V:    14.3293
dgesdd_:        1.82801
dgesdd_ U+V:    3.16488

Actually, when only the singular values are computed, the bidiagonalization step takes about 90% of the computation time. Making it work on blocks (or better tiles), would likely permit to catch up with Lapack.

gael.

On Tue, Aug 20, 2013 at 5:16 PM, Gael Guennebaud wrote:
excellent!

Lapack is using rational approximations to help solving the non-linear equation. There is also this paper [1] that suggest using the fast-multipole-method, but before moving to other algorithms we should make some performance analysis to see how far we can get with that one.

gael

On Tue, Aug 20, 2013 at 3:34 PM, Benoit Jacob wrote:
\o/

Thanks Jitse, that's very useful work!

Benoit

2013/8/20 Jitse Niesen
Hello,

I continued work on the BDCSVD (bidiagonalizing divide-and-conquer SVD), building on the excellent work of the group of students at ensimag in Grenoble. The basic algorithm is now fully implemented. It took me longer than expected; small mistakes and short-cuts that I took lead to loss of accuracy. However, at the moment all tests pass, it seems accurate on random matrices, and it's faster than JacobiSVD (about a factor of four for a 160-by-160 matrix).

I used the bisection method to solve the nonlinear equation at the heart of the algorithm, which is hardly state-of-the-art. In fact, I think most of the lines of code I added can be improved, so I intend to spend some time optimizing and fine-tuning the BDCSVD class.

Thanks again to Gauthier, Ncolas, Jean and Pierre for their work. Their well-documented code and their report made it easy for me to get started.

Jitse

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