internal/ceres/block_sparse_matrix.h

   1 // Ceres Solver - A fast non-linear least squares minimizer
   2 // Copyright 2015 Google Inc. All rights reserved.
   3 // http://ceres-solver.org/
   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 // 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 TripletSparseMatrix;
  47
  48 // This class implements the SparseMatrix interface for storing and
  49 // manipulating block sparse matrices. The block structure is stored
  50 // in the CompressedRowBlockStructure object and one is needed to
  51 // initialize the matrix. For details on how the blocks structure of
  52 // the matrix is stored please see the documentation
  53 //
  54 //   internal/ceres/block_structure.h
  55 //
  56 class BlockSparseMatrix : public SparseMatrix {
  57  public:
  58   // Construct a block sparse matrix with a fully initialized
  59   // CompressedRowBlockStructure objected. The matrix takes over
  60   // ownership of this object and destroys it upon destruction.
  61   //
  62   // TODO(sameeragarwal): Add a function which will validate legal
  63   // CompressedRowBlockStructure objects.
  64   explicit BlockSparseMatrix(CompressedRowBlockStructure* block_structure);
  65
  66   BlockSparseMatrix();
  67   virtual ~BlockSparseMatrix();
  68
  69   // Implementation of SparseMatrix interface.
  70   virtual void SetZero();
  71   virtual void RightMultiply(const double* x, double* y) const;
  72   virtual void LeftMultiply(const double* x, double* y) const;
  73   virtual void SquaredColumnNorm(double* x) const;
  74   virtual void ScaleColumns(const double* scale);
  75   virtual void ToDenseMatrix(Matrix* dense_matrix) const;
  76   virtual void ToTextFile(FILE* file) const;
  77
  78   virtual int num_rows()         const { return num_rows_;     }
  79   virtual int num_cols()         const { return num_cols_;     }
  80   virtual int num_nonzeros()     const { return num_nonzeros_; }
  81   virtual const double* values() const { return values_.get(); }
  82   virtual double* mutable_values()     { return values_.get(); }
  83
  84   void ToTripletSparseMatrix(TripletSparseMatrix* matrix) const;
  85   const CompressedRowBlockStructure* block_structure() const;
  86
  87   // Append the contents of m to the bottom of this matrix. m must
  88   // have the same column blocks structure as this matrix.
  89   void AppendRows(const BlockSparseMatrix& m);
  90
  91   // Delete the bottom delta_rows_blocks.
  92   void DeleteRowBlocks(int delta_row_blocks);
  93
  94   static BlockSparseMatrix* CreateDiagonalMatrix(
  95       const double* diagonal,
  96       const std::vector<Block>& column_blocks);
  97
  98   struct RandomMatrixOptions {
  99     RandomMatrixOptions()
 100         : num_row_blocks(0),
 101           min_row_block_size(0),
 102           max_row_block_size(0),
 103           num_col_blocks(0),
 104           min_col_block_size(0),
 105           max_col_block_size(0),
 106           block_density(0.0) {
 107     }
 108
 109     int num_row_blocks;
 110     int min_row_block_size;
 111     int max_row_block_size;
 112     int num_col_blocks;
 113     int min_col_block_size;
 114     int max_col_block_size;
 115
 116     // 0 < block_density <= 1 is the probability of a block being
 117     // present in the matrix. A given random matrix will not have
 118     // precisely this density.
 119     double block_density;
 120   };
 121
 122   // Create a random BlockSparseMatrix whose entries are normally
 123   // distributed and whose structure is determined by
 124   // RandomMatrixOptions.
 125   //
 126   // Caller owns the result.
 127   static BlockSparseMatrix* CreateRandomMatrix(
 128       const RandomMatrixOptions& options);
 129
 130  private:
 131   int num_rows_;
 132   int num_cols_;
 133   int num_nonzeros_;
 134   int max_num_nonzeros_;
 135   scoped_array<double> values_;
 136   scoped_ptr<CompressedRowBlockStructure> block_structure_;
 137   CERES_DISALLOW_COPY_AND_ASSIGN(BlockSparseMatrix);
 138 };
 139
 140 }  // namespace internal
 141 }  // namespace ceres
 142
 143 #endif  // CERES_INTERNAL_BLOCK_SPARSE_MATRIX_H_