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 45namespace ceres { 46namespace internal { 47 48class BlockEvaluatePreparer; 49class Program; 50class SparseMatrix; 51 52class 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 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