|[eigen] Getting Householder reflections right|
[ Thread Index |
| More lists.tuxfamily.org/eigen Archives
- To: eigen <eigen@xxxxxxxxxxxxxxxxxxx>
- Subject: [eigen] Getting Householder reflections right
- From: Benoit Jacob <jacob.benoit.1@xxxxxxxxx>
- Date: Fri, 8 May 2009 21:22:22 +0200
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:received:date:message-id:subject :from:to:content-type:content-transfer-encoding; bh=STrehI0dsO4t3AtZzRWaTs2z6GIzZ7+0VTOBiaZryR4=; b=nmW50qGIzFTmKlafeh55scIXrBKMdutfkSyCHQfvNy7p4yJXgTGB77DR2PcwWHuXkn 8glWMy2KIcpcBcKyaAC/LJ6Sg5Gc6IfGSOAeJACoL+DyfCcGZXMtBt8ZynL2pEJI1qdR it1JIJylVq/WZiHHCMPM+hkQkMZF+Ns6eaI+o=
- Domainkey-signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:date:message-id:subject:from:to:content-type :content-transfer-encoding; b=isgtrBdKREyir/OIQaherW6WsEcMXMh1a3x1R9P++wB67a7YMqIlq2BokcfY0fOmRq w9bE2sMR2e7urgM4s8Dn8plX0tgwM+VqJ3Cq0oL+tpcX7qRn3onwY469goKMpLO55yUj VdOwU1g+zhSuB489Jrk4YVGTB8gDDtx1MikP4=
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
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).