Home | History | Annotate | Download | only in ceres 
      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: sameeragarwal (at) google.com (Sameer Agarwal)
     30 //
     31 // A solver for sparse linear least squares problem based on solving
     32 // the normal equations via a sparse cholesky factorization.
     33 
     34 #ifndef CERES_INTERNAL_SPARSE_NORMAL_CHOLESKY_SOLVER_H_
     35 #define CERES_INTERNAL_SPARSE_NORMAL_CHOLESKY_SOLVER_H_
     36 
     37 // This include must come before any #ifndef check on Ceres compile options.
     38 #include "ceres/internal/port.h"
     39 
     40 #include "ceres/internal/macros.h"
     41 #include "ceres/linear_solver.h"
     42 #include "ceres/suitesparse.h"
     43 #include "ceres/cxsparse.h"
     44 
     45 #ifdef CERES_USE_EIGEN_SPARSE
     46 #include "Eigen/SparseCholesky"
     47 #endif
     48 
     49 namespace ceres {
     50 namespace internal {
     51 
     52 class CompressedRowSparseMatrix;
     53 
     54 // Solves the normal equations (A'A + D'D) x = A'b, using the CHOLMOD sparse
     55 // cholesky solver.
     56 class SparseNormalCholeskySolver : public CompressedRowSparseMatrixSolver {
     57  public:
     58   explicit SparseNormalCholeskySolver(const LinearSolver::Options& options);
     59   virtual ~SparseNormalCholeskySolver();
     60 
     61  private:
     62   virtual LinearSolver::Summary SolveImpl(
     63       CompressedRowSparseMatrix* A,
     64       const double* b,
     65       const LinearSolver::PerSolveOptions& options,
     66       double* x);
     67 
     68   LinearSolver::Summary SolveImplUsingSuiteSparse(
     69       CompressedRowSparseMatrix* A,
     70       const LinearSolver::PerSolveOptions& options,
     71       double* rhs_and_solution);
     72 
     73   // Crashes if CSparse is not installed.
     74   LinearSolver::Summary SolveImplUsingCXSparse(
     75       CompressedRowSparseMatrix* A,
     76       const LinearSolver::PerSolveOptions& options,
     77       double* rhs_and_solution);
     78 
     79   // Crashes if CERES_USE_LGPGL_CODE is not defined.
     80   LinearSolver::Summary SolveImplUsingEigen(
     81       CompressedRowSparseMatrix* A,
     82       const LinearSolver::PerSolveOptions& options,
     83       double* rhs_and_solution);
     84 
     85   void FreeFactorization();
     86 
     87   SuiteSparse ss_;
     88   // Cached factorization
     89   cholmod_factor* factor_;
     90 
     91   CXSparse cxsparse_;
     92   // Cached factorization
     93   cs_dis* cxsparse_factor_;
     94 
     95 #ifdef CERES_USE_EIGEN_SPARSE
     96   typedef Eigen::SimplicialLDLT<Eigen::SparseMatrix<double>,
     97                                 Eigen::Upper> SimplicialLDLT;
     98   scoped_ptr<SimplicialLDLT> simplicial_ldlt_;
     99 #endif
    100 
    101   scoped_ptr<CompressedRowSparseMatrix> outer_product_;
    102   vector<int> pattern_;
    103   const LinearSolver::Options options_;
    104   CERES_DISALLOW_COPY_AND_ASSIGN(SparseNormalCholeskySolver);
    105 };
    106 
    107 }  // namespace internal
    108 }  // namespace ceres
    109 
    110 #endif  // CERES_INTERNAL_SPARSE_NORMAL_CHOLESKY_SOLVER_H_
    111