Re: [eigen] Student contribution

There is also a particular point that I should elaborate on:

If there existed such a thing as a 1.7x speed improvement over JacobiSVD with no downsides, of course we would want to include it. (Such a thing might actually exist, by the way, by making JacobiSVD blocked).

The problem is that bidiagonalization means that we lose the accuracy characteristics of JacobiSVD.

There are two usual kinds of SVD algorithms (at least, for the purpose of this conversation):

- Jacobi SVD, which is accurate but slow,

- Bidiagonalizing SVD, which is (relatively) inaccurate but fast

The question becomes whether there are sufficient use cases for a Jacobi algorithm that has accuracy characteristics comparable to other bidiagonalizing SVD's, while being slower than typical bidiagonalizing SVD's.

Benoit

2013/6/16 Benoit Jacob <jacob.benoit.1@xxxxxxxxx>

Hi,

Maybe I shouldn't have hopped onto this thread: I have been away from the Eigen project for a long while, and it's up to the current maintainers, not me, to decide on the specifics here.

My personal opinion is that what we really want, as described in bug 67, is something similar to LAPACK's SGESDD. As Gael pointed out, this should bring an order-of-magnitude speed improvement over JacobiSVD, at least on already-bidiagonal matrices (the rest is up to the speed of bidiagonalization, which can we worked on independently).

A 1.7x speed improvement is always nice, but I will leave it up to current maintainers to decide where exactly the bar is for deciding to include a new SVD algorithm. Of course, as you suggested, there is always the option to include it in unsupported/ so that it can be easily found and improved by other people.

The other factor to consider to what extent this code provides the right basis for a future implementation of the SGESDD-like SVD.

In any case, do feel free to reply on bug 67 to mention this work!

Finally I also want to say that this work shows that the students have very solid C++ skills, as Eigen is a notoriously difficult C++ codebase to get familiar with. Regardless of inclusion in Eigen, this should be considered a successful student project.

Thanks,
Benoit

2013/6/16 Matthieu Moy <Matthieu.Moy@xxxxxxxxxxxxxxx>

Hi,

(I'm one of the school supervisors of the project)

Benoit Jacob <jacob.benoit.1@xxxxxxxxx> writes:

> I think that actually implementing the SVD code (without resorting to
> JacobiSVD), and supporting complex matrices, should be the two main
> missing prerequisites to consider including this in Eigen.

I can't speak for students, but a 100% complete implementation seems
unlikely to happen before the end of the project (which is next
wednesday, and there are other non-technical tasks which will take time
too). Students have an internship after the project, so they are
unlikely to find more time to work on this (although I do encourage all
of them to continue contributing!).

In any case, we should find a way for the work already done to be useful
to Eigen. I think that leaving some unmaintained code on bitbucket has
little chance to be actually useful one day.

Obviously, a nice scenario would be that someone from the Eigen
community volunteers to continue the work started and merge it.

If not, we have to find a way to make it easy for someone to take over
the project. At least, mentionning the bitbucket repository on the
appropriate bug may help:

http://eigen.tuxfamily.org/bz/show_bug.cgi?id=67

(together with some instructions on what's still to be done)

I had the feeling that merging at least part of the code into Eigen
could help too, even if it doesn't bring immediate and substancial
benefits. But I do not know Eigen enough to really tell, and I
understand that merging right before a release is not a good idea.

How do you see the future of this project? Is anyone interested in
continuing the work?

Thanks,

--
Matthieu Moy
http://www-verimag.imag.fr/~moy/