1 // Ceres Solver - A fast non-linear least squares minimizer
2 // Copyright 2010, 2011, 2012 Google Inc. All rights reserved.
3 // http://code.google.com/p/ceres-solver/
4 //
5 // Redistribution and use in source and binary forms, with or without
6 // modification, are permitted provided that the following conditions are met:
7 //
8 // * Redistributions of source code must retain the above copyright notice,
9 // this list of conditions and the following disclaimer.
10 // * Redistributions in binary form must reproduce the above copyright notice,
11 // this list of conditions and the following disclaimer in the documentation
12 // and/or other materials provided with the distribution.
13 // * Neither the name of Google Inc. nor the names of its contributors may be
14 // used to endorse or promote products derived from this software without
15 // specific prior written permission.
16 //
17 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
18 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 // ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
21 // LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
22 // CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
23 // SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
24 // INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
25 // CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
26 // ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
27 // POSSIBILITY OF SUCH DAMAGE.
28 //
29 // Author: keir@google.com (Keir Mierle)
30 // sameeragarwal@google.com (Sameer Agarwal)
31
32 #include "ceres/solver.h"
33
34 #include <vector>
35 #include "ceres/problem.h"
36 #include "ceres/problem_impl.h"
37 #include "ceres/program.h"
38 #include "ceres/solver_impl.h"
39 #include "ceres/stringprintf.h"
40 #include "ceres/wall_time.h"
41
42 namespace ceres {
43
~Options()44 Solver::Options::~Options() {
45 delete linear_solver_ordering;
46 delete inner_iteration_ordering;
47 }
48
~Solver()49 Solver::~Solver() {}
50
Solve(const Solver::Options & options,Problem * problem,Solver::Summary * summary)51 void Solver::Solve(const Solver::Options& options,
52 Problem* problem,
53 Solver::Summary* summary) {
54 double start_time_seconds = internal::WallTimeInSeconds();
55 internal::ProblemImpl* problem_impl =
56 CHECK_NOTNULL(problem)->problem_impl_.get();
57 internal::SolverImpl::Solve(options, problem_impl, summary);
58 summary->total_time_in_seconds =
59 internal::WallTimeInSeconds() - start_time_seconds;
60 }
61
Solve(const Solver::Options & options,Problem * problem,Solver::Summary * summary)62 void Solve(const Solver::Options& options,
63 Problem* problem,
64 Solver::Summary* summary) {
65 Solver solver;
66 solver.Solve(options, problem, summary);
67 }
68
Summary()69 Solver::Summary::Summary()
70 // Invalid values for most fields, to ensure that we are not
71 // accidentally reporting default values.
72 : termination_type(DID_NOT_RUN),
73 initial_cost(-1.0),
74 final_cost(-1.0),
75 fixed_cost(-1.0),
76 num_successful_steps(-1),
77 num_unsuccessful_steps(-1),
78 preprocessor_time_in_seconds(-1.0),
79 minimizer_time_in_seconds(-1.0),
80 postprocessor_time_in_seconds(-1.0),
81 total_time_in_seconds(-1.0),
82 num_parameter_blocks(-1),
83 num_parameters(-1),
84 num_residual_blocks(-1),
85 num_residuals(-1),
86 num_parameter_blocks_reduced(-1),
87 num_parameters_reduced(-1),
88 num_residual_blocks_reduced(-1),
89 num_residuals_reduced(-1),
90 num_threads_given(-1),
91 num_threads_used(-1),
92 num_linear_solver_threads_given(-1),
93 num_linear_solver_threads_used(-1),
94 linear_solver_type_given(SPARSE_NORMAL_CHOLESKY),
95 linear_solver_type_used(SPARSE_NORMAL_CHOLESKY),
96 preconditioner_type(IDENTITY),
97 trust_region_strategy_type(LEVENBERG_MARQUARDT),
98 sparse_linear_algebra_library(SUITE_SPARSE) {
99 }
100
BriefReport() const101 string Solver::Summary::BriefReport() const {
102 string report = "Ceres Solver Report: ";
103 if (termination_type == DID_NOT_RUN) {
104 CHECK(!error.empty())
105 << "Solver terminated with DID_NOT_RUN but the solver did not "
106 << "return a reason. This is a Ceres error. Please report this "
107 << "to the Ceres team";
108 return report + "Termination: DID_NOT_RUN, because " + error;
109 }
110
111 internal::StringAppendF(&report, "Iterations: %d",
112 num_successful_steps + num_unsuccessful_steps);
113 internal::StringAppendF(&report, ", Initial cost: %e", initial_cost);
114
115 // If the solver failed or was aborted, then the final_cost has no
116 // meaning.
117 if (termination_type != NUMERICAL_FAILURE &&
118 termination_type != USER_ABORT) {
119 internal::StringAppendF(&report, ", Final cost: %e", final_cost);
120 }
121
122 internal::StringAppendF(&report, ", Termination: %s.",
123 SolverTerminationTypeToString(termination_type));
124 return report;
125 };
126
FullReport() const127 string Solver::Summary::FullReport() const {
128 string report =
129 "\n"
130 "Ceres Solver Report\n"
131 "-------------------\n";
132
133 if (termination_type == DID_NOT_RUN) {
134 internal::StringAppendF(&report, " Original\n");
135 internal::StringAppendF(&report, "Parameter blocks % 10d\n",
136 num_parameter_blocks);
137 internal::StringAppendF(&report, "Parameters % 10d\n",
138 num_parameters);
139 internal::StringAppendF(&report, "Residual blocks % 10d\n",
140 num_residual_blocks);
141 internal::StringAppendF(&report, "Residuals % 10d\n\n",
142 num_residuals);
143 } else {
144 internal::StringAppendF(&report, "%45s %21s\n", "Original", "Reduced");
145 internal::StringAppendF(&report, "Parameter blocks % 25d% 25d\n",
146 num_parameter_blocks, num_parameter_blocks_reduced);
147 internal::StringAppendF(&report, "Parameters % 25d% 25d\n",
148 num_parameters, num_parameters_reduced);
149 internal::StringAppendF(&report, "Residual blocks % 25d% 25d\n",
150 num_residual_blocks, num_residual_blocks_reduced);
151 internal::StringAppendF(&report, "Residual % 25d% 25d\n\n",
152 num_residuals, num_residuals_reduced);
153 }
154
155 internal::StringAppendF(&report, "%45s %21s\n", "Given", "Used");
156 internal::StringAppendF(&report, "Linear solver %25s%25s\n",
157 LinearSolverTypeToString(linear_solver_type_given),
158 LinearSolverTypeToString(linear_solver_type_used));
159
160 if (linear_solver_type_given == CGNR ||
161 linear_solver_type_given == ITERATIVE_SCHUR) {
162 internal::StringAppendF(&report, "Preconditioner %25s%25s\n",
163 PreconditionerTypeToString(preconditioner_type),
164 PreconditionerTypeToString(preconditioner_type));
165 } else {
166 internal::StringAppendF(&report, "Preconditioner %25s%25s\n",
167 "N/A", "N/A");
168 }
169
170 // TODO(sameeragarwal): Add support for logging the ordering object.
171 internal::StringAppendF(&report, "Threads: % 25d% 25d\n",
172 num_threads_given, num_threads_used);
173 internal::StringAppendF(&report, "Linear solver threads % 23d% 25d\n",
174 num_linear_solver_threads_given,
175 num_linear_solver_threads_used);
176
177 if (linear_solver_type_used == SPARSE_NORMAL_CHOLESKY ||
178 linear_solver_type_used == SPARSE_SCHUR ||
179 (linear_solver_type_used == ITERATIVE_SCHUR &&
180 (preconditioner_type == SCHUR_JACOBI ||
181 preconditioner_type == CLUSTER_JACOBI ||
182 preconditioner_type == CLUSTER_TRIDIAGONAL))) {
183 internal::StringAppendF(&report, "\nSparse Linear Algebra Library %15s\n",
184 SparseLinearAlgebraLibraryTypeToString(
185 sparse_linear_algebra_library));
186 }
187
188 internal::StringAppendF(&report, "Trust Region Strategy %19s",
189 TrustRegionStrategyTypeToString(
190 trust_region_strategy_type));
191 if (trust_region_strategy_type == DOGLEG) {
192 if (dogleg_type == TRADITIONAL_DOGLEG) {
193 internal::StringAppendF(&report, " (TRADITIONAL)");
194 } else {
195 internal::StringAppendF(&report, " (SUBSPACE)");
196 }
197 }
198 internal::StringAppendF(&report, "\n");
199
200
201 if (termination_type == DID_NOT_RUN) {
202 CHECK(!error.empty())
203 << "Solver terminated with DID_NOT_RUN but the solver did not "
204 << "return a reason. This is a Ceres error. Please report this "
205 << "to the Ceres team";
206 internal::StringAppendF(&report, "Termination: %20s\n",
207 "DID_NOT_RUN");
208 internal::StringAppendF(&report, "Reason: %s\n", error.c_str());
209 return report;
210 }
211
212 internal::StringAppendF(&report, "\nCost:\n");
213 internal::StringAppendF(&report, "Initial % 30e\n", initial_cost);
214 if (termination_type != NUMERICAL_FAILURE && termination_type != USER_ABORT) {
215 internal::StringAppendF(&report, "Final % 30e\n", final_cost);
216 internal::StringAppendF(&report, "Change % 30e\n",
217 initial_cost - final_cost);
218 }
219
220 internal::StringAppendF(&report, "\nNumber of iterations:\n");
221 internal::StringAppendF(&report, "Successful % 20d\n",
222 num_successful_steps);
223 internal::StringAppendF(&report, "Unsuccessful % 20d\n",
224 num_unsuccessful_steps);
225 internal::StringAppendF(&report, "Total % 20d\n",
226 num_successful_steps + num_unsuccessful_steps);
227 internal::StringAppendF(&report, "\nTime (in seconds):\n");
228 internal::StringAppendF(&report, "Preprocessor % 25e\n",
229 preprocessor_time_in_seconds);
230 internal::StringAppendF(&report, "Minimizer % 25e\n",
231 minimizer_time_in_seconds);
232 internal::StringAppendF(&report, "Total % 25e\n",
233 total_time_in_seconds);
234
235 internal::StringAppendF(&report, "Termination: %25s\n",
236 SolverTerminationTypeToString(termination_type));
237 return report;
238 };
239
240 } // namespace ceres
241