Google Git
Sign in
ceres-solver / ceres-solver / 9364e31ee8dacbdd2c1689c4f74c291c5d7000f0
commit9364e31ee8dacbdd2c1689c4f74c291c5d7000f0[log] [tgz]
authorSameer Agarwal <sameeragarwal@google.com>Mon Oct 31 15:01:26 2022 -0700
committerSameer Agarwal <sameeragarwal@google.com>Mon Oct 31 15:03:37 2022 -0700
treee633f8d7dec916c96c2890afa1b94503d3b2c419
parent89b3e1f88fe548fba30759d88f5389b784165470 [diff]
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
1 file changed
tree: e633f8d7dec916c96c2890afa1b94503d3b2c419
  1. .github/
  2. bazel/
  3. cmake/
  4. config/
  5. data/
  6. docs/
  7. examples/
  8. include/
  9. internal/
  10. scripts/
  11. .clang-format
  12. .gitignore
  13. BUILD
  14. CITATION.cff
  15. CMakeLists.txt
  16. CONTRIBUTING.md
  17. LICENSE
  18. package.xml
  19. README.md
  20. WORKSPACE
README.md

Android Linux macOS Windows

Ceres Solver

Ceres Solver is an open source C++ library for modeling and solving large, complicated optimization problems. It is a feature rich, mature and performant library which has been used in production at Google since 2010. Ceres Solver can solve two kinds of problems.

  1. Non-linear Least Squares problems with bounds constraints.
  2. General unconstrained optimization problems.

Please see ceres-solver.org for more information.