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 (at) google.com (Sameer Agarwal) 30 31 #ifndef CERES_INTERNAL_COMPRESSED_ROW_SPARSE_MATRIX_H_ 32 #define CERES_INTERNAL_COMPRESSED_ROW_SPARSE_MATRIX_H_ 33 34 #include <vector> 35 #include <glog/logging.h> 36 #include "ceres/sparse_matrix.h" 37 #include "ceres/triplet_sparse_matrix.h" 38 #include "ceres/internal/eigen.h" 39 #include "ceres/internal/macros.h" 40 #include "ceres/internal/port.h" 41 #include "ceres/types.h" 42 43 namespace ceres { 44 45 struct CRSMatrix; 46 47 namespace internal { 48 49 class SparseMatrixProto; 50 51 class CompressedRowSparseMatrix : public SparseMatrix { 52 public: 53 // Build a matrix with the same content as the TripletSparseMatrix 54 // m. TripletSparseMatrix objects are easier to construct 55 // incrementally, so we use them to initialize SparseMatrix 56 // objects. 57 // 58 // We assume that m does not have any repeated entries. 59 explicit CompressedRowSparseMatrix(const TripletSparseMatrix& m); 60 #ifndef CERES_NO_PROTOCOL_BUFFERS 61 explicit CompressedRowSparseMatrix(const SparseMatrixProto& proto); 62 #endif 63 64 // Use this constructor only if you know what you are doing. This 65 // creates a "blank" matrix with the appropriate amount of memory 66 // allocated. However, the object itself is in an inconsistent state 67 // as the rows and cols matrices do not match the values of 68 // num_rows, num_cols and max_num_nonzeros. 69 // 70 // The use case for this constructor is that when the user knows the 71 // size of the matrix to begin with and wants to update the layout 72 // manually, instead of going via the indirect route of first 73 // constructing a TripletSparseMatrix, which leads to more than 74 // double the peak memory usage. 75 CompressedRowSparseMatrix(int num_rows, 76 int num_cols, 77 int max_num_nonzeros); 78 79 // Build a square sparse diagonal matrix with num_rows rows and 80 // columns. The diagonal m(i,i) = diagonal(i); 81 CompressedRowSparseMatrix(const double* diagonal, int num_rows); 82 83 virtual ~CompressedRowSparseMatrix(); 84 85 // SparseMatrix interface. 86 virtual void SetZero(); 87 virtual void RightMultiply(const double* x, double* y) const; 88 virtual void LeftMultiply(const double* x, double* y) const; 89 virtual void SquaredColumnNorm(double* x) const; 90 virtual void ScaleColumns(const double* scale); 91 92 virtual void ToDenseMatrix(Matrix* dense_matrix) const; 93 #ifndef CERES_NO_PROTOCOL_BUFFERS 94 virtual void ToProto(SparseMatrixProto* proto) const; 95 #endif 96 virtual void ToTextFile(FILE* file) const; 97 virtual int num_rows() const { return num_rows_; } 98 virtual int num_cols() const { return num_cols_; } 99 virtual int num_nonzeros() const { return rows_[num_rows_]; } 100 virtual const double* values() const { return values_.get(); } 101 virtual double* mutable_values() { return values_.get(); } 102 103 // Delete the bottom delta_rows. 104 // num_rows -= delta_rows 105 void DeleteRows(int delta_rows); 106 107 // Append the contents of m to the bottom of this matrix. m must 108 // have the same number of columns as this matrix. 109 void AppendRows(const CompressedRowSparseMatrix& m); 110 111 void ToCRSMatrix(CRSMatrix* matrix) const; 112 113 // Low level access methods that expose the structure of the matrix. 114 const int* cols() const { return cols_.get(); } 115 int* mutable_cols() { return cols_.get(); } 116 117 const int* rows() const { return rows_.get(); } 118 int* mutable_rows() { return rows_.get(); } 119 120 const vector<int>& row_blocks() const { return row_blocks_; } 121 vector<int>* mutable_row_blocks() { return &row_blocks_; } 122 123 const vector<int>& col_blocks() const { return col_blocks_; } 124 vector<int>* mutable_col_blocks() { return &col_blocks_; } 125 126 private: 127 scoped_array<int> cols_; 128 scoped_array<int> rows_; 129 scoped_array<double> values_; 130 131 int num_rows_; 132 int num_cols_; 133 int max_num_nonzeros_; 134 135 // If the matrix has an underlying block structure, then it can also 136 // carry with it row and column block sizes. This is auxilliary and 137 // optional information for use by algorithms operating on the 138 // matrix. The class itself does not make use of this information in 139 // any way. 140 vector<int> row_blocks_; 141 vector<int> col_blocks_; 142 143 CERES_DISALLOW_COPY_AND_ASSIGN(CompressedRowSparseMatrix); 144 }; 145 146 } // namespace internal 147 } // namespace ceres 148 149 #endif // CERES_INTERNAL_COMPRESSED_ROW_SPARSE_MATRIX_H_ 150