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
diff --git a/examples/bundle_adjuster.cc b/examples/bundle_adjuster.cc
index d03c2ff..87e18e1 100644
--- a/examples/bundle_adjuster.cc
+++ b/examples/bundle_adjuster.cc
@@ -95,7 +95,7 @@
"Options are: suite_sparse and cx_sparse.");
DEFINE_string(dense_linear_algebra_library, "eigen",
"Options are: eigen, lapack, and cuda");
-DEFINE_string(ordering, "automatic", "Options are: automatic, user.");
+DEFINE_string(ordering, "amd", "Options are: amd, nesdis and user");
DEFINE_bool(use_quaternions, false, "If true, uses quaternions to represent "
"rotations. If false, angle axis is used.");
@@ -128,7 +128,6 @@
DEFINE_string(initial_ply, "", "Export the BAL file data as a PLY file.");
DEFINE_string(final_ply, "", "Export the refined BAL file data as a PLY "
"file.");
-
// clang-format on
namespace ceres::examples {
@@ -228,24 +227,30 @@
// the right ParameterBlock ordering, or by manually specifying a
// suitable ordering vector and defining
// Options::num_eliminate_blocks.
- if (CERES_GET_FLAG(FLAGS_ordering) == "automatic") {
- return;
+ if (CERES_GET_FLAG(FLAGS_ordering) == "user") {
+ auto* ordering = new ceres::ParameterBlockOrdering;
+
+ // The points come before the cameras.
+ for (int i = 0; i < num_points; ++i) {
+ ordering->AddElementToGroup(points + point_block_size * i, 0);
+ }
+
+ for (int i = 0; i < num_cameras; ++i) {
+ // When using axis-angle, there is a single parameter block for
+ // the entire camera.
+ ordering->AddElementToGroup(cameras + camera_block_size * i, 1);
+ }
+
+ options->linear_solver_ordering.reset(ordering);
+ } else {
+ if (CERES_GET_FLAG(FLAGS_ordering) == "amd") {
+ options->linear_solver_ordering_type = AMD;
+ } else if (CERES_GET_FLAG(FLAGS_ordering) == "nesdis") {
+ options->linear_solver_ordering_type = NESDIS;
+ } else {
+ LOG(FATAL) << "Unknown ordering type: " << CERES_GET_FLAG(FLAGS_ordering);
+ }
}
-
- auto* ordering = new ceres::ParameterBlockOrdering;
-
- // The points come before the cameras.
- for (int i = 0; i < num_points; ++i) {
- ordering->AddElementToGroup(points + point_block_size * i, 0);
- }
-
- for (int i = 0; i < num_cameras; ++i) {
- // When using axis-angle, there is a single parameter block for
- // the entire camera.
- ordering->AddElementToGroup(cameras + camera_block_size * i, 1);
- }
-
- options->linear_solver_ordering.reset(ordering);
}
void SetMinimizerOptions(Solver::Options* options) {
