| Re: [eigen] Thin JacobiSVD |
[ Thread Index |
Date Index
| More lists.tuxfamily.org/eigen Archives
]
- To: eigen@xxxxxxxxxxxxxxxxxxx
- Subject: Re: [eigen] Thin JacobiSVD
- From: Gael Guennebaud <gael.guennebaud@xxxxxxxxx>
- Date: Fri, 8 Jun 2012 15:35:05 +0200
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :content-type:content-transfer-encoding; bh=7TrA8kn2DGGjTOzDZYz0nks6sbwM00FdI2DeMgYkpRM=; b=k+IiKdj4Kvtr8rYc+dYrxf6ziLRyYS492OK11dfSNbM0ang66WN0Y2KLG7YOr120uX 1W2U7ZHY5Ky6VSoekqTW7O/9Y+ZMosPs0+NjHkUX7BENx3JtD67/lZobgz81Fzh54Ya4 TC+kvpaxqzfjw5eBsxZRM1U0byxY5Hm5v434+on5GwLlDIucfavg48q4ZoCY8yWmuAZg hmQY9yS9QE56igVqkjjYhYX8IUBdjTp7ELA+YFal1QOQqQIL+Pss+9VZwg1+BNULha9E B96jeXe1g63Yjy+nV4x0EOGQIjcDC1yb8TvOUf3G8Z5V5aXkGJ0rj1CToWifuhlYWzGi wziA==
On Fri, Jun 8, 2012 at 3:17 PM, Mark Borgerding <mark@xxxxxxxxxxxxxx> wrote:
> 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.
That's another story, but you are right, JacobiSVD is good for small
matrices, but too slow for big ones. It's clear we need another
algorithm too.
> 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.
Excellent. I have some notes on that topic.
cheers,
Gael.
>
> -- 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;)
>>
>
>
>