internal/ceres/schur_jacobi_preconditioner.h

   1 // Ceres Solver - A fast non-linear least squares minimizer
   2 // Copyright 2015 Google Inc. All rights reserved.
   3 // http://ceres-solver.org/
   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 // Detailed descriptions of these preconditions beyond what is
  32 // documented here can be found in
  33 //
  34 // Bundle Adjustment in the Large
  35 // S. Agarwal, N. Snavely, S. Seitz & R. Szeliski, ECCV 2010
  36 // http://www.cs.washington.edu/homes/sagarwal/bal.pdf
  37
  38 #ifndef CERES_INTERNAL_SCHUR_JACOBI_PRECONDITIONER_H_
  39 #define CERES_INTERNAL_SCHUR_JACOBI_PRECONDITIONER_H_
  40
  41 #include <set>
  42 #include <vector>
  43 #include <utility>
  44 #include "ceres/collections_port.h"
  45 #include "ceres/internal/macros.h"
  46 #include "ceres/internal/scoped_ptr.h"
  47 #include "ceres/preconditioner.h"
  48
  49 namespace ceres {
  50 namespace internal {
  51
  52 class BlockRandomAccessDiagonalMatrix;
  53 class BlockSparseMatrix;
  54 struct CompressedRowBlockStructure;
  55 class SchurEliminatorBase;
  56
  57 // This class implements the SCHUR_JACOBI preconditioner for Structure
  58 // from Motion/Bundle Adjustment problems. Full mathematical details
  59 // can be found in
  60 //
  61 // Bundle Adjustment in the Large
  62 // S. Agarwal, N. Snavely, S. Seitz & R. Szeliski, ECCV 2010
  63 // http://www.cs.washington.edu/homes/sagarwal/bal.pdf
  64 //
  65 // Example usage:
  66 //
  67 //   Preconditioner::Options options;
  68 //   options.preconditioner_type = SCHUR_JACOBI;
  69 //   options.elimination_groups.push_back(num_points);
  70 //   options.elimination_groups.push_back(num_cameras);
  71 //   SchurJacobiPreconditioner preconditioner(
  72 //      *A.block_structure(), options);
  73 //   preconditioner.Update(A, NULL);
  74 //   preconditioner.RightMultiply(x, y);
  75 //
  76 class SchurJacobiPreconditioner : public BlockSparseMatrixPreconditioner {
  77  public:
  78   // Initialize the symbolic structure of the preconditioner. bs is
  79   // the block structure of the linear system to be solved. It is used
  80   // to determine the sparsity structure of the preconditioner matrix.
  81   //
  82   // It has the same structural requirement as other Schur complement
  83   // based solvers. Please see schur_eliminator.h for more details.
  84   SchurJacobiPreconditioner(const CompressedRowBlockStructure& bs,
  85                             const Preconditioner::Options& options);
  86   virtual ~SchurJacobiPreconditioner();
  87
  88   // Preconditioner interface.
  89   virtual void RightMultiply(const double* x, double* y) const;
  90   virtual int num_rows() const;
  91
  92  private:
  93   void InitEliminator(const CompressedRowBlockStructure& bs);
  94   virtual bool UpdateImpl(const BlockSparseMatrix& A, const double* D);
  95
  96   Preconditioner::Options options_;
  97   scoped_ptr<SchurEliminatorBase> eliminator_;
  98   // Preconditioner matrix.
  99   scoped_ptr<BlockRandomAccessDiagonalMatrix> m_;
 100   CERES_DISALLOW_COPY_AND_ASSIGN(SchurJacobiPreconditioner);
 101 };
 102
 103 }  // namespace internal
 104 }  // namespace ceres
 105
 106 #endif  // CERES_INTERNAL_SCHUR_JACOBI_PRECONDITIONER_H_