Solver::Options::ordering* are dead.
Remove the old ordering API, and modify solver_impl.cc
to use the new API everywhere.
In the process also clean up the linear solver instantion
logic in solver_impl.cc a bit too.
Change-Id: Ia66898abc7f622070b184b21fce8cc6140c4cebf
diff --git a/docs/build.tex b/docs/build.tex
index 9794663..05bceb4 100644
--- a/docs/build.tex
+++ b/docs/build.tex
@@ -126,8 +126,6 @@
Given Used
Linear solver DENSE_SCHUR DENSE_SCHUR
Preconditioner N/A N/A
-Ordering SCHUR SCHUR
-num_eliminate_blocks N/A 22106
Threads: 1 1
Linear Solver Threads: 1 1
diff --git a/docs/bundleadjustment.tex b/docs/bundleadjustment.tex
index 5a1298c..1f63361 100644
--- a/docs/bundleadjustment.tex
+++ b/docs/bundleadjustment.tex
@@ -92,7 +92,6 @@
\begin{minted}{c++}
ceres::Solver::Options options;
options.linear_solver_type = ceres::DENSE_SCHUR;
-options.ordering_type = ceres::SCHUR;
options.minimizer_progress_to_stdout = true;
ceres::Solver::Summary summary;
ceres::Solve(options, &problem, &summary);
diff --git a/docs/solving.tex b/docs/solving.tex
index 3e9f419..8398c7f 100644
--- a/docs/solving.tex
+++ b/docs/solving.tex
@@ -291,6 +291,8 @@
For bundle adjustment problems arising in reconstruction from community photo collections, more effective preconditioners can be constructed by analyzing and exploiting the camera-point visibility structure of the scene~\cite{kushal2012}. Ceres implements the two visibility based preconditioners described by Kushal \& Agarwal as \texttt{CLUSTER\_JACOBI} and \texttt{CLUSTER\_TRIDIAGONAL}. These are fairly new preconditioners and Ceres' implementation of them is in its early stages and is not as mature as the other preconditioners described above.
\section{Ordering}
+TBD - re-write this section once the ordering API is complete.
+
All three of the Schur based solvers depend on the user indicating to the solver, which of the parameter blocks correspond to the points and which correspond to the cameras. Ceres refers to them as \texttt{e\_block}s and \texttt{f\_blocks}. The only constraint on \texttt{e\_block}s is that there should be no term in the objective function with two or more \texttt{e\_block}s.
As we saw in Section~\ref{chapter:tutorial:bundleadjustment}, there are two ways to indicate \texttt{e\_block}s to Ceres. The first is to explicitly create an ordering vector \texttt{Solver::Options::ordering} containing the parameter blocks such that all the \texttt{e\_block}s/points occur before the \texttt{f\_blocks}, and setting \texttt{Solver::Options::num\_eliminate\_blocks} to the number \texttt{e\_block}s.
@@ -426,25 +428,25 @@
\item{\texttt{num\_linear\_solver\_threads }}(\texttt{1}) Number of
threads used by the linear solver.
-\item{\texttt{num\_eliminate\_blocks }}(\texttt{0})
-For Schur reduction based methods, the first 0 to num blocks are
-eliminated using the Schur reduction. For example, when solving
-traditional structure from motion problems where the parameters are in
-two classes (cameras and points) then \texttt{num\_eliminate\_blocks}
-would be the number of points.
-
-\item{\texttt{ordering\_type }}(\texttt{NATURAL}) Internally Ceres
- reorders the parameter blocks to help the various linear
- solvers. This parameter allows the user to influence the re-ordering
- strategy used. For structure from motion problems use
- \texttt{SCHUR}, for other problems \texttt{NATURAL} (default) is a
- good choice. In case you wish to specify your own ordering scheme,
- for example in conjunction with \texttt{num\_eliminate\_blocks}, use
- \texttt{USER}.
-
-\item{\texttt{ordering }} The ordering of the parameter blocks. The
- solver pays attention to it if the \texttt{ordering\_type} is set to
- \texttt{USER} and the ordering vector is non-empty.
+%\item{\texttt{num\_eliminate\_blocks }}(\texttt{0})
+%For Schur reduction based methods, the first 0 to num blocks are
+%eliminated using the Schur reduction. For example, when solving
+%traditional structure from motion problems where the parameters are in
+%two classes (cameras and points) then \texttt{num\_eliminate\_blocks}
+%would be the number of points.
+%
+%\item{\texttt{ordering\_type }}(\texttt{NATURAL}) Internally Ceres
+% reorders the parameter blocks to help the various linear
+% solvers. This parameter allows the user to influence the re-ordering
+% strategy used. For structure from motion problems use
+% \texttt{SCHUR}, for other problems \texttt{NATURAL} (default) is a
+% good choice. In case you wish to specify your own ordering scheme,
+% for example in conjunction with \texttt{num\_eliminate\_blocks}, use
+% \texttt{USER}.
+%
+%\item{\texttt{ordering }} The ordering of the parameter blocks. The
+% solver pays attention to it if the \texttt{ordering\_type} is set to
+% \texttt{USER} and the ordering vector is non-empty.
\item{\texttt{use\_block\_amd } (\texttt{true})} By virtue of the
modeling layer in Ceres being block oriented, all the matrices used
diff --git a/examples/bundle_adjuster.cc b/examples/bundle_adjuster.cc
index 2bbffcf..6cd8c6a 100644
--- a/examples/bundle_adjuster.cc
+++ b/examples/bundle_adjuster.cc
@@ -67,44 +67,44 @@
DEFINE_string(input, "", "Input File name");
DEFINE_string(trust_region_strategy, "levenberg_marquardt",
- "Options are: levenberg_marquardt, dogleg");
+ "Options are: levenberg_marquardt, dogleg.");
DEFINE_string(linear_solver, "sparse_schur", "Options are: "
"sparse_schur, dense_schur, iterative_schur, sparse_normal_cholesky, "
- "dense_qr, dense_normal_cholesky and cgnr");
+ "dense_qr, dense_normal_cholesky and cgnr.");
DEFINE_string(preconditioner, "jacobi", "Options are: "
"identity, jacobi, schur_jacobi, cluster_jacobi, "
- "cluster_tridiagonal");
+ "cluster_tridiagonal.");
DEFINE_string(sparse_linear_algebra_library, "suite_sparse",
- "Options are: suite_sparse and cx_sparse");
-DEFINE_string(ordering, "schur", "Options are: schur, user, natural");
+ "Options are: suite_sparse and cx_sparse.");
+DEFINE_string(ordering, "automatic", "Options are: automatic, user.");
DEFINE_string(dogleg, "traditional_dogleg", "Options are: traditional_dogleg,"
- "subspace_dogleg");
+ "subspace_dogleg.");
DEFINE_bool(use_quaternions, false, "If true, uses quaternions to represent "
- "rotations. If false, angle axis is used");
+ "rotations. If false, angle axis is used.");
DEFINE_bool(use_local_parameterization, false, "For quaternions, use a local "
"parameterization.");
-DEFINE_bool(robustify, false, "Use a robust loss function");
+DEFINE_bool(robustify, false, "Use a robust loss function.");
DEFINE_double(eta, 1e-2, "Default value for eta. Eta determines the "
"accuracy of each linear solve of the truncated newton step. "
- "Changing this parameter can affect solve performance ");
+ "Changing this parameter can affect solve performance.");
DEFINE_bool(use_block_amd, true, "Use a block oriented fill reducing "
"ordering.");
-DEFINE_int32(num_threads, 1, "Number of threads");
-DEFINE_int32(num_iterations, 5, "Number of iterations");
+DEFINE_int32(num_threads, 1, "Number of threads.");
+DEFINE_int32(num_iterations, 5, "Number of iterations.");
DEFINE_double(max_solver_time, 1e32, "Maximum solve time in seconds.");
DEFINE_bool(nonmonotonic_steps, false, "Trust region algorithm can use"
- " nonmonotic steps");
+ " nonmonotic steps.");
DEFINE_double(rotation_sigma, 0.0, "Standard deviation of camera rotation "
"perturbation.");
DEFINE_double(translation_sigma, 0.0, "Standard deviation of the camera "
"translation perturbation.");
DEFINE_double(point_sigma, 0.0, "Standard deviation of the point "
- "perturbation");
+ "perturbation.");
DEFINE_int32(random_seed, 38401, "Random seed used to set the state "
"of the pseudo random number generator used to generate "
"the pertubations.");
@@ -131,18 +131,14 @@
// them amenable to more specialized and much more efficient
// solution strategies. The SPARSE_SCHUR, DENSE_SCHUR and
// ITERATIVE_SCHUR solvers make use of this specialized
- // structure. Using them however requires that the ParameterBlocks
- // are in a particular order (points before cameras) and
- // Solver::Options::num_eliminate_blocks is set to the number of
- // points.
+ // structure.
//
// This can either be done by specifying Options::ordering_type =
// ceres::SCHUR, in which case Ceres will automatically determine
// the right ParameterBlock ordering, or by manually specifying a
// suitable ordering vector and defining
// Options::num_eliminate_blocks.
- options->use_new_ordering_api = true;
- if (FLAGS_ordering == "schur") {
+ if (FLAGS_ordering == "automatic") {
return;
}
@@ -172,7 +168,7 @@
}
}
- options->ordering_new_api = ordering;
+ options->ordering = ordering;
}
void SetMinimizerOptions(Solver::Options* options) {
diff --git a/examples/simple_bundle_adjuster.cc b/examples/simple_bundle_adjuster.cc
index 16c2dde..850690e 100644
--- a/examples/simple_bundle_adjuster.cc
+++ b/examples/simple_bundle_adjuster.cc
@@ -201,7 +201,6 @@
// for standard bundle adjustment problems.
ceres::Solver::Options options;
options.linear_solver_type = ceres::DENSE_SCHUR;
- options.ordering_type = ceres::SCHUR;
options.minimizer_progress_to_stdout = true;
ceres::Solver::Summary summary;
diff --git a/include/ceres/ordering.h b/include/ceres/ordering.h
index b3cd1b1..c302aad 100644
--- a/include/ceres/ordering.h
+++ b/include/ceres/ordering.h
@@ -109,13 +109,15 @@
// block is not known to the Ordering, calling this method results
// in a crash.
int GroupIdForParameterBlock(double* parameter_block) const;
- int NumParameterBlocks() const;
- int NumGroups() const;
// This function always succeeds. For a group_id unknown to the
// ordering is treated as empty groups and the function returns
// zero.
int GroupSize(int group_id) const;
+
+ bool ContainsParameterBlock(double* parameter_block) const;
+ int NumParameterBlocks() const;
+ int NumGroups() const;
const map<int, set<double*> >& group_id_to_parameter_blocks() const;
private:
diff --git a/include/ceres/solver.h b/include/ceres/solver.h
index 0e94ee8..95d6ba0 100644
--- a/include/ceres/solver.h
+++ b/include/ceres/solver.h
@@ -90,17 +90,13 @@
#endif
num_linear_solver_threads = 1;
- use_new_ordering_api = false;
- ordering_new_api = NULL;
- num_eliminate_blocks = 0;
- ordering_type = NATURAL;
#if defined(CERES_NO_SUITESPARSE)
use_block_amd = false;
#else
use_block_amd = true;
#endif
-
+ ordering = NULL;
linear_solver_min_num_iterations = 1;
linear_solver_max_num_iterations = 500;
eta = 1e-1;
@@ -121,6 +117,7 @@
update_state_every_iteration = false;
}
+ ~Options();
// Minimizer options ----------------------------------------
TrustRegionStrategyType trust_region_strategy_type;
@@ -232,41 +229,10 @@
// using this setting.
int num_linear_solver_threads;
- // Whether the old or the new ordering API should be used. If this
- // is true, all assignments to Solve::Options::ordering_type,
- // Solver::Options::ordering and
- // Solver::Options::num_eliminate_blocks are ignored.
- bool use_new_ordering_api;
-
- // Ordering object for the new ordering API. If NULL, then all
- // parameter blocks are assumed to be in the same group and the
- // solver is free to decide the best ordering. (See ordering.h for
- // more details).
- Ordering* ordering_new_api;
-
- // For Schur reduction based methods, the first 0 to num blocks are
- // eliminated using the Schur reduction. For example, when solving
- // traditional structure from motion problems where the parameters are in
- // two classes (cameras and points) then num_eliminate_blocks would be the
- // number of points.
- //
- // This parameter is used in conjunction with the ordering.
- // Applies to: Preprocessor and linear least squares solver.
- int num_eliminate_blocks;
-
- // Internally Ceres reorders the parameter blocks to help the
- // various linear solvers. This parameter allows the user to
- // influence the re-ordering strategy used. For structure from
- // motion problems use SCHUR, for other problems NATURAL (default)
- // is a good choice. In case you wish to specify your own ordering
- // scheme, for example in conjunction with num_eliminate_blocks,
- // use USER.
- OrderingType ordering_type;
-
- // The ordering of the parameter blocks. The solver pays attention
- // to it if the ordering_type is set to USER and the vector is
- // non-empty.
- vector<double*> ordering;
+ // If NULL, then all parameter blocks are assumed to be in the
+ // same group and the solver is free to decide the best
+ // ordering. (See ordering.h for more details).
+ Ordering* ordering;
// By virtue of the modeling layer in Ceres being block oriented,
// all the matrices used by Ceres are also block oriented. When
@@ -523,7 +489,6 @@
LinearSolverType linear_solver_type_used;
PreconditionerType preconditioner_type;
- OrderingType ordering_type;
TrustRegionStrategyType trust_region_strategy_type;
DoglegType dogleg_type;
diff --git a/include/ceres/types.h b/include/ceres/types.h
index 30dcada..888e9b0 100644
--- a/include/ceres/types.h
+++ b/include/ceres/types.h
@@ -145,18 +145,6 @@
FAILURE
};
-enum OrderingType {
- // The order in which the parameter blocks were defined.
- NATURAL,
-
- // Use the ordering specificed in the vector ordering.
- USER,
-
- // Automatically figure out the best ordering to use the schur
- // complement based solver.
- SCHUR
-};
-
// Logging options
// The options get progressively noisier.
enum LoggingType {
@@ -310,9 +298,6 @@
string value,
SparseLinearAlgebraLibraryType* type);
-const char* OrderingTypeToString(OrderingType type);
-bool StringToOrderingType(string value, OrderingType* type);
-
const char* TrustRegionStrategyTypeToString(TrustRegionStrategyType type);
bool StringToTrustRegionStrategyType(string value,
TrustRegionStrategyType* type);
diff --git a/internal/ceres/minimizer.h b/internal/ceres/minimizer.h
index cfc98a3..667d80a 100644
--- a/internal/ceres/minimizer.h
+++ b/internal/ceres/minimizer.h
@@ -74,7 +74,6 @@
lsqp_dump_directory = options.lsqp_dump_directory;
lsqp_iterations_to_dump = options.lsqp_iterations_to_dump;
lsqp_dump_format_type = options.lsqp_dump_format_type;
- num_eliminate_blocks = options.num_eliminate_blocks;
max_num_consecutive_invalid_steps =
options.max_num_consecutive_invalid_steps;
min_trust_region_radius = options.min_trust_region_radius;
@@ -104,7 +103,6 @@
vector<int> lsqp_iterations_to_dump;
DumpFormatType lsqp_dump_format_type;
string lsqp_dump_directory;
- int num_eliminate_blocks;
int max_num_consecutive_invalid_steps;
int min_trust_region_radius;
diff --git a/internal/ceres/ordering.cc b/internal/ceres/ordering.cc
index 8b53ea5..4b3ec25 100644
--- a/internal/ceres/ordering.cc
+++ b/internal/ceres/ordering.cc
@@ -70,6 +70,12 @@
return it->second;
}
+bool Ordering::ContainsParameterBlock(double* parameter_block) const {
+ const map<double*, int>::const_iterator it =
+ parameter_block_to_group_id_.find(parameter_block);
+ return (it != parameter_block_to_group_id_.end());
+}
+
int Ordering::NumParameterBlocks() const {
return parameter_block_to_group_id_.size();
}
diff --git a/internal/ceres/solver.cc b/internal/ceres/solver.cc
index 84c2756..5a84cfc 100644
--- a/internal/ceres/solver.cc
+++ b/internal/ceres/solver.cc
@@ -82,8 +82,6 @@
num_parameters_reduced(-1),
num_residual_blocks_reduced(-1),
num_residuals_reduced(-1),
- num_eliminate_blocks_given(-1),
- num_eliminate_blocks_used(-1),
num_threads_given(-1),
num_threads_used(-1),
num_linear_solver_threads_given(-1),
@@ -91,7 +89,6 @@
linear_solver_type_given(SPARSE_NORMAL_CHOLESKY),
linear_solver_type_used(SPARSE_NORMAL_CHOLESKY),
preconditioner_type(IDENTITY),
- ordering_type(NATURAL),
trust_region_strategy_type(LEVENBERG_MARQUARDT),
sparse_linear_algebra_library(SUITE_SPARSE) {
}
@@ -165,22 +162,7 @@
"N/A", "N/A");
}
- internal::StringAppendF(&report, "Ordering %25s%25s\n",
- OrderingTypeToString(ordering_type),
- OrderingTypeToString(ordering_type));
-
- if (IsSchurType(linear_solver_type_given)) {
- if (ordering_type == SCHUR) {
- internal::StringAppendF(&report, "num_eliminate_blocks%25s% 25d\n",
- "N/A",
- num_eliminate_blocks_used);
- } else {
- internal::StringAppendF(&report, "num_eliminate_blocks% 25d% 25d\n",
- num_eliminate_blocks_given,
- num_eliminate_blocks_used);
- }
- }
-
+ // TODO(sameeragarwal): Add support for logging the ordering object.
internal::StringAppendF(&report, "Threads: % 25d% 25d\n",
num_threads_given, num_threads_used);
internal::StringAppendF(&report, "Linear solver threads % 23d% 25d\n",
diff --git a/internal/ceres/solver_impl.cc b/internal/ceres/solver_impl.cc
index 4bedbe3..7e90c9b 100644
--- a/internal/ceres/solver_impl.cc
+++ b/internal/ceres/solver_impl.cc
@@ -52,6 +52,13 @@
#include "ceres/wall_time.h"
namespace ceres {
+
+Solver::Options::~Options() {
+ if (ordering != NULL) {
+ delete ordering;
+ }
+}
+
namespace internal {
namespace {
@@ -202,57 +209,11 @@
Solver::Summary* summary) {
double solver_start_time = WallTimeInSeconds();
Solver::Options options(original_options);
-
- // Code for supporting both the old and the new ordering API. This
- // code will get refactored and re-written as the old API is
- // steadily deprecated.
-
- // Clobber all the input parameters from the old api parameters.
- if (options.use_new_ordering_api) {
- // For linear solvers which are not of Schur type, do nothing.
- options.ordering.clear();
- options.num_eliminate_blocks = 0;
- options.ordering_type = NATURAL;
-
- if (IsSchurType(options.linear_solver_type)) {
- if (options.ordering_new_api == NULL) {
- // User says we are free to find the independent set, and order
- // any which way.
- options.ordering_type = SCHUR;
- } else {
- // User has given an ordering and asked for a Schur type solver.
- options.ordering_type = USER;
-
- // The lowest numbered group corresponds to
- // num_eliminate_blocks e_blocks.
- const map<int, set<double*> >& group_id_to_parameter_block
- = options.ordering_new_api->group_id_to_parameter_blocks();
-
- map<int, set<double*> >::const_iterator it =
- group_id_to_parameter_block.begin();
- CHECK(it != group_id_to_parameter_block.end());
-
- options.num_eliminate_blocks = it->second.size();
- for (; it != group_id_to_parameter_block.end(); ++it) {
- options.ordering.insert(options.ordering.end(),
- it->second.begin(),
- it->second.end());
- }
- CHECK_EQ(options.ordering.size(),
- original_problem_impl->NumParameterBlocks());
- }
- }
- } else {
- CHECK(options.ordering_new_api == NULL);
- }
-
-
Program* original_program = original_problem_impl->mutable_program();
ProblemImpl* problem_impl = original_problem_impl;
// Reset the summary object to its default values.
*CHECK_NOTNULL(summary) = Solver::Summary();
-
#ifndef CERES_USE_OPENMP
if (options.num_threads > 1) {
LOG(WARNING)
@@ -270,25 +231,10 @@
}
#endif
- if (IsSchurType(options.linear_solver_type) &&
- options.ordering_type != SCHUR &&
- options.num_eliminate_blocks < 1) {
- summary->error =
- StringPrintf("Using a Schur type solver with %s"
- " ordering requires that"
- " Solver::Options::num_eliminate_blocks"
- " be set to a positive integer.",
- OrderingTypeToString(options.ordering_type));
- LOG(WARNING) << summary->error;
- return;
- }
-
summary->linear_solver_type_given = options.linear_solver_type;
- summary->num_eliminate_blocks_given = original_options.num_eliminate_blocks;
summary->num_threads_given = original_options.num_threads;
summary->num_linear_solver_threads_given =
original_options.num_linear_solver_threads;
- summary->ordering_type = original_options.ordering_type;
summary->num_parameter_blocks = problem_impl->NumParameterBlocks();
summary->num_parameters = problem_impl->NumParameters();
@@ -301,6 +247,23 @@
summary->trust_region_strategy_type = options.trust_region_strategy_type;
summary->dogleg_type = options.dogleg_type;
+ if (original_options.ordering != NULL) {
+ if (!IsOrderingValid(original_options, problem_impl, &summary->error)) {
+ LOG(WARNING) << summary->error;
+ return;
+ }
+ options.ordering = new Ordering(*original_options.ordering);
+ } else {
+ options.ordering = new Ordering;
+ const ProblemImpl::ParameterMap& parameter_map =
+ problem_impl->parameter_map();
+ for (ProblemImpl::ParameterMap::const_iterator it = parameter_map.begin();
+ it != parameter_map.end();
+ ++it) {
+ options.ordering->AddParameterBlockToGroup(it->first, 0);
+ }
+ }
+
// Evaluate the initial cost, residual vector and the jacobian
// matrix if requested by the user. The initial cost needs to be
// computed on the original unpreprocessed problem, as it is used to
@@ -313,13 +276,14 @@
options.return_initial_residuals ? &summary->initial_residuals : NULL,
options.return_initial_gradient ? &summary->initial_gradient : NULL,
options.return_initial_jacobian ? &summary->initial_jacobian : NULL);
- original_program->SetParameterBlockStatePtrsToUserStatePtrs();
+ original_program->SetParameterBlockStatePtrsToUserStatePtrs();
// If the user requests gradient checking, construct a new
// ProblemImpl by wrapping the CostFunctions of problem_impl inside
// GradientCheckingCostFunction and replacing problem_impl with
// gradient_checking_problem_impl.
scoped_ptr<ProblemImpl> gradient_checking_problem_impl;
+
// Save the original problem impl so we don't use the gradient
// checking one when computing the residuals.
if (options.check_gradients) {
@@ -353,7 +317,6 @@
linear_solver(CreateLinearSolver(&options, &summary->error));
summary->linear_solver_type_used = options.linear_solver_type;
summary->preconditioner_type = options.preconditioner_type;
- summary->num_eliminate_blocks_used = options.num_eliminate_blocks;
summary->num_linear_solver_threads_used = options.num_linear_solver_threads;
if (linear_solver == NULL) {
@@ -421,13 +384,67 @@
WallTimeInSeconds() - post_process_start_time;
}
+bool SolverImpl::IsOrderingValid(const Solver::Options& options,
+ const ProblemImpl* problem_impl,
+ string* error) {
+ if (options.ordering->NumParameterBlocks() !=
+ problem_impl->NumParameterBlocks()) {
+ *error = "Number of parameter blocks in user supplied ordering "
+ "does not match the number of parameter blocks in the problem";
+ return false;
+ }
+
+ const Program& program = problem_impl->program();
+ const vector<ParameterBlock*>& parameter_blocks = program.parameter_blocks();
+ const vector<ResidualBlock*>& residual_blocks = program.residual_blocks();
+ for (vector<ParameterBlock*>::const_iterator it = parameter_blocks.begin();
+ it != parameter_blocks.end();
+ ++it) {
+ if (!options.ordering->ContainsParameterBlock(
+ const_cast<double*>((*it)->user_state()))) {
+ *error = "Problem contains a parameter block that is not in "
+ "the user specified ordering.";
+ return false;
+ }
+ }
+
+ if (IsSchurType(options.linear_solver_type) &&
+ options.ordering->NumGroups() > 1) {
+ const set<double*>& e_blocks =
+ options.ordering->group_id_to_parameter_blocks().begin()->second;
+
+ // Loop over each residual block and ensure that no two parameter
+ // blocks in the same residual block are part of the first
+ // elimination group, as that would violate the assumption that it
+ // is an independent set in the Hessian matrix.
+ for (vector<ResidualBlock*>::const_iterator it = residual_blocks.begin();
+ it != residual_blocks.end();
+ ++it) {
+ ParameterBlock* const* parameter_blocks = (*it)->parameter_blocks();
+ const int num_parameter_blocks = (*it)->NumParameterBlocks();
+ int count = 0;
+ for (int i = 0; i < num_parameter_blocks; ++i) {
+ count += e_blocks.count(const_cast<double*>(
+ parameter_blocks[i]->user_state()));
+ }
+
+ if (count > 1) {
+ *error = "The user requested the use of a Schur type solver. "
+ "But the first elimination group in the ordering is not an "
+ "independent set.";
+ return false;
+ }
+ }
+ }
+ return true;
+}
+
// Strips varying parameters and residuals, maintaining order, and updating
// num_eliminate_blocks.
bool SolverImpl::RemoveFixedBlocksFromProgram(Program* program,
- int* num_eliminate_blocks,
+ Ordering* ordering,
double* fixed_cost,
string* error) {
- int original_num_eliminate_blocks = *num_eliminate_blocks;
vector<ParameterBlock*>* parameter_blocks =
program->mutable_parameter_blocks();
@@ -484,7 +501,7 @@
}
// Filter out unused or fixed parameter blocks, and update
- // num_eliminate_blocks as necessary.
+ // the ordering.
{
vector<ParameterBlock*>* parameter_blocks =
program->mutable_parameter_blocks();
@@ -493,8 +510,8 @@
ParameterBlock* parameter_block = (*parameter_blocks)[i];
if (parameter_block->index() == 1) {
(*parameter_blocks)[j++] = parameter_block;
- } else if (i < original_num_eliminate_blocks) {
- (*num_eliminate_blocks)--;
+ } else {
+ ordering->RemoveParameterBlock(parameter_block->mutable_user_state());
}
}
parameter_blocks->resize(j);
@@ -512,35 +529,17 @@
ProblemImpl* problem_impl,
double* fixed_cost,
string* error) {
+ CHECK_NOTNULL(options->ordering);
Program* original_program = problem_impl->mutable_program();
scoped_ptr<Program> transformed_program(new Program(*original_program));
+ Ordering* ordering = options->ordering;
- if (options->ordering_type == USER &&
- !ApplyUserOrdering(*problem_impl,
- options->ordering,
- transformed_program.get(),
- error)) {
- return NULL;
- }
-
- if (options->ordering_type == SCHUR && options->num_eliminate_blocks != 0) {
- *error = "Can't specify SCHUR ordering and num_eliminate_blocks "
- "at the same time; SCHUR ordering determines "
- "num_eliminate_blocks automatically.";
- return NULL;
- }
-
- if (options->ordering_type == SCHUR && options->ordering.size() != 0) {
- *error = "Can't specify SCHUR ordering type and the ordering "
- "vector at the same time; SCHUR ordering determines "
- "a suitable parameter ordering automatically.";
- return NULL;
- }
-
- int num_eliminate_blocks = options->num_eliminate_blocks;
+ const int min_group_id =
+ ordering->group_id_to_parameter_blocks().begin()->first;
+ const int original_num_groups = ordering->NumGroups();
if (!RemoveFixedBlocksFromProgram(transformed_program.get(),
- &num_eliminate_blocks,
+ ordering,
fixed_cost,
error)) {
return NULL;
@@ -552,21 +551,70 @@
return transformed_program.release();
}
- if (options->ordering_type == SCHUR) {
+ // If the user supplied an ordering with just one group, it is
+ // equivalent to the user supplying NULL as ordering. Ceres is
+ // completely free to choose the parameter block ordering as it sees
+ // fit. For Schur type solvers, this means that the user wishes for
+ // Ceres to identify the e_blocks, which we do by computing a
+ // maximal independent set.
+ if (original_num_groups == 1 &&
+ IsSchurType(options->linear_solver_type)) {
vector<ParameterBlock*> schur_ordering;
- num_eliminate_blocks = ComputeSchurOrdering(*transformed_program,
- &schur_ordering);
+ const int num_eliminate_blocks = ComputeSchurOrdering(*original_program,
+ &schur_ordering);
CHECK_EQ(schur_ordering.size(), transformed_program->NumParameterBlocks())
<< "Congratulations, you found a Ceres bug! Please report this error "
<< "to the developers.";
- // Replace the transformed program's ordering with the schur ordering.
- swap(*transformed_program->mutable_parameter_blocks(), schur_ordering);
+ for (int i = 0; i < schur_ordering.size(); ++i) {
+ ordering->AddParameterBlockToGroup(schur_ordering[i]->mutable_user_state(),
+ (i < num_eliminate_blocks) ? 0 : 1);
+ }
}
- options->num_eliminate_blocks = num_eliminate_blocks;
- CHECK_GE(options->num_eliminate_blocks, 0)
- << "Congratulations, you found a Ceres bug! Please report this error "
- << "to the developers.";
+
+ if (!ApplyUserOrdering(
+ *problem_impl, ordering, transformed_program.get(), error)) {
+ return NULL;
+ }
+
+ // If the user requested the use of a Schur type solver, and
+ // supplied a non-NULL ordering object with more than one
+ // elimimation group, then it can happen that after all the
+ // parameter blocks which are fixed or unused have been removed from
+ // the program and the ordering, there are no more parameter blocks
+ // in the first elimination group.
+ //
+ // In such a case, the use of a Schur type solver is not possible,
+ // as they assume there is at least one e_block. Thus, we
+ // automatically switch to one of the other solvers, depending on
+ // the user's indicated preferences.
+ if (IsSchurType(options->linear_solver_type) &&
+ original_num_groups > 1 &&
+ ordering->GroupSize(min_group_id) == 0) {
+ string msg = "No e_blocks remaining. Switching from ";
+ if (options->linear_solver_type == SPARSE_SCHUR) {
+ options->linear_solver_type = SPARSE_NORMAL_CHOLESKY;
+ msg += "SPARSE_SCHUR to SPARSE_NORMAL_CHOLESKY.";
+ } else if (options->linear_solver_type == DENSE_SCHUR) {
+ // TODO(sameeragarwal): This is probably not a great choice.
+ // Ideally, we should have a DENSE_NORMAL_CHOLESKY, that can
+ // take a BlockSparseMatrix as input.
+ options->linear_solver_type = DENSE_QR;
+ msg += "DENSE_SCHUR to DENSE_QR.";
+ } else if (options->linear_solver_type == ITERATIVE_SCHUR) {
+ msg += StringPrintf("ITERATIVE_SCHUR with %s preconditioner "
+ "to CGNR with JACOBI preconditioner.",
+ PreconditionerTypeToString(
+ options->preconditioner_type));
+ options->linear_solver_type = CGNR;
+ if (options->preconditioner_type != IDENTITY) {
+ // CGNR currently only supports the JACOBI preconditioner.
+ options->preconditioner_type = JACOBI;
+ }
+ }
+
+ LOG(WARNING) << msg;
+ }
// Since the transformed program is the "active" program, and it is mutated,
// update the parameter offsets and indices.
@@ -576,6 +624,10 @@
LinearSolver* SolverImpl::CreateLinearSolver(Solver::Options* options,
string* error) {
+ CHECK_NOTNULL(options);
+ CHECK_NOTNULL(options->ordering);
+ CHECK_NOTNULL(error);
+
if (options->trust_region_strategy_type == DOGLEG) {
if (options->linear_solver_type == ITERATIVE_SCHUR ||
options->linear_solver_type == CGNR) {
@@ -593,6 +645,24 @@
"SuiteSparse was not enabled when Ceres was built.";
return NULL;
}
+
+ if (linear_solver_options.preconditioner_type == SCHUR_JACOBI) {
+ *error = "SCHUR_JACOBI preconditioner not suppored. Please build Ceres "
+ "with SuiteSparse support.";
+ return NULL;
+ }
+
+ if (linear_solver_options.preconditioner_type == CLUSTER_JACOBI) {
+ *error = "CLUSTER_JACOBI preconditioner not suppored. Please build Ceres "
+ "with SuiteSparse support.";
+ return NULL;
+ }
+
+ if (linear_solver_options.preconditioner_type == CLUSTER_TRIDIAGONAL) {
+ *error = "CLUSTER_TRIDIAGONAL preconditioner not suppored. Please build "
+ "Ceres with SuiteSparse support.";
+ return NULL;
+ }
#endif
#ifdef CERES_NO_CXSPARSE
@@ -604,6 +674,13 @@
}
#endif
+#if defined(CERES_NO_SUITESPARSE) && defined(CERES_NO_CXSPARSE)
+ if (linear_solver_options.type == SPARSE_SCHUR) {
+ *error = "Can't use SPARSE_SCHUR because neither SuiteSparse nor"
+ "CXSparse was enabled when Ceres was compiled.";
+ return NULL;
+ }
+#endif
if (options->linear_solver_max_num_iterations <= 0) {
*error = "Solver::Options::linear_solver_max_num_iterations is 0.";
@@ -629,61 +706,8 @@
linear_solver_options.preconditioner_type = options->preconditioner_type;
linear_solver_options.sparse_linear_algebra_library =
options->sparse_linear_algebra_library;
- linear_solver_options.use_block_amd = options->use_block_amd;
-
-#ifdef CERES_NO_SUITESPARSE
- if (linear_solver_options.preconditioner_type == SCHUR_JACOBI) {
- *error = "SCHUR_JACOBI preconditioner not suppored. Please build Ceres "
- "with SuiteSparse support.";
- return NULL;
- }
-
- if (linear_solver_options.preconditioner_type == CLUSTER_JACOBI) {
- *error = "CLUSTER_JACOBI preconditioner not suppored. Please build Ceres "
- "with SuiteSparse support.";
- return NULL;
- }
-
- if (linear_solver_options.preconditioner_type == CLUSTER_TRIDIAGONAL) {
- *error = "CLUSTER_TRIDIAGONAL preconditioner not suppored. Please build "
- "Ceres with SuiteSparse support.";
- return NULL;
- }
-#endif
linear_solver_options.num_threads = options->num_linear_solver_threads;
- if (options->num_eliminate_blocks > 0) {
- linear_solver_options
- .elimination_groups.push_back(options->num_eliminate_blocks);
- }
-
- // TODO(sameeragarwal): Fix this. Right now these are dummy values
- // and violate the contract that elimination_groups should sum to
- // the number of parameter blocks, but fixing this requires a bit
- // more refactoring in solver_impl.cc, which is better done as we
- // start deprecating the old API.
- linear_solver_options.elimination_groups.push_back(1);
-
- if (linear_solver_options.elimination_groups.size() == 1 &&
- IsSchurType(linear_solver_options.type)) {
-#if defined(CERES_NO_SUITESPARSE) && defined(CERES_NO_CXSPARSE)
- LOG(INFO) << "No elimination block remaining switching to DENSE_QR.";
- linear_solver_options.type = DENSE_QR;
-#else
- LOG(INFO) << "No elimination block remaining "
- << "switching to SPARSE_NORMAL_CHOLESKY.";
- linear_solver_options.type = SPARSE_NORMAL_CHOLESKY;
-#endif
- }
-
-#if defined(CERES_NO_SUITESPARSE) && defined(CERES_NO_CXSPARSE)
- if (linear_solver_options.type == SPARSE_SCHUR) {
- *error = "Can't use SPARSE_SCHUR because neither SuiteSparse nor"
- "CXSparse was enabled when Ceres was compiled.";
- return NULL;
- }
-#endif
-
// The matrix used for storing the dense Schur complement has a
// single lock guarding the whole matrix. Running the
// SchurComplementSolver with multiple threads leads to maximum
@@ -698,56 +722,68 @@
<< "switching to single-threaded.";
linear_solver_options.num_threads = 1;
}
-
- options->linear_solver_type = linear_solver_options.type;
options->num_linear_solver_threads = linear_solver_options.num_threads;
+ linear_solver_options.use_block_amd = options->use_block_amd;
+ const map<int, set<double*> >& groups =
+ options->ordering->group_id_to_parameter_blocks();
+ for (map<int, set<double*> >::const_iterator it = groups.begin();
+ it != groups.end();
+ ++it) {
+ linear_solver_options.elimination_groups.push_back(it->second.size());
+ }
+ // Schur type solvers, expect at least two elimination groups. If
+ // there is only one elimination group, then CreateReducedProblem
+ // guarantees that this group only contains e_blocks. Thus we add a
+ // dummy elimination group with zero blocks in it.
+ if (IsSchurType(linear_solver_options.type) &&
+ linear_solver_options.elimination_groups.size() == 1) {
+ linear_solver_options.elimination_groups.push_back(0);
+ }
+
return LinearSolver::Create(linear_solver_options);
}
bool SolverImpl::ApplyUserOrdering(const ProblemImpl& problem_impl,
- vector<double*>& ordering,
+ const Ordering* ordering,
Program* program,
string* error) {
- if (ordering.size() != program->NumParameterBlocks()) {
+ if (ordering->NumParameterBlocks() != program->NumParameterBlocks()) {
*error = StringPrintf("User specified ordering does not have the same "
"number of parameters as the problem. The problem"
- "has %d blocks while the ordering has %ld blocks.",
+ "has %d blocks while the ordering has %d blocks.",
program->NumParameterBlocks(),
- ordering.size());
+ ordering->NumParameterBlocks());
return false;
}
- // Ensure that there are no duplicates in the user's ordering.
- {
- vector<double*> ordering_copy(ordering);
- sort(ordering_copy.begin(), ordering_copy.end());
- if (unique(ordering_copy.begin(), ordering_copy.end())
- != ordering_copy.end()) {
- *error = "User specified ordering contains duplicates.";
- return false;
- }
- }
-
vector<ParameterBlock*>* parameter_blocks =
program->mutable_parameter_blocks();
+ parameter_blocks->clear();
- fill(parameter_blocks->begin(),
- parameter_blocks->end(),
- static_cast<ParameterBlock*>(NULL));
+ const ProblemImpl::ProblemImpl::ParameterMap& parameter_map =
+ problem_impl.parameter_map();
+ const map<int, set<double*> >& groups =
+ ordering->group_id_to_parameter_blocks();
- const ProblemImpl::ParameterMap& parameter_map = problem_impl.parameter_map();
- for (int i = 0; i < ordering.size(); ++i) {
- ProblemImpl::ParameterMap::const_iterator it =
- parameter_map.find(ordering[i]);
- if (it == parameter_map.end()) {
- *error = StringPrintf("User specified ordering contains a pointer "
- "to a double that is not a parameter block in the "
- "problem. The invalid double is at position %d "
- " in options.ordering.", i);
- return false;
+ for (map<int, set<double*> >::const_iterator group_it = groups.begin();
+ group_it != groups.end();
+ ++group_it) {
+ const set<double*>& group = group_it->second;
+ for (set<double*>::const_iterator parameter_block_ptr_it = group.begin();
+ parameter_block_ptr_it != group.end();
+ ++parameter_block_ptr_it) {
+ ProblemImpl::ParameterMap::const_iterator parameter_block_it =
+ parameter_map.find(*parameter_block_ptr_it);
+ if (parameter_block_it == parameter_map.end()) {
+ *error = StringPrintf("User specified ordering contains a pointer "
+ "to a double that is not a parameter block in the "
+ "problem. The invalid double is in group: %d",
+ group_it->first);
+ return false;
+ }
+ parameter_blocks->push_back(parameter_block_it->second);
}
- (*parameter_blocks)[i] = it->second;
}
return true;
}
@@ -782,28 +818,26 @@
return true;
}
- CHECK_NE(0, options.num_eliminate_blocks)
- << "Congratulations, you found a Ceres bug! Please report this error "
- << "to the developers.";
+ const int num_eliminate_blocks =
+ options.ordering->group_id_to_parameter_blocks().begin()->second.size();
// Create a histogram of the number of residuals for each E block. There is an
// extra bucket at the end to catch all non-eliminated F blocks.
- vector<int> residual_blocks_per_e_block(options.num_eliminate_blocks + 1);
+ vector<int> residual_blocks_per_e_block(num_eliminate_blocks + 1);
vector<ResidualBlock*>* residual_blocks = program->mutable_residual_blocks();
vector<int> min_position_per_residual(residual_blocks->size());
for (int i = 0; i < residual_blocks->size(); ++i) {
ResidualBlock* residual_block = (*residual_blocks)[i];
- int position = MinParameterBlock(residual_block,
- options.num_eliminate_blocks);
+ int position = MinParameterBlock(residual_block, num_eliminate_blocks);
min_position_per_residual[i] = position;
- DCHECK_LE(position, options.num_eliminate_blocks);
+ DCHECK_LE(position, num_eliminate_blocks);
residual_blocks_per_e_block[position]++;
}
// Run a cumulative sum on the histogram, to obtain offsets to the start of
// each histogram bucket (where each bucket is for the residuals for that
// E-block).
- vector<int> offsets(options.num_eliminate_blocks + 1);
+ vector<int> offsets(num_eliminate_blocks + 1);
std::partial_sum(residual_blocks_per_e_block.begin(),
residual_blocks_per_e_block.end(),
offsets.begin());
@@ -842,7 +876,7 @@
// Sanity check #1: The difference in bucket offsets should match the
// histogram sizes.
- for (int i = 0; i < options.num_eliminate_blocks; ++i) {
+ for (int i = 0; i < num_eliminate_blocks; ++i) {
CHECK_EQ(residual_blocks_per_e_block[i], offsets[i + 1] - offsets[i])
<< "Congratulations, you found a Ceres bug! Please report this error "
<< "to the developers.";
@@ -864,7 +898,12 @@
string* error) {
Evaluator::Options evaluator_options;
evaluator_options.linear_solver_type = options.linear_solver_type;
- evaluator_options.num_eliminate_blocks = options.num_eliminate_blocks;
+
+ evaluator_options.num_eliminate_blocks =
+ (options.ordering->NumGroups() > 0 &&
+ IsSchurType(options.linear_solver_type))
+ ? options.ordering->group_id_to_parameter_blocks().begin()->second.size()
+ : 0;
evaluator_options.num_threads = options.num_threads;
return Evaluator::Create(evaluator_options, program, error);
}
diff --git a/internal/ceres/solver_impl.h b/internal/ceres/solver_impl.h
index 11b44de..076a371 100644
--- a/internal/ceres/solver_impl.h
+++ b/internal/ceres/solver_impl.h
@@ -37,6 +37,8 @@
#include "ceres/solver.h"
namespace ceres {
+class Ordering;
+
namespace internal {
class Evaluator;
@@ -76,7 +78,7 @@
// indicates an error was encountered whose cause is logged to
// LOG(ERROR).
static bool ApplyUserOrdering(const ProblemImpl& problem_impl,
- vector<double*>& ordering,
+ const Ordering* ordering,
Program* program,
string* error);
@@ -108,9 +110,13 @@
// If fixed_cost is not NULL, the residual blocks that are removed
// are evaluated and the sum of their cost is returned in fixed_cost.
static bool RemoveFixedBlocksFromProgram(Program* program,
- int* num_eliminate_blocks,
+ Ordering* ordering,
double* fixed_cost,
string* error);
+
+ static bool IsOrderingValid(const Solver::Options& options,
+ const ProblemImpl* problem_impl,
+ string* error);
};
} // namespace internal
diff --git a/internal/ceres/solver_impl_test.cc b/internal/ceres/solver_impl_test.cc
index 7d7740a..a19fca0 100644
--- a/internal/ceres/solver_impl_test.cc
+++ b/internal/ceres/solver_impl_test.cc
@@ -31,6 +31,7 @@
#include "gtest/gtest.h"
#include "ceres/autodiff_cost_function.h"
#include "ceres/linear_solver.h"
+#include "ceres/ordering.h"
#include "ceres/parameter_block.h"
#include "ceres/problem_impl.h"
#include "ceres/program.h"
@@ -87,29 +88,19 @@
string error;
{
- int num_eliminate_blocks = 0;
+ Ordering ordering;
+ ordering.AddParameterBlockToGroup(&x, 0);
+ ordering.AddParameterBlockToGroup(&y, 0);
+ ordering.AddParameterBlockToGroup(&z, 0);
+
Program program(*problem.mutable_program());
EXPECT_TRUE(SolverImpl::RemoveFixedBlocksFromProgram(&program,
- &num_eliminate_blocks,
+ &ordering,
NULL,
&error));
EXPECT_EQ(program.NumParameterBlocks(), 3);
EXPECT_EQ(program.NumResidualBlocks(), 3);
- EXPECT_EQ(num_eliminate_blocks, 0);
- }
-
- // Check that num_eliminate_blocks is preserved, when it contains
- // all blocks.
- {
- int num_eliminate_blocks = 3;
- Program program(problem.program());
- EXPECT_TRUE(SolverImpl::RemoveFixedBlocksFromProgram(&program,
- &num_eliminate_blocks,
- NULL,
- &error));
- EXPECT_EQ(program.NumParameterBlocks(), 3);
- EXPECT_EQ(program.NumResidualBlocks(), 3);
- EXPECT_EQ(num_eliminate_blocks, 3);
+ EXPECT_EQ(ordering.NumParameterBlocks(), 3);
}
}
@@ -121,16 +112,18 @@
problem.AddResidualBlock(new UnaryCostFunction(), NULL, &x);
problem.SetParameterBlockConstant(&x);
- int num_eliminate_blocks = 0;
+ Ordering ordering;
+ ordering.AddParameterBlockToGroup(&x, 0);
+
Program program(problem.program());
string error;
EXPECT_TRUE(SolverImpl::RemoveFixedBlocksFromProgram(&program,
- &num_eliminate_blocks,
+ &ordering,
NULL,
&error));
EXPECT_EQ(program.NumParameterBlocks(), 0);
EXPECT_EQ(program.NumResidualBlocks(), 0);
- EXPECT_EQ(num_eliminate_blocks, 0);
+ EXPECT_EQ(ordering.NumParameterBlocks(), 0);
}
TEST(SolverImpl, RemoveFixedBlocksNoResidualBlocks) {
@@ -143,16 +136,21 @@
problem.AddParameterBlock(&y, 1);
problem.AddParameterBlock(&z, 1);
- int num_eliminate_blocks = 0;
+ Ordering ordering;
+ ordering.AddParameterBlockToGroup(&x, 0);
+ ordering.AddParameterBlockToGroup(&y, 0);
+ ordering.AddParameterBlockToGroup(&z, 0);
+
+
Program program(problem.program());
string error;
EXPECT_TRUE(SolverImpl::RemoveFixedBlocksFromProgram(&program,
- &num_eliminate_blocks,
+ &ordering,
NULL,
&error));
EXPECT_EQ(program.NumParameterBlocks(), 0);
EXPECT_EQ(program.NumResidualBlocks(), 0);
- EXPECT_EQ(num_eliminate_blocks, 0);
+ EXPECT_EQ(ordering.NumParameterBlocks(), 0);
}
TEST(SolverImpl, RemoveFixedBlocksOneParameterBlockConstant) {
@@ -164,20 +162,26 @@
problem.AddParameterBlock(&x, 1);
problem.AddParameterBlock(&y, 1);
problem.AddParameterBlock(&z, 1);
+
+ Ordering ordering;
+ ordering.AddParameterBlockToGroup(&x, 0);
+ ordering.AddParameterBlockToGroup(&y, 0);
+ ordering.AddParameterBlockToGroup(&z, 0);
+
problem.AddResidualBlock(new UnaryCostFunction(), NULL, &x);
problem.AddResidualBlock(new BinaryCostFunction(), NULL, &x, &y);
problem.SetParameterBlockConstant(&x);
- int num_eliminate_blocks = 0;
+
Program program(problem.program());
string error;
EXPECT_TRUE(SolverImpl::RemoveFixedBlocksFromProgram(&program,
- &num_eliminate_blocks,
+ &ordering,
NULL,
&error));
EXPECT_EQ(program.NumParameterBlocks(), 1);
EXPECT_EQ(program.NumResidualBlocks(), 1);
- EXPECT_EQ(num_eliminate_blocks, 0);
+ EXPECT_EQ(ordering.NumParameterBlocks(), 1);
}
TEST(SolverImpl, RemoveFixedBlocksNumEliminateBlocks) {
@@ -194,16 +198,22 @@
problem.AddResidualBlock(new BinaryCostFunction(), NULL, &x, &y);
problem.SetParameterBlockConstant(&x);
- int num_eliminate_blocks = 2;
+ Ordering ordering;
+ ordering.AddParameterBlockToGroup(&x, 0);
+ ordering.AddParameterBlockToGroup(&y, 0);
+ ordering.AddParameterBlockToGroup(&z, 1);
+
Program program(problem.program());
string error;
EXPECT_TRUE(SolverImpl::RemoveFixedBlocksFromProgram(&program,
- &num_eliminate_blocks,
+ &ordering,
NULL,
&error));
EXPECT_EQ(program.NumParameterBlocks(), 2);
EXPECT_EQ(program.NumResidualBlocks(), 2);
- EXPECT_EQ(num_eliminate_blocks, 1);
+ EXPECT_EQ(ordering.NumParameterBlocks(), 2);
+ EXPECT_EQ(ordering.GroupIdForParameterBlock(&y), 0);
+ EXPECT_EQ(ordering.GroupIdForParameterBlock(&z), 1);
}
TEST(SolverImpl, RemoveFixedBlocksFixedCost) {
@@ -220,7 +230,11 @@
problem.AddResidualBlock(new BinaryCostFunction(), NULL, &x, &y);
problem.SetParameterBlockConstant(&x);
- int num_eliminate_blocks = 2;
+ Ordering ordering;
+ ordering.AddParameterBlockToGroup(&x, 0);
+ ordering.AddParameterBlockToGroup(&y, 0);
+ ordering.AddParameterBlockToGroup(&z, 1);
+
double fixed_cost = 0.0;
Program program(problem.program());
@@ -231,12 +245,14 @@
string error;
EXPECT_TRUE(SolverImpl::RemoveFixedBlocksFromProgram(&program,
- &num_eliminate_blocks,
+ &ordering,
&fixed_cost,
&error));
EXPECT_EQ(program.NumParameterBlocks(), 2);
EXPECT_EQ(program.NumResidualBlocks(), 2);
- EXPECT_EQ(num_eliminate_blocks, 1);
+ EXPECT_EQ(ordering.NumParameterBlocks(), 2);
+ EXPECT_EQ(ordering.GroupIdForParameterBlock(&y), 0);
+ EXPECT_EQ(ordering.GroupIdForParameterBlock(&z), 1);
EXPECT_DOUBLE_EQ(fixed_cost, expected_fixed_cost);
}
@@ -253,6 +269,11 @@
problem.AddResidualBlock(new TernaryCostFunction(), NULL, &x, &y, &z);
problem.AddResidualBlock(new BinaryCostFunction(), NULL, &x, &y);
+ Ordering ordering;
+ ordering.AddParameterBlockToGroup(&x, 0);
+ ordering.AddParameterBlockToGroup(&y, 0);
+ ordering.AddParameterBlockToGroup(&z, 0);
+
const vector<ResidualBlock*>& residual_blocks =
problem.program().residual_blocks();
vector<ResidualBlock*> current_residual_blocks(residual_blocks);
@@ -270,31 +291,6 @@
}
}
-TEST(SolverImpl, ReorderResidualBlockNumEliminateBlockDeathTest) {
- ProblemImpl problem;
- double x;
- double y;
- double z;
-
- problem.AddParameterBlock(&x, 1);
- problem.AddParameterBlock(&y, 1);
- problem.AddParameterBlock(&z, 1);
- problem.AddResidualBlock(new UnaryCostFunction(), NULL, &x);
- problem.AddResidualBlock(new TernaryCostFunction(), NULL, &x, &y, &z);
- problem.AddResidualBlock(new BinaryCostFunction(), NULL, &x, &y);
-
- Solver::Options options;
- options.linear_solver_type = DENSE_SCHUR;
- options.num_eliminate_blocks = 0;
- string error;
-#ifndef _WIN32
- EXPECT_DEATH(
- SolverImpl::MaybeReorderResidualBlocks(
- options, problem.mutable_program(), &error),
- "Congratulations");
-#endif // _WIN32
-}
-
TEST(SolverImpl, ReorderResidualBlockNormalFunction) {
ProblemImpl problem;
double x;
@@ -312,9 +308,14 @@
problem.AddResidualBlock(new BinaryCostFunction(), NULL, &x, &y);
problem.AddResidualBlock(new UnaryCostFunction(), NULL, &y);
+ Ordering* ordering = new Ordering;
+ ordering->AddParameterBlockToGroup(&x, 0);
+ ordering->AddParameterBlockToGroup(&y, 0);
+ ordering->AddParameterBlockToGroup(&z, 1);
+
Solver::Options options;
options.linear_solver_type = DENSE_SCHUR;
- options.num_eliminate_blocks = 2;
+ options.ordering = ordering;
const vector<ResidualBlock*>& residual_blocks =
problem.program().residual_blocks();
@@ -368,9 +369,14 @@
problem.AddResidualBlock(new BinaryCostFunction(), NULL, &x, &z); // 6 x
problem.AddResidualBlock(new UnaryCostFunction(), NULL, &y); // 7
+ Ordering* ordering = new Ordering;
+ ordering->AddParameterBlockToGroup(&x, 0);
+ ordering->AddParameterBlockToGroup(&z, 0);
+ ordering->AddParameterBlockToGroup(&y, 1);
+
Solver::Options options;
options.linear_solver_type = DENSE_SCHUR;
- options.num_eliminate_blocks = 2;
+ options.ordering = ordering;
// Create the reduced program. This should remove the fixed block "z",
// marking the index to -1 at the same time. x and y also get indices.
@@ -423,42 +429,18 @@
problem.AddParameterBlock(&y, 1);
problem.AddParameterBlock(&z, 1);
- vector<double*> ordering;
- ordering.push_back(&x);
- ordering.push_back(&z);
+ Ordering ordering;
+ ordering.AddParameterBlockToGroup(&x, 0);
+ ordering.AddParameterBlockToGroup(&y, 1);
Program program(problem.program());
string error;
EXPECT_FALSE(SolverImpl::ApplyUserOrdering(problem,
- ordering,
+ &ordering,
&program,
&error));
}
-TEST(SolverImpl, ApplyUserOrderingHasDuplicates) {
- ProblemImpl problem;
- double x;
- double y;
- double z;
-
- problem.AddParameterBlock(&x, 1);
- problem.AddParameterBlock(&y, 1);
- problem.AddParameterBlock(&z, 1);
-
- vector<double*> ordering;
- ordering.push_back(&x);
- ordering.push_back(&z);
- ordering.push_back(&z);
-
- Program program(problem.program());
- string error;
- EXPECT_FALSE(SolverImpl::ApplyUserOrdering(problem,
- ordering,
- &program,
- &error));
-}
-
-
TEST(SolverImpl, ApplyUserOrderingNormal) {
ProblemImpl problem;
double x;
@@ -469,16 +451,16 @@
problem.AddParameterBlock(&y, 1);
problem.AddParameterBlock(&z, 1);
- vector<double*> ordering;
- ordering.push_back(&x);
- ordering.push_back(&z);
- ordering.push_back(&y);
+ Ordering ordering;
+ ordering.AddParameterBlockToGroup(&x, 0);
+ ordering.AddParameterBlockToGroup(&y, 2);
+ ordering.AddParameterBlockToGroup(&z, 1);
Program* program = problem.mutable_program();
string error;
EXPECT_TRUE(SolverImpl::ApplyUserOrdering(problem,
- ordering,
+ &ordering,
program,
&error));
const vector<ParameterBlock*>& parameter_blocks = program->parameter_blocks();
@@ -502,6 +484,8 @@
Solver::Options options;
options.linear_solver_type = DENSE_QR;
options.linear_solver_max_num_iterations = -1;
+ // CreateLinearSolver assumes a non-empty ordering.
+ options.ordering = new Ordering;
string error;
EXPECT_EQ(SolverImpl::CreateLinearSolver(&options, &error),
static_cast<LinearSolver*>(NULL));
@@ -511,6 +495,8 @@
Solver::Options options;
options.linear_solver_type = DENSE_QR;
options.linear_solver_min_num_iterations = -1;
+ // CreateLinearSolver assumes a non-empty ordering.
+ options.ordering = new Ordering;
string error;
EXPECT_EQ(SolverImpl::CreateLinearSolver(&options, &error),
static_cast<LinearSolver*>(NULL));
@@ -521,44 +507,24 @@
options.linear_solver_type = DENSE_QR;
options.linear_solver_min_num_iterations = 10;
options.linear_solver_max_num_iterations = 5;
+ options.ordering = new Ordering;
string error;
EXPECT_EQ(SolverImpl::CreateLinearSolver(&options, &error),
static_cast<LinearSolver*>(NULL));
}
-TEST(SolverImpl, CreateLinearSolverZeroNumEliminateBlocks) {
- Solver::Options options;
- options.num_eliminate_blocks = 0;
- options.linear_solver_type = DENSE_SCHUR;
- string error;
- scoped_ptr<LinearSolver> solver(
- SolverImpl::CreateLinearSolver(&options, &error));
- EXPECT_TRUE(solver != NULL);
-
-#if defined(CERES_NO_SUITESPARSE) && defined(CERES_NO_CXSPARSE)
- EXPECT_EQ(options.linear_solver_type, DENSE_QR);
-#else
- EXPECT_EQ(options.linear_solver_type, SPARSE_NORMAL_CHOLESKY);
-#endif
-}
-
-TEST(SolverImpl, ZeroNumEliminateBlocks) {
- Solver::Options options;
- options.num_eliminate_blocks = 0;
- options.linear_solver_type = DENSE_SCHUR;
- options.ordering_type = NATURAL;
- ProblemImpl problem;
- Solver::Summary summary;
- SolverImpl::Solve(options, &problem, &summary);
- EXPECT_EQ(summary.termination_type, DID_NOT_RUN);
- EXPECT_EQ(summary.error.substr(0,25), "Using a Schur type solver");
-}
-
TEST(SolverImpl, CreateLinearSolverDenseSchurMultipleThreads) {
Solver::Options options;
- options.num_eliminate_blocks = 1;
options.linear_solver_type = DENSE_SCHUR;
options.num_linear_solver_threads = 2;
+ // The Schur type solvers can only be created with the Ordering
+ // contains at least one elimination group.
+ options.ordering = new Ordering;
+ double x;
+ double y;
+ options.ordering->AddParameterBlockToGroup(&x, 0);
+ options.ordering->AddParameterBlockToGroup(&y, 0);
+
string error;
scoped_ptr<LinearSolver> solver(
SolverImpl::CreateLinearSolver(&options, &error));
@@ -570,6 +536,8 @@
TEST(SolverImpl, CreateIterativeLinearSolverForDogleg) {
Solver::Options options;
options.trust_region_strategy_type = DOGLEG;
+ // CreateLinearSolver assumes a non-empty ordering.
+ options.ordering = new Ordering;
string error;
options.linear_solver_type = ITERATIVE_SCHUR;
EXPECT_EQ(SolverImpl::CreateLinearSolver(&options, &error),
@@ -584,6 +552,8 @@
Solver::Options options;
scoped_ptr<LinearSolver> solver;
options.linear_solver_type = DENSE_QR;
+ // CreateLinearSolver assumes a non-empty ordering.
+ options.ordering = new Ordering;
string error;
solver.reset(SolverImpl::CreateLinearSolver(&options, &error));
EXPECT_EQ(options.linear_solver_type, DENSE_QR);
@@ -610,14 +580,17 @@
EXPECT_TRUE(solver.get() != NULL);
#endif
+ double x;
+ double y;
+ options.ordering->AddParameterBlockToGroup(&x, 0);
+ options.ordering->AddParameterBlockToGroup(&y, 0);
+
options.linear_solver_type = DENSE_SCHUR;
- options.num_eliminate_blocks = 2;
solver.reset(SolverImpl::CreateLinearSolver(&options, &error));
EXPECT_EQ(options.linear_solver_type, DENSE_SCHUR);
EXPECT_TRUE(solver.get() != NULL);
options.linear_solver_type = SPARSE_SCHUR;
- options.num_eliminate_blocks = 2;
solver.reset(SolverImpl::CreateLinearSolver(&options, &error));
#if defined(CERES_NO_SUITESPARSE) && defined(CERES_NO_CXSPARSE)
@@ -628,7 +601,6 @@
#endif
options.linear_solver_type = ITERATIVE_SCHUR;
- options.num_eliminate_blocks = 2;
solver.reset(SolverImpl::CreateLinearSolver(&options, &error));
EXPECT_EQ(options.linear_solver_type, ITERATIVE_SCHUR);
EXPECT_TRUE(solver.get() != NULL);
diff --git a/internal/ceres/system_test.cc b/internal/ceres/system_test.cc
index 3dfbc00..4d78de7 100644
--- a/internal/ceres/system_test.cc
+++ b/internal/ceres/system_test.cc
@@ -44,6 +44,7 @@
#include <string>
#include "ceres/autodiff_cost_function.h"
+#include "ceres/ordering.h"
#include "ceres/problem.h"
#include "ceres/rotation.h"
#include "ceres/solver.h"
@@ -57,28 +58,30 @@
namespace ceres {
namespace internal {
+const bool kAutomaticOrdering = true;
+const bool kUserOrdering = false;
+
// Struct used for configuring the solver.
struct SolverConfig {
SolverConfig(LinearSolverType linear_solver_type,
SparseLinearAlgebraLibraryType sparse_linear_algebra_library,
- OrderingType ordering_type)
+ bool use_automatic_ordering)
: linear_solver_type(linear_solver_type),
sparse_linear_algebra_library(sparse_linear_algebra_library),
- ordering_type(ordering_type),
+ use_automatic_ordering(use_automatic_ordering),
preconditioner_type(IDENTITY),
num_threads(1) {
}
SolverConfig(LinearSolverType linear_solver_type,
SparseLinearAlgebraLibraryType sparse_linear_algebra_library,
- OrderingType ordering_type,
- PreconditionerType preconditioner_type,
- int num_threads)
+ bool use_automatic_ordering,
+ PreconditionerType preconditioner_type)
: linear_solver_type(linear_solver_type),
sparse_linear_algebra_library(sparse_linear_algebra_library),
- ordering_type(ordering_type),
+ use_automatic_ordering(use_automatic_ordering),
preconditioner_type(preconditioner_type),
- num_threads(num_threads) {
+ num_threads(1) {
}
string ToString() const {
@@ -86,14 +89,14 @@
"(%s, %s, %s, %s, %d)",
LinearSolverTypeToString(linear_solver_type),
SparseLinearAlgebraLibraryTypeToString(sparse_linear_algebra_library),
- OrderingTypeToString(ordering_type),
+ use_automatic_ordering ? "AUTOMATIC" : "USER",
PreconditionerTypeToString(preconditioner_type),
num_threads);
}
LinearSolverType linear_solver_type;
SparseLinearAlgebraLibraryType sparse_linear_algebra_library;
- OrderingType ordering_type;
+ bool use_automatic_ordering;
PreconditionerType preconditioner_type;
int num_threads;
};
@@ -129,18 +132,14 @@
options.linear_solver_type = config.linear_solver_type;
options.sparse_linear_algebra_library =
config.sparse_linear_algebra_library;
- options.ordering_type = config.ordering_type;
options.preconditioner_type = config.preconditioner_type;
options.num_threads = config.num_threads;
options.num_linear_solver_threads = config.num_threads;
options.return_final_residuals = true;
- if (options.ordering_type == SCHUR || options.ordering_type == NATURAL) {
- options.ordering.clear();
- }
-
- if (options.ordering_type == SCHUR) {
- options.num_eliminate_blocks = 0;
+ if (config.use_automatic_ordering) {
+ delete options.ordering;
+ options.ordering = NULL;
}
LOG(INFO) << "Running solver configuration: "
@@ -279,21 +278,19 @@
sparse_linear_algebra_library, \
ordering))
- CONFIGURE(DENSE_QR, SUITE_SPARSE, NATURAL);
- CONFIGURE(DENSE_NORMAL_CHOLESKY, SUITE_SPARSE, NATURAL);
- CONFIGURE(DENSE_SCHUR, SUITE_SPARSE, SCHUR);
+ CONFIGURE(DENSE_QR, SUITE_SPARSE, kAutomaticOrdering);
+ CONFIGURE(DENSE_NORMAL_CHOLESKY, SUITE_SPARSE, kAutomaticOrdering);
+ CONFIGURE(DENSE_SCHUR, SUITE_SPARSE, kAutomaticOrdering);
#ifndef CERES_NO_SUITESPARSE
- CONFIGURE(SPARSE_NORMAL_CHOLESKY, SUITE_SPARSE, NATURAL);
- CONFIGURE(SPARSE_NORMAL_CHOLESKY, SUITE_SPARSE, SCHUR);
+ CONFIGURE(SPARSE_NORMAL_CHOLESKY, SUITE_SPARSE, kAutomaticOrdering);
#endif // CERES_NO_SUITESPARSE
#ifndef CERES_NO_CXSPARSE
- CONFIGURE(SPARSE_NORMAL_CHOLESKY, CX_SPARSE, NATURAL);
- CONFIGURE(SPARSE_NORMAL_CHOLESKY, CX_SPARSE, SCHUR);
+ CONFIGURE(SPARSE_NORMAL_CHOLESKY, CX_SPARSE, kAutomaticOrdering);
#endif // CERES_NO_CXSPARSE
- CONFIGURE(ITERATIVE_SCHUR, SUITE_SPARSE, SCHUR);
+ CONFIGURE(ITERATIVE_SCHUR, SUITE_SPARSE, kAutomaticOrdering);
#undef CONFIGURE
@@ -390,16 +387,17 @@
problem_.AddResidualBlock(cost_function, NULL, camera, point);
}
+ options_.ordering = new Ordering;
+
// The points come before the cameras.
for (int i = 0; i < num_points_; ++i) {
- options_.ordering.push_back(points + 3 * i);
+ options_.ordering->AddParameterBlockToGroup(points + 3 * i, 0);
}
for (int i = 0; i < num_cameras_; ++i) {
- options_.ordering.push_back(cameras + 9 * i);
+ options_.ordering->AddParameterBlockToGroup(cameras + 9 * i, 1);
}
- options_.num_eliminate_blocks = num_points();
options_.max_num_iterations = 25;
options_.function_tolerance = 1e-10;
options_.gradient_tolerance = 1e-10;
@@ -479,46 +477,43 @@
TEST(SystemTest, BundleAdjustmentProblem) {
vector<SolverConfig> configs;
-#define CONFIGURE(linear_solver, sparse_linear_algebra_library, ordering, preconditioner, threads) \
+#define CONFIGURE(linear_solver, sparse_linear_algebra_library, ordering, preconditioner) \
configs.push_back(SolverConfig(linear_solver, \
sparse_linear_algebra_library, \
ordering, \
- preconditioner, \
- threads))
+ preconditioner))
#ifndef CERES_NO_SUITESPARSE
- CONFIGURE(SPARSE_NORMAL_CHOLESKY, SUITE_SPARSE, NATURAL, IDENTITY, 1);
- CONFIGURE(SPARSE_NORMAL_CHOLESKY, SUITE_SPARSE, USER, IDENTITY, 1);
- CONFIGURE(SPARSE_NORMAL_CHOLESKY, SUITE_SPARSE, SCHUR, IDENTITY, 1);
+ CONFIGURE(SPARSE_NORMAL_CHOLESKY, SUITE_SPARSE, kAutomaticOrdering, IDENTITY);
+ CONFIGURE(SPARSE_NORMAL_CHOLESKY, SUITE_SPARSE, kUserOrdering, IDENTITY);
- CONFIGURE(SPARSE_SCHUR, SUITE_SPARSE, USER, IDENTITY, 1);
- CONFIGURE(SPARSE_SCHUR, SUITE_SPARSE, SCHUR, IDENTITY, 1);
+ CONFIGURE(SPARSE_SCHUR, SUITE_SPARSE, kAutomaticOrdering, IDENTITY);
+ CONFIGURE(SPARSE_SCHUR, SUITE_SPARSE, kUserOrdering, IDENTITY);
#endif // CERES_NO_SUITESPARSE
#ifndef CERES_NO_CXSPARSE
- CONFIGURE(SPARSE_SCHUR, CX_SPARSE, USER, IDENTITY, 1);
- CONFIGURE(SPARSE_SCHUR, CX_SPARSE, SCHUR, IDENTITY, 1);
+ CONFIGURE(SPARSE_SCHUR, CX_SPARSE, kAutomaticOrdering, IDENTITY);
+ CONFIGURE(SPARSE_SCHUR, CX_SPARSE, kUserOrdering, IDENTITY);
#endif // CERES_NO_CXSPARSE
- CONFIGURE(DENSE_SCHUR, SUITE_SPARSE, USER, IDENTITY, 1);
- CONFIGURE(DENSE_SCHUR, SUITE_SPARSE, SCHUR, IDENTITY, 1);
+ CONFIGURE(DENSE_SCHUR, SUITE_SPARSE, kAutomaticOrdering, IDENTITY);
+ CONFIGURE(DENSE_SCHUR, SUITE_SPARSE, kUserOrdering, IDENTITY);
- CONFIGURE(CGNR, SUITE_SPARSE, USER, JACOBI, 1);
-
- CONFIGURE(ITERATIVE_SCHUR, SUITE_SPARSE, USER, JACOBI, 1);
+ CONFIGURE(CGNR, SUITE_SPARSE, kAutomaticOrdering, JACOBI);
+ CONFIGURE(ITERATIVE_SCHUR, SUITE_SPARSE, kUserOrdering, JACOBI);
#ifndef CERES_NO_SUITESPARSE
- CONFIGURE(ITERATIVE_SCHUR, SUITE_SPARSE, USER, SCHUR_JACOBI, 1);
- CONFIGURE(ITERATIVE_SCHUR, SUITE_SPARSE, USER, CLUSTER_JACOBI, 1);
- CONFIGURE(ITERATIVE_SCHUR, SUITE_SPARSE, USER, CLUSTER_TRIDIAGONAL, 1);
+ CONFIGURE(ITERATIVE_SCHUR, SUITE_SPARSE, kUserOrdering, SCHUR_JACOBI);
+ CONFIGURE(ITERATIVE_SCHUR, SUITE_SPARSE, kUserOrdering, CLUSTER_JACOBI);
+ CONFIGURE(ITERATIVE_SCHUR, SUITE_SPARSE, kUserOrdering, CLUSTER_TRIDIAGONAL);
#endif // CERES_NO_SUITESPARSE
- CONFIGURE(ITERATIVE_SCHUR, SUITE_SPARSE, SCHUR, JACOBI, 1);
+ CONFIGURE(ITERATIVE_SCHUR, SUITE_SPARSE, kAutomaticOrdering, JACOBI);
#ifndef CERES_NO_SUITESPARSE
- CONFIGURE(ITERATIVE_SCHUR, SUITE_SPARSE, SCHUR, SCHUR_JACOBI, 1);
- CONFIGURE(ITERATIVE_SCHUR, SUITE_SPARSE, SCHUR, CLUSTER_JACOBI, 1);
- CONFIGURE(ITERATIVE_SCHUR, SUITE_SPARSE, SCHUR, CLUSTER_TRIDIAGONAL, 1);
+ CONFIGURE(ITERATIVE_SCHUR, SUITE_SPARSE, kAutomaticOrdering, SCHUR_JACOBI);
+ CONFIGURE(ITERATIVE_SCHUR, SUITE_SPARSE, kAutomaticOrdering, CLUSTER_JACOBI);
+ CONFIGURE(ITERATIVE_SCHUR, SUITE_SPARSE, kAutomaticOrdering, CLUSTER_TRIDIAGONAL);
#endif // CERES_NO_SUITESPARSE
#undef CONFIGURE
diff --git a/internal/ceres/trust_region_minimizer.cc b/internal/ceres/trust_region_minimizer.cc
index 5e9fc04..9f93deb 100644
--- a/internal/ceres/trust_region_minimizer.cc
+++ b/internal/ceres/trust_region_minimizer.cc
@@ -97,22 +97,14 @@
// moved inside TrustRegionStrategy, its not clear how we dump the
// regularization vector/matrix anymore.
//
- // Doing this right requires either an API change to the
- // TrustRegionStrategy and/or how LinearLeastSquares problems are
- // stored on disk.
+ // Also num_eliminate_blocks is not visible to the trust region
+ // minimizer either.
//
- // For now, we will just not dump the regularizer.
- return (!binary_search(options_.lsqp_iterations_to_dump.begin(),
- options_.lsqp_iterations_to_dump.end(),
- iteration) ||
- DumpLinearLeastSquaresProblem(options_.lsqp_dump_directory,
- iteration,
- options_.lsqp_dump_format_type,
- jacobian,
- NULL,
- residuals,
- step,
- options_.num_eliminate_blocks));
+ // Both of these indicate that this is the wrong place for this
+ // code, and going forward this should needs fixing/refactoring.
+ LOG(WARNING) << "Dumping linear least squares problem to disk is "
+ << "currently broken.";
+ return true;
}
void TrustRegionMinimizer::Minimize(const Minimizer::Options& options,
diff --git a/internal/ceres/types.cc b/internal/ceres/types.cc
index 74c6af4..225384d 100644
--- a/internal/ceres/types.cc
+++ b/internal/ceres/types.cc
@@ -112,24 +112,6 @@
return false;
}
-const char* OrderingTypeToString(OrderingType ordering_type) {
- switch (ordering_type) {
- CASESTR(NATURAL);
- CASESTR(USER);
- CASESTR(SCHUR);
- default:
- return "UNKNOWN";
- }
-}
-
-bool StringToOrderingType(string value, OrderingType* type) {
- UpperCase(&value);
- STRENUM(NATURAL);
- STRENUM(USER);
- STRENUM(SCHUR);
- return false;
-}
-
const char* TrustRegionStrategyTypeToString(
TrustRegionStrategyType trust_region_strategy_type) {
switch (trust_region_strategy_type) {
