commit | 39ec5e8f99c595226ab3cd760d4945e61c31fc57 | [log] [tgz] |
---|---|---|
author | Sameer Agarwal <sameeragarwal@google.com> | Sat May 14 08:05:49 2022 -0700 |
committer | Sameer Agarwal <sameeragarwal@google.com> | Thu May 19 12:36:20 2022 -0700 |
tree | 26193762df54e1dfeba76a5712af2b664409f8db | |
parent | aa62dd86a8cd978cd75245a711ef3bbdd0defb15 [diff] |
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 or SPARSE_SCHUR. 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 https://lucacarlone.mit.edu/datasets/ 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 used. This patch is based on the original work done by NeroBurner in https://ceres-solver-review.googlesource.com/c/ceres-solver/+/20580 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 reorder_program.cc and trust_region_processor.cc to use nested dissection. 4. Update bundle_adjuster.cc to use nested dissection. Change-Id: I388b027934f86c58b4da2b65a4fa5204ea73bf40
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.
Please see ceres-solver.org for more information.