Re: [eigen] notes on Householder and Givens |
[ Thread Index |
Date Index
| More lists.tuxfamily.org/eigen Archives
]
- To: eigen@xxxxxxxxxxxxxxxxxxx
- Subject: Re: [eigen] notes on Householder and Givens
- From: Benoit Jacob <jacob.benoit.1@xxxxxxxxx>
- Date: Wed, 4 Feb 2009 19:34:37 +0100
- 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=D7/gA28vTfrJR7ck7j3bxNttVMBKC5dwyi9i986f3SI=; b=K6WdezOOaD47Hl8WWHUukJfRoJTWvQJPPAnEUtaKZF7tS9wmWqPFq1kMyXdWPf+IGv 7kVg9ilSpygTsQwajJxkCziPR4y3Y+wOTYlBCm35ZBMwuZoGt4CRJphVdaGU6SpGB/Wp yHl27kxZ87XuED+nPMrc34N1vt+jiHxC/tjgg=
- 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=N3NoFxl1vRBKR9zm0KH5onbRLviGLdYP3JQXXZEuOmeqrKEXIUqOtNwZqj0T23Nglg tfnsPw9ergNax1xKFJTECrqPQVT/GatS/IjewABH7jAILsHcu6Zky7SAgjHkf6BLSEng FgSIOdIajDfjRE6tnq7YZ1j/Y9IQBePaw0fog=
OK, last email, i promise.
Actually even my last ei_compute_householder can be made to work with
zero branching, in the case of real numbers. This would be a nice
optimization in the case of real, small (fixed size...) SVD, which
you're interested in.
The idea is that for real numbers, " x0 / abs(x0) is just the sign of
x. And one can code a bitwise "sign" function that works without any
branching. It doesn't matter what happens around x0==0 as long as that
function always returns +1 or -1, because if x0 is near zero then both
x + norm(x) e0 and x - norm(x) e0 are good possible choices for v.
To summarize, in real case:
void ei_compute_householder(const Vector& x of size n, Householder *h)
{
// compute natural householder vector v
Vector v = x;
v0 += sign(x0) * norm(x);
Vector v_starting_with_1 = v/v0;
h->essential = v_starting_with_1.end(n-1);
h->beta = 2 / v_starting_with_1.squaredNorm();
};
in the complex case, sign(x0) could still return x0/abs(x0) if x0 is
not near 0, but there we must be careful if x0 is close to zero: some
branching is neeeded.
Cheers,
Benoit