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 #include <limits> 32 #include <vector> 33 #include "ceres/block_random_access_sparse_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(BlockRandomAccessSparseMatrix, 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 BlockRandomAccessSparseMatrix 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 EXPECT_EQ(row_stride, blocks[row_block_id]); 82 EXPECT_EQ(col_stride, blocks[col_block_id]); 83 84 // Write into the block 85 MatrixRef(cell->values, row_stride, col_stride).block( 86 row, col, blocks[row_block_id], blocks[col_block_id]) = 87 (row_block_id + 1) * (col_block_id +1) * 88 Matrix::Ones(blocks[row_block_id], blocks[col_block_id]); 89 } 90 91 const TripletSparseMatrix* tsm = m.matrix(); 92 EXPECT_EQ(tsm->num_nonzeros(), num_nonzeros); 93 EXPECT_EQ(tsm->max_num_nonzeros(), num_nonzeros); 94 95 Matrix dense; 96 tsm->ToDenseMatrix(&dense); 97 98 double kTolerance = 1e-14; 99 100 // (0,0) 101 EXPECT_NEAR((dense.block(0, 0, 3, 3) - Matrix::Ones(3, 3)).norm(), 102 0.0, 103 kTolerance); 104 // (1,1) 105 EXPECT_NEAR((dense.block(3, 3, 4, 4) - 2 * 2 * Matrix::Ones(4, 4)).norm(), 106 0.0, 107 kTolerance); 108 // (1,2) 109 EXPECT_NEAR((dense.block(3, 3 + 4, 4, 5) - 2 * 3 * Matrix::Ones(4, 5)).norm(), 110 0.0, 111 kTolerance); 112 // (2,0) 113 EXPECT_NEAR((dense.block(3 + 4, 0, 5, 3) - 3 * 1 * Matrix::Ones(5, 3)).norm(), 114 0.0, 115 kTolerance); 116 117 // There is nothing else in the matrix besides these four blocks. 118 EXPECT_NEAR(dense.norm(), sqrt(9. + 16. * 16. + 36. * 20. + 9. * 15.), 119 kTolerance); 120 } 121 122 // IntPairToLong is private, thus this fixture is needed to access and 123 // test it. 124 class BlockRandomAccessSparseMatrixTest : public ::testing::Test { 125 public: 126 virtual void SetUp() { 127 vector<int> blocks; 128 blocks.push_back(1); 129 set< pair<int, int> > block_pairs; 130 block_pairs.insert(make_pair(0, 0)); 131 m_.reset(new BlockRandomAccessSparseMatrix(blocks, block_pairs)); 132 } 133 134 void CheckIntPair(int a, int b) { 135 int64 value = m_->IntPairToLong(a, b); 136 EXPECT_GT(value, 0) << "Overflow a = " << a << " b = " << b; 137 EXPECT_GT(value, a) << "Overflow a = " << a << " b = " << b; 138 EXPECT_GT(value, b) << "Overflow a = " << a << " b = " << b; 139 } 140 141 private: 142 scoped_ptr<BlockRandomAccessSparseMatrix> m_; 143 }; 144 145 TEST_F(BlockRandomAccessSparseMatrixTest, IntPairToLongOverflow) { 146 CheckIntPair(numeric_limits<int>::max(), numeric_limits<int>::max()); 147 } 148 149 } // namespace internal 150 } // namespace ceres 151
