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*: Tue, 24 Jun 2008 15:53:01 +0200

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**

**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

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

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

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