Add dynamic_sparsity option.
The standard sparse normal Cholesky solver assumes a fixed
sparsity pattern which is useful for a large number of problems
presented to Ceres. However, some problems are symbolically dense
but numerically sparse i.e. each residual is a function of a
large number of parameters but at any given state the residual
only depends on a sparse subset of them. For these class of
problems it is faster to re-analyse the sparsity pattern of the
jacobian at each iteration of the non-linear optimisation instead
of including all of the zero entries in the step computation.
The proposed solution adds the dynamic_sparsity option which can
be used with SPARSE_NORMAL_CHOLESKY. A
DynamicCompressedRowSparseMatrix type (which extends
CompressedRowSparseMatrix) has been introduced which allows
dynamic addition and removal of elements. A Finalize method is
provided which then consolidates the matrix so that it can be
used in place of a regular CompressedRowSparseMatrix. An
associated jacobian writer has also been provided.
Changes that were required to make this extension were adding the
SetMaxNumNonZeros method to CompressedRowSparseMatrix and adding
a JacobianFinalizer template parameter to the ProgramEvaluator.
Change-Id: Ia5a8a9523fdae8d5b027bc35e70b4611ec2a8d01
diff --git a/internal/ceres/compressed_row_jacobian_writer.h b/internal/ceres/compressed_row_jacobian_writer.h
index c103165..935e650 100644
--- a/internal/ceres/compressed_row_jacobian_writer.h
+++ b/internal/ceres/compressed_row_jacobian_writer.h
@@ -39,6 +39,7 @@
namespace ceres {
namespace internal {
+class CompressedRowSparseMatrix;
class Program;
class SparseMatrix;
@@ -49,6 +50,36 @@
: program_(program) {
}
+ // `PopulateJacobianRowAndColumnBlockVectors` sets `col_blocks` and
+ // `row_blocks` for a `CompressedRowSparseMatrix`, based on the parameter
+ // block sizes and residual sizes respectively from the program. This is
+ // useful when Solver::Options::use_block_amd = true;
+ //
+ // This function is static so that it is available to other jacobian
+ // writers which use `CompressedRowSparseMatrix` (or derived types).
+ // (Jacobian writers do not fall under any type hierarchy; they only
+ // have to provide an interface as specified in program_evaluator.h).
+ static void PopulateJacobianRowAndColumnBlockVectors(
+ const Program* program,
+ CompressedRowSparseMatrix* jacobian);
+
+ // It is necessary to determine the order of the jacobian blocks before
+ // copying them into a `CompressedRowSparseMatrix` (or derived type).
+ // Just because a cost function uses parameter blocks 1 after 2 in its
+ // arguments does not mean that the block 1 occurs before block 2 in the
+ // column layout of the jacobian. Thus, `GetOrderedParameterBlocks`
+ // determines the order by sorting the jacobian blocks by their position in
+ // the state vector.
+ //
+ // This function is static so that it is available to other jacobian
+ // writers which use `CompressedRowSparseMatrix` (or derived types).
+ // (Jacobian writers do not fall under any type hierarchy; they only
+ // have to provide an interface as specified in program_evaluator.h).
+ static void GetOrderedParameterBlocks(
+ const Program* program,
+ int residual_id,
+ vector<pair<int, int> >* evaluated_jacobian_blocks);
+
// JacobianWriter interface.
// Since the compressed row matrix has different layout than that assumed by
