10ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Ceres Solver - A fast non-linear least squares minimizer 20ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Copyright 2010, 2011, 2012 Google Inc. All rights reserved. 30ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// http://code.google.com/p/ceres-solver/ 40ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// 50ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Redistribution and use in source and binary forms, with or without 60ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// modification, are permitted provided that the following conditions are met: 70ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// 80ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// * Redistributions of source code must retain the above copyright notice, 90ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// this list of conditions and the following disclaimer. 100ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// * Redistributions in binary form must reproduce the above copyright notice, 110ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// this list of conditions and the following disclaimer in the documentation 120ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// and/or other materials provided with the distribution. 130ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// * Neither the name of Google Inc. nor the names of its contributors may be 140ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// used to endorse or promote products derived from this software without 150ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// specific prior written permission. 160ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// 170ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 180ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 190ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 200ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 210ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 220ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 230ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 240ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 250ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 260ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 270ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// POSSIBILITY OF SUCH DAMAGE. 280ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// 290ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Author: sameeragarwal@google.com (Sameer Agarwal) 300ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// 310ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Interface for matrices that allow block based random access. 320ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 330ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#ifndef CERES_INTERNAL_BLOCK_RANDOM_ACCESS_MATRIX_H_ 340ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#define CERES_INTERNAL_BLOCK_RANDOM_ACCESS_MATRIX_H_ 350ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 360ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#include "ceres/mutex.h" 370ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 380ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kongnamespace ceres { 390ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kongnamespace internal { 400ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 410ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// A matrix implementing the BlockRandomAccessMatrix interface is a 420ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// matrix whose rows and columns are divided into blocks. For example 430ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// the matrix A: 440ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// 450ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// 3 4 5 460ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// A = 5 [c_11 c_12 c_13] 470ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// 4 [c_21 c_22 c_23] 480ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// 490ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// has row blocks of size 5 and 4, and column blocks of size 3, 4 and 500ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// 5. It has six cells corresponding to the six row-column block 510ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// combinations. 520ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// 530ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// BlockRandomAccessMatrix objects provide access to cells c_ij using 540ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// the GetCell method. when a cell is present, GetCell will return a 550ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// CellInfo object containing a pointer to an array which contains the 560ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// cell as a submatrix and a mutex that guards this submatrix. If the 570ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// user is accessing the matrix concurrently, it is his responsibility 580ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// to use the mutex to exclude other writers from writing to the cell 590ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// concurrently. 600ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// 610ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// There is no requirement that all cells be present, i.e. the matrix 620ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// itself can be block sparse. When a cell is not present, the GetCell 630ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// method will return a NULL pointer. 640ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// 650ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// There is no requirement about how the cells are stored beyond that 660ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// form a dense submatrix of a larger dense matrix. Like everywhere 670ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// else in Ceres, RowMajor storage assumed. 680ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// 690ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Example usage: 700ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// 710ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// BlockRandomAccessMatrix* A = new BlockRandomAccessMatrixSubClass(...) 720ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// 730ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// int row, col, row_stride, col_stride; 740ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// CellInfo* cell = A->GetCell(row_block_id, col_block_id, 750ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// &row, &col, 760ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// &row_stride, &col_stride); 770ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// 780ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// if (cell != NULL) { 790ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// MatrixRef m(cell->values, row_stride, col_stride); 800ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// CeresMutexLock l(&cell->m); 810ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// m.block(row, col, row_block_size, col_block_size) = ... 820ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// } 830ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 840ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Structure to carry a pointer to the array containing a cell and the 850ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong// Mutex guarding it. 860ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kongstruct CellInfo { 870ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong CellInfo() 880ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong : values(NULL) { 890ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 900ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 910ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong explicit CellInfo(double* ptr) 920ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong : values(ptr) { 930ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong } 940ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 950ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong double* values; 960ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong Mutex m; 970ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong}; 980ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 990ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kongclass BlockRandomAccessMatrix { 1000ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong public: 1010ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong virtual ~BlockRandomAccessMatrix(); 1020ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1030ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // If the cell (row_block_id, col_block_id) is present, then return 1040ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // a CellInfo with a pointer to the dense matrix containing it, 1050ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // otherwise return NULL. The dense matrix containing this cell has 1060ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // size row_stride, col_stride and the cell is located at position 1070ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // (row, col) within this matrix. 1080ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // 1090ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // The size of the cell is row_block_size x col_block_size is 1100ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // assumed known to the caller. row_block_size less than or equal to 1110ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // row_stride and col_block_size is upper bounded by col_stride. 1120ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong virtual CellInfo* GetCell(int row_block_id, 1130ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int col_block_id, 1140ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int* row, 1150ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int* col, 1160ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int* row_stride, 1170ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong int* col_stride) = 0; 1180ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1190ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Zero out the values of the array. The structure of the matrix 1200ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // (size and sparsity) is preserved. 1210ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong virtual void SetZero() = 0; 1220ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1230ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // Number of scalar rows and columns in the matrix, i.e the sum of 1240ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong // all row blocks and column block sizes respectively. 1250ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong virtual int num_rows() const = 0; 1260ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong virtual int num_cols() const = 0; 1270ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong}; 1280ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1290ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong} // namespace internal 1300ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong} // namespace ceres 1310ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong 1320ae28bd5885b5daa526898fcf7c323dc2c3e1963Angus Kong#endif // CERES_INTERNAL_BLOCK_RANDOM_ACCESS_MATRIX_H_ 133