1// Ceres Solver - A fast non-linear least squares minimizer 2// Copyright 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: sameeragarwal@google.com (Sameer Agarwal) 30// 31// Solve dense rectangular systems Ax = b by forming the normal 32// equations and solving them using the Cholesky factorization. 33 34#ifndef CERES_INTERNAL_DENSE_NORMAL_CHOLESKY_SOLVER_H_ 35#define CERES_INTERNAL_DENSE_NORMAL_CHOLESKY_SOLVER_H_ 36 37#include "ceres/linear_solver.h" 38#include "ceres/internal/macros.h" 39 40namespace ceres { 41namespace internal { 42 43class DenseSparseMatrix; 44 45// This class implements the LinearSolver interface for solving 46// rectangular/unsymmetric (well constrained) linear systems of the 47// form 48// 49// Ax = b 50// 51// Since there does not usually exist a solution that satisfies these 52// equations, the solver instead solves the linear least squares 53// problem 54// 55// min_x |Ax - b|^2 56// 57// Setting the gradient of the above optimization problem to zero 58// gives us the normal equations 59// 60// A'Ax = A'b 61// 62// A'A is a positive definite matrix (hopefully), and the resulting 63// linear system can be solved using Cholesky factorization. 64// 65// If the PerSolveOptions struct has a non-null array D, then the 66// augmented/regularized linear system 67// 68// [ A ]x = [b] 69// [ diag(D) ] [0] 70// 71// is solved. 72// 73// This class uses the LDLT factorization routines from the Eigen 74// library. This solver always returns a solution, it is the user's 75// responsibility to judge if the solution is good enough for their 76// purposes. 77class DenseNormalCholeskySolver: public DenseSparseMatrixSolver { 78 public: 79 explicit DenseNormalCholeskySolver(const LinearSolver::Options& options); 80 81 private: 82 virtual LinearSolver::Summary SolveImpl( 83 DenseSparseMatrix* A, 84 const double* b, 85 const LinearSolver::PerSolveOptions& per_solve_options, 86 double* x); 87 88 LinearSolver::Summary SolveUsingLAPACK( 89 DenseSparseMatrix* A, 90 const double* b, 91 const LinearSolver::PerSolveOptions& per_solve_options, 92 double* x); 93 94 LinearSolver::Summary SolveUsingEigen( 95 DenseSparseMatrix* A, 96 const double* b, 97 const LinearSolver::PerSolveOptions& per_solve_options, 98 double* x); 99 100 const LinearSolver::Options options_; 101 CERES_DISALLOW_COPY_AND_ASSIGN(DenseNormalCholeskySolver); 102}; 103 104} // namespace internal 105} // namespace ceres 106 107#endif // CERES_INTERNAL_DENSE_NORMAL_CHOLESKY_SOLVER_H_ 108