|Summary:||Optimize addition/subtraction of sparse and dense matrices/vectors|
|Product:||Eigen||Reporter:||Alexander Werner <alexander.werner>|
|Severity:||Optimization||CC:||chtz, gael.guennebaud, jitseniesen, v_trifonov|
|Bug Depends on:|
Description Alexander Werner 2013-07-19 11:19:46 UTC
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.