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

[Benoît Jacob <jacob@xxxxxxxxxxxxxxx>]

I don't know what to say, this is just plainly awesome :)

Updating the list: yesterday we vectorized sum(), giving the best 
vectorization boost we got so far (for floats, it goes 4x faster, which is 
the theoretical maximum). Today I am transposing this code to dot-product and 
I expect similar results.

Cheers,

Benoit

On Tuesday 24 June 2008 01:06:55 Gael Guennebaud wrote:
> Hi,
>
> some news from the front. First of all I implemented HashMatrix which
> is essentially a column vector of std::map<>. The purpose is to allow
> random writes which at the first place sounds to be needed to
> implement matrix-:matrix products. First result: it is about 4 times
> slower to fill a HashMatrix than filling a SparseMatrix in a coherent
> order.
>
> Then I implemented a  <sparse column matrix> * <sparse column matrix>
> product. The algorithm to compute res = lhs * rhs is pretty simple:
>
> std::vector tmp<res.cols()>;
> for (int j=0; j<rhs.cols(); ++j)
> {
>     tmp = 0.0;
>     // for each coeff of the column j of rhs
>     for (Rhs::InnerIterator rhsIt(rhs, j); rhsIt; ++rhsIt)
>     {
>        // for each coeff of the column rhsIt.index() of lhs
>       for (Lhs::InnerIterator lhsIt(lhs, rhsIt.index()); lhsIt; ++lhsIt)
>          tmp[lhsIt.index()] += lhsIt.value() * rhsIt.value();
>     }
>     // copy skipping the zero entries:
>     res.col(j) = tmp;
> }
>
> as you can see it's pretty simple and and the trick is to allocate a
> single dense column to avoid many writes to a sparse array. The memory
> cost of this temporary should not be an issue since the SparseMatrix
> already stores a dense column vector to index the start of each
> column. Moreover this algorithm still fill the result sparse matrix in
> a coherent order meaning that so far there is no real need for a
> HashMatrix with random write access.
>
> The results are pretty good:
>
> 2048^3, 10% of nonzero entries:
>
> Eigen dense = 1.92237
> Eigen sparse = 0.399866
> Eigen hash = 1.30217
> GMM++ sparse = 15.973
>
>
> 2048^3, 1% of nonzero entries:
>
> Eigen dense = 1.86719
> Eigen sparse = 0.0492229
> Eigen hash = 0.186288
> GMM++ sparse = 0.24993
>
> FYI, the same algorihm without the dense temporary  and using a
> HashMatrix for the result is much much slower (~ one order of
> magnitude).
>
> cheers,
> gael.
>

Attachment: signature.asc
Description: This is a digitally signed message part.