|Re: [eigen] Specialized QR|
[ Thread Index |
| More lists.tuxfamily.org/eigen Archives
- To: eigen@xxxxxxxxxxxxxxxxxxx
- Subject: Re: [eigen] Specialized QR
- From: Benoit Jacob <jacob.benoit.1@xxxxxxxxx>
- Date: Wed, 20 May 2009 03:51:28 +0200
- Cc: Gael Guennebaud <gael.guennebaud@xxxxxxxxx>
- 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:cc:content-type :content-transfer-encoding; bh=IAagkX3gePcf8MlHVj8G/Hjgclzsj4+9xbECBJI7vA4=; b=FduUiwA//0Z4od05eoEiXLbA131neYeuSgUabTX6k1/sUkuyvNLc85WwVcAXAc2gMK 92tZPg/ljFwKkavPEGtKwQ54QMsuhwJn9DkGV2xYvExyPBK+VnosAjeJT9Gmd22klK+Z edcMeMuOTFz7JyvVS+UmP5P9eBygLxhk3yi00=
- 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 :cc:content-type:content-transfer-encoding; b=qeEALMckRTHFbIpD7v9BePB0mOFXnoOd6Pw6H1VjtuJ0eMSGXTZjVGnmJYBA9DuCMl iUoutsxSubmfMlOZnfqwBxXV9aeNEFibtr0TDM7WTuAU3rB+VW3YrNPaNpsARdOs40dC wPLMIQvJTw+SURPsP+BPDoQfDvTvp6wG3ymJg=
Thanks a lot for all that.
I think that the following things emerge from your mail and from a
quick google search I did: we probably want to keep both Givens and
Householder QR general implementations. That is, not only use QR for
fixed-size specializations, but actually offer your Givens QR
alongside the existing Householder QR. Indeed, I read that Givens QR
is more stable; regarding speed, it seems that neither is always
faster than the other which is a good reason to have both.
Gael: I would propose to rename our QR class to HouseholderQR and
eventually add GivensQR. Not sure if we want any of them to have the
name "QR": i don't see any use case for beginners who would absolutely
need a simple name for that. The most common use case is
orthonormalization but we want anyway to offer convenience methods
specially for that. And the two are really different, since the
HouseholderQR stores Householder vectors.
Andrea: I would propose that you get yourself an account on
bitbucket.org, read this page,
fork the eigen2 repository into your own repo, and develop your QR
stuff there. Since this is meant to integrate into the existing module
QR, I would suggest that you work directly there: no need this time to
start in the unsupported/ directory. It is very much appreciated if
alongside the code you can also develop a unit-test, starting from
test/qr.cpp as a model.
(All this is written with the assumption that you wanted to take care
of this: I don't want to sound like I'm giving you orders!!)
> You said me to use Eigen expressions like matrix.row() instead of for-loops,
> but I noticed a performance increase using a for-loop instead of Eigen rows
> sum. I think that this issue is due to an incorrect use of row and row
> expressions. Maybe if someone helps me to optimize the class, we'll reach
> more performance.
interesting, we'll have a look at when possible...
> I used only dynamically-sized matriced, but in theory thereis no difference
> between dynamic and fixed (the function is exactly the same).
good it works in both cases (with Eigen, it always should, the
contrary is a sign of bad code). (Tiny) fixed-size performance of that
code is irrelevant because good tiny fixed-size performance is only
achieved (usually) with explicit control of unrolling (hand or meta
unrolling). So consider this a separate issue. I mean that it's great
that your code works in both cases, but for e.g. 3x3 matrices we'll
eventually want to add a special path.
> For complex ones,
This is a bit less significant because we have quite some room for
improvement in complex matrices speed.
> Now the class store the entire Q matrix
> as well as the entire R matrix, using more memory, but requiring less
> operations in case the user need the Q matrix, too.
> I think that this behaviour is more general. Do you agree?
Unless someone who knows better disagrees, I think that in plain QR
decompositions (not RRQR) it's pretty safe to assume that the Q matrix
is wanted. Indeed the main use cases are: orthonormalization and
solving. There are very few contexts that I can think of, where the R
matrix would be all what is wanted. One such context is if we want to
compute the absolute value of the determinant of a matrix. But if
speed is the most important, nothing will beat PartialLU for that.
Also, HouseholderQR definitely doesn't compute Q unless needed, so
there's always that. So yes it seems OK to me to have GivensQR
computing Q right away, if that's useful to you. Not bad either to
have Householder and Givens diverge a bit from each other, they'll
cover different use cases.