Re: [eigen] Thin JacobiSVD

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

Certainly, a fast scalable non-Jacobi SVD is much needed and I'm sorry
I said I'd do it and never did. As you mention, the right approach is
householder bidiagonalization followed by divide-and-conquer
bidiagonal SVD, which is what SGESDD do. There's even a bug filed for
that, http://eigen.tuxfamily.org/bz/show_bug.cgi?id=67

Benoit

2012/6/8 Mark Borgerding <mark@xxxxxxxxxxxxxx>:
> I'm not really knowledgable enough in the algorithms to have an opinion on
> *how* to do it, but I would like to register a show of support for having a
> faster SVD (maybe not Jacobi?). Thinning would be one dimension in that
> optimization space.   I've got some code for doing SVDs using Eigen that is
> beautiful, elegant, maintainable ... and commented out.  Unfortunately, the
> Eigen code is several times slower than the ugly hackish LAPACK calls
>  [SCDZ]GESDD. I can provide demo code upon request.
>
> On an orthogonal topic: I am not taking classes this summer, so I should
> have some time to clean up the FFT module and move it out of unsupported.
>
> -- Mark
>
>
> On 06/08/2012 09:00 AM, Gael Guennebaud wrote:
>>
>> Hi,
>>
>> currently JacobiSVD cannot compute a thin factorization with a fixed
>> number of columns. This is because the 'thin' status is provided at
>> runtime while fixed dimensions have to be known at compile-time.
>> However, a typical use case for JacobiSVD is to solve for a
>> Matrix<scalar, Dynamic or large_value, small_value>  matrix with a
>> small fixed number of columns but many rows.
>>
>> I see three options:
>>
>> One option would be to relax the JacobiSVD's matrix types for the U
>> factor to always use a dynamic number of columns, but keep
>> MaxRowsAtCompileTime for the max column size to keep static allocation
>> when possible. The drawback is that we cannot exploit a fixed number
>> of columns for unrolling or other optimizations.
>>
>> This last limitation could be addressed by instancing the code twice
>> (thin and full), and do a dynamic branching.
>>
>> The last option I see, and perhaps my favorite, would be to add a
>> ThinJacobiSVD class (on top of the general JacobiSVD) that would
>> always compute the thin U and thin V. This variant would be ideal for
>> solving: it would prevent the need to add ComputeThinU|ComputeThinV
>> every time. I'm pretty sure it would cover 90% of the use cases. Of
>> course we would also add a .thinJacobiSVD() member to MatrixBase.
>>
>>
>> Any opinion?
>>
>>
>> cheers,
>> Gael, who is trying to restart some dynamism in Eigen's development;)
>>
>
>
>