internal/ceres/dynamic_compressed_row_sparse_matrix_test.cc

   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: richie.stebbing@gmail.com (Richard Stebbing)
  30
  31 #include "ceres/dynamic_compressed_row_sparse_matrix.h"
  32
  33 #include "ceres/casts.h"
  34 #include "ceres/compressed_row_sparse_matrix.h"
  35 #include "ceres/internal/eigen.h"
  36 #include "ceres/internal/scoped_ptr.h"
  37 #include "ceres/linear_least_squares_problems.h"
  38 #include "ceres/triplet_sparse_matrix.h"
  39 #include "gtest/gtest.h"
  40
  41 namespace ceres {
  42 namespace internal {
  43
  44 using std::copy;
  45 using std::vector;
  46
  47 class DynamicCompressedRowSparseMatrixTest : public ::testing::Test {
  48  protected:
  49   virtual void SetUp() {
  50     num_rows = 7;
  51     num_cols = 4;
  52
  53     // The number of additional elements reserved when `Finalize` is called
  54     // should have no effect on the number of rows, columns or nonzeros.
  55     // Set this to some nonzero value to be sure.
  56     num_additional_elements = 13;
  57
  58     expected_num_nonzeros = num_rows * num_cols - std::min(num_rows, num_cols);
  59
  60     InitialiseDenseReference();
  61     InitialiseSparseMatrixReferences();
  62
  63     dcrsm.reset(new DynamicCompressedRowSparseMatrix(num_rows,
  64                                                      num_cols,
  65                                                      0));
  66   }
  67
  68   void Finalize() {
  69     dcrsm->Finalize(num_additional_elements);
  70   }
  71
  72   void InitialiseDenseReference() {
  73     dense.resize(num_rows, num_cols);
  74     dense.setZero();
  75     int num_nonzeros = 0;
  76     for (int i = 0; i < (num_rows * num_cols); ++i) {
  77       const int r = i / num_cols, c = i % num_cols;
  78       if (r != c) {
  79         dense(r, c) = i + 1;
  80         ++num_nonzeros;
  81       }
  82     }
  83     ASSERT_EQ(num_nonzeros, expected_num_nonzeros);
  84   }
  85
  86   void InitialiseSparseMatrixReferences() {
  87     vector<int> rows, cols;
  88     vector<double> values;
  89     for (int i = 0; i < (num_rows * num_cols); ++i) {
  90       const int r = i / num_cols, c = i % num_cols;
  91       if (r != c) {
  92         rows.push_back(r);
  93         cols.push_back(c);
  94         values.push_back(i + 1);
  95       }
  96     }
  97     ASSERT_EQ(values.size(), expected_num_nonzeros);
  98
  99     tsm.reset(new TripletSparseMatrix(num_rows,
 100                                       num_cols,
 101                                       expected_num_nonzeros));
 102     copy(rows.begin(), rows.end(), tsm->mutable_rows());
 103     copy(cols.begin(), cols.end(), tsm->mutable_cols());
 104     copy(values.begin(), values.end(), tsm->mutable_values());
 105     tsm->set_num_nonzeros(values.size());
 106
 107     Matrix dense_from_tsm;
 108     tsm->ToDenseMatrix(&dense_from_tsm);
 109     ASSERT_TRUE((dense.array() == dense_from_tsm.array()).all());
 110
 111     crsm.reset(CompressedRowSparseMatrix::FromTripletSparseMatrix(*tsm));
 112     Matrix dense_from_crsm;
 113     crsm->ToDenseMatrix(&dense_from_crsm);
 114     ASSERT_TRUE((dense.array() == dense_from_crsm.array()).all());
 115   }
 116
 117   void InsertNonZeroEntriesFromDenseReference() {
 118     for (int r = 0; r < num_rows; ++r) {
 119       for (int c = 0; c < num_cols; ++c) {
 120         const double& v = dense(r, c);
 121         if (v != 0.0) {
 122           dcrsm->InsertEntry(r, c, v);
 123         }
 124       }
 125     }
 126   }
 127
 128   void ExpectEmpty() {
 129     EXPECT_EQ(dcrsm->num_rows(), num_rows);
 130     EXPECT_EQ(dcrsm->num_cols(), num_cols);
 131     EXPECT_EQ(dcrsm->num_nonzeros(), 0);
 132
 133     Matrix dense_from_dcrsm;
 134     dcrsm->ToDenseMatrix(&dense_from_dcrsm);
 135     EXPECT_EQ(dense_from_dcrsm.rows(), num_rows);
 136     EXPECT_EQ(dense_from_dcrsm.cols(), num_cols);
 137     EXPECT_TRUE((dense_from_dcrsm.array() == 0.0).all());
 138   }
 139
 140   void ExpectEqualToDenseReference() {
 141     Matrix dense_from_dcrsm;
 142     dcrsm->ToDenseMatrix(&dense_from_dcrsm);
 143     EXPECT_TRUE((dense.array() == dense_from_dcrsm.array()).all());
 144   }
 145
 146   void ExpectEqualToCompressedRowSparseMatrixReference() {
 147     typedef Eigen::Map<const Eigen::VectorXi> ConstIntVectorRef;
 148
 149     ConstIntVectorRef crsm_rows(crsm->rows(), crsm->num_rows() + 1);
 150     ConstIntVectorRef dcrsm_rows(dcrsm->rows(), dcrsm->num_rows() + 1);
 151     EXPECT_TRUE((crsm_rows.array() == dcrsm_rows.array()).all());
 152
 153     ConstIntVectorRef crsm_cols(crsm->cols(), crsm->num_nonzeros());
 154     ConstIntVectorRef dcrsm_cols(dcrsm->cols(), dcrsm->num_nonzeros());
 155     EXPECT_TRUE((crsm_cols.array() == dcrsm_cols.array()).all());
 156
 157     ConstVectorRef crsm_values(crsm->values(), crsm->num_nonzeros());
 158     ConstVectorRef dcrsm_values(dcrsm->values(), dcrsm->num_nonzeros());
 159     EXPECT_TRUE((crsm_values.array() == dcrsm_values.array()).all());
 160   }
 161
 162   int num_rows;
 163   int num_cols;
 164
 165   int num_additional_elements;
 166
 167   int expected_num_nonzeros;
 168
 169   Matrix dense;
 170   scoped_ptr<TripletSparseMatrix> tsm;
 171   scoped_ptr<CompressedRowSparseMatrix> crsm;
 172
 173   scoped_ptr<DynamicCompressedRowSparseMatrix> dcrsm;
 174 };
 175
 176 TEST_F(DynamicCompressedRowSparseMatrixTest, Initialization) {
 177   ExpectEmpty();
 178
 179   Finalize();
 180   ExpectEmpty();
 181 }
 182
 183 TEST_F(DynamicCompressedRowSparseMatrixTest, InsertEntryAndFinalize) {
 184   InsertNonZeroEntriesFromDenseReference();
 185   ExpectEmpty();
 186
 187   Finalize();
 188   ExpectEqualToDenseReference();
 189   ExpectEqualToCompressedRowSparseMatrixReference();
 190 }
 191
 192 TEST_F(DynamicCompressedRowSparseMatrixTest, ClearRows) {
 193   InsertNonZeroEntriesFromDenseReference();
 194   Finalize();
 195   ExpectEqualToDenseReference();
 196   ExpectEqualToCompressedRowSparseMatrixReference();
 197
 198   dcrsm->ClearRows(0, 0);
 199   Finalize();
 200   ExpectEqualToDenseReference();
 201   ExpectEqualToCompressedRowSparseMatrixReference();
 202
 203   dcrsm->ClearRows(0, num_rows);
 204   ExpectEqualToCompressedRowSparseMatrixReference();
 205
 206   Finalize();
 207   ExpectEmpty();
 208
 209   InsertNonZeroEntriesFromDenseReference();
 210   dcrsm->ClearRows(1, 2);
 211   Finalize();
 212   dense.block(1, 0, 2, num_cols).setZero();
 213   ExpectEqualToDenseReference();
 214
 215   InitialiseDenseReference();
 216 }
 217
 218 }  // namespace internal
 219 }  // namespace ceres