Fix a regression in SuiteSparse::AnalyzeCholesky
When AnalyzeCholesky is called on a Jacobian which has been
pre-ordered in the preprocessor, we assume a NATURAL ordering.
In this case, asking CHOLMOD to do a postordering is detrimental
to the performance. This regression was introduced in
https://github.com/ceres-solver/ceres-solver/commit/d09f7e9d5e3bfab2d7ec7e81fd6a55786edca17a
based on an email exchange with Prof. Tim Davis the author of CHOLMOD
who suggested that this should be innocous. Unfortunately this is not
the case. The following table shows the performance of bundle_adjuster
on a variety of problems. This matches the performance of the
bundle adjuster before the CL that introduced the regression.
Before After
problem-49-7776-pre.txt
SPARSE_NORMAL_CHOLESKY + AMD 0.8 0.6
SPARSE_NORMAL_CHOLESKY + NESDIS 0.8 0.6
SPARSE_SCHUR + AMD 0.1 0.1
SPARSE_SCHUR + NESDIS 0.1 0.1
problem-1778-993923-pre.txt
SPARSE_NORMAL_CHOLESKY + AMD 247.1 197.0
SPARSE_NORMAL_CHOLESKY + NESDIS 234.0 193.2
SPARSE_SCHUR + AMD 78.7 71.8
SPARSE_SCHUR + NESDIS 78.7 71.4
problem-1031-110968-pre.txt
SPARSE_NORMAL_CHOLESKY + AMD 26.1 22.4
SPARSE_NORMAL_CHOLESKY + NESDIS 26.0 23.0
SPARSE_SCHUR + AMD 14.9 13.1
SPARSE_SCHUR + NESDIS 14.9 13.1
problem-356-226730-pre.txt
SPARSE_NORMAL_CHOLESKY + AMD 43.9 34.7
SPARSE_NORMAL_CHOLESKY + NESDIS 42.5 34.8
SPARSE_SCHUR + AMD 6.8 6.1
SPARSE_SCHUR + NESDIS 6.8 6.1
problem-951-708276-pre.txt
SPARSE_NORMAL_CHOLESKY + AMD 170.3 139.0
SPARSE_NORMAL_CHOLESKY + NESDIS 168.9 139.8
SPARSE_SCHUR + AMD 52.3 47.9
SPARSE_SCHUR + NESDIS 52.0 47.7
Change-Id: I6421060dd835ab2fc81d270238f6f67e29f3ecd5
diff --git a/internal/ceres/suitesparse.cc b/internal/ceres/suitesparse.cc
index e108ec6..189a24f 100644
--- a/internal/ceres/suitesparse.cc
+++ b/internal/ceres/suitesparse.cc
@@ -165,6 +165,13 @@
std::string* message) {
cc_.nmethods = 1;
cc_.method[0].ordering = OrderingTypeToCHOLMODEnum(ordering_type);
+
+ // postordering with a NATURAL ordering leads to a significant regression in
+ // performance. See https://github.com/ceres-solver/ceres-solver/issues/905
+ if (ordering_type == OrderingType::NATURAL) {
+ cc_.postorder = 0;
+ }
+
cholmod_factor* factor = cholmod_analyze(A, &cc_);
if (cc_.status != CHOLMOD_OK) {
