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

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

Two further remarks:
- we really want SVD for all rectangular matrix sizes
- i checked, there do exist cache-efficient block bidiagonalization
algorithms although the articles seem recent, for example this 2008
paper:
http://portal.acm.org/citation.cfm?id=1356055
Since they're so recent, I think it'd be acceptable to start
short-term with a traditional householder bidiagonalization before
starting considering these...

Benoit


2009/4/18 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
>>
>>
>