| 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: Rohit Garg <rpg.314@xxxxxxxxx>
- Date: Sat, 9 May 2009 00:59:31 +0530
- 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=LJCkj/jWBc5Tn4B18DMWclti8+WpNDKUiCmAlOyRuGk=; b=n/Ygrty1WwUHFb2PhBd5dnGd6QjOSLS5UOnhXMPvBjgRUErYtDV6o7cKmonaIGPJmD EvlXjvMxXPIVmZWdRlxoQ9HRA01bPkUJGkcyHJpoUcR2LyKnCkIfucWkiPUY3lO4LaEt cr6LSrPOKBpSrU0TgGhLJnc3DOdrkFC2efbsw=
- 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=bFrCC/wmGwirrLeiZkbkWcSTfIXYrHH+9LuN80M7WCuhWZdgpHCr9hwqImE0HpxihS UPzoJ1YvWyCebNppfLdDf3t6CFpx6s4ndJ3rz1Anf1+wX1i0KkooIKQbJ6mzaKzya9VT 703x4MGys8/kzhVu78C/WJOX6ZNfvE3i+nILI=
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