Sparse matrix multiplication appears to be slow

[Paul Buerkner]

Dear Stan Team,

I have been playing around a bit with the sparse matrix multiplication in Stan and found, to my surprise, that it doesn't seem to be faster (sometimes slower) even with matrices that are ~90% sparse.

Maybe I am doing something wrong?

I have attached a toy example (linear regression) with a design matrix that is 90% sparse. On my machine, the sparse matrix version is roughly 2 times slower than the ordinary version.

Many thanks for your help!

Paul

[Bob Carpenter]

I didn't know the cutoff point, but there's a pretty big
overhead for sparsity and we haven't really spent much time
optimizing the sparse matrix code (or the dense code, for
that matter --- memory locality optimization may be able to
eke out another factor of 2 or more).

Is it faster above 90% sparsity? We should probably indicate
this in the manual:

https://github.com/stan-dev/stan/issues/1709#issuecomment-200870788

- Bob

> --
> You received this message because you are subscribed to the Google Groups "Stan users mailing list" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to stan-users+...@googlegroups.com.
> To post to this group, send email to stan-...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.
> <slow_sparse_matrix_mult.zip>

[Paul Buerkner]

I haven't tried so far, but given that it's currently ~2 times slower for 90% sparsity (at least in the toy example), I bet that we need at least a few more percent until it's equally efficient.

[Krzysztof Sakrejda]

At this point the big advantage for sparsity is the lower memory use.  It lets you manipulate matrices that just don't fit in memory. It does take a lot of sparsity before you get a speed advantage and it depends on whether it's column-oriented or row-oriented sparsity (empty rows are simply not stored/processed so that improves faster).  It's on my plate to do an explicit comparison (and soon since it's come up for rstanarm) but I'm swamped so it'll be a few weeks.  

Krzysztof