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_TRIPLET_SPARSE_MATRIX_H_ 32 #define CERES_INTERNAL_TRIPLET_SPARSE_MATRIX_H_ 33 34 #include "ceres/sparse_matrix.h" 35 #include "ceres/internal/eigen.h" 36 #include "ceres/internal/scoped_ptr.h" 37 #include "ceres/types.h" 38 39 namespace ceres { 40 namespace internal { 41 42 class SparseMatrixProto; 43 44 // An implementation of the SparseMatrix interface to store and 45 // manipulate sparse matrices in triplet (i,j,s) form. This object is 46 // inspired by the design of the cholmod_triplet struct used in the 47 // SuiteSparse package and is memory layout compatible with it. 48 class TripletSparseMatrix : public SparseMatrix { 49 public: 50 TripletSparseMatrix(); 51 TripletSparseMatrix(int num_rows, int num_cols, int max_num_nonzeros); 52 explicit TripletSparseMatrix(const TripletSparseMatrix& orig); 53 #ifndef CERES_NO_PROTOCOL_BUFFERS 54 explicit TripletSparseMatrix(const SparseMatrixProto& proto); 55 #endif 56 57 TripletSparseMatrix& operator=(const TripletSparseMatrix& rhs); 58 59 ~TripletSparseMatrix(); 60 61 // Implementation of the SparseMatrix interface. 62 virtual void SetZero(); 63 virtual void RightMultiply(const double* x, double* y) const; 64 virtual void LeftMultiply(const double* x, double* y) const; 65 virtual void SquaredColumnNorm(double* x) const; 66 virtual void ScaleColumns(const double* scale); 67 virtual void ToDenseMatrix(Matrix* dense_matrix) const; 68 #ifndef CERES_NO_PROTOCOL_BUFFERS 69 virtual void ToProto(SparseMatrixProto *proto) const; 70 #endif 71 virtual void ToTextFile(FILE* file) const; 72 virtual int num_rows() const { return num_rows_; } 73 virtual int num_cols() const { return num_cols_; } 74 virtual int num_nonzeros() const { return num_nonzeros_; } 75 virtual const double* values() const { return values_.get(); } 76 virtual double* mutable_values() { return values_.get(); } 77 virtual void set_num_nonzeros(int num_nonzeros); 78 79 // Increase max_num_nonzeros and correspondingly increase the size 80 // of rows_, cols_ and values_. If new_max_num_nonzeros is smaller 81 // than max_num_nonzeros_, then num_non_zeros should be less than or 82 // equal to new_max_num_nonzeros, otherwise data loss is possible 83 // and the method crashes. 84 void Reserve(int new_max_num_nonzeros); 85 86 // Append the matrix B at the bottom of this matrix. B should have 87 // the same number of columns as num_cols_. 88 void AppendRows(const TripletSparseMatrix& B); 89 90 // Append the matrix B at the right of this matrix. B should have 91 // the same number of rows as num_rows_; 92 void AppendCols(const TripletSparseMatrix& B); 93 94 // Resize the matrix. Entries which fall outside the new matrix 95 // bounds are dropped and the num_non_zeros changed accordingly. 96 void Resize(int new_num_rows, int new_num_cols); 97 98 int max_num_nonzeros() const { return max_num_nonzeros_; } 99 const int* rows() const { return rows_.get(); } 100 const int* cols() const { return cols_.get(); } 101 int* mutable_rows() { return rows_.get(); } 102 int* mutable_cols() { return cols_.get(); } 103 104 // Returns true if the entries of the matrix obey the row, column, 105 // and column size bounds and false otherwise. 106 bool AllTripletsWithinBounds() const; 107 108 bool IsValid() const { return AllTripletsWithinBounds(); } 109 110 // Build a sparse diagonal matrix of size num_rows x num_rows from 111 // the array values. Entries of the values array are copied into the 112 // sparse matrix. 113 static TripletSparseMatrix* CreateSparseDiagonalMatrix(const double* values, 114 int num_rows); 115 116 private: 117 void AllocateMemory(); 118 void CopyData(const TripletSparseMatrix& orig); 119 120 int num_rows_; 121 int num_cols_; 122 int max_num_nonzeros_; 123 int num_nonzeros_; 124 125 // The data is stored as three arrays. For each i, values_[i] is 126 // stored at the location (rows_[i], cols_[i]). If the there are 127 // multiple entries with the same (rows_[i], cols_[i]), the values_ 128 // entries corresponding to them are summed up. 129 scoped_array<int> rows_; 130 scoped_array<int> cols_; 131 scoped_array<double> values_; 132 }; 133 134 } // namespace internal 135 } // namespace ceres 136 137 #endif // CERES_INTERNAL_TRIPLET_SPARSE_MATRIX_H__ 138
