How do I evaluate the Jacobian for a solved problem?
How do I choose the right linear solver?
When using the
TRUST_REGIONminimizer, the choice of linear solver is an important decision. It affects solution quality and runtime. Here is a simple way to reason about it.
For small (a few hundred parameters) or dense problems use
For general sparse problems (i.e., the Jacobian matrix has a substantial number of zeros) use
SPARSE_NORMAL_CHOLESKY. This requires that you have
For bundle adjustment problems with up to a hundred or so cameras, use
For larger bundle adjustment problems with sparse Schur Complement/Reduced camera matrices use
SPARSE_SCHUR. This requires that you build Ceres with support for
CXSparseor Eigen’s sparse linear algebra libraries.
If you do not have access to these libraries for whatever reason,
SCHUR_JACOBIis an excellent alternative.
For large bundle adjustment problems (a few thousand cameras or more) use the
ITERATIVE_SCHURsolver. There are a number of preconditioner choices here.
SCHUR_JACOBIoffers an excellent balance of speed and accuracy. This is also the recommended option if you are solving medium sized problems for which
DENSE_SCHURis too slow but
SuiteSparseis not available.
If you are solving small to medium sized problems, consider setting
true, it can result in a substantial performance boost.
If you are not satisfied with
SCHUR_JACOBI‘s performance try
CLUSTER_TRIDIAGONALin that order. They require that you have
SuiteSparseinstalled. Both of these preconditioners use a clustering algorithm. Use
Solver::Summary::FullReport()to diagnose performance problems.
When diagnosing Ceres performance issues - runtime and convergence, the first place to start is by looking at the output of
Solver::Summary::FullReport. Here is an example
./bin/bundle_adjuster --input ../data/problem-16-22106-pre.txt iter cost cost_change |gradient| |step| tr_ratio tr_radius ls_iter iter_time total_time 0 4.185660e+06 0.00e+00 2.16e+07 0.00e+00 0.00e+00 1.00e+04 0 7.50e-02 3.58e-01 1 1.980525e+05 3.99e+06 5.34e+06 2.40e+03 9.60e-01 3.00e+04 1 1.84e-01 5.42e-01 2 5.086543e+04 1.47e+05 2.11e+06 1.01e+03 8.22e-01 4.09e+04 1 1.53e-01 6.95e-01 3 1.859667e+04 3.23e+04 2.87e+05 2.64e+02 9.85e-01 1.23e+05 1 1.71e-01 8.66e-01 4 1.803857e+04 5.58e+02 2.69e+04 8.66e+01 9.93e-01 3.69e+05 1 1.61e-01 1.03e+00 5 1.803391e+04 4.66e+00 3.11e+02 1.02e+01 1.00e+00 1.11e+06 1 1.49e-01 1.18e+00 Ceres Solver v1.12.0 Solve Report ---------------------------------- Original Reduced Parameter blocks 22122 22122 Parameters 66462 66462 Residual blocks 83718 83718 Residual 167436 167436 Minimizer TRUST_REGION Sparse linear algebra library SUITE_SPARSE Trust region strategy LEVENBERG_MARQUARDT Given Used Linear solver SPARSE_SCHUR SPARSE_SCHUR Threads 1 1 Linear solver threads 1 1 Linear solver ordering AUTOMATIC 22106, 16 Cost: Initial 4.185660e+06 Final 1.803391e+04 Change 4.167626e+06 Minimizer iterations 5 Successful steps 5 Unsuccessful steps 0 Time (in seconds): Preprocessor 0.283 Residual evaluation 0.061 Jacobian evaluation 0.361 Linear solver 0.382 Minimizer 0.895 Postprocessor 0.002 Total 1.220 Termination: NO_CONVERGENCE (Maximum number of iterations reached.)
Let us focus on run-time performance. The relevant lines to look at areTime (in seconds): Preprocessor 0.283 Residual evaluation 0.061 Jacobian evaluation 0.361 Linear solver 0.382 Minimizer 0.895 Postprocessor 0.002 Total 1.220
Which tell us that of the total 1.2 seconds, about .3 seconds was spent in the linear solver and the rest was mostly spent in preprocessing and jacobian evaluation.
The preprocessing seems particularly expensive. Looking back at the report, we observeLinear solver ordering AUTOMATIC 22106, 16
Which indicates that we are using automatic ordering for the
SPARSE_SCHURsolver. This can be expensive at times. A straight forward way to deal with this is to give the ordering manually. For
bundle_adjusterthis can be done by passing the flag
-ordering=user. Doing so and looking at the timing block of the full report gives usTime (in seconds): Preprocessor 0.051 Residual evaluation 0.053 Jacobian evaluation 0.344 Linear solver 0.372 Minimizer 0.854 Postprocessor 0.002 Total 0.935
The preprocessor time has gone down by more than 5.5x!.