Re: [eigen] first benchmark of large and sparse matrix |

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

*To*: eigen@xxxxxxxxxxxxxxxxxxx*Subject*: Re: [eigen] first benchmark of large and sparse matrix*From*: "Schleimer, Ben" <bensch128@xxxxxxxxx>*Date*: Mon, 23 Jun 2008 10:38:59 -0700 (PDT)*Domainkey-signature*: a=rsa-sha1; q=dns; c=nofws; s=s1024; d=yahoo.com; h=Received:X-Mailer:Date:From:Reply-To:Subject:To:In-Reply-To:MIME-Version:Content-Type:Content-Transfer-Encoding:Message-ID; b=Jb9N9bFt4Cy9wQ1mjXfTyUOwh0O/yt2Tw9s4xfrWlrUzterNusZDvLPiEtpvn2f2/zfOoRQPaIoidBeK86e/khRdSltwkX7hNelg5P3pjOoCqUPNjl16/zzBLPpIFQ3F8MLli6Hj+u2V1P3M+IoMtaBJtrqspOOj6VAnVLWJHbo=;

Hi guys, I didn't know gmm++ matrices were so slow either. I wonder if we could take the gmm++ algos and use templated eigen sparse matrices with them... btw, how are you designing sparse templated matrices? Do you have any papers to point to? Cheers Ben --- On Sun, 6/22/08, Benoît Jacob <jacob@xxxxxxxxxxxxxxx> wrote: > From: Benoît Jacob <jacob@xxxxxxxxxxxxxxx> > Subject: Re: [eigen] first benchmark of large and sparse matrix > To: eigen@xxxxxxxxxxxxxxxxxxx > Cc: "Gael Guennebaud" <gael.guennebaud@xxxxxxxxx> > Date: Sunday, June 22, 2008, 11:05 PM > Man, that is good...!!! > > It's normal that the sparse matrix is a bit slower than > the dense one with 10% > nonzero coeffs; also I suppose that the memory usage is > already significantly > lower. So your numbers look very good! > > I wasn't expecting GMM++ to perform so poorly; it > sounds to me as if their > sparse matrices are not intented for doing matrix > arithmetic, but instead are > just intended to apply solving algorithms; still, being > able to form sums is > at least useful to construct the matrices in the first > place! (And I > definitely personnally see use cases for full support for > arithmetic on > sparse matrices, as this models a mathematical object known > as a 'convolution > algebra' and is thus very interesting). > > So it is sounding like you're solving the problem of > sparse matrix storage; if > there exists a possibility of providing an abstraction > layer for sparse > algorithms supporting multiple backends (as discussed on > IRC, implementing > sparse algos ourselves is really too ambitious, so we want > to reuse existing > code for that) then we would get a very, very good > Eigen-Sparse module (or > auxiliary library, depending on how you see it). > > FYI this is of high interest for Krita and for Step and > probably has countless > interesting applications; a while ago Benjamin did play > with some research > papers on vector graphics using sparse matrices to > interpolate intelligently > between vector shapes, which was very interesting (still > have the app he > coded using gmm++ and eigen1, can send it to you)... so no > need to convince > me about the usefulness of all this. > > Cheers, > Benoit > > P.S. I'm adding vectorization to Redux > > On Monday 23 June 2008 02:09:15 Gael Guennebaud wrote: > > Hi, > > > > this WE I started looking at sparse matrices and I > started to write > > some experimental piece of code to see how they could > be integrated > > into the current base code. The current sparse matrix > class implement > > the "Compressed Column Storage" (CCS) scheme > and does not require any > > change in Core: an InnerIterator template class is > specialized for > > each matrix and expression type. These iterators allow > to efficiently > > skip the zero coefficients of a row while being > compatible with the > > expression template mechanism. > > > > To check whether it was worth it, I benchmarked the > sum of 3 matrices > > of 4000x4000 with 10% of non zero coefficients > (random) : > > > > for (int k=0; k<10; ++k) > > m4 = m1 + m2 + m3; > > > > the results: > > > > * dense matrix (with vectorization and all eigen > optimizations) : 0.7sec > > > > * dense matrix without xpr template, i.e.: > > m4 = (m1 + m2).eval() + m3 > > => 1.6 sec > > > > * experimental sparse matrix with generic xpr > template: 1.6 sec > > > > * experimental sparse matrix without xpr template (but > with a > > specialized operator* for the sum): 2.1 sec > > > > * GMM++: 19sec !! (+ very high memory consumption) > > > > so yeah it was worth it ! Even with sparse matrix the > ET is pretty > > useful. Moreover the current implementation is far to > be optimized > > (e.g. it uses std::vector<>) so we can expect > even better performance. > > > > I believe the poor perf of GMM++ is partly due to the > use of "mapped" > > sparse matrix (one std::map per row) for the result > because their > > implementation of CCS matrix is read-only. > > > > cheers, > > gael.

**Follow-Ups**:**Re: [eigen] first benchmark of large and sparse matrix***From:*Gael Guennebaud

**References**:**Re: [eigen] first benchmark of large and sparse matrix***From:*Benoît Jacob

**Messages sorted by:**[ date | thread ]- Prev by Date:
**Re: [eigen] vectorization of sum** - Next by Date:
**Re: [eigen] first benchmark of large and sparse matrix** - Previous by thread:
**Re: [eigen] first benchmark of large and sparse matrix** - Next by thread:
**Re: [eigen] first benchmark of large and sparse matrix**

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