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 // Implementation of the SparseMatrix interface for block sparse 32 // matrices. 33 34 #ifndef CERES_INTERNAL_BLOCK_SPARSE_MATRIX_H_ 35 #define CERES_INTERNAL_BLOCK_SPARSE_MATRIX_H_ 36 37 #include "ceres/block_structure.h" 38 #include "ceres/sparse_matrix.h" 39 #include "ceres/internal/eigen.h" 40 #include "ceres/internal/macros.h" 41 #include "ceres/internal/scoped_ptr.h" 42 43 namespace ceres { 44 namespace internal { 45 46 class SparseMatrixProto; 47 class TripletSparseMatrix; 48 49 // A further extension of the SparseMatrix interface to support block-oriented 50 // matrices. The key addition is the RowBlockValues() accessor, which enables 51 // the lazy block sparse matrix implementation. 52 class BlockSparseMatrixBase : public SparseMatrix { 53 public: BlockSparseMatrixBase()54 BlockSparseMatrixBase() {} ~BlockSparseMatrixBase()55 virtual ~BlockSparseMatrixBase() {} 56 57 // Convert this matrix into a triplet sparse matrix. 58 virtual void ToTripletSparseMatrix(TripletSparseMatrix* matrix) const = 0; 59 60 // Returns a pointer to the block structure. Does not transfer 61 // ownership. 62 virtual const CompressedRowBlockStructure* block_structure() const = 0; 63 64 // Returns a pointer to a row of the matrix. The returned array is only valid 65 // until the next call to RowBlockValues. The caller does not own the result. 66 // 67 // The returned array is laid out such that cells on the specified row are 68 // contiguous in the returned array, though neighbouring cells in row order 69 // may not be contiguous in the row values. The cell values for cell 70 // (row_block, cell_block) are found at offset 71 // 72 // block_structure()->rows[row_block].cells[cell_block].position 73 // 74 virtual const double* RowBlockValues(int row_block_index) const = 0; 75 76 private: 77 CERES_DISALLOW_COPY_AND_ASSIGN(BlockSparseMatrixBase); 78 }; 79 80 // This class implements the SparseMatrix interface for storing and 81 // manipulating block sparse matrices. The block structure is stored 82 // in the CompressedRowBlockStructure object and one is needed to 83 // initialize the matrix. For details on how the blocks structure of 84 // the matrix is stored please see the documentation 85 // 86 // internal/ceres/block_structure.h 87 // 88 class BlockSparseMatrix : public BlockSparseMatrixBase { 89 public: 90 // Construct a block sparse matrix with a fully initialized 91 // CompressedRowBlockStructure objected. The matrix takes over 92 // ownership of this object and destroys it upon destruction. 93 // 94 // TODO(sameeragarwal): Add a function which will validate legal 95 // CompressedRowBlockStructure objects. 96 explicit BlockSparseMatrix(CompressedRowBlockStructure* block_structure); 97 98 // Construct a block sparse matrix from a protocol buffer. 99 #ifndef CERES_NO_PROTOCOL_BUFFERS 100 explicit BlockSparseMatrix(const SparseMatrixProto& proto); 101 #endif 102 103 BlockSparseMatrix(); 104 virtual ~BlockSparseMatrix(); 105 106 // Implementation of SparseMatrix interface. 107 virtual void SetZero(); 108 virtual void RightMultiply(const double* x, double* y) const; 109 virtual void LeftMultiply(const double* x, double* y) const; 110 virtual void SquaredColumnNorm(double* x) const; 111 virtual void ScaleColumns(const double* scale); 112 virtual void ToDenseMatrix(Matrix* dense_matrix) const; 113 #ifndef CERES_NO_PROTOCOL_BUFFERS 114 virtual void ToProto(SparseMatrixProto* proto) const; 115 #endif 116 virtual void ToTextFile(FILE* file) const; 117 num_rows()118 virtual int num_rows() const { return num_rows_; } num_cols()119 virtual int num_cols() const { return num_cols_; } num_nonzeros()120 virtual int num_nonzeros() const { return num_nonzeros_; } values()121 virtual const double* values() const { return values_.get(); } mutable_values()122 virtual double* mutable_values() { return values_.get(); } 123 124 // Implementation of BlockSparseMatrixBase interface. 125 virtual void ToTripletSparseMatrix(TripletSparseMatrix* matrix) const; 126 virtual const CompressedRowBlockStructure* block_structure() const; RowBlockValues(int row_block_index)127 virtual const double* RowBlockValues(int row_block_index) const { 128 return values_.get(); 129 } 130 131 private: 132 int num_rows_; 133 int num_cols_; 134 int max_num_nonzeros_; 135 int num_nonzeros_; 136 scoped_array<double> values_; 137 scoped_ptr<CompressedRowBlockStructure> block_structure_; 138 CERES_DISALLOW_COPY_AND_ASSIGN(BlockSparseMatrix); 139 }; 140 141 } // namespace internal 142 } // namespace ceres 143 144 #endif // CERES_INTERNAL_BLOCK_SPARSE_MATRIX_H_ 145