1 // Ceres Solver - A fast non-linear least squares minimizer 2 // Copyright 2014 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: richie.stebbing@gmail.com (Richard Stebbing) 30 // 31 // A compressed row sparse matrix that provides an extended interface to 32 // allow dynamic insertion of entries. This is provided for the use case 33 // where the sparsity structure and number of non-zero entries is dynamic. 34 // This flexibility is achieved by using an (internal) scratch space that 35 // allows independent insertion of entries into each row (thread-safe). 36 // Once insertion is complete, the `Finalize` method must be called to ensure 37 // that the underlying `CompressedRowSparseMatrix` is consistent. 38 // 39 // This should only be used if you really do need a dynamic sparsity pattern. 40 41 #ifndef CERES_INTERNAL_DYNAMIC_COMPRESSED_ROW_SPARSE_MATRIX_H_ 42 #define CERES_INTERNAL_DYNAMIC_COMPRESSED_ROW_SPARSE_MATRIX_H_ 43 44 #include "ceres/compressed_row_sparse_matrix.h" 45 46 namespace ceres { 47 namespace internal { 48 49 class DynamicCompressedRowSparseMatrix : public CompressedRowSparseMatrix { 50 public: 51 // Set the number of rows and columns for the underlyig 52 // `CompressedRowSparseMatrix` and set the initial number of maximum non-zero 53 // entries. Note that following the insertion of entries, when `Finalize` 54 // is called the number of non-zeros is determined and all internal 55 // structures are adjusted as required. If you know the upper limit on the 56 // number of non-zeros, then passing this value here can prevent future 57 // memory reallocations which may improve performance. Otherwise, if no 58 // upper limit is available a value of 0 is sufficient. 59 // 60 // Typical usage of this class is to define a new instance with a given 61 // number of rows, columns and maximum number of non-zero elements 62 // (if available). Next, entries are inserted at row and column positions 63 // using `InsertEntry`. Finally, once all elements have been inserted, 64 // `Finalize` must be called to make the underlying 65 // `CompressedRowSparseMatrix` consistent. 66 DynamicCompressedRowSparseMatrix(int num_rows, 67 int num_cols, 68 int initial_max_num_nonzeros); 69 70 // Insert an entry at a given row and column position. This method is 71 // thread-safe across rows i.e. different threads can insert values 72 // simultaneously into different rows. It should be emphasised that this 73 // method always inserts a new entry and does not check for existing 74 // entries at the specified row and column position. Duplicate entries 75 // for a given row and column position will result in undefined 76 // behavior. 77 void InsertEntry(int row, int col, const double& value); 78 79 // Clear all entries for rows, starting from row index `row_start` 80 // and proceeding for `num_rows`. 81 void ClearRows(int row_start, int num_rows); 82 83 // Make the underlying internal `CompressedRowSparseMatrix` data structures 84 // consistent. Additional space for non-zero entries in the 85 // `CompressedRowSparseMatrix` can be reserved by specifying 86 // `num_additional_elements`. This is useful when it is known that rows will 87 // be appended to the `CompressedRowSparseMatrix` (e.g. appending a diagonal 88 // matrix to the jacobian) as it prevents need for future reallocation. 89 void Finalize(int num_additional_elements); 90 91 private: 92 vector<vector<int> > dynamic_cols_; 93 vector<vector<double> > dynamic_values_; 94 }; 95 96 } // namespace internal 97 } // namespace ceres 98 99 #endif // CERES_INTERNAL_DYNAMIC_COMPRESSED_ROW_SPARSE_MATRIX_H_ 100