Re: [eigen] Specialized QR |

[ Thread Index | Date 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, http://eigen.tuxfamily.org/index.php?title=Developer's_Corner#Mercurial_workflow 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. Cheers, Benoit

**Follow-Ups**:**Re: [eigen] Specialized QR***From:*Andrea Arteaga

**Re: [eigen] Specialized QR***From:*Jitse Niesen

**References**:**Re: [eigen] Specialized QR***From:*Andrea Arteaga

**Re: [eigen] Specialized QR***From:*Benoit Jacob

**Re: [eigen] Specialized QR***From:*Benoit Jacob

**Re: [eigen] Specialized QR***From:*Andrea Arteaga

**Messages sorted by:**[ date | thread ]- Prev by Date:
**Re: [eigen] Specialized QR** - Next by Date:
**Re: [eigen] Specialized QR** - Previous by thread:
**Re: [eigen] Specialized QR** - Next by thread:
**Re: [eigen] Specialized QR**

Mail converted by MHonArc 2.6.19+ | http://listengine.tuxfamily.org/ |