New user self-registration is disabled due to spam. Please email eigen-core-team @ lists.tuxfamily.org if you need an account.
Before reporting a bug, please make sure that your Eigen version is up-to-date!
Bug 1194 - Improve det4x4
Summary: Improve det4x4
Status: RESOLVED FIXED
Alias: None
Product: Eigen
Classification: Unclassified
Component: LU (show other bugs)
Version: 3.3 (current stable)
Hardware: All All
: Normal Optimization
Assignee: Nobody
URL:
Whiteboard:
Keywords:
Depends on:
Blocks: 3.4
  Show dependency treegraph
 
Reported: 2016-04-08 11:33 UTC by Marc Glisse
Modified: 2019-02-18 15:24 UTC (History)
2 users (show)



Attachments

Description Marc Glisse 2016-04-08 11:33:41 UTC
Hello,

in LU/Determinant.h, one can read

    // trick by Martin Costabel to compute 4x4 det with only 30 muls

If I compare with another project (CGAL/determinant.h), they have only 28 muls (and the same number of add+sub). The license is not compatible so I won't copy the code here, but they are using a simple algorithm: develop with respect to the last column, recursively, and notice the common sub-expressions. In other words
* compute the 6 2x2 subdeterminants of the first 2 columns (2 muls each)
* compute the 4 3x3 subdeterminants of the first 3 columns (3 muls each)
* conclude (4 muls)

(the same strategy is still profitable for dimension 5 IIRC)
Comment 1 Gael Guennebaud 2019-02-18 15:24:35 UTC
ok, done:

https://bitbucket.org/eigen/eigen/commits/e7fb55b0b186/

The new version is better vectorized by clang. GCC does not vectorize any of them.

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