diff options
Diffstat (limited to 'extern/ceres/internal/ceres/compressed_row_sparse_matrix.h')
| -rw-r--r-- | extern/ceres/internal/ceres/compressed_row_sparse_matrix.h | 173 |
1 files changed, 110 insertions, 63 deletions
diff --git a/extern/ceres/internal/ceres/compressed_row_sparse_matrix.h b/extern/ceres/internal/ceres/compressed_row_sparse_matrix.h index 987339d09a1..758b40bbc8a 100644 --- a/extern/ceres/internal/ceres/compressed_row_sparse_matrix.h +++ b/extern/ceres/internal/ceres/compressed_row_sparse_matrix.h @@ -32,7 +32,6 @@ #define CERES_INTERNAL_COMPRESSED_ROW_SPARSE_MATRIX_H_ #include <vector> -#include "ceres/internal/macros.h" #include "ceres/internal/port.h" #include "ceres/sparse_matrix.h" #include "ceres/types.h" @@ -48,13 +47,35 @@ class TripletSparseMatrix; class CompressedRowSparseMatrix : public SparseMatrix { public: - // Build a matrix with the same content as the TripletSparseMatrix - // m. TripletSparseMatrix objects are easier to construct - // incrementally, so we use them to initialize SparseMatrix - // objects. + enum StorageType { + UNSYMMETRIC, + // Matrix is assumed to be symmetric but only the lower triangular + // part of the matrix is stored. + LOWER_TRIANGULAR, + // Matrix is assumed to be symmetric but only the upper triangular + // part of the matrix is stored. + UPPER_TRIANGULAR + }; + + // Create a matrix with the same content as the TripletSparseMatrix + // input. We assume that input does not have any repeated + // entries. // - // We assume that m does not have any repeated entries. - explicit CompressedRowSparseMatrix(const TripletSparseMatrix& m); + // The storage type of the matrix is set to UNSYMMETRIC. + // + // Caller owns the result. + static CompressedRowSparseMatrix* FromTripletSparseMatrix( + const TripletSparseMatrix& input); + + // Create a matrix with the same content as the TripletSparseMatrix + // input transposed. We assume that input does not have any repeated + // entries. + // + // The storage type of the matrix is set to UNSYMMETRIC. + // + // Caller owns the result. + static CompressedRowSparseMatrix* FromTripletSparseMatrixTransposed( + const TripletSparseMatrix& input); // Use this constructor only if you know what you are doing. This // creates a "blank" matrix with the appropriate amount of memory @@ -67,30 +88,30 @@ class CompressedRowSparseMatrix : public SparseMatrix { // manually, instead of going via the indirect route of first // constructing a TripletSparseMatrix, which leads to more than // double the peak memory usage. - CompressedRowSparseMatrix(int num_rows, - int num_cols, - int max_num_nonzeros); + // + // The storage type is set to UNSYMMETRIC. + CompressedRowSparseMatrix(int num_rows, int num_cols, int max_num_nonzeros); // Build a square sparse diagonal matrix with num_rows rows and // columns. The diagonal m(i,i) = diagonal(i); + // + // The storage type is set to UNSYMMETRIC CompressedRowSparseMatrix(const double* diagonal, int num_rows); - virtual ~CompressedRowSparseMatrix(); - // SparseMatrix interface. - virtual void SetZero(); - virtual void RightMultiply(const double* x, double* y) const; - virtual void LeftMultiply(const double* x, double* y) const; - virtual void SquaredColumnNorm(double* x) const; - virtual void ScaleColumns(const double* scale); - - virtual void ToDenseMatrix(Matrix* dense_matrix) const; - virtual void ToTextFile(FILE* file) const; - virtual int num_rows() const { return num_rows_; } - virtual int num_cols() const { return num_cols_; } - virtual int num_nonzeros() const { return rows_[num_rows_]; } - virtual const double* values() const { return &values_[0]; } - virtual double* mutable_values() { return &values_[0]; } + virtual ~CompressedRowSparseMatrix(); + void SetZero() final; + void RightMultiply(const double* x, double* y) const final; + void LeftMultiply(const double* x, double* y) const final; + void SquaredColumnNorm(double* x) const final; + void ScaleColumns(const double* scale) final; + void ToDenseMatrix(Matrix* dense_matrix) const final; + void ToTextFile(FILE* file) const final; + int num_rows() const final { return num_rows_; } + int num_cols() const final { return num_cols_; } + int num_nonzeros() const final { return rows_[num_rows_]; } + const double* values() const final { return &values_[0]; } + double* mutable_values() final { return &values_[0]; } // Delete the bottom delta_rows. // num_rows -= delta_rows @@ -102,6 +123,15 @@ class CompressedRowSparseMatrix : public SparseMatrix { void ToCRSMatrix(CRSMatrix* matrix) const; + CompressedRowSparseMatrix* Transpose() const; + + // Destructive array resizing method. + void SetMaxNumNonZeros(int num_nonzeros); + + // Non-destructive array resizing method. + void set_num_rows(const int num_rows) { num_rows_ = num_rows; } + void set_num_cols(const int num_cols) { num_cols_ = num_cols; } + // Low level access methods that expose the structure of the matrix. const int* cols() const { return &cols_[0]; } int* mutable_cols() { return &cols_[0]; } @@ -109,60 +139,79 @@ class CompressedRowSparseMatrix : public SparseMatrix { const int* rows() const { return &rows_[0]; } int* mutable_rows() { return &rows_[0]; } + const StorageType storage_type() const { return storage_type_; } + void set_storage_type(const StorageType storage_type) { + storage_type_ = storage_type; + } + const std::vector<int>& row_blocks() const { return row_blocks_; } std::vector<int>* mutable_row_blocks() { return &row_blocks_; } const std::vector<int>& col_blocks() const { return col_blocks_; } std::vector<int>* mutable_col_blocks() { return &col_blocks_; } - // Destructive array resizing method. - void SetMaxNumNonZeros(int num_nonzeros); - - // Non-destructive array resizing method. - void set_num_rows(const int num_rows) { num_rows_ = num_rows; } - void set_num_cols(const int num_cols) { num_cols_ = num_cols; } - - void SolveLowerTriangularInPlace(double* solution) const; - void SolveLowerTriangularTransposeInPlace(double* solution) const; - - CompressedRowSparseMatrix* Transpose() const; - + // Create a block diagonal CompressedRowSparseMatrix with the given + // block structure. The individual blocks are assumed to be laid out + // contiguously in the diagonal array, one block at a time. + // + // Caller owns the result. static CompressedRowSparseMatrix* CreateBlockDiagonalMatrix( - const double* diagonal, - const std::vector<int>& blocks); + const double* diagonal, const std::vector<int>& blocks); - // Compute the sparsity structure of the product m.transpose() * m - // and create a CompressedRowSparseMatrix corresponding to it. + // Options struct to control the generation of random block sparse + // matrices in compressed row sparse format. + // + // The random matrix generation proceeds as follows. // - // Also compute a "program" vector, which for every term in the - // outer product points to the entry in the values array of the - // result matrix where it should be accumulated. + // First the row and column block structure is determined by + // generating random row and column block sizes that lie within the + // given bounds. // - // This program is used by the ComputeOuterProduct function below to - // compute the outer product. + // Then we walk the block structure of the resulting matrix, and with + // probability block_density detemine whether they are structurally + // zero or not. If the answer is no, then we generate entries for the + // block which are distributed normally. + struct RandomMatrixOptions { + // Type of matrix to create. + // + // If storage_type is UPPER_TRIANGULAR (LOWER_TRIANGULAR), then + // create a square symmetric matrix with just the upper triangular + // (lower triangular) part. In this case, num_col_blocks, + // min_col_block_size and max_col_block_size will be ignored and + // assumed to be equal to the corresponding row settings. + StorageType storage_type = UNSYMMETRIC; + + int num_row_blocks = 0; + int min_row_block_size = 0; + int max_row_block_size = 0; + int num_col_blocks = 0; + int min_col_block_size = 0; + int max_col_block_size = 0; + + // 0 < block_density <= 1 is the probability of a block being + // present in the matrix. A given random matrix will not have + // precisely this density. + double block_density = 0.0; + }; + + // Create a random CompressedRowSparseMatrix whose entries are + // normally distributed and whose structure is determined by + // RandomMatrixOptions. // - // Since the entries of the program are the same for rows with the - // same sparsity structure, the program only stores the result for - // one row per row block. The ComputeOuterProduct function reuses - // this information for each row in the row block. - static CompressedRowSparseMatrix* CreateOuterProductMatrixAndProgram( - const CompressedRowSparseMatrix& m, - std::vector<int>* program); - - // Compute the values array for the expression m.transpose() * m, - // where the matrix used to store the result and a program have been - // created using the CreateOuterProductMatrixAndProgram function - // above. - static void ComputeOuterProduct(const CompressedRowSparseMatrix& m, - const std::vector<int>& program, - CompressedRowSparseMatrix* result); + // Caller owns the result. + static CompressedRowSparseMatrix* CreateRandomMatrix( + RandomMatrixOptions options); private: + static CompressedRowSparseMatrix* FromTripletSparseMatrix( + const TripletSparseMatrix& input, bool transpose); + int num_rows_; int num_cols_; std::vector<int> rows_; std::vector<int> cols_; std::vector<double> values_; + StorageType storage_type_; // If the matrix has an underlying block structure, then it can also // carry with it row and column block sizes. This is auxilliary and @@ -171,8 +220,6 @@ class CompressedRowSparseMatrix : public SparseMatrix { // any way. std::vector<int> row_blocks_; std::vector<int> col_blocks_; - - CERES_DISALLOW_COPY_AND_ASSIGN(CompressedRowSparseMatrix); }; } // namespace internal |