tree 26193762df54e1dfeba76a5712af2b664409f8db
parent aa62dd86a8cd978cd75245a711ef3bbdd0defb15
author Sameer Agarwal <sameeragarwal@google.com> 1652540749 -0700
committer Sameer Agarwal <sameeragarwal@google.com> 1652988980 -0700

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