internal/ceres/block_jacobian_writer.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: keir@google.com (Keir Mierle)
  30 //
  31 // A jacobian writer that writes to block sparse matrices. The "writer" name is
  32 // misleading, since the Write() operation on the block jacobian writer does not
  33 // write anything. Instead, the Prepare() method on the BlockEvaluatePreparers
  34 // makes a jacobians array which has direct pointers into the block sparse
  35 // jacobian. When the cost function is evaluated, the jacobian blocks get placed
  36 // directly in their final location.
  37
  38 #ifndef CERES_INTERNAL_BLOCK_JACOBIAN_WRITER_H_
  39 #define CERES_INTERNAL_BLOCK_JACOBIAN_WRITER_H_
  40
  41 #include <vector>
  42 #include "ceres/evaluator.h"
  43 #include "ceres/internal/port.h"
  44
  45 namespace ceres {
  46 namespace internal {
  47
  48 class BlockEvaluatePreparer;
  49 class Program;
  50 class SparseMatrix;
  51
  52 // TODO(sameeragarwal): This class needs documemtation.
  53 class BlockJacobianWriter {
  54  public:
  55   BlockJacobianWriter(const Evaluator::Options& options,
  56                       Program* program);
  57
  58   // JacobianWriter interface.
  59
  60   // Create evaluate prepareres that point directly into the final jacobian.
  61   // This makes the final Write() a nop.
  62   BlockEvaluatePreparer* CreateEvaluatePreparers(int num_threads);
  63
  64   SparseMatrix* CreateJacobian() const;
  65
  66   void Write(int /* residual_id */,
  67              int /* residual_offset */,
  68              double** /* jacobians */,
  69              SparseMatrix* /* jacobian */) {
  70     // This is a noop since the blocks were written directly into their final
  71     // position by the outside evaluate call, thanks to the jacobians array
  72     // prepared by the BlockEvaluatePreparers.
  73   }
  74
  75  private:
  76   Program* program_;
  77
  78   // Stores the position of each residual / parameter jacobian.
  79   //
  80   // The block sparse matrix that this writer writes to is stored as a set of
  81   // contiguos dense blocks, one after each other; see BlockSparseMatrix. The
  82   // "double* values_" member of the block sparse matrix contains all of these
  83   // blocks. Given a pointer to the first element of a block and the size of
  84   // that block, it's possible to write to it.
  85   //
  86   // In the case of a block sparse jacobian, the jacobian writer needs a way to
  87   // find the offset in the values_ array of each residual/parameter jacobian
  88   // block.
  89   //
  90   // That is the purpose of jacobian_layout_.
  91   //
  92   // In particular, jacobian_layout_[i][j] is the offset in the values_ array of
  93   // the derivative of residual block i with respect to the parameter block at
  94   // active argument position j.
  95   //
  96   // The active qualifier means that non-active parameters do not count. Care
  97   // must be taken when indexing into jacobian_layout_ to account for this.
  98   // Consider a single residual example:
  99   //
 100   //   r(x, y, z)
 101   //
 102   // with r in R^3, x in R^4, y in R^2, and z in R^5.
 103   // Take y as a constant (non-active) parameter.
 104   // Take r as residual number 0.
 105   //
 106   // In this case, the active arguments are only (x, z), so the active argument
 107   // position for x is 0, and the active argument position for z is 1. This is
 108   // similar to thinking of r as taking only 2 parameters:
 109   //
 110   //   r(x, z)
 111   //
 112   // There are only 2 jacobian blocks: dr/dx and dr/dz. jacobian_layout_ would
 113   // have the following contents:
 114   //
 115   //   jacobian_layout_[0] = { 0, 12 }
 116   //
 117   // which indicates that dr/dx is located at values_[0], and dr/dz is at
 118   // values_[12]. See BlockEvaluatePreparer::Prepare()'s comments about 'j'.
 119   std::vector<int*> jacobian_layout_;
 120
 121   // The pointers in jacobian_layout_ point directly into this vector.
 122   std::vector<int> jacobian_layout_storage_;
 123 };
 124
 125 }  // namespace internal
 126 }  // namespace ceres
 127
 128 #endif  // CERES_INTERNAL_BLOCK_JACOBIAN_WRITER_H_