Add Nested Dissection based fill reducing ordering

With this change, the user can now choose between Approximate Minimum
Degree and Nested Dissection as a fill reducing algorithm when using
a sparse direct factorization based linear solver like SPARSE_NORMAL_CHOLESKY

Currenly only SUITE_SPARSE is supported. It requires that
SuiteSparse be compiled with Metis support enabled.

On most problems AMD is still the better choice, but in some cases
like the grid3D dataset from
the solution time with AMD is 57s and with NESDIS 38 on my M1 Mac.

On some other problems at Google we have observed speedups of 10x,
there is also a corresponding decrease in the total amount of memory

This patch is based on the original work done by NeroBurner in

1. Add a new enum to the public api LinearSolverOrderingType and
   a setting Solver::Options::linear_solver_ordering_type.
2. TrustRegionPreprocessor had some complicated logic which determined
   when linear solvers should reorder their matrices on their own and not
   this has been refactored into a more readable function that lives
   inside reorder_program.h/cc.
3. Plumbing in and to use
   nested dissection.
4. Update to use nested dissection.

Change-Id: I388b027934f86c58b4da2b65a4fa5204ea73bf40
10 files changed
tree: 26193762df54e1dfeba76a5712af2b664409f8db
  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
  18. package.xml

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 for more information.