| .. _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!. |
