This bugzilla service is closed. All entries have been migrated to
Bug 1194 - Improve det4x4
Summary: Improve det4x4
Alias: None
Product: Eigen
Classification: Unclassified
Component: LU (show other bugs)
Version: 3.3 (current stable)
Hardware: All All
: Normal Optimization
Assignee: Nobody
Depends on:
Blocks: 3.4
  Show dependency treegraph
Reported: 2016-04-08 11:33 UTC by Marc Glisse
Modified: 2019-12-04 15:37 UTC (History)
2 users (show)


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

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:

The new version is better vectorized by clang. GCC does not vectorize any of them.
Comment 2 Nobody 2019-12-04 15:37:52 UTC
-- GitLab Migration Automatic Message --

This bug has been migrated to'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:

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