Minor changes to the documentation. 1. Section title changes. 2. Moving the glog discussion into installation.rst 3. Re-working the faqs into two separate chapters. Change-Id: I95dd25bace50f0f9077ef114504999190686963e
diff --git a/docs/source/api.rst b/docs/source/api.rst deleted file mode 100644 index 051f6e7..0000000 --- a/docs/source/api.rst +++ /dev/null
@@ -1,12 +0,0 @@ -.. _chapter-api: - -============= -API Reference -============= - -.. toctree:: - :maxdepth: 3 - - nnls_modeling - nnls_solving - gradient_solver
diff --git a/docs/source/conf.py b/docs/source/conf.py index 86e00f1..59a418e 100644 --- a/docs/source/conf.py +++ b/docs/source/conf.py
@@ -41,7 +41,7 @@ # General information about the project. project = u'Ceres Solver' -copyright = u'2015 Google Inc' +copyright = u'2016 Google Inc' # The version info for the project you're documenting, acts as replacement for # |version| and |release|, also used in various other places throughout the @@ -86,7 +86,6 @@ # A list of ignored prefixes for module index sorting. #modindex_common_prefix = [] - # -- Options for HTML output --------------------------------------------------- # The theme to use for HTML and HTML Help pages. See the documentation for
diff --git a/docs/source/faqs.rst b/docs/source/faqs.rst index 7513f44..5a28f41 100644 --- a/docs/source/faqs.rst +++ b/docs/source/faqs.rst
@@ -1,5 +1,9 @@ .. _chapter-tricks: +.. default-domain:: cpp + +.. cpp:namespace:: ceres + =================== FAQS, Tips & Tricks =================== @@ -7,324 +11,12 @@ Answers to frequently asked questions, tricks of the trade and general wisdom. -Building -======== +.. toctree:: + :maxdepth: 2 -#. 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 ``-logtostderr`` 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 - differentiation. This is a bad idea. Numeric differentiation is - slow, ill-behaved, hard to get right, and results in poor - convergence behaviour. - - Ceres allows the user to define templated functors which will - be automatically differentiated. For most situations this is enough - and we recommend using this facility. In some cases the derivatives - are simple enough or the performance considerations are such that - the overhead of automatic differentiation is too much. In such - cases, analytic derivatives are recommended. - - The use of numerical derivatives should be a measure of last - resort, where it is simply not possible to write a templated - implementation of the cost function. - - In many cases it is not possible to do analytic or automatic - differentiation of the entire cost function, but it is generally - the case that it is possible to decompose the cost function into - parts that need to be numerically differentiated and parts that can - be automatically or analytically differentiated. - - To this end, Ceres has extensive support for mixing analytic, - automatic and numeric differentiation. See - :class:`CostFunctionToFunctor`. - -#. When using Quaternions, consider using :class:`QuaternionParameterization`. - - `Quaternions <https://en.wikipedia.org/wiki/Quaternion>`_ are a - four dimensional parameterization of the space of three dimensional - rotations :math:`SO(3)`. However, the :math:`SO(3)` is a three - dimensional set, and so is the tangent space of a - Quaternion. Therefore, it is sometimes (not always) benefecial to - associate a local parameterization with parameter blocks - representing a Quaternion. Assuming that the order of entries in - your parameter block is :math:`w,x,y,z`, you can use - :class:`QuaternionParameterization`. - - If however, you are using `Eigen's Quaternion - <http://eigen.tuxfamily.org/dox/classEigen_1_1Quaternion.html>`_ - object, whose layout is :math:`x,y,z,w`, then we recommend you use - Lloyd Hughes's `Ceres Extensions - <https://github.com/system123/ceres_extensions>`_. - -#. How do I solve problems with general linear & non-linear - **inequality** constraints with Ceres Solver? - - Currently, Ceres Solver only supports upper and lower bounds - constraints on the parameter blocks. - - A crude way of dealing with inequality constraints is have one or - more of your cost functions check if the inequalities you are - interested in are satisfied, and if not return false instead of - true. This will prevent the solver from ever stepping into an - infeasible region. - - This requires that the starting point for the optimization be a - feasible point. You also risk pre-mature convergence using this - method. - -#. How do I solve problems with general linear & non-linear **equality** - constraints with Ceres Solver? - - There is no built in support in ceres for solving problems with - equality constraints. Currently, Ceres Solver only supports upper - and lower bounds constraints on the parameter blocks. - - The trick described above for dealing with inequality - constraints will **not** work for equality constraints. - -#. How do I set one or more components of a parameter block constant? - - Using :class:`SubsetParameterization`. - -#. 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 WGS84 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 - its inverse is the Jacobian of :math:`f^{-1}(y)` 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); - - -Solving -======= - -#. How do I evaluate the Jacobian for a solver problem? - - Using :func:`Problem::Evaluate`. - -#. 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 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 - - + modeling_faqs + solving_faqs - The preprocessor time has gone down by more than 5.5x!. Further Reading ===============
diff --git a/docs/source/features.rst b/docs/source/features.rst index 681876e..1f5e91e 100644 --- a/docs/source/features.rst +++ b/docs/source/features.rst
@@ -1,6 +1,6 @@ -======== -Features -======== +==== +Why? +==== .. _chapter-features: * **Code Quality** - Ceres Solver has been used in production at
diff --git a/docs/source/guide.rst b/docs/source/guide.rst new file mode 100644 index 0000000..bcf6bc8 --- /dev/null +++ b/docs/source/guide.rst
@@ -0,0 +1,12 @@ +.. _chapter-users-guide: + +============ +User's Guide +============ + +.. toctree:: + :maxdepth: 2 + + nnls_modeling + nnls_solving + gradient_solver
diff --git a/docs/source/index.rst b/docs/source/index.rst index f7f02ef..3851dd1 100644 --- a/docs/source/index.rst +++ b/docs/source/index.rst
@@ -1,20 +1,30 @@ -.. Ceres Solver documentation master file, created by - sphinx-quickstart on Sat Jan 19 00:07:33 2013. - You can adapt this file completely to your liking, but it should at least - contain the root `toctree` directive. - ============ Ceres Solver ============ +Ceres Solver [#f1]_ is an open source C++ library for modeling and +solving large, complicated optimization problems. It can be used to +solve `Non-linear Least Squares`_ problems with bounds constraints and +general unconstrained optimization problems. It is a mature, feature +rich, and performant library that has been used in production at +Google since 2010. For more, see :doc:`features`. + +`ceres-solver@googlegroups.com +<https://groups.google.com/forum/?fromgroups#!forum/ceres-solver>`_ is +the place for discussions and questions about Ceres Solver. We use the +`GitHub Issue Tracker +<https://github.com/ceres-solver/ceres-solver/issues>`_ to manage bug +reports and feature requests. + + .. toctree:: - :maxdepth: 3 + :maxdepth: 1 :hidden: - features - building + installation tutorial - api + guide + features faqs users contributing @@ -22,34 +32,8 @@ bibliography license -Ceres Solver [#f1]_ is an open source C++ library for modeling and -solving large, complicated optimization problems. It is a feature -rich, mature and performant library which has been used in production -at Google since 2010. Ceres Solver can solve two kinds of problems. - -1. `Non-linear Least Squares`_ problems with bounds constraints. -2. General unconstrained optimization problems. - .. _Non-linear Least Squares: http://en.wikipedia.org/wiki/Non-linear_least_squares -Getting started -=============== - -* Download the `latest stable release - <http://ceres-solver.org/ceres-solver-1.12.0.tar.gz>`_ or clone the - Git repository for the latest development version. - - .. code-block:: bash - - git clone https://ceres-solver.googlesource.com/ceres-solver - -* Read the :ref:`chapter-tutorial` and browse the :ref:`chapter-api`. -* Join the `mailing list - <https://groups.google.com/forum/?fromgroups#!forum/ceres-solver>`_ - and ask questions. -* File bugs, feature requests on `GitHub - <https://github.com/ceres-solver/ceres-solver/issues>`_. - Cite Us =======
diff --git a/docs/source/building.rst b/docs/source/installation.rst similarity index 61% rename from docs/source/building.rst rename to docs/source/installation.rst index 37a3942..ddda50f 100644 --- a/docs/source/building.rst +++ b/docs/source/installation.rst
@@ -1,8 +1,8 @@ -.. _chapter-building: +.. _chapter-installation: -======================= -Building & Installation -======================= +============ +Installation +============ Getting the source code ======================= @@ -37,30 +37,41 @@ - `CMake <http://www.cmake.org>`_ 2.8.0 or later. **Required on all platforms except for Android.** -- `Google Log <http://code.google.com/p/google-glog>`_ 0.3.1 or +- `glog <https://github.com/google/glog>`_ 0.3.1 or later. **Recommended** - .. NOTE:: + ``glog`` is used extensively throughout Ceres for logging detailed + information about memory allocations and time consumed in various + parts of the solve, internal error conditions etc. The Ceres + developers use it extensively to observe and analyze Ceres's + performance. `glog <https://github.com/google/glog>`_ allows you to + control its behaviour from the command line. Starting with + ``-logtostderr`` you can add ``-v=N`` for increasing values of ``N`` + to get more and more verbose and detailed information about Ceres + internals. - Ceres has a minimal replacement of ``glog`` called ``miniglog`` - that can be enabled with the ``MINIGLOG`` build - option. ``miniglog`` is needed on Android as ``glog`` currently - does not build using the NDK. It can however be used on other - platforms too. + Unfortunately, the current version of `google-glog + <https://github.com/google/glog>`_ does not build using the Android + NDK. So, Ceres also ships with a minimal replacement of ``glog`` + called ``miniglog`` that can be enabled with the ``MINIGLOG`` build + option. - **We do not advise using** ``miniglog`` **on platforms other than - Android due to the various performance and functionality - compromises in** ``miniglog``. + So, in an attempt to reduce dependencies, it is tempting to use + `miniglog` on platforms other than Android. While there is nothing + preventing the user from doing so, we strongly recommend against + it. ``miniglog`` has worse performance than ``glog`` and is much + harder to control and use. .. NOTE :: - If you are compiling ``glog`` from source, please note that currently, - the unit tests for ``glog`` (which are enabled by default) do not compile - against a default build of ``gflags`` 2.1 as the gflags namespace changed - from ``google::`` to ``gflags::``. A patch to fix this is available from - `here <https://code.google.com/p/google-glog/issues/detail?id=194>`_. + If you are compiling ``glog`` from source, please note that + currently, the unit tests for ``glog`` (which are enabled by + default) do not compile against a default build of ``gflags`` 2.1 + as the gflags namespace changed from ``google::`` to + ``gflags::``. A patch to fix this is available from `here + <https://code.google.com/p/google-glog/issues/detail?id=194>`_. -- `Google Flags <http://code.google.com/p/gflags>`_. Needed to build +- `gflags <https://github.com/gflags/gflags>`_. Needed to build examples and tests. - `SuiteSparse @@ -110,8 +121,9 @@ package repository (built from SuiteSparse v3.4.0) **cannot** be used to build Ceres as a *shared* library. Thus if you want to build Ceres as a shared library using SuiteSparse, you must perform a - source install of SuiteSparse or use an external PPA (see - `bug report here <https://bugs.launchpad.net/ubuntu/+source/suitesparse/+bug/1333214>`_). + source install of SuiteSparse or use an external PPA (see `bug report + here + <https://bugs.launchpad.net/ubuntu/+source/suitesparse/+bug/1333214>`_). It is recommended that you use the current version of SuiteSparse (4.2.1 at the time of writing). @@ -333,15 +345,16 @@ are at least two possible fixes to this problem: #. Use ``google-glog`` and define ``GLOG_NO_ABBREVIATED_SEVERITIES`` - when building Ceres and your own project, as documented - `here <http://google-glog.googlecode.com/svn/trunk/doc/glog.html>`__. - Note that this fix will not work for ``miniglog``, - but use of ``miniglog`` is strongly discouraged on any platform for which + when building Ceres and your own project, as documented `here + <http://google-glog.googlecode.com/svn/trunk/doc/glog.html>`__. + Note that this fix will not work for ``miniglog``, but use of + ``miniglog`` is strongly discouraged on any platform for which ``google-glog`` is available (which includes Windows). - #. If you do not require GDI, then define ``NOGDI`` **before** including - windows.h. This solution should work for both ``google-glog`` and - ``miniglog`` and is documented for ``google-glog`` - `here <https://code.google.com/p/google-glog/issues/detail?id=33>`__. + #. If you do not require GDI, then define ``NOGDI`` **before** + including windows.h. This solution should work for both + ``google-glog`` and ``miniglog`` and is documented for + ``google-glog`` `here + <https://code.google.com/p/google-glog/issues/detail?id=33>`__. #. Make a toplevel directory for deps & build & src somewhere: ``ceres/`` #. Get dependencies; unpack them as subdirectories in ``ceres/`` @@ -353,17 +366,19 @@ #. ``google-glog`` Open up the Visual Studio solution and build it. #. ``gflags`` Open up the Visual Studio solution and build it. - #. (Experimental) ``SuiteSparse`` Previously SuiteSparse was not available - on Windows, recently it has become possible to build it on Windows using - the `suitesparse-metis-for-windows <https://github.com/jlblancoc/suitesparse-metis-for-windows>`_ - project. If you wish to use ``SuiteSparse``, follow their instructions - for obtaining and building it. + #. (Experimental) ``SuiteSparse`` Previously SuiteSparse was not + available on Windows, recently it has become possible to build + it on Windows using the `suitesparse-metis-for-windows + <https://github.com/jlblancoc/suitesparse-metis-for-windows>`_ + project. If you wish to use ``SuiteSparse``, follow their + instructions for obtaining and building it. - #. (Experimental) ``CXSparse`` Previously CXSparse was not available on - Windows, there are now several ports that enable it to be, including: - `[1] <https://github.com/PetterS/CXSparse>`_ and - `[2] <https://github.com/TheFrenchLeaf/CXSparse>`_. If you wish to use - ``CXSparse``, follow their instructions for obtaining and building it. + #. (Experimental) ``CXSparse`` Previously CXSparse was not + available on Windows, there are now several ports that enable it + to be, including: `[1] <https://github.com/PetterS/CXSparse>`_ + and `[2] <https://github.com/TheFrenchLeaf/CXSparse>`_. If you + wish to use ``CXSparse``, follow their instructions for + obtaining and building it. #. Unpack the Ceres tarball into ``ceres``. For the tarball, you should get a directory inside ``ceres`` similar to @@ -391,12 +406,13 @@ #. (Optional) ``CXSPARSE_INCLUDE_DIR_HINTS`` #. (Optional) ``CXSPARSE_LIBRARY_DIR_HINTS`` - to the appropriate directories where you unpacked/built them. If any of - the variables are not visible in the ``CMake`` GUI, create a new entry - for them. We recommend using the ``<NAME>_(INCLUDE/LIBRARY)_DIR_HINTS`` - variables rather than setting the ``<NAME>_INCLUDE_DIR`` & - ``<NAME>_LIBRARY`` variables directly to keep all of the validity - checking, and to avoid having to specify the library files manually. + to the appropriate directories where you unpacked/built them. If + any of the variables are not visible in the ``CMake`` GUI, create a + new entry for them. We recommend using the + ``<NAME>_(INCLUDE/LIBRARY)_DIR_HINTS`` variables rather than + setting the ``<NAME>_INCLUDE_DIR`` & ``<NAME>_LIBRARY`` variables + directly to keep all of the validity checking, and to avoid having + to specify the library files manually. #. You may have to tweak some more settings to generate a MSVC project. After each adjustment, try pressing Configure & Generate @@ -442,8 +458,9 @@ You need iOS version 7.0 or higher to build Ceres Solver. -To build Ceres for iOS, we need to force ``CMake`` to find the toolchains from -the iOS SDK instead of using the standard ones. For example: +To build Ceres for iOS, we need to force ``CMake`` to find the +toolchains from the iOS SDK instead of using the standard ones. For +example: .. code-block:: bash @@ -454,21 +471,24 @@ <PATH_TO_CERES_SOURCE> ``PLATFORM`` can be: ``OS``, ``SIMULATOR`` or ``SIMULATOR64``. You can -build for ``OS`` (``armv7``, ``armv7s``, ``arm64``), ``SIMULATOR`` (``i386``) or -``SIMULATOR64`` (``x86_64``) separately and use ``lipo`` to merge them into -one static library. See ``cmake/iOS.cmake`` for more options. +build for ``OS`` (``armv7``, ``armv7s``, ``arm64``), ``SIMULATOR`` +(``i386``) or ``SIMULATOR64`` (``x86_64``) separately and use ``lipo`` +to merge them into one static library. See ``cmake/iOS.cmake`` for +more options. -After building, you will get a ``libceres.a`` library, which you will need to -add to your Xcode project. +After building, you will get a ``libceres.a`` library, which you will +need to add to your Xcode project. The default CMake configuration builds a bare bones version of Ceres -Solver that only depends on Eigen (``MINIGLOG`` is compiled into Ceres if it is -used), this should be sufficient for solving small to moderate sized problems -(No ``SPARSE_SCHUR``, ``SPARSE_NORMAL_CHOLESKY`` linear solvers and no -``CLUSTER_JACOBI`` and ``CLUSTER_TRIDIAGONAL`` preconditioners). +Solver that only depends on Eigen (``MINIGLOG`` is compiled into Ceres +if it is used), this should be sufficient for solving small to +moderate sized problems (No ``SPARSE_SCHUR``, +``SPARSE_NORMAL_CHOLESKY`` linear solvers and no ``CLUSTER_JACOBI`` +and ``CLUSTER_TRIDIAGONAL`` preconditioners). -If you decide to use ``LAPACK`` and ``BLAS``, then you also need to add -``Accelerate.framework`` to your Xcode project's linking dependency. +If you decide to use ``LAPACK`` and ``BLAS``, then you also need to +add ``Accelerate.framework`` to your Xcode project's linking +dependency. .. _section-customizing: @@ -477,28 +497,30 @@ It is possible to reduce the libraries needed to build Ceres and customize the build process by setting the appropriate options in -``CMake``. These options can either be set in the ``CMake`` GUI, -or via ``-D<OPTION>=<ON/OFF>`` when running ``CMake`` from the -command line. In general, you should only modify these options from -their defaults if you know what you are doing. +``CMake``. These options can either be set in the ``CMake`` GUI, or +via ``-D<OPTION>=<ON/OFF>`` when running ``CMake`` from the command +line. In general, you should only modify these options from their +defaults if you know what you are doing. .. NOTE:: - If you are setting variables via ``-D<VARIABLE>=<VALUE>`` when calling - ``CMake``, it is important to understand that this forcibly **overwrites** the - variable ``<VARIABLE>`` in the ``CMake`` cache at the start of *every configure*. + If you are setting variables via ``-D<VARIABLE>=<VALUE>`` when + calling ``CMake``, it is important to understand that this forcibly + **overwrites** the variable ``<VARIABLE>`` in the ``CMake`` cache at + the start of *every configure*. - This can lead to confusion if you are invoking the ``CMake`` - `curses <http://www.gnu.org/software/ncurses/ncurses.html>`_ terminal GUI - (via ``ccmake``, e.g. ```ccmake -D<VARIABLE>=<VALUE> <PATH_TO_SRC>``). - In this case, even if you change the value of ``<VARIABLE>`` in the ``CMake`` - GUI, your changes will be **overwritten** with the value passed via - ``-D<VARIABLE>=<VALUE>`` (if one exists) at the start of each configure. + This can lead to confusion if you are invoking the ``CMake`` `curses + <http://www.gnu.org/software/ncurses/ncurses.html>`_ terminal GUI + (via ``ccmake``, e.g. ```ccmake -D<VARIABLE>=<VALUE> + <PATH_TO_SRC>``). In this case, even if you change the value of + ``<VARIABLE>`` in the ``CMake`` GUI, your changes will be + **overwritten** with the value passed via ``-D<VARIABLE>=<VALUE>`` + (if one exists) at the start of each configure. - As such, it is generally easier not to pass values to ``CMake`` via ``-D`` - and instead interactively experiment with their values in the ``CMake`` GUI. - If they are not present in the *Standard View*, toggle to the *Advanced View* - with ``<t>``. + As such, it is generally easier not to pass values to ``CMake`` via + ``-D`` and instead interactively experiment with their values in the + ``CMake`` GUI. If they are not present in the *Standard View*, + toggle to the *Advanced View* with ``<t>``. Options controlling Ceres configuration --------------------------------------- @@ -548,33 +570,35 @@ #. ``CXX11 [Default: OFF]`` *Non-MSVC compilers only*. - Although Ceres does not currently use C++11, it does use ``shared_ptr`` - (required) and ``unordered_map`` (if available); both of which existed in the - previous iterations of what became the C++11 standard: TR1 & C++0x. As such, - Ceres can compile on pre-C++11 compilers, using the TR1/C++0x versions of - ``shared_ptr`` & ``unordered_map``. + Although Ceres does not currently use C++11, it does use + ``shared_ptr`` (required) and ``unordered_map`` (if available); + both of which existed in the previous iterations of what became the + C++11 standard: TR1 & C++0x. As such, Ceres can compile on + pre-C++11 compilers, using the TR1/C++0x versions of ``shared_ptr`` + & ``unordered_map``. - Note that when using GCC & Clang, compiling against the TR1/C++0x versions: - ``CXX11=OFF`` (the default) *does not* require ``-std=c++11`` when compiling - Ceres, *nor* does it require that any client code using Ceres use - ``-std=c++11``. However, this will cause compile errors if any client code - that uses Ceres also uses C++11 (mismatched versions of ``shared_ptr`` & - ``unordered_map``). + Note that when using GCC & Clang, compiling against the TR1/C++0x + versions: ``CXX11=OFF`` (the default) *does not* require + ``-std=c++11`` when compiling Ceres, *nor* does it require that any + client code using Ceres use ``-std=c++11``. However, this will + cause compile errors if any client code that uses Ceres also uses + C++11 (mismatched versions of ``shared_ptr`` & ``unordered_map``). Enabling this option: ``CXX11=ON`` forces Ceres to use the C++11 - versions of ``shared_ptr`` & ``unordered_map`` if they are available, and - thus imposes the requirement that all client code using Ceres also - compile with ``-std=c++11``. This requirement is handled automatically - through CMake target properties on the exported Ceres target for CMake >= - 2.8.12 (when it was introduced). Thus, any client code which uses CMake will - automatically be compiled with ``-std=c++11``. **On CMake versions < - 2.8.12, you are responsible for ensuring that any code which uses Ceres is + versions of ``shared_ptr`` & ``unordered_map`` if they are + available, and thus imposes the requirement that all client code + using Ceres also compile with ``-std=c++11``. This requirement is + handled automatically through CMake target properties on the + exported Ceres target for CMake >= 2.8.12 (when it was introduced). + Thus, any client code which uses CMake will automatically be + compiled with ``-std=c++11``. **On CMake versions < 2.8.12, you + are responsible for ensuring that any code which uses Ceres is compiled with** ``-std=c++11``. - On OS X 10.9+, Clang will use the C++11 versions of ``shared_ptr`` & - ``unordered_map`` without ``-std=c++11`` and so this option does not change - the versions detected, although enabling it *will* require that client code - compile with ``-std=c++11``. + On OS X 10.9+, Clang will use the C++11 versions of ``shared_ptr`` + & ``unordered_map`` without ``-std=c++11`` and so this option does + not change the versions detected, although enabling it *will* + require that client code compile with ``-std=c++11``. The following table summarises the effects of the ``CXX11`` option: @@ -587,61 +611,68 @@ OS X 10.9+ ON std **Yes** =================== ========== ================ ====================================== - The ``CXX11`` option does does not exist when using MSVC, as there any new - C++ features available are enabled by default, and there is no analogue of - ``-std=c++11``. It will however be available on MinGW & CygWin, which can - support ``-std=c++11``. + The ``CXX11`` option does does not exist when using MSVC, as there + any new C++ features available are enabled by default, and there is + no analogue of ``-std=c++11``. It will however be available on + MinGW & CygWin, which can support ``-std=c++11``. #. ``BUILD_SHARED_LIBS [Default: OFF]``: By default Ceres is built as a static library, turn this ``ON`` to instead build Ceres as a shared library. -#. ``EXPORT_BUILD_DIR [Default: OFF]``: By default Ceres is configured solely - for installation, and so must be installed in order for clients to use it. - Turn this ``ON`` to export Ceres' build directory location into the - `user's local CMake package registry <http://www.cmake.org/cmake/help/v3.2/manual/cmake-packages.7.html#user-package-registry>`_ - where it will be detected **without requiring installation** in a client - project using CMake when `find_package(Ceres) <http://www.cmake.org/cmake/help/v3.2/command/find_package.html>`_ +#. ``EXPORT_BUILD_DIR [Default: OFF]``: By default Ceres is configured + solely for installation, and so must be installed in order for + clients to use it. Turn this ``ON`` to export Ceres' build + directory location into the `user's local CMake package registry + <http://www.cmake.org/cmake/help/v3.2/manual/cmake-packages.7.html#user-package-registry>`_ + where it will be detected **without requiring installation** in a + client project using CMake when `find_package(Ceres) + <http://www.cmake.org/cmake/help/v3.2/command/find_package.html>`_ is invoked. #. ``BUILD_DOCUMENTATION [Default: OFF]``: Use this to enable building - the documentation, requires `Sphinx <http://sphinx-doc.org/>`_ and the - `sphinx_rtd_theme <https://pypi.python.org/pypi/sphinx_rtd_theme>`_ - package available from the Python package index. In addition, - ``make ceres_docs`` can be used to build only the documentation. + the documentation, requires `Sphinx <http://sphinx-doc.org/>`_ and + the `sphinx-better-theme + <https://pypi.python.org/pypi/sphinx-better-theme>`_ package + available from the Python package index. In addition, ``make + ceres_docs`` can be used to build only the documentation. #. ``MSVC_USE_STATIC_CRT [Default: OFF]`` *Windows Only*: By default - Ceres will use the Visual Studio default, *shared* C-Run Time (CRT) library. - Turn this ``ON`` to use the *static* C-Run Time library instead. + Ceres will use the Visual Studio default, *shared* C-Run Time (CRT) + library. Turn this ``ON`` to use the *static* C-Run Time library + instead. -#. ``LIB_SUFFIX [Default: "64" on non-Debian/Arch based 64-bit Linux, otherwise: ""]``: - The suffix to append to the library install directory, built from: +#. ``LIB_SUFFIX [Default: "64" on non-Debian/Arch based 64-bit Linux, + otherwise: ""]``: The suffix to append to the library install + directory, built from: ``${CMAKE_INSTALL_PREFIX}/lib${LIB_SUFFIX}``. - The filesystem hierarchy standard recommends that 64-bit systems install - native libraries to lib64 rather than lib. Most Linux distributions follow - this convention, but Debian and Arch based distros do not. Note that the - only generally sensible values for ``LIB_SUFFIX`` are "" and "64". + The filesystem hierarchy standard recommends that 64-bit systems + install native libraries to lib64 rather than lib. Most Linux + distributions follow this convention, but Debian and Arch based + distros do not. Note that the only generally sensible values for + ``LIB_SUFFIX`` are "" and "64". - Although by default Ceres will auto-detect non-Debian/Arch based 64-bit - Linux distributions and default ``LIB_SUFFIX`` to "64", this can always be - overridden by manually specifying LIB_SUFFIX using: ``-DLIB_SUFFIX=<VALUE>`` - when invoking CMake. + Although by default Ceres will auto-detect non-Debian/Arch based + 64-bit Linux distributions and default ``LIB_SUFFIX`` to "64", this + can always be overridden by manually specifying LIB_SUFFIX using: + ``-DLIB_SUFFIX=<VALUE>`` when invoking CMake. Options controlling Ceres dependency locations ---------------------------------------------- -Ceres uses the ``CMake`` -`find_package <http://www.cmake.org/cmake/help/v3.2/command/find_package.html>`_ +Ceres uses the ``CMake`` `find_package +<http://www.cmake.org/cmake/help/v3.2/command/find_package.html>`_ function to find all of its dependencies using -``Find<DEPENDENCY_NAME>.cmake`` scripts which are either included in Ceres -(for most dependencies) or are shipped as standard with ``CMake`` -(for ``LAPACK`` & ``BLAS``). These scripts will search all of the "standard" -install locations for various OSs for each dependency. However, particularly -for Windows, they may fail to find the library, in this case you will have to -manually specify its installed location. The ``Find<DEPENDENCY_NAME>.cmake`` -scripts shipped with Ceres support two ways for you to do this: +``Find<DEPENDENCY_NAME>.cmake`` scripts which are either included in +Ceres (for most dependencies) or are shipped as standard with +``CMake`` (for ``LAPACK`` & ``BLAS``). These scripts will search all +of the "standard" install locations for various OSs for each +dependency. However, particularly for Windows, they may fail to find +the library, in this case you will have to manually specify its +installed location. The ``Find<DEPENDENCY_NAME>.cmake`` scripts +shipped with Ceres support two ways for you to do this: #. Set the *hints* variables specifying the *directories* to search in preference, but in addition, to the search directories in the @@ -663,58 +694,62 @@ ``Find<DEPENDENCY_NAME>.cmake`` script, but validation is still performed. - These variables are available to set in the ``CMake`` GUI. They - are visible in the *Standard View* if the library has not been - found (but the current Ceres configuration requires it), but - are always visible in the *Advanced View*. They can also be - set directly via ``-D<VAR>=<VALUE>`` arguments to ``CMake``. + These variables are available to set in the ``CMake`` GUI. They are + visible in the *Standard View* if the library has not been found + (but the current Ceres configuration requires it), but are always + visible in the *Advanced View*. They can also be set directly via + ``-D<VAR>=<VALUE>`` arguments to ``CMake``. Building using custom BLAS & LAPACK installs ---------------------------------------------- -If the standard find package scripts for ``BLAS`` & ``LAPACK`` which ship with -``CMake`` fail to find the desired libraries on your system, try setting -``CMAKE_LIBRARY_PATH`` to the path(s) to the directories containing the -``BLAS`` & ``LAPACK`` libraries when invoking ``CMake`` to build Ceres via -``-D<VAR>=<VALUE>``. This should result in the libraries being found for any -common variant of each. +If the standard find package scripts for ``BLAS`` & ``LAPACK`` which +ship with ``CMake`` fail to find the desired libraries on your system, +try setting ``CMAKE_LIBRARY_PATH`` to the path(s) to the directories +containing the ``BLAS`` & ``LAPACK`` libraries when invoking ``CMake`` +to build Ceres via ``-D<VAR>=<VALUE>``. This should result in the +libraries being found for any common variant of each. -If you are building on an exotic system, or setting ``CMAKE_LIBRARY_PATH`` -does not work, or is not appropriate for some other reason, one option would be -to write your own custom versions of ``FindBLAS.cmake`` & -``FindLAPACK.cmake`` specific to your environment. In this case you must set -``CMAKE_MODULE_PATH`` to the directory containing these custom scripts when -invoking ``CMake`` to build Ceres and they will be used in preference to the -default versions. However, in order for this to work, your scripts must provide -the full set of variables provided by the default scripts. Also, if you are -building Ceres with ``SuiteSparse``, the versions of ``BLAS`` & ``LAPACK`` -used by ``SuiteSparse`` and Ceres should be the same. +If you are building on an exotic system, or setting +``CMAKE_LIBRARY_PATH`` does not work, or is not appropriate for some +other reason, one option would be to write your own custom versions of +``FindBLAS.cmake`` & ``FindLAPACK.cmake`` specific to your +environment. In this case you must set ``CMAKE_MODULE_PATH`` to the +directory containing these custom scripts when invoking ``CMake`` to +build Ceres and they will be used in preference to the default +versions. However, in order for this to work, your scripts must +provide the full set of variables provided by the default scripts. +Also, if you are building Ceres with ``SuiteSparse``, the versions of +``BLAS`` & ``LAPACK`` used by ``SuiteSparse`` and Ceres should be the +same. .. _section-using-ceres: Using Ceres with CMake ====================== -In order to use Ceres in client code with CMake using -`find_package() <http://www.cmake.org/cmake/help/v3.2/command/find_package.html>`_ +In order to use Ceres in client code with CMake using `find_package() +<http://www.cmake.org/cmake/help/v3.2/command/find_package.html>`_ then either: -#. Ceres must have been installed with ``make install``. - If the install location is non-standard (i.e. is not in CMake's default +#. Ceres must have been installed with ``make install``. If the + install location is non-standard (i.e. is not in CMake's default search paths) then it will not be detected by default, see: :ref:`section-local-installations`. - Note that if you are using a non-standard install location you should - consider exporting Ceres instead, as this will not require any extra - information to be provided in client code for Ceres to be detected. + Note that if you are using a non-standard install location you + should consider exporting Ceres instead, as this will not require + any extra information to be provided in client code for Ceres to + be detected. -#. Or Ceres' build directory must have been exported - by enabling the ``EXPORT_BUILD_DIR`` option when Ceres was configured. +#. Or Ceres' build directory must have been exported by enabling the + ``EXPORT_BUILD_DIR`` option when Ceres was configured. As an example of how to use Ceres, to compile `examples/helloworld.cc <https://ceres-solver.googlesource.com/ceres-solver/+/master/examples/helloworld.cc>`_ -in a separate standalone project, the following CMakeList.txt can be used: +in a separate standalone project, the following CMakeList.txt can be +used: .. code-block:: cmake @@ -729,22 +764,25 @@ add_executable(helloworld helloworld.cc) target_link_libraries(helloworld ${CERES_LIBRARIES}) -Irrespective of whether Ceres was installed or exported, if multiple versions -are detected, set: ``Ceres_DIR`` to control which is used. If Ceres was -installed ``Ceres_DIR`` should be the path to the directory containing the -installed ``CeresConfig.cmake`` file (e.g. ``/usr/local/share/Ceres``). If -Ceres was exported, then ``Ceres_DIR`` should be the path to the exported -Ceres build directory. +Irrespective of whether Ceres was installed or exported, if multiple +versions are detected, set: ``Ceres_DIR`` to control which is used. +If Ceres was installed ``Ceres_DIR`` should be the path to the +directory containing the installed ``CeresConfig.cmake`` file +(e.g. ``/usr/local/share/Ceres``). If Ceres was exported, then +``Ceres_DIR`` should be the path to the exported Ceres build +directory. Specify Ceres components ------------------------------------- -You can specify particular Ceres components that you require (in order for Ceres -to be reported as found) when invoking ``find_package(Ceres)``. This allows you -to specify, for example, that you require a version of Ceres built with -SuiteSparse support. By definition, if you do not specify any components when -calling ``find_package(Ceres)`` (the default) any version of Ceres detected will -be reported as found, irrespective of which components it was built with. +You can specify particular Ceres components that you require (in order +for Ceres to be reported as found) when invoking +``find_package(Ceres)``. This allows you to specify, for example, +that you require a version of Ceres built with SuiteSparse support. +By definition, if you do not specify any components when calling +``find_package(Ceres)`` (the default) any version of Ceres detected +will be reported as found, irrespective of which components it was +built with. The Ceres components which can be specified are: @@ -801,95 +839,102 @@ ------------------- If Ceres was installed in a non-standard path by specifying -``-DCMAKE_INSTALL_PREFIX="/some/where/local"``, then the user should add -the **PATHS** option to the ``find_package()`` command, e.g., +``-DCMAKE_INSTALL_PREFIX="/some/where/local"``, then the user should +add the **PATHS** option to the ``find_package()`` command, e.g., .. code-block:: cmake find_package(Ceres REQUIRED PATHS "/some/where/local/") Note that this can be used to have multiple versions of Ceres -installed. However, particularly if you have only a single version of Ceres -which you want to use but do not wish to install to a system location, you -should consider exporting Ceres using the ``EXPORT_BUILD_DIR`` option instead -of a local install, as exported versions of Ceres will be automatically detected -by CMake, irrespective of their location. +installed. However, particularly if you have only a single version of +Ceres which you want to use but do not wish to install to a system +location, you should consider exporting Ceres using the +``EXPORT_BUILD_DIR`` option instead of a local install, as exported +versions of Ceres will be automatically detected by CMake, +irrespective of their location. Understanding the CMake Package System ---------------------------------------- -Although a full tutorial on CMake is outside the scope of this guide, here -we cover some of the most common CMake misunderstandings that crop up -when using Ceres. For more detailed CMake usage, the following references are -very useful: +Although a full tutorial on CMake is outside the scope of this guide, +here we cover some of the most common CMake misunderstandings that +crop up when using Ceres. For more detailed CMake usage, the +following references are very useful: - The `official CMake tutorial <http://www.cmake.org/cmake-tutorial/>`_ Provides a tour of the core features of CMake. -- `ProjectConfig tutorial <http://www.cmake.org/Wiki/CMake/Tutorials/How_to_create_a_ProjectConfig.cmake_file>`_ and the `cmake-packages documentation <http://www.cmake.org/cmake/help/git-master/manual/cmake-packages.7.html>`_ +- `ProjectConfig tutorial + <http://www.cmake.org/Wiki/CMake/Tutorials/How_to_create_a_ProjectConfig.cmake_file>`_ + and the `cmake-packages documentation + <http://www.cmake.org/cmake/help/git-master/manual/cmake-packages.7.html>`_ - Cover how to write a ``ProjectConfig.cmake`` file, discussed below, for - your own project when installing or exporting it using CMake. It also covers - how these processes in conjunction with ``find_package()`` are actually - handled by CMake. The - `ProjectConfig tutorial <http://www.cmake.org/Wiki/CMake/Tutorials/How_to_create_a_ProjectConfig.cmake_file>`_ - is the older style, currently used by Ceres for compatibility with older - versions of CMake. + Cover how to write a ``ProjectConfig.cmake`` file, discussed below, + for your own project when installing or exporting it using CMake. + It also covers how these processes in conjunction with + ``find_package()`` are actually handled by CMake. The + `ProjectConfig tutorial + <http://www.cmake.org/Wiki/CMake/Tutorials/How_to_create_a_ProjectConfig.cmake_file>`_ + is the older style, currently used by Ceres for compatibility with + older versions of CMake. .. NOTE :: **Targets in CMake.** All libraries and executables built using CMake are represented as - *targets* created using - `add_library() + *targets* created using `add_library() <http://www.cmake.org/cmake/help/v3.2/command/add_library.html>`_ - and - `add_executable() + and `add_executable() <http://www.cmake.org/cmake/help/v3.2/command/add_executable.html>`_. - Targets encapsulate the rules and dependencies (which can be other targets) - required to build or link against an object. This allows CMake to - implicitly manage dependency chains. Thus it is sufficient to tell CMake - that a library target: ``B`` depends on a previously declared library target - ``A``, and CMake will understand that this means that ``B`` also depends on - all of the public dependencies of ``A``. + Targets encapsulate the rules and dependencies (which can be other + targets) required to build or link against an object. This allows + CMake to implicitly manage dependency chains. Thus it is + sufficient to tell CMake that a library target: ``B`` depends on a + previously declared library target ``A``, and CMake will + understand that this means that ``B`` also depends on all of the + public dependencies of ``A``. -When a project like Ceres is installed using CMake, or its build directory is -exported into the local CMake package registry -(see :ref:`section-install-vs-export`), in addition to the public -headers and compiled libraries, a set of CMake-specific project configuration -files are also installed to: ``<INSTALL_ROOT>/share/Ceres`` (if Ceres is -installed), or created in the build directory (if Ceres' build directory is -exported). When `find_package -<http://www.cmake.org/cmake/help/v3.2/command/find_package.html>`_ -is invoked, CMake checks various standard install locations (including -``/usr/local`` on Linux & UNIX systems), and the local CMake package registry -for CMake configuration files for the project to be found (i.e. Ceres in the -case of ``find_package(Ceres)``). Specifically it looks for: +When a project like Ceres is installed using CMake, or its build +directory is exported into the local CMake package registry (see +:ref:`section-install-vs-export`), in addition to the public headers +and compiled libraries, a set of CMake-specific project configuration +files are also installed to: ``<INSTALL_ROOT>/share/Ceres`` (if Ceres +is installed), or created in the build directory (if Ceres' build +directory is exported). When `find_package +<http://www.cmake.org/cmake/help/v3.2/command/find_package.html>`_ is +invoked, CMake checks various standard install locations (including +``/usr/local`` on Linux & UNIX systems), and the local CMake package +registry for CMake configuration files for the project to be found +(i.e. Ceres in the case of ``find_package(Ceres)``). Specifically it +looks for: -- ``<PROJECT_NAME>Config.cmake`` (or ``<lower_case_project_name>-config.cmake``) +- ``<PROJECT_NAME>Config.cmake`` (or + ``<lower_case_project_name>-config.cmake``) - Which is written by the developers of the project, and is configured with - the selected options and installed locations when the project is built and - defines the CMake variables: ``<PROJECT_NAME>_INCLUDE_DIRS`` & - ``<PROJECT_NAME>_LIBRARIES`` which are used by the caller to import - the project. + Which is written by the developers of the project, and is + configured with the selected options and installed locations when + the project is built and defines the CMake variables: + ``<PROJECT_NAME>_INCLUDE_DIRS`` & ``<PROJECT_NAME>_LIBRARIES`` + which are used by the caller to import the project. -The ``<PROJECT_NAME>Config.cmake`` typically includes a second file installed to -the same location: +The ``<PROJECT_NAME>Config.cmake`` typically includes a second file +installed to the same location: - ``<PROJECT_NAME>Targets.cmake`` Which is autogenerated by CMake as part of the install process and defines **imported targets** for the project in the caller's CMake scope. -An **imported target** contains the same information about a library as a CMake -target that was declared locally in the current CMake project using -``add_library()``. However, imported targets refer to objects that have already -been built by a different CMake project. Principally, an imported -target contains the location of the compiled object and all of its public -dependencies required to link against it. Any locally declared target can -depend on an imported target, and CMake will manage the dependency chain, just -as if the imported target had been declared locally by the current project. +An **imported target** contains the same information about a library +as a CMake target that was declared locally in the current CMake +project using ``add_library()``. However, imported targets refer to +objects that have already been built by a different CMake project. +Principally, an imported target contains the location of the compiled +object and all of its public dependencies required to link against it. +Any locally declared target can depend on an imported target, and +CMake will manage the dependency chain, just as if the imported target +had been declared locally by the current project. Crucially, just like any locally declared CMake target, an imported target is identified by its **name** when adding it as a dependency to another target. @@ -901,41 +946,46 @@ find_package(Ceres REQUIRED) message("CERES_LIBRARIES = ${CERES_LIBRARIES}") -You would see the output: ``CERES_LIBRARIES = ceres``. **However**, here -``ceres`` is an **imported target** created when ``CeresTargets.cmake`` was -read as part of ``find_package(Ceres REQUIRED)``. It does **not** refer -(directly) to the compiled Ceres library: ``libceres.a/so/dylib/lib``. This -distinction is important, as depending on the options selected when it was -built, Ceres can have public link dependencies which are encapsulated in the -imported target and automatically added to the link step when Ceres is added -as a dependency of another target by CMake. In this case, linking only against -``libceres.a/so/dylib/lib`` without these other public dependencies would -result in a linker error. +You would see the output: ``CERES_LIBRARIES = ceres``. **However**, +here ``ceres`` is an **imported target** created when +``CeresTargets.cmake`` was read as part of ``find_package(Ceres +REQUIRED)``. It does **not** refer (directly) to the compiled Ceres +library: ``libceres.a/so/dylib/lib``. This distinction is important, +as depending on the options selected when it was built, Ceres can have +public link dependencies which are encapsulated in the imported target +and automatically added to the link step when Ceres is added as a +dependency of another target by CMake. In this case, linking only +against ``libceres.a/so/dylib/lib`` without these other public +dependencies would result in a linker error. -Note that this description applies both to projects that are **installed** -using CMake, and to those whose **build directory is exported** using -`export() <http://www.cmake.org/cmake/help/v3.2/command/export.html>`_ -(instead of -`install() <http://www.cmake.org/cmake/help/v3.2/command/install.html>`_). -Ceres supports both installation and export of its build directory if the -``EXPORT_BUILD_DIR`` option is enabled, see :ref:`section-customizing`. +Note that this description applies both to projects that are +**installed** using CMake, and to those whose **build directory is +exported** using `export() +<http://www.cmake.org/cmake/help/v3.2/command/export.html>`_ (instead +of `install() +<http://www.cmake.org/cmake/help/v3.2/command/install.html>`_). Ceres +supports both installation and export of its build directory if the +``EXPORT_BUILD_DIR`` option is enabled, see +:ref:`section-customizing`. .. _section-install-vs-export: Installing a project with CMake vs Exporting its build directory ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ -When a project is **installed**, the compiled libraries and headers are copied -from the source & build directory to the install location, and it is these -copied files that are used by any client code. When a project's build directory -is **exported**, instead of copying the compiled libraries and headers, CMake -creates an entry for the project in the -`user's local CMake package registry <http://www.cmake.org/cmake/help/v3.2/manual/cmake-packages.7.html#user-package-registry>`_, -``<USER_HOME>/.cmake/packages`` on Linux & OS X, which contains the path to -the project's build directory which will be checked by CMake during a call to -``find_package()``. The effect of which is that any client code uses the -compiled libraries and headers in the build directory directly, **thus not -requiring the project to be installed to be used**. +When a project is **installed**, the compiled libraries and headers +are copied from the source & build directory to the install location, +and it is these copied files that are used by any client code. When a +project's build directory is **exported**, instead of copying the +compiled libraries and headers, CMake creates an entry for the project +in the `user's local CMake package registry +<http://www.cmake.org/cmake/help/v3.2/manual/cmake-packages.7.html#user-package-registry>`_, +``<USER_HOME>/.cmake/packages`` on Linux & OS X, which contains the +path to the project's build directory which will be checked by CMake +during a call to ``find_package()``. The effect of which is that any +client code uses the compiled libraries and headers in the build +directory directly, **thus not requiring the project to be installed +to be used**. Installing / Exporting a project that uses Ceres -------------------------------------------------- @@ -945,25 +995,28 @@ represents Ceres. If you are installing / exporting your *own* project which *uses* Ceres, it is important to understand that: -**imported targets are not (re)exported when a project which imported them is +**Imported targets are not (re)exported when a project which imported them is exported**. Thus, when a project ``Foo`` which uses Ceres is exported, its list of -dependencies as seen by another project ``Bar`` which imports ``Foo`` via: -``find_package(Foo REQUIRED)`` will contain: ``ceres``. However, the -definition of ``ceres`` as an imported target is **not (re)exported** when Foo -is exported. Hence, without any additional steps, when processing ``Bar``, -``ceres`` will not be defined as an imported target. Thus, when processing -``Bar``, CMake will assume that ``ceres`` refers only to: -``libceres.a/so/dylib/lib`` (the compiled Ceres library) directly if it is on -the current list of search paths. In which case, no CMake errors will occur, -but ``Bar`` will not link properly, as it does not have the required public link -dependencies of Ceres, which are stored in the imported target defintion. +dependencies as seen by another project ``Bar`` which imports ``Foo`` +via: ``find_package(Foo REQUIRED)`` will contain: ``ceres``. However, +the definition of ``ceres`` as an imported target is **not +(re)exported** when Foo is exported. Hence, without any additional +steps, when processing ``Bar``, ``ceres`` will not be defined as an +imported target. Thus, when processing ``Bar``, CMake will assume +that ``ceres`` refers only to: ``libceres.a/so/dylib/lib`` (the +compiled Ceres library) directly if it is on the current list of +search paths. In which case, no CMake errors will occur, but ``Bar`` +will not link properly, as it does not have the required public link +dependencies of Ceres, which are stored in the imported target +defintion. -The solution to this is for ``Foo`` (i.e., the project that uses Ceres) to -invoke ``find_package(Ceres)`` in ``FooConfig.cmake``, thus ``ceres`` will be -defined as an imported target when CMake processes ``Bar``. An example of the -required modifications to ``FooConfig.cmake`` are show below: +The solution to this is for ``Foo`` (i.e., the project that uses +Ceres) to invoke ``find_package(Ceres)`` in ``FooConfig.cmake``, thus +``ceres`` will be defined as an imported target when CMake processes +``Bar``. An example of the required modifications to +``FooConfig.cmake`` are show below: .. code-block:: cmake
diff --git a/docs/source/license.rst b/docs/source/license.rst index d1099fa..2abbcec 100644 --- a/docs/source/license.rst +++ b/docs/source/license.rst
@@ -4,7 +4,7 @@ Ceres Solver is licensed under the New BSD license, whose terms are as follows. -Copyright 2015 Google Inc. All rights reserved. +Copyright 2016 Google Inc. All rights reserved. Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
diff --git a/docs/source/modeling_faqs.rst b/docs/source/modeling_faqs.rst new file mode 100644 index 0000000..ee4e62c --- /dev/null +++ b/docs/source/modeling_faqs.rst
@@ -0,0 +1,134 @@ +.. _chapter-modeling_faqs: + +.. default-domain:: cpp + +.. cpp:namespace:: ceres + +======== +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 + differentiation. This is a bad idea. Numeric differentiation is + slow, ill-behaved, hard to get right, and results in poor + convergence behaviour. + + Ceres allows the user to define templated functors which will + be automatically differentiated. For most situations this is enough + and we recommend using this facility. In some cases the derivatives + are simple enough or the performance considerations are such that + the overhead of automatic differentiation is too much. In such + cases, analytic derivatives are recommended. + + The use of numerical derivatives should be a measure of last + resort, where it is simply not possible to write a templated + implementation of the cost function. + + In many cases it is not possible to do analytic or automatic + differentiation of the entire cost function, but it is generally + the case that it is possible to decompose the cost function into + parts that need to be numerically differentiated and parts that can + be automatically or analytically differentiated. + + To this end, Ceres has extensive support for mixing analytic, + automatic and numeric differentiation. See + :class:`CostFunctionToFunctor`. + +#. When using Quaternions, consider using :class:`QuaternionParameterization`. + + `Quaternions <https://en.wikipedia.org/wiki/Quaternion>`_ are a + four dimensional parameterization of the space of three dimensional + rotations :math:`SO(3)`. However, the :math:`SO(3)` is a three + dimensional set, and so is the tangent space of a + Quaternion. Therefore, it is sometimes (not always) benefecial to + associate a local parameterization with parameter blocks + representing a Quaternion. Assuming that the order of entries in + your parameter block is :math:`w,x,y,z`, you can use + :class:`QuaternionParameterization`. + + .. NOTE:: + + If you are using `Eigen's Quaternion + <http://eigen.tuxfamily.org/dox/classEigen_1_1Quaternion.html>`_ + object, whose layout is :math:`x,y,z,w`, then you should use + :class:`EigenQuaternionParameterization`. + + +#. How do I solve problems with general linear & non-linear + **inequality** constraints with Ceres Solver? + + Currently, Ceres Solver only supports upper and lower bounds + constraints on the parameter blocks. + + A crude way of dealing with inequality constraints is have one or + more of your cost functions check if the inequalities you are + interested in are satisfied, and if not return false instead of + true. This will prevent the solver from ever stepping into an + infeasible region. + + This requires that the starting point for the optimization be a + feasible point. You also risk pre-mature convergence using this + method. + +#. How do I solve problems with general linear & non-linear **equality** + constraints with Ceres Solver? + + There is no built in support in ceres for solving problems with + equality constraints. Currently, Ceres Solver only supports upper + and lower bounds constraints on the parameter blocks. + + The trick described above for dealing with inequality + constraints will **not** work for equality constraints. + +#. How do I set one or more components of a parameter block constant? + + Using :class:`SubsetParameterization`. + +#. 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 WGS84 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 + its inverse is the Jacobian of :math:`f^{-1}(y)` 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/nnls_modeling.rst b/docs/source/nnls_modeling.rst index 911bd63..972ea5b 100644 --- a/docs/source/nnls_modeling.rst +++ b/docs/source/nnls_modeling.rst
@@ -370,7 +370,7 @@ NumericDiffOptions. Update DynamicNumericDiffOptions in a similar manner. - .. code-block:: c++ + .. code-block:: c++ template <typename CostFunctor, NumericDiffMethodType method = CENTRAL, @@ -389,15 +389,15 @@ SizedCostFunction<kNumResiduals, N0, N1, N2, N3, N4, N5, N6, N7, N8, N9> { }; - To get a numerically differentiated :class:`CostFunction`, you must - define a class with a ``operator()`` (a functor) that computes the - residuals. The functor must write the computed value in the last - argument (the only non-``const`` one) and return ``true`` to - indicate success. Please see :class:`CostFunction` for details on - how the return value may be used to impose simple constraints on - the parameter block. e.g., an object of the form + To get a numerically differentiated :class:`CostFunction`, you must + define a class with a ``operator()`` (a functor) that computes the + residuals. The functor must write the computed value in the last + argument (the only non-``const`` one) and return ``true`` to + indicate success. Please see :class:`CostFunction` for details on + how the return value may be used to impose simple constraints on the + parameter block. e.g., an object of the form - .. code-block:: c++ + .. code-block:: c++ struct ScalarFunctor { public: @@ -406,19 +406,19 @@ double* residuals) const; } - For example, consider a scalar error :math:`e = k - x'y`, where - both :math:`x` and :math:`y` are two-dimensional column vector - parameters, the prime sign indicates transposition, and :math:`k` - is a constant. The form of this error, which is the difference - between a constant and an expression, is a common pattern in least - squares problems. For example, the value :math:`x'y` might be the - model expectation for a series of measurements, where there is an - instance of the cost function for each measurement :math:`k`. + For example, consider a scalar error :math:`e = k - x'y`, where both + :math:`x` and :math:`y` are two-dimensional column vector + parameters, the prime sign indicates transposition, and :math:`k` is + a constant. The form of this error, which is the difference between + a constant and an expression, is a common pattern in least squares + problems. For example, the value :math:`x'y` might be the model + expectation for a series of measurements, where there is an instance + of the cost function for each measurement :math:`k`. - To write an numerically-differentiable class:`CostFunction` for the - above model, first define the object + To write an numerically-differentiable class:`CostFunction` for the + above model, first define the object - .. code-block:: c++ + .. code-block:: c++ class MyScalarCostFunctor { MyScalarCostFunctor(double k): k_(k) {} @@ -434,39 +434,39 @@ double k_; }; - Note that in the declaration of ``operator()`` the input parameters - ``x`` and ``y`` come first, and are passed as const pointers to - arrays of ``double`` s. If there were three input parameters, then - the third input parameter would come after ``y``. The output is - always the last parameter, and is also a pointer to an array. In - the example above, the residual is a scalar, so only - ``residuals[0]`` is set. + Note that in the declaration of ``operator()`` the input parameters + ``x`` and ``y`` come first, and are passed as const pointers to + arrays of ``double`` s. If there were three input parameters, then + the third input parameter would come after ``y``. The output is + always the last parameter, and is also a pointer to an array. In the + example above, the residual is a scalar, so only ``residuals[0]`` is + set. - Then given this class definition, the numerically differentiated - :class:`CostFunction` with central differences used for computing - the derivative can be constructed as follows. + Then given this class definition, the numerically differentiated + :class:`CostFunction` with central differences used for computing + the derivative can be constructed as follows. - .. code-block:: c++ + .. code-block:: c++ - CostFunction* cost_function - = new NumericDiffCostFunction<MyScalarCostFunctor, CENTRAL, 1, 2, 2>( - new MyScalarCostFunctor(1.0)); ^ ^ ^ ^ - | | | | - Finite Differencing Scheme -+ | | | - Dimension of residual ------------+ | | - Dimension of x ----------------------+ | - Dimension of y -------------------------+ + CostFunction* cost_function + = new NumericDiffCostFunction<MyScalarCostFunctor, CENTRAL, 1, 2, 2>( + new MyScalarCostFunctor(1.0)); ^ ^ ^ ^ + | | | | + Finite Differencing Scheme -+ | | | + Dimension of residual ------------+ | | + Dimension of x ----------------------+ | + Dimension of y -------------------------+ - In this example, there is usually an instance for each measurement - of `k`. + In this example, there is usually an instance for each measurement + of `k`. - In the instantiation above, the template parameters following - ``MyScalarCostFunctor``, ``1, 2, 2``, describe the functor as - computing a 1-dimensional output from two arguments, both - 2-dimensional. + In the instantiation above, the template parameters following + ``MyScalarCostFunctor``, ``1, 2, 2``, describe the functor as + computing a 1-dimensional output from two arguments, both + 2-dimensional. - NumericDiffCostFunction also supports cost functions with a - runtime-determined number of residuals. For example: + NumericDiffCostFunction also supports cost functions with a + runtime-determined number of residuals. For example: .. code-block:: c++ @@ -483,42 +483,44 @@ Dimension of y ---------------------------------------------------+ - The framework can currently accommodate cost functions of up to 10 - independent variables, and there is no limit on the dimensionality - of each of them. + The framework can currently accommodate cost functions of up to 10 + independent variables, and there is no limit on the dimensionality + of each of them. - There are three available numeric differentiation schemes in ceres-solver: + There are three available numeric differentiation schemes in ceres-solver: - The ``FORWARD`` difference method, which approximates :math:`f'(x)` - by computing :math:`\frac{f(x+h)-f(x)}{h}`, computes the cost function - one additional time at :math:`x+h`. It is the fastest but least accurate - method. + The ``FORWARD`` difference method, which approximates :math:`f'(x)` + by computing :math:`\frac{f(x+h)-f(x)}{h}`, computes the cost + function one additional time at :math:`x+h`. It is the fastest but + least accurate method. - The ``CENTRAL`` difference method is more accurate at - the cost of twice as many function evaluations than forward - difference, estimating :math:`f'(x)` by computing - :math:`\frac{f(x+h)-f(x-h)}{2h}`. + The ``CENTRAL`` difference method is more accurate at the cost of + twice as many function evaluations than forward difference, + estimating :math:`f'(x)` by computing + :math:`\frac{f(x+h)-f(x-h)}{2h}`. - The ``RIDDERS`` difference method[Ridders]_ is an adaptive scheme that - estimates derivatives by performing multiple central differences - at varying scales. Specifically, the algorithm starts at a certain - :math:`h` and as the derivative is estimated, this step size decreases. - To conserve function evaluations and estimate the derivative error, the - method performs Richardson extrapolations between the tested step sizes. - The algorithm exhibits considerably higher accuracy, but does so by - additional evaluations of the cost function. + The ``RIDDERS`` difference method[Ridders]_ is an adaptive scheme + that estimates derivatives by performing multiple central + differences at varying scales. Specifically, the algorithm starts at + a certain :math:`h` and as the derivative is estimated, this step + size decreases. To conserve function evaluations and estimate the + derivative error, the method performs Richardson extrapolations + between the tested step sizes. The algorithm exhibits considerably + higher accuracy, but does so by additional evaluations of the cost + function. - Consider using ``CENTRAL`` differences to begin with. Based on the - results, either try forward difference to improve performance or - Ridders' method to improve accuracy. + Consider using ``CENTRAL`` differences to begin with. Based on the + results, either try forward difference to improve performance or + Ridders' method to improve accuracy. - **WARNING** A common beginner's error when first using - NumericDiffCostFunction is to get the sizing wrong. In particular, - there is a tendency to set the template parameters to (dimension of - residual, number of parameters) instead of passing a dimension - parameter for *every parameter*. In the example above, that would - be ``<MyScalarCostFunctor, 1, 2>``, which is missing the last ``2`` - argument. Please be careful when setting the size parameters. + **WARNING** A common beginner's error when first using + :class:`NumericDiffCostFunction` is to get the sizing wrong. In + particular, there is a tendency to set the template parameters to + (dimension of residual, number of parameters) instead of passing a + dimension parameter for *every parameter*. In the example above, + that would be ``<MyScalarCostFunctor, 1, 2>``, which is missing the + last ``2`` argument. Please be careful when setting the size + parameters. Numeric Differentiation & LocalParameterization
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!.
diff --git a/scripts/make_docs.py b/scripts/make_docs.py index bb51620..c1e711f 100644 --- a/scripts/make_docs.py +++ b/scripts/make_docs.py
@@ -76,7 +76,7 @@ # The title for the homepage is not ideal, so change it. ('<title>Ceres Solver — Ceres Solver</title>', - '<title>Ceres Solver — A Nonlinear Least Squares Minimizer</title>') + '<title>Ceres Solver — A Large Scale Non-linear Optimization Library</title>') ] # This is a nasty hack to strip the breadcrumb navigation. A better strategy is @@ -86,7 +86,7 @@ '''<div role="navigation" aria-label="breadcrumbs navigation"> <ul class="wy-breadcrumbs"> <li><a href="index.html">Docs</a> »</li> - + <li>''' # The index page has a slightly different breadcrumb. @@ -95,7 +95,7 @@ breadcrumb_end = \ '''</li> <li class="wy-breadcrumbs-aside"> - + </li> </ul> <hr/>