More documentation updates
Change-Id: I762bd28b4ebc327d39a572990e02157ef55ad617
diff --git a/docs/source/solving.rst b/docs/source/solving.rst
index a4564d6..c992c5b 100644
--- a/docs/source/solving.rst
+++ b/docs/source/solving.rst
@@ -998,33 +998,6 @@
Number of threads used by the linear solver.
-.. member:: bool Solver::Options::use_inner_iterations
-
- Default: ``false``
-
- Use a non-linear version of a simplified variable projection
- algorithm. Essentially this amounts to doing a further optimization
- on each Newton/Trust region step using a coordinate descent
- algorithm. For more details, see :ref:`section-inner-iterations`.
-
-.. member:: ParameterBlockOrdering* Solver::Options::inner_iteration_ordering
-
- Default: ``NULL``
-
- If :member:`Solver::Options::use_inner_iterations` true, then the user has
- two choices.
-
- 1. Let the solver heuristically decide which parameter blocks to
- optimize in each inner iteration. To do this, set
- :member:`Solver::Options::inner_iteration_ordering` to ``NULL``.
-
- 2. Specify a collection of of ordered independent sets. The lower
- numbered groups are optimized before the higher number groups
- during the inner optimization phase. Each group must be an
- independent set.
-
- See :ref:`section-ordering` for more details.
-
.. member:: ParameterBlockOrdering* Solver::Options::linear_solver_ordering
Default: ``NULL``
@@ -1034,29 +1007,33 @@
linear solvers. See section~\ref{sec:ordering`` for more details.
If ``NULL``, the solver is free to choose an ordering that it
- thinks is best. Note: currently, this option only has an effect on
- the Schur type solvers, support for the ``SPARSE_NORMAL_CHOLESKY``
- solver is forth coming.
+ thinks is best.
See :ref:`section-ordering` for more details.
-.. member:: bool Solver::Options::use_block_amd
+.. member:: bool Solver::Options::use_post_ordering
- Default: ``true``
+ Default: ``false``
- By virtue of the modeling layer in Ceres being block oriented, all
- the matrices used by Ceres are also block oriented. When doing
- sparse direct factorization of these matrices, the fill-reducing
- ordering algorithms can either be run on the block or the scalar
- form of these matrices. Running it on the block form exposes more
- of the super-nodal structure of the matrix to the Cholesky
- factorization routines. This leads to substantial gains in
- factorization performance. Setting this parameter to true, enables
- the use of a block oriented Approximate Minimum Degree ordering
- algorithm. Settings it to ``false``, uses a scalar AMD
- algorithm. This option only makes sense when using
- :member:`Solver::Options::sparse_linear_algebra_library` = ``SUITE_SPARSE``
- as it uses the ``AMD`` package that is part of ``SuiteSparse``.
+ Sparse Cholesky factorization algorithms use a fill-reducing
+ ordering to permute the columns of the Jacobian matrix. There are
+ two ways of doing this.
+
+ 1. Compute the Jacobian matrix in some order and then have the
+ factorization algorithm permute the columns of the Jacobian.
+
+ 2. Compute the Jacobian with it's columns already permuted.
+
+ The first option incurs a significant memory penalty. The
+ factorization algorithm has to make a copy of the permuted Jacobian
+ matrix, thus Ceres pre-permutes the columns of the Jacobian matrix
+ and generally speaking, there is no performance penalty for doing
+ so.
+
+ In some rare cases, it is worth using a more complicated reordering
+ algorithm which has slightly better runtime performance at the
+ expense of an extra copy of the Jacobian matrix. Setting
+ ``use_postordering`` to ``true`` enables this tradeoff.
.. member:: int Solver::Options::linear_solver_min_num_iterations
@@ -1094,6 +1071,48 @@
columns before being passed to the linear solver. This improves the
numerical conditioning of the normal equations.
+.. member:: bool Solver::Options::use_inner_iterations
+
+ Default: ``false``
+
+ Use a non-linear version of a simplified variable projection
+ algorithm. Essentially this amounts to doing a further optimization
+ on each Newton/Trust region step using a coordinate descent
+ algorithm. For more details, see :ref:`section-inner-iterations`.
+
+.. member:: double Solver::Options::inner_itearation_tolerance
+
+ Default: ``1e-3``
+
+ Generally speaking, inner iterations make significant progress in
+ the early stages of the solve and then their contribution drops
+ down sharply, at which point the time spent doing inner iterations
+ is not worth it.
+
+ Once the relative decrease in the objective function due to inner
+ iterations drops below ``inner_iteration_tolerance``, the use of
+ inner iterations in subsequent trust region minimizer iterations is
+ disabled.
+
+.. member:: ParameterBlockOrdering* Solver::Options::inner_iteration_ordering
+
+ Default: ``NULL``
+
+ If :member:`Solver::Options::use_inner_iterations` true, then the user has
+ two choices.
+
+ 1. Let the solver heuristically decide which parameter blocks to
+ optimize in each inner iteration. To do this, set
+ :member:`Solver::Options::inner_iteration_ordering` to ``NULL``.
+
+ 2. Specify a collection of of ordered independent sets. The lower
+ numbered groups are optimized before the higher number groups
+ during the inner optimization phase. Each group must be an
+ independent set. Not all parameter blocks need to be included in
+ the ordering.
+
+ See :ref:`section-ordering` for more details.
+
.. member:: LoggingType Solver::Options::logging_type
Default: ``PER_MINIMIZER_ITERATION``
@@ -1234,7 +1253,60 @@
.. class:: ParameterBlockOrdering
- TBD
+ ``ParameterBlockOrdering`` is a class for storing and manipulating
+ an ordered collection of groups/sets with the following semantics:
+
+ Group IDs are non-negative integer values. Elements are any type
+ that can serve as a key in a map or an element of a set.
+
+ An element can only belong to one group at a time. A group may
+ contain an arbitrary number of elements.
+
+ Groups are ordered by their group id.
+
+.. function:: bool ParameterBlockOrdering::AddElementToGroup(const double* element, const int group)
+
+ Add an element to a group. If a group with this id does not exist,
+ one is created. This method can be called any number of times for
+ the same element. Group ids should be non-negative numbers. Return
+ value indicates if adding the element was a success.
+
+.. function:: void ParameterBlockOrdering::Clear()
+
+ Clear the ordering.
+
+.. function:: bool ParameterBlockOrdering::Remove(const double* element)
+
+ Remove the element, no matter what group it is in. If the element
+ is not a member of any group, calling this method will result in a
+ crash. Return value indicates if the element was actually removed.
+
+.. function:: void ParameterBlockOrdering::Reverse()
+
+ Reverse the order of the groups in place.
+
+.. function:: int ParameterBlockOrdering::GroupId(const double* element) const
+
+ Return the group id for the element. If the element is not a member
+ of any group, return -1.
+
+.. function:: bool ParameterBlockOrdering::IsMember(const double* element) const
+
+ True if there is a group containing the parameter block.
+
+.. function:: int ParameterBlockOrdering::GroupSize(const int group) const
+
+ This function always succeeds, i.e., implicitly there exists a
+ group for every integer.
+
+.. function:: int ParameterBlockOrdering::NumElements() const
+
+ Number of elements in the ordering.
+
+.. function:: int ParameterBlockOrdering::NumGroups() const
+
+ Number of groups with one or more elements.
+
:class:`IterationCallback`
--------------------------
