New user self-registration is currently disabled. Please email eigen-core-team @ lists.tuxfamily.org if you need an account.
Bug 632 - Optimize addition/subtraction of sparse and dense matrices/vectors
Optimize addition/subtraction of sparse and dense matrices/vectors
Status: CONFIRMED
Product: Eigen
Classification: Unclassified
Component: Sparse
3.4 (development)
All All
: Low Optimization
Assigned To: Nobody
:
: 832 (view as bug list)
Depends on:
Blocks: 3.4
  Show dependency treegraph
 
Reported: 2013-07-19 11:19 UTC by Alexander Werner
Modified: 2016-01-30 13:59 UTC (History)
4 users (show)



Attachments
Code to reproduce problem (186 bytes, text/x-c++src)
2013-07-19 11:19 UTC, Alexander Werner
no flags Details

Description Alexander Werner 2013-07-19 11:19:46 UTC
Created attachment 369 [details]
Code to reproduce problem

The Documentation states that mixing sparse and dense matrices
in addition and substraction is supported, but this does not compile.
Comment 1 Christoph Hertzberg 2014-03-14 13:06:55 UTC
Sorry for not having reacted to this report yet.

I can confirm your bug, also for any other combinations of dense sparse additions and subtractions.

A workaround is to use += or -= operators:

  M1 = S1 - M2;        // does not work at the moment
  M1 = -M2; M1 += S1;  // workaround

I'm marking this as blocking 3.3 and I increased the importance, since it contradicts the documentation:
http://eigen.tuxfamily.org/dox-devel/group__TutorialSparse.html#TutorialSparseFeatureSet
Comment 2 Gael Guennebaud 2014-03-14 13:32:31 UTC
Implementing this feature properly requires evaluators to proceed as the workaround, but transparently for the user.
Comment 3 Jitse Niesen 2014-04-07 15:17:29 UTC
I changed the documentation for 3.2 to note this (changeset 890ef3f93085). I did not change the docs for the dev branch because we will change it (so if we do not, we should transplant the changeset).
Comment 4 Christoph Hertzberg 2014-06-25 22:24:10 UTC
*** Bug 832 has been marked as a duplicate of this bug. ***
Comment 5 Christoph Hertzberg 2014-06-25 22:27:43 UTC
I changed the summary, to make this easier to find.
Most likely this won't be fixed before bug 99. Until then you must use the work-around.
Comment 6 Gael Guennebaud 2016-01-29 11:55:09 UTC
btw, another workaround is:

M1 = S1 - M2.sparseView();

See also:

https://forum.kde.org/viewtopic.php?f=74&t=130758

We should bench to see which approach really works best.
Comment 7 Gael Guennebaud 2016-01-29 13:06:38 UTC
As expected, the "M1 = -M2; M1 += S1;" way is clearly faster but not that much, I observed a factor of about x1.5.
Comment 8 Gael Guennebaud 2016-01-29 21:11:58 UTC
Done using the SparseView approach, which is much simpler to implement:

https://bitbucket.org/eigen/eigen/commits/cfac973b6dd6/
Summary:     Bug 632: add support for "dense +/- sparse" operations. The current implementation is based on SparseView to make the dense subexpression compatible with the sparse one.


Next step is optimizing common use cases at the assignment level.
Comment 9 Gael Guennebaud 2016-01-30 13:59:30 UTC
For the record, the implementation is not based on SparseView anymore:

https://bitbucket.org/eigen/eigen/commits/9bb69b315472/
Summary:     Bug 632: implement general coefficient-wise "dense op sparse" operations through specialized evaluators instead of using SparseView.
This permits to deal with arbitrary storage order, and to by-pass the more complex iterator of the sparse-sparse case.

Note You need to log in before you can comment on or make changes to this bug.