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