Rename tricks.rst to faq.rst. Reorganize into sections and add some advice on linear solvers. Change-Id: Ia2d8665720c64b17da67f466f2fc154efb2b6c50
diff --git a/docs/source/tricks.rst b/docs/source/faqs.rst similarity index 73% rename from docs/source/tricks.rst rename to docs/source/faqs.rst index 32d0499..08ec0e5 100644 --- a/docs/source/tricks.rst +++ b/docs/source/faqs.rst
@@ -1,13 +1,43 @@ .. _chapter-tricks: =================== -Tips, Tricks & FAQs +FAQS, Tips & Tricks =================== -A collection of miscellanous tips, tricks and answers to frequently -asked questions. +Answers to frequently asked questions, tricks of the trade and general +wisdom. -1. Use analytical/automatic derivatives when possible. +Building +======== + +#. Use `google-glog <http://code.google.com/p/google-glog>`_. + + Ceres has extensive support for logging detailed information about + memory allocations and time consumed in various parts of the solve, + internal error conditions etc. This is done logging using the + `google-glog <http://code.google.com/p/google-glog>`_ library. We + use it extensively to observe and analyze Ceres's + performance. `google-glog <http://code.google.com/p/google-glog>`_ + allows you to control its behaviour from the command line `flags + <http://google-glog.googlecode.com/svn/trunk/doc/glog.html>`_. Starting + with ``-logtostdterr`` you can add ``-v=N`` for increasing values + of ``N`` to get more and more verbose and detailed information + about Ceres internals. + + In an attempt to reduce dependencies, it is tempting to use + `miniglog` - a minimal implementation of the ``glog`` interface + that ships with Ceres. This is a bad idea. ``miniglog`` was written + primarily for building and using Ceres on Android because the + current version of `google-glog + <http://code.google.com/p/google-glog>`_ does not build using the + NDK. It has worse performance than the full fledged glog library + and is much harder to control and use. + + +Modeling +======== + +#. Use analytical/automatic derivatives. This is the single most important piece of advice we can give to you. It is tempting to take the easy way out and use numeric @@ -36,32 +66,100 @@ automatic and numeric differentiation. See :class:`NumericDiffFunctor` and :class:`CostFunctionToFunctor`. +#. Putting `Inverse Function Theorem + <http://en.wikipedia.org/wiki/Inverse_function_theorem>`_ to use. -2. Use `google-glog <http://code.google.com/p/google-glog>`_. + Every now and then we have to deal with functions which cannot be + evaluated analytically. Computing the Jacobian in such cases is + tricky. A particularly interesting case is where the inverse of the + function is easy to compute analytically. An example of such a + function is the Coordinate transformation between the `ECEF + <http://en.wikipedia.org/wiki/ECEF>`_ and the `WGS84 + <http://en.wikipedia.org/wiki/World_Geodetic_System>`_ where the + conversion from WGS84 to ECEF is analytic, but the conversion back + to ECEF uses an iterative algorithm. So how do you compute the + derivative of the ECEF to WGS84 transformation? - Ceres has extensive support for logging various stages of the - solve. This includes detailed information about memory allocations - and time consumed in various parts of the solve, internal error - conditions etc. This logging structure is built on top of the - `google-glog <http://code.google.com/p/google-glog>`_ library and - can easily be controlled from the command line. + One obvious approach would be to numerically + differentiate the conversion function. This is not a good idea. For + one, it will be slow, but it will also be numerically quite + bad. - We use it extensively to observe and analyze Ceres's - performance. Starting with ``-logtostdterr`` you can add ``-v=N`` - for increasing values of N to get more and more verbose and - detailed information about Ceres internals. + Turns out you can use the `Inverse Function Theorem + <http://en.wikipedia.org/wiki/Inverse_function_theorem>`_ in this + case to compute the derivatives more or less analytically. - Building Ceres like this introduces an external dependency, and it - is tempting instead to use the `miniglog` implementation that ships - inside Ceres instead. This is a bad idea. + The key result here is. If :math:`x = f^{-1}(y)`, and :math:`Df(x)` + is the invertible Jacobian of :math:`f` at :math:`x`. Then the + Jacobian :math:`Df^{-1}(y) = [Df(x)]^{-1}`, i.e., the Jacobian of + the :math:`f^{-1}` is the inverse of the Jacobian of :math:`f`. - ``miniglog`` was written primarily for building and using Ceres on - Android because the current version of `google-glog - <http://code.google.com/p/google-glog>`_ does not build using the - NDK. It has worse performance than the full fledged glog library - and is much harder to control and use. + Algorithmically this means that given :math:`y`, compute :math:`x = + f^{-1}(y)` by whatever means you can. Evaluate the Jacobian of + :math:`f` at :math:`x`. If the Jacobian matrix is invertible, then + the inverse is the Jacobian of the inverse at :math:`y`. -3. `Solver::Summary::FullReport` is your friend. + One can put this into practice with the following code fragment. + + .. code-block:: c++ + + Eigen::Vector3d ecef; // Fill some values + // Iterative computation. + Eigen::Vector3d lla = ECEFToLLA(ecef); + // Analytic derivatives + Eigen::Matrix3d lla_to_ecef_jacobian = LLAToECEFJacobian(lla); + bool invertible; + Eigen::Matrix3d ecef_to_lla_jacobian; + lla_to_ecef_jacobian.computeInverseWithCheck(ecef_to_lla_jacobian, invertible); + +#. When using Quaternions, use :class:`QuaternionParameterization`. + + TBD + +#. How to choose a parameter block size? + + TBD + +Solving +======= + +#. Choosing a 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 have ``SuiteSparse`` or ``CXSparse`` + installed. + + 5. For large bundle adjustment problems (a few thousand cameras or + more) use the ``ITERATIVE_SCHUR`` solver. There are a number of + preconditioners 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. + + 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 `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 @@ -169,50 +267,3 @@ Total 0.998 The preprocessor time has gone down by more than 4x!. - - -4. Putting `Inverse Function Theorem - <http://en.wikipedia.org/wiki/Inverse_function_theorem>`_ to use. - - Every now and then we have to deal with functions which cannot be - evaluated analytically. Computing the Jacobian in such cases is - tricky. A particularly interesting case is where the inverse of the - function is easy to compute analytically. An example of such a - function is the Coordinate transformation between the `ECEF - <http://en.wikipedia.org/wiki/ECEF>`_ and the `WGS84 - <http://en.wikipedia.org/wiki/World_Geodetic_System>`_ where the - conversion from WGS84 to ECEF is analytic, but the conversion back - to ECEF uses an iterative algorithm. So how do you compute the - derivative of the ECEF to WGS84 transformation? - - One obvious approach would be to numerically - differentiate the conversion function. This is not a good idea. For - one, it will be slow, but it will also be numerically quite - bad. - - Turns out you can use the `Inverse Function Theorem - <http://en.wikipedia.org/wiki/Inverse_function_theorem>`_ in this - case to compute the derivatives more or less analytically. - - The key result here is. If :math:`x = f^{-1}(y)`, and :math:`Df(x)` - is the invertible Jacobian of :math:`f` at :math:`x`. Then the - Jacobian :math:`Df^{-1}(y) = [Df(x)]^{-1}`, i.e., the Jacobian of - the :math:`f^{-1}` is the inverse of the Jacobian of :math:`f`. - - Algorithmically this means that given :math:`y`, compute :math:`x = - f^{-1}(y)` by whatever means you can. Evaluate the Jacobian of - :math:`f` at :math:`x`. If the Jacobian matrix is invertible, then - the inverse is the Jacobian of the inverse at :math:`y`. - - One can put this into practice with the following code fragment. - - .. code-block:: c++ - - Eigen::Vector3d ecef; // Fill some values - // Iterative computation. - Eigen::Vector3d lla = ECEFToLLA(ecef); - // Analytic derivatives - Eigen::Matrix3d lla_to_ecef_jacobian = LLAToECEFJacobian(lla); - bool invertible; - Eigen::Matrix3d ecef_to_lla_jacobian; - lla_to_ecef_jacobian.computeInverseWithCheck(ecef_to_lla_jacobian, invertible);
diff --git a/docs/source/index.rst b/docs/source/index.rst index 74ce20b..62d4c0b 100644 --- a/docs/source/index.rst +++ b/docs/source/index.rst
@@ -43,7 +43,7 @@ tutorial modeling solving - tricks + faqs reading contributing acknowledgements