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 (at) google.com (Keir Mierle) 30 // sameeragarwal (at) 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 44 Solver::Options::~Options() { 45 delete linear_solver_ordering; 46 delete inner_iteration_ordering; 47 } 48 49 Solver::~Solver() {} 50 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 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 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 101 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 127 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