1 // Ceres Solver - A fast non-linear least squares minimizer 2 // Copyright 2013 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 #include <limits> 32 #include <vector> 33 #include "ceres/block_random_access_crs_matrix.h" 34 #include "ceres/internal/eigen.h" 35 #include "glog/logging.h" 36 #include "gtest/gtest.h" 37 38 namespace ceres { 39 namespace internal { 40 41 TEST(BlockRandomAccessCRSMatrix, GetCell) { 42 vector<int> blocks; 43 blocks.push_back(3); 44 blocks.push_back(4); 45 blocks.push_back(5); 46 const int num_rows = 3 + 4 + 5; 47 48 set< pair<int, int> > block_pairs; 49 int num_nonzeros = 0; 50 block_pairs.insert(make_pair(0, 0)); 51 num_nonzeros += blocks[0] * blocks[0]; 52 53 block_pairs.insert(make_pair(1, 1)); 54 num_nonzeros += blocks[1] * blocks[1]; 55 56 block_pairs.insert(make_pair(1, 2)); 57 num_nonzeros += blocks[1] * blocks[2]; 58 59 block_pairs.insert(make_pair(2, 0)); 60 num_nonzeros += blocks[2] * blocks[0]; 61 62 BlockRandomAccessCRSMatrix m(blocks, block_pairs); 63 EXPECT_EQ(m.num_rows(), num_rows); 64 EXPECT_EQ(m.num_cols(), num_rows); 65 66 for (set<pair<int, int> >::const_iterator it = block_pairs.begin(); 67 it != block_pairs.end(); 68 ++it) { 69 const int row_block_id = it->first; 70 const int col_block_id = it->second; 71 int row; 72 int col; 73 int row_stride; 74 int col_stride; 75 CellInfo* cell = m.GetCell(row_block_id, col_block_id, 76 &row, &col, 77 &row_stride, &col_stride); 78 EXPECT_TRUE(cell != NULL); 79 EXPECT_EQ(row, 0); 80 EXPECT_EQ(col, 0); 81 82 // Write into the block. 83 MatrixRef(cell->values, row_stride, col_stride).block( 84 row, col, blocks[row_block_id], blocks[col_block_id]) = 85 (row_block_id + 1) * (col_block_id +1) * 86 Matrix::Ones(blocks[row_block_id], blocks[col_block_id]); 87 } 88 89 const CompressedRowSparseMatrix* crsm = m.matrix(); 90 EXPECT_EQ(crsm->num_nonzeros(), num_nonzeros); 91 92 Matrix dense; 93 crsm->ToDenseMatrix(&dense); 94 95 double kTolerance = 1e-14; 96 97 // (0,0) 98 EXPECT_NEAR((dense.block(0, 0, 3, 3) - Matrix::Ones(3, 3)).norm(), 99 0.0, 100 kTolerance); 101 // (1,1) 102 EXPECT_NEAR((dense.block(3, 3, 4, 4) - 2 * 2 * Matrix::Ones(4, 4)).norm(), 103 0.0, 104 kTolerance); 105 // (1,2) 106 EXPECT_NEAR((dense.block(3, 3 + 4, 4, 5) - 2 * 3 * Matrix::Ones(4, 5)).norm(), 107 0.0, 108 kTolerance); 109 // (2,0) 110 EXPECT_NEAR((dense.block(3 + 4, 0, 5, 3) - 3 * 1 * Matrix::Ones(5, 3)).norm(), 111 0.0, 112 kTolerance); 113 114 // There is nothing else in the matrix besides these four blocks. 115 EXPECT_NEAR(dense.norm(), sqrt(9. + 16. * 16. + 36. * 20. + 9. * 15.), 116 kTolerance); 117 } 118 119 // IntPairToLong is private, thus this fixture is needed to access and 120 // test it. 121 class BlockRandomAccessCRSMatrixTest : public ::testing::Test { 122 public: 123 virtual void SetUp() { 124 vector<int> blocks; 125 blocks.push_back(1); 126 set< pair<int, int> > block_pairs; 127 block_pairs.insert(make_pair(0, 0)); 128 m_.reset(new BlockRandomAccessCRSMatrix(blocks, block_pairs)); 129 } 130 131 void CheckIntPair(int a, int b) { 132 int64 value = m_->IntPairToLong(a, b); 133 EXPECT_GT(value, 0) << "Overflow a = " << a << " b = " << b; 134 EXPECT_GT(value, a) << "Overflow a = " << a << " b = " << b; 135 EXPECT_GT(value, b) << "Overflow a = " << a << " b = " << b; 136 } 137 138 private: 139 scoped_ptr<BlockRandomAccessCRSMatrix> m_; 140 }; 141 142 TEST_F(BlockRandomAccessCRSMatrixTest, IntPairToLongOverflow) { 143 CheckIntPair(numeric_limits<int>::max(), numeric_limits<int>::max()); 144 } 145 146 147 } // namespace internal 148 } // namespace ceres 149
