Re: [eigen] GivensQR |

[ Thread Index | Date Index | More lists.tuxfamily.org/eigen Archives ]

*To*: eigen@xxxxxxxxxxxxxxxxxxx*Subject*: Re: [eigen] GivensQR*From*: Benoit Jacob <jacob.benoit.1@xxxxxxxxx>*Date*: Wed, 19 Aug 2009 09:46:30 -0400*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; bh=+PK/Q4WPj+z505OmLXnI1MmK0x3lT5niaR7nA4wGKzs=; b=sof/FX4qfjASKvBt/LXEyUjJU7oIkryAmHt2q5EhRmOjADJykhsMnc93huO30ZoynJ 2qD/KIQnQChwbjkHM7vuvCGnU0AtcIkiz0JEZYq2XYPfLVizQwRMMO/gUVRd2CC2X/vB vSorwOrx9TUkBr5H3od+g15P66wsKXYqAWhW8=*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; b=VHahC8NoGiikblLw8+zp9vWHceZYP7t509wK0hvdsvkh/43Iq+7+dxyinze6oBJdxB akY/2TGCsHFYc+4norZ5xCqrsmoehPm8h7wPNQWHQlqndneuMw8UZDF0wlSKJW7EWm2/ 74UC1Gku6YNIXpi5xSTZTXhep11NNEuaMNzmg=

Thank you! I was intrigued by the option of computing/storing only the sequence of Givens rotations, which doesn't seem like common practice at all; i was expecting a GivensQR class to compute/store Q and/or R according to what the user asked for. So I wondered what was the use case for the approach of storing the sequence of Givens rotations, and it seems to me that the best use case for it should be when doing only 1 vector solve. Indeed, in that case, avoiding the overhead of computing Q or R should be the most beneficial. So i did a benchmark (attached). Result (times in seconds, lower is better): === 09:28:49 ~$ g++ bench.cpp -o bench -O2 -DNDEBUG -I eigen2 && ./bench *** size 3 *** GivensQR: 0.751133 sec PartialLU: 0.542512 sec LU: 0.8757 sec *** size 4 *** GivensQR: 0.689996 sec PartialLU: 0.452786 sec LU: 0.702428 sec *** size 20 *** GivensQR: 1.79185 sec PartialLU: 0.778664 sec LU: 1.0921 sec *** size 200 *** GivensQR: 11.1207 sec PartialLU: 2.26197 sec LU: 4.75969 sec Note that this is without vectorization, indeed there's room for improvement of vectorization in your code, so I didn't want to make that influence the result. As expected, enabling vectorization only widens the difference. The bottom line is that even on the most favorable use case, a single vector solve, GivensQR is never really faster than the full-pivoting LU (the biggest is a 15% difference for 3x3 size) and gets much slower for larger sizes. So I'm tempted not to keep that aspect of GivensQR where only the sequence of rotations is computed. Instead, I would like to harmonize GivensQR with the other decs by making it templated in parameters allowing the user to say if they want Q and/or R, storing Q as a plain matrix (a packed storage of the cosines would require taking a lot of sqrts for getting the sines) and, like in other decompositions, making the decomposition actually happen at construction time (the constructor GivensQR(matrix) calls a compute() method). Are you OK? Am I missing something? Thanks, Benoit 2009/8/19 Andrea Arteaga <yo.eres@xxxxxxxxx>: > I (re-)created the givensqr fork. So I committed the file I posted yesterday > and some small modifications. Link: https://bitbucket.org/spiros/givensqr/ . > > I added bjacob as administrator.

#include <Eigen/Eigen> #include <bench/BenchTimer.h> using namespace std; using namespace Eigen; template<int size, template<typename T> class decomp> double bench() { enum { repeat = 10000000/(size*size), csize = size>10?Dynamic:size }; typedef Matrix<float,csize,csize> mtype; typedef Matrix<float,csize,1> vtype; mtype m = mtype::Random(size,size); vtype v = vtype::Random(size); vtype res = vtype::Zero(size); BenchTimer t; t.start(); for(int i = 0; i < repeat; i++) { m(0,0)=res(0)/repeat; decomp<mtype> d(m); d.solve(v, &res); } t.stop(); return t.value(); } int main() { cout << "*** size 3 ***" << endl; cout << "GivensQR: " << bench<3, GivensQR>() << " sec" << endl; cout << "PartialLU: " << bench<3, PartialLU>() << " sec" << endl; cout << "LU: " << bench<3, LU>() << " sec" << endl; cout << "*** size 4 ***" << endl; cout << "GivensQR: " << bench<4, GivensQR>() << " sec" << endl; cout << "PartialLU: " << bench<4, PartialLU>() << " sec" << endl; cout << "LU: " << bench<4, LU>() << " sec" << endl; cout << "*** size 20 ***" << endl; cout << "GivensQR: " << bench<20, GivensQR>() << " sec" << endl; cout << "PartialLU: " << bench<20, PartialLU>() << " sec" << endl; cout << "LU: " << bench<20, LU>() << " sec" << endl; cout << "*** size 200 ***" << endl; cout << "GivensQR: " << bench<200, GivensQR>() << " sec" << endl; cout << "PartialLU: " << bench<200, PartialLU>() << " sec" << endl; cout << "LU: " << bench<200, LU>() << " sec" << endl; }

**Follow-Ups**:**Re: [eigen] GivensQR***From:*Benoit Jacob

**Re: [eigen] GivensQR***From:*Jitse Niesen

**References**:**[eigen] GivensQR***From:*Andrea Arteaga

**Re: [eigen] GivensQR***From:*Benoit Jacob

**Re: [eigen] GivensQR***From:*Benoit Jacob

**Re: [eigen] GivensQR***From:*Andrea Arteaga

**Messages sorted by:**[ date | thread ]- Prev by Date:
**Re: [eigen] proposal for "clean" output arguments** - Next by Date:
**Re: [eigen] GivensQR** - Previous by thread:
**Re: [eigen] GivensQR** - Next by thread:
**Re: [eigen] GivensQR**

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