| Re: [eigen] Getting Householder reflections right |
[ Thread Index |
Date Index
| More lists.tuxfamily.org/eigen Archives
]
- To: eigen@xxxxxxxxxxxxxxxxxxx
- Subject: Re: [eigen] Getting Householder reflections right
- From: Benoit Jacob <jacob.benoit.1@xxxxxxxxx>
- Date: Fri, 8 May 2009 21:33:29 +0200
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:received:in-reply-to:references :date:message-id:subject:from:to:content-type :content-transfer-encoding; bh=G6QU058LWh/D0qcYH1rD+udADJD2W2Vp+hAbjv1mYf0=; b=FRql1GBWQLyB8PcRk9hKeK6fNZIWFwglz/pleLEwlf52q6+mw2faFuoFh0Plse5bDX JtG48AZIyofLMzcWlG7/zOSGP4T14Ml9is4q/JFeGjuDiryN/qZ6+CUpjL5kvo8agzNc 7km93XAmZUuxesOSUegSs8S6USsFffCAcmJys=
- Domainkey-signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :content-type:content-transfer-encoding; b=wI7CpxYOt9isvq+nCRXJfB11LCuu6sXS+UJ0VhKXw6w1aP5Mf5o1f/2L/fADrGl4mZ k5hgKpSjSq726KTQqlTb71yR9LcLCRbV5S/e9UH48zjJhyXpe9WlZVByf9KfWp7l4CK1 8aU7+RcZaPnsy6de/wHDpMQWXyh8H0dpHFLVM=
thanks for the reminder, it's actually the right time to look at that
as it may impact the design.
Benoit
2009/5/8 Rohit Garg <rpg.314@xxxxxxxxx>:
> Possibly OT
>
> May be you should look at block wise House holder transformations. I'd
> infact recommend that all algorithms is-as-far-as-possible be done in
> a blockwise manner.
>
> On Sat, May 9, 2009 at 12:52 AM, Benoit Jacob <jacob.benoit.1@xxxxxxxxx> wrote:
>> Hi,
>>
>> I'm wondering how to do Householder reflections right.
>> Books (Golub&vanLoan) and libraries (LAPACK) seem to _always_ use the
>> following packed storage for a Householder vector v:
>> they normalize it so that v(0)=1, hence they don't need to store v(0)
>> which is useful for storing decompositions in a packed way in a single
>> matrix.
>> However, they store separately the norm of v, in order to avoid having
>> to recompute it everytime.
>>
>> I'm not saying this is always a bad idea, i'm saying that's not always
>> a good idea.
>>
>> That's a good idea for the QR decomposition, because it allows to
>> store the whole decomposition in a single matrix, plus a vector to
>> store the norms of the v's.
>>
>> But right now i'm looking at bidiagonalization and i'm seriously
>> wondering if this packed storage is a good idea.
>> With the packed storage, i can store in a single matrix the bidiagonal
>> matrix, and the essential parts of the householder vectors, but then i
>> need to store in 2 separate vectors the norms of the householder
>> vectors.
>> While _without_ packed storage, i'd be able to store entirely in a
>> single matrix (of the same size) the whole householder vectors, and
>> then i'd store the bidiagonal matrix separately (obviously in a
>> compact way).
>> So here, I don't see any advantage in using packed Householder storage.
>> On the other hand, NOT packing the householder vectors will give
>> simpler code and slightly better speed.
>>
>> Maybe the only advantage is to make our bidiagonalization storage
>> compatible with LAPACK. But if that's important, we can add conversion
>> methods, and, having n^2 complexity, the conversion won't have a big
>> overhead compared to the n^3 cost of the decomposition itself.
>>
>> Same remarks for these close relatives: tridiagonalization and
>> hessenberg decomposition (which i'll rework along the way).
>>
>> Opinions?
>>
>> Cheers,
>> Benoit
>>
>>
>>
>
>
>
> --
> Rohit Garg
>
> http://rpg-314.blogspot.com/
>
> Senior Undergraduate
> Department of Physics
> Indian Institute of Technology
> Bombay
>
>
>