Squashed 'third_party/ceres/' content from commit e51e9b4
Change-Id: I763587619d57e594d3fa158dc3a7fe0b89a1743b
git-subtree-dir: third_party/ceres
git-subtree-split: e51e9b46f6ca88ab8b2266d0e362771db6d98067
diff --git a/docs/source/solving_faqs.rst b/docs/source/solving_faqs.rst
new file mode 100644
index 0000000..64604c4
--- /dev/null
+++ b/docs/source/solving_faqs.rst
@@ -0,0 +1,171 @@
+.. _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!.