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: fredp (at) google.com (Fred Pighin) 30 // 31 // Tests for linear solvers that solve symmetric linear systems. Some 32 // of this code is inhertited from Fred Pighin's code for testing the 33 // old Conjugate Gradients solver. 34 // 35 // TODO(sameeragarwal): More comprehensive testing with larger and 36 // more badly conditioned problem. 37 38 #include "gtest/gtest.h" 39 #include "ceres/conjugate_gradients_solver.h" 40 #include "ceres/linear_solver.h" 41 #include "ceres/triplet_sparse_matrix.h" 42 #include "ceres/internal/eigen.h" 43 #include "ceres/internal/scoped_ptr.h" 44 #include "ceres/types.h" 45 46 namespace ceres { 47 namespace internal { 48 49 TEST(ConjugateGradientTest, Solves3x3IdentitySystem) { 50 double diagonal[] = { 1.0, 1.0, 1.0 }; 51 scoped_ptr<TripletSparseMatrix> 52 A(TripletSparseMatrix::CreateSparseDiagonalMatrix(diagonal, 3)); 53 Vector b(3); 54 Vector x(3); 55 56 b(0) = 1.0; 57 b(1) = 2.0; 58 b(2) = 3.0; 59 60 x(0) = 1; 61 x(1) = 1; 62 x(2) = 1; 63 64 LinearSolver::Options options; 65 options.max_num_iterations = 10; 66 67 LinearSolver::PerSolveOptions per_solve_options; 68 per_solve_options.r_tolerance = 1e-9; 69 70 ConjugateGradientsSolver solver(options); 71 LinearSolver::Summary summary = 72 solver.Solve(A.get(), b.data(), per_solve_options, x.data()); 73 74 EXPECT_EQ(summary.termination_type, LINEAR_SOLVER_SUCCESS); 75 ASSERT_EQ(summary.num_iterations, 1); 76 77 ASSERT_DOUBLE_EQ(1, x(0)); 78 ASSERT_DOUBLE_EQ(2, x(1)); 79 ASSERT_DOUBLE_EQ(3, x(2)); 80 } 81 82 83 TEST(ConjuateGradientTest, Solves3x3SymmetricSystem) { 84 scoped_ptr<TripletSparseMatrix> A(new TripletSparseMatrix(3, 3, 9)); 85 Vector b(3); 86 Vector x(3); 87 88 // | 2 -1 0| 89 // A = |-1 2 -1| is symmetric positive definite. 90 // | 0 -1 2| 91 int* Ai = A->mutable_rows(); 92 int* Aj = A->mutable_cols(); 93 double* Ax = A->mutable_values(); 94 int counter = 0; 95 for (int i = 0; i < 3; ++i) { 96 for (int j = 0; j < 3; ++j) { 97 Ai[counter] = i; 98 Aj[counter] = j; 99 ++counter; 100 } 101 } 102 Ax[0] = 2.; 103 Ax[1] = -1.; 104 Ax[2] = 0; 105 Ax[3] = -1.; 106 Ax[4] = 2; 107 Ax[5] = -1; 108 Ax[6] = 0; 109 Ax[7] = -1; 110 Ax[8] = 2; 111 A->set_num_nonzeros(9); 112 113 b(0) = -1; 114 b(1) = 0; 115 b(2) = 3; 116 117 x(0) = 1; 118 x(1) = 1; 119 x(2) = 1; 120 121 LinearSolver::Options options; 122 options.max_num_iterations = 10; 123 124 LinearSolver::PerSolveOptions per_solve_options; 125 per_solve_options.r_tolerance = 1e-9; 126 127 ConjugateGradientsSolver solver(options); 128 LinearSolver::Summary summary = 129 solver.Solve(A.get(), b.data(), per_solve_options, x.data()); 130 131 EXPECT_EQ(summary.termination_type, LINEAR_SOLVER_SUCCESS); 132 133 ASSERT_DOUBLE_EQ(0, x(0)); 134 ASSERT_DOUBLE_EQ(1, x(1)); 135 ASSERT_DOUBLE_EQ(2, x(2)); 136 } 137 138 } // namespace internal 139 } // namespace ceres 140
