This bugzilla service is closed. All entries have been migrated to https://gitlab.com/libeigen/eigen
Bug 632 - Optimize addition/subtraction of sparse and dense matrices/vectors
Summary: Optimize addition/subtraction of sparse and dense matrices/vectors
Status: RESOLVED FIXED
Alias: None
Product: Eigen
Classification: Unclassified
Component: Sparse (show other bugs)
Version: 3.4 (development)
Hardware: All All
: Low Optimization
Assignee: Nobody
URL:
Whiteboard:
Keywords:
: 832 (view as bug list)
Depends on:
Blocks: 3.4
  Show dependency treegraph
 
Reported: 2013-07-19 11:19 UTC by Alexander Werner
Modified: 2019-12-04 12:30 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.
Comment 10 Gael Guennebaud 2018-10-10 20:52:31 UTC
I've just implemented the respective rewriting rules for common cases:

https://bitbucket.org/eigen/eigen/commits/c6447b6d24bb
Comment 11 Nobody 2019-12-04 12:30:22 UTC
-- GitLab Migration Automatic Message --

This bug has been migrated to gitlab.com's GitLab instance and has been closed from further activity.

You can subscribe and participate further through the new bug through this link to our GitLab instance: https://gitlab.com/libeigen/eigen/issues/632.

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