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

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

and this one:
http://portal.acm.org/citation.cfm?id=1330191

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