|Re: [eigen] Getting Householder reflections right|
[ Thread Index |
| More lists.tuxfamily.org/eigen Archives
- To: eigen@xxxxxxxxxxxxxxxxxxx
- Subject: Re: [eigen] Getting Householder reflections right
- From: Gael Guennebaud <gael.guennebaud@xxxxxxxxx>
- Date: Mon, 11 May 2009 21:57:06 +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=2NPjZHarfIWK5fW77VQhHaTInCtj0qZQeMelTzZhXOA=; b=jXhXTY4zRruImX/06Np4dbaaUS3hOO4X0RBen/9LHJhrA3ztnbstTOZYru/h6X3c+8 D/8Bu3TKV5ChKoo9/tXuYzAhZe+KzKAHkItjMS7Cy5tYBLQXdWGPVKUnND58R0TB5d2W RJvyg7iIU+/7pURKsOf0KnRAIuz67xc7vsxRI=
- 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=CMsTvr+2LAwjubXg1BUjBMCUWMtK+1XFlmGoRRvlEtMNhGENIiapPaBi7VEJ5cFlcQ 80GFtnfEakCKCaAPurI0TkeaSqktKC63CdOyJR3fwO2ioCdQjE9eecZ1w95OIDbeWEBY bd5dcr22UThAirqtzrvGFfXr0F7bUEmqdO5zI=
BTW, JAMA used another scheme than LAPACK (or the GSL) for that. I
don't remember how they did it but I can have a look... perhaps there
is at least one good thing in their code.... Right now I can tell they
based their work on that book: Bowdler, Martin, Reinsch, and
Wilkinson, Handbook for Auto. Comp., Vol.ii-Linear Algebra.
Also, I'm not considering the LAPACK compatibility as an argument
anymore. If there exists a better option, then let's go for it.
On Fri, May 8, 2009 at 9:22 PM, Benoit Jacob <jacob.benoit.1@xxxxxxxxx> wrote:
> 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
> 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
> 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).