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@google.com (Sameer Agarwal) 30 // 31 // Interface for matrices that allow block based random access. 32 33 #ifndef CERES_INTERNAL_BLOCK_RANDOM_ACCESS_MATRIX_H_ 34 #define CERES_INTERNAL_BLOCK_RANDOM_ACCESS_MATRIX_H_ 35 36 #include "ceres/mutex.h" 37 38 namespace ceres { 39 namespace internal { 40 41 // A matrix implementing the BlockRandomAccessMatrix interface is a 42 // matrix whose rows and columns are divided into blocks. For example 43 // the matrix A: 44 // 45 // 3 4 5 46 // A = 5 [c_11 c_12 c_13] 47 // 4 [c_21 c_22 c_23] 48 // 49 // has row blocks of size 5 and 4, and column blocks of size 3, 4 and 50 // 5. It has six cells corresponding to the six row-column block 51 // combinations. 52 // 53 // BlockRandomAccessMatrix objects provide access to cells c_ij using 54 // the GetCell method. when a cell is present, GetCell will return a 55 // CellInfo object containing a pointer to an array which contains the 56 // cell as a submatrix and a mutex that guards this submatrix. If the 57 // user is accessing the matrix concurrently, it is his responsibility 58 // to use the mutex to exclude other writers from writing to the cell 59 // concurrently. 60 // 61 // There is no requirement that all cells be present, i.e. the matrix 62 // itself can be block sparse. When a cell is not present, the GetCell 63 // method will return a NULL pointer. 64 // 65 // There is no requirement about how the cells are stored beyond that 66 // form a dense submatrix of a larger dense matrix. Like everywhere 67 // else in Ceres, RowMajor storage assumed. 68 // 69 // Example usage: 70 // 71 // BlockRandomAccessMatrix* A = new BlockRandomAccessMatrixSubClass(...) 72 // 73 // int row, col, row_stride, col_stride; 74 // CellInfo* cell = A->GetCell(row_block_id, col_block_id, 75 // &row, &col, 76 // &row_stride, &col_stride); 77 // 78 // if (cell != NULL) { 79 // MatrixRef m(cell->values, row_stride, col_stride); 80 // CeresMutexLock l(&cell->m); 81 // m.block(row, col, row_block_size, col_block_size) = ... 82 // } 83 84 // Structure to carry a pointer to the array containing a cell and the 85 // Mutex guarding it. 86 struct CellInfo { CellInfoCellInfo87 CellInfo() 88 : values(NULL) { 89 } 90 CellInfoCellInfo91 explicit CellInfo(double* ptr) 92 : values(ptr) { 93 } 94 95 double* values; 96 Mutex m; 97 }; 98 99 class BlockRandomAccessMatrix { 100 public: 101 virtual ~BlockRandomAccessMatrix(); 102 103 // If the cell (row_block_id, col_block_id) is present, then return 104 // a CellInfo with a pointer to the dense matrix containing it, 105 // otherwise return NULL. The dense matrix containing this cell has 106 // size row_stride, col_stride and the cell is located at position 107 // (row, col) within this matrix. 108 // 109 // The size of the cell is row_block_size x col_block_size is 110 // assumed known to the caller. row_block_size less than or equal to 111 // row_stride and col_block_size is upper bounded by col_stride. 112 virtual CellInfo* GetCell(int row_block_id, 113 int col_block_id, 114 int* row, 115 int* col, 116 int* row_stride, 117 int* col_stride) = 0; 118 119 // Zero out the values of the array. The structure of the matrix 120 // (size and sparsity) is preserved. 121 virtual void SetZero() = 0; 122 123 // Number of scalar rows and columns in the matrix, i.e the sum of 124 // all row blocks and column block sizes respectively. 125 virtual int num_rows() const = 0; 126 virtual int num_cols() const = 0; 127 }; 128 129 } // namespace internal 130 } // namespace ceres 131 132 #endif // CERES_INTERNAL_BLOCK_RANDOM_ACCESS_MATRIX_H_ 133