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

[Benoît Jacob <jacob@xxxxxxxxxxxxxxx>]

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
Description: This is a digitally signed message part.