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