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*: Benoît Jacob <jacob@xxxxxxxxxxxxxxx>*Date*: Mon, 23 Jun 2008 07:05:30 +0200*Cc*: "Gael Guennebaud" <gael.guennebaud@xxxxxxxxx>

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.

**Attachment:
signature.asc**

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

**Re: [eigen] first benchmark of large and sparse matrix***From:*Schleimer, Ben

**References**:**[eigen] first benchmark of large and sparse matrix***From:*Gael Guennebaud

**Messages sorted by:**[ date | thread ]- Prev by Date:
**[eigen] first benchmark of large and sparse matrix** - Next by Date:
**Re: [eigen] first benchmark of large and sparse matrix** - Previous by thread:
**[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/ |