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/evaluator.cc b/internal/ceres/evaluator.cc
index 31a4176..c94c62c 100644
--- a/internal/ceres/evaluator.cc
+++ b/internal/ceres/evaluator.cc
@@ -35,6 +35,8 @@
#include "ceres/compressed_row_sparse_matrix.h"
#include "ceres/crs_matrix.h"
#include "ceres/dense_jacobian_writer.h"
+#include "ceres/dynamic_compressed_row_finalizer.h"
+#include "ceres/dynamic_compressed_row_jacobian_writer.h"
#include "ceres/evaluator.h"
#include "ceres/internal/port.h"
#include "ceres/program_evaluator.h"
@@ -63,9 +65,17 @@
BlockJacobianWriter>(options,
program);
case SPARSE_NORMAL_CHOLESKY:
- return new ProgramEvaluator<ScratchEvaluatePreparer,
- CompressedRowJacobianWriter>(options,
- program);
+ if (options.dynamic_sparsity) {
+ return new ProgramEvaluator<ScratchEvaluatePreparer,
+ DynamicCompressedRowJacobianWriter,
+ DynamicCompressedRowJacobianFinalizer>(
+ options, program);
+ } else {
+ return new ProgramEvaluator<ScratchEvaluatePreparer,
+ CompressedRowJacobianWriter>(options,
+ program);
+ }
+
default:
*error = "Invalid Linear Solver Type. Unable to create evaluator.";
return NULL;
