.. _chapter-solving_faqs:
.. default-domain:: cpp
.. cpp:namespace:: ceres
=======
Solving
=======
#. How do I evaluate the Jacobian for a solved problem?
Using :func:`Problem::Evaluate`.
#. How do I choose the right linear solver?
When using the ``TRUST_REGION`` minimizer, the choice of linear
solver is an important decision. It affects solution quality and
runtime. Here is a simple way to reason about it.
1. For small (a few hundred parameters) or dense problems use
``DENSE_QR``.
2. For general sparse problems (i.e., the Jacobian matrix has a
substantial number of zeros) use
``SPARSE_NORMAL_CHOLESKY``. This requires that you have
``SuiteSparse`` or ``CXSparse`` installed.
3. For bundle adjustment problems with up to a hundred or so
cameras, use ``DENSE_SCHUR``.
4. For larger bundle adjustment problems with sparse Schur
Complement/Reduced camera matrices use ``SPARSE_SCHUR``. This
requires that you build Ceres with support for ``SuiteSparse``,
``CXSparse`` or Eigen's sparse linear algebra libraries.
If you do not have access to these libraries for whatever
reason, ``ITERATIVE_SCHUR`` with ``SCHUR_JACOBI`` is an
excellent alternative.
5. For large bundle adjustment problems (a few thousand cameras or
more) use the ``ITERATIVE_SCHUR`` solver. There are a number of
preconditioner choices here. ``SCHUR_JACOBI`` offers an
excellent balance of speed and accuracy. This is also the
recommended option if you are solving medium sized problems for
which ``DENSE_SCHUR`` is too slow but ``SuiteSparse`` is not
available.
.. NOTE::
If you are solving small to medium sized problems, consider
setting ``Solver::Options::use_explicit_schur_complement`` to
``true``, it can result in a substantial performance boost.
If you are not satisfied with ``SCHUR_JACOBI``'s performance try
``CLUSTER_JACOBI`` and ``CLUSTER_TRIDIAGONAL`` in that
order. They require that you have ``SuiteSparse``
installed. Both of these preconditioners use a clustering
algorithm. Use ``SINGLE_LINKAGE`` before ``CANONICAL_VIEWS``.
#. Use :func:`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
.. code-block:: bash
./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
are
.. code-block:: bash
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
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 observe
.. code-block:: bash
Linear solver ordering AUTOMATIC 22106, 16
Which indicates that we are using automatic ordering for the
``SPARSE_SCHUR`` solver. This can be expensive at times. A straight
forward way to deal with this is to give the ordering manually. For
``bundle_adjuster`` this can be done by passing the flag
``-ordering=user``. Doing so and looking at the timing block of the
full report gives us
.. code-block:: bash
Time (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!.