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#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 39namespace ceres { 40namespace internal { 41 42class 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. 48class 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