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 31 #ifndef CERES_INTERNAL_SOLVER_IMPL_H_ 32 #define CERES_INTERNAL_SOLVER_IMPL_H_ 33 34 #include <string> 35 #include <vector> 36 #include "ceres/internal/port.h" 37 #include "ceres/ordered_groups.h" 38 #include "ceres/problem_impl.h" 39 #include "ceres/solver.h" 40 41 namespace ceres { 42 namespace internal { 43 44 class CoordinateDescentMinimizer; 45 class Evaluator; 46 class LinearSolver; 47 class Program; 48 49 class SolverImpl { 50 public: 51 // Mirrors the interface in solver.h, but exposes implementation 52 // details for testing internally. 53 static void Solve(const Solver::Options& options, 54 ProblemImpl* problem_impl, 55 Solver::Summary* summary); 56 57 // Create the transformed Program, which has all the fixed blocks 58 // and residuals eliminated, and in the case of automatic schur 59 // ordering, has the E blocks first in the resulting program, with 60 // options.num_eliminate_blocks set appropriately. 61 // 62 // If fixed_cost is not NULL, the residual blocks that are removed 63 // are evaluated and the sum of their cost is returned in fixed_cost. 64 static Program* CreateReducedProgram(Solver::Options* options, 65 ProblemImpl* problem_impl, 66 double* fixed_cost, 67 string* error); 68 69 // Create the appropriate linear solver, taking into account any 70 // config changes decided by CreateTransformedProgram(). The 71 // selected linear solver, which may be different from what the user 72 // selected; consider the case that the remaining elimininated 73 // blocks is zero after removing fixed blocks. 74 static LinearSolver* CreateLinearSolver(Solver::Options* options, 75 string* error); 76 77 // Reorder the parameter blocks in program using the ordering. A 78 // return value of true indicates success and false indicates an 79 // error was encountered whose cause is logged to LOG(ERROR). 80 static bool ApplyUserOrdering(const ProblemImpl::ParameterMap& parameter_map, 81 const ParameterBlockOrdering* ordering, 82 Program* program, 83 string* error); 84 85 86 // Reorder the residuals for program, if necessary, so that the 87 // residuals involving e block (i.e., the first num_eliminate_block 88 // parameter blocks) occur together. This is a necessary condition 89 // for the Schur eliminator. 90 static bool LexicographicallyOrderResidualBlocks( 91 const int num_eliminate_blocks, 92 Program* program, 93 string* error); 94 95 // Create the appropriate evaluator for the transformed program. 96 static Evaluator* CreateEvaluator( 97 const Solver::Options& options, 98 const ProblemImpl::ParameterMap& parameter_map, 99 Program* program, 100 string* error); 101 102 // Run the minimization for the given evaluator and configuration. 103 static void Minimize(const Solver::Options &options, 104 Program* program, 105 CoordinateDescentMinimizer* inner_iteration_minimizer, 106 Evaluator* evaluator, 107 LinearSolver* linear_solver, 108 double* parameters, 109 Solver::Summary* summary); 110 111 // Remove the fixed or unused parameter blocks and residuals 112 // depending only on fixed parameters from the problem. Also updates 113 // num_eliminate_blocks, since removed parameters changes the point 114 // at which the eliminated blocks is valid. If fixed_cost is not 115 // NULL, the residual blocks that are removed are evaluated and the 116 // sum of their cost is returned in fixed_cost. 117 static bool RemoveFixedBlocksFromProgram(Program* program, 118 ParameterBlockOrdering* ordering, 119 double* fixed_cost, 120 string* error); 121 122 static bool IsOrderingValid(const Solver::Options& options, 123 const ProblemImpl* problem_impl, 124 string* error); 125 126 static bool IsParameterBlockSetIndependent( 127 const set<double*>& parameter_block_ptrs, 128 const vector<ResidualBlock*>& residual_blocks); 129 130 static CoordinateDescentMinimizer* CreateInnerIterationMinimizer( 131 const Solver::Options& options, 132 const Program& program, 133 const ProblemImpl::ParameterMap& parameter_map, 134 string* error); 135 }; 136 137 } // namespace internal 138 } // namespace ceres 139 140 #endif // CERES_INTERNAL_SOLVER_IMPL_H_ 141
