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 // 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:
     54   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 
    118   virtual int num_rows()         const { return num_rows_;     }
    119   virtual int num_cols()         const { return num_cols_;     }
    120   virtual int num_nonzeros()     const { return num_nonzeros_; }
    121   virtual const double* values() const { return values_.get(); }
    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;
    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