[eigen] first benchmark of large and sparse matrix

["Gael Guennebaud" <gael.guennebaud@xxxxxxxxx>]

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.