Re: [eigen] Adapting code from OpenCV (a seemingly much faster SVD)

[Benoit Jacob <jacob.benoit.1@xxxxxxxxx>]

Hi,

it's well known that our current SVD code, taken from JAMA, has many
issues. We didn't intend to keep it long :)

So it's been on my TODO to rewrite it from scratch. I was planning to
do it "very soon" but I've been lagging so I don't want to hold this
back any further if you think you've come up with a good solution.

Here's what we really want for the SVD:
- it should be written on top of Eigen expressions rather than plain for loops.
- it should have fixed-size specializations, ideally generic working
for all fixed sizes.
- it should handle also complex numbers.

That's why porting from OpenCV is not necessarily much shorter than
writing from scratch (unless they already have the fixed-size
specializations and Eigenifying all that isnt too hard).

A useful thing would be to look at OpenCV's code and see if they are
doing clever cache-friendly things, especially in the
bidiagonalization step. That would be impressive and would justify
using their code rather than cooking our own. If they do, check if
it's octonion-based -- that would be interesting to know, but also
that wouldn't work with complex numbers.

Otherwise, if they just do the classical householder
bidiagonalization, then we sure can to the same quickly by ourselves.

Yes, the license is an issue. Actually it seems that they already had
the converse problem:
http://www.nabble.com/linking-to-LGPL-code-td16653123.html

I'd say before considering license issues, check if they really do
such clever things that it's really better to use their code than
start from scratch. SVD isn't complicated unless one does special
cachefriendly things.

Cheers,
Benoit

2009/4/18 Hauke Heibel <hauke.heibel@xxxxxxxxxxxxxx>:
> Hi,
>
> After performing some comparisons with Eigen's SVD (see attachment), I am
> wondering whether it might be of interest or possible at all to use the
> decomposition from OpenCV. I would volunteer :) to port it - maybe in a
> first step as a new SVD class in the 'disabled' folder that enables
> repeatable comparisons. This would obviously only make sense in case it is
> possible at all to use the code I have from the OpenCV lib. Actually, I
> ported the code before to our own hand-crafted linear algebra lib. But for
> Eigen, one definitely needs to take care of license issues. Since I have
> very little knowledge about these things, I am wondering whether somebody
> could comment on the attached license file - afaik, it is the same as when I
> copied the SVD code.
>
> The test results from the attached PDF were generated with double precision,
> dynamic size matrices of dimensions 25x25 up to 200x200 - each decomposition
> has been run 100 times. The graph contains the mean decomposition time in
> seconds for different matrix sizes (y-axis). The standard deviations in the
> legend are the deviations that occured while performing one and the same
> decomposition 100 times.
>
> Any comments would be welcome...
>
> Regards,
> Hauke
>
>