Sameer Agarwal | efa0911 | 2017-06-07 20:59:44 -0400 | [diff] [blame] | 1 | // Ceres Solver - A fast non-linear least squares minimizer |
Sameer Agarwal | 5a30cae | 2023-09-19 15:29:34 -0700 | [diff] [blame] | 2 | // Copyright 2023 Google Inc. All rights reserved. |
Sameer Agarwal | efa0911 | 2017-06-07 20:59:44 -0400 | [diff] [blame] | 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: sameeragarwal@google.com (Sameer Agarwal) |
| 30 | |
Keir Mierle | 7c4e8a4 | 2018-03-30 16:16:59 -0700 | [diff] [blame] | 31 | #include <memory> |
Nikolaus Demmel | 7b8f675 | 2020-09-20 21:45:24 +0200 | [diff] [blame] | 32 | |
Sameer Agarwal | efa0911 | 2017-06-07 20:59:44 -0400 | [diff] [blame] | 33 | #include "ceres/casts.h" |
Mike Vitus | f408f89 | 2018-02-22 10:28:39 -0800 | [diff] [blame] | 34 | #include "ceres/context_impl.h" |
Sameer Agarwal | 4705159 | 2022-03-12 15:22:19 -0800 | [diff] [blame] | 35 | #include "ceres/internal/config.h" |
Sameer Agarwal | efa0911 | 2017-06-07 20:59:44 -0400 | [diff] [blame] | 36 | #include "ceres/linear_least_squares_problems.h" |
| 37 | #include "ceres/linear_solver.h" |
| 38 | #include "ceres/triplet_sparse_matrix.h" |
| 39 | #include "ceres/types.h" |
| 40 | #include "glog/logging.h" |
| 41 | #include "gtest/gtest.h" |
| 42 | |
Sameer Agarwal | caf614a | 2022-04-21 17:41:10 -0700 | [diff] [blame] | 43 | namespace ceres::internal { |
Sameer Agarwal | efa0911 | 2017-06-07 20:59:44 -0400 | [diff] [blame] | 44 | |
Sergiu Deitsch | c8658c8 | 2022-02-20 02:22:17 +0100 | [diff] [blame] | 45 | using Param = ::testing:: |
| 46 | tuple<LinearSolverType, DenseLinearAlgebraLibraryType, bool, int>; |
Sameer Agarwal | efa0911 | 2017-06-07 20:59:44 -0400 | [diff] [blame] | 47 | |
Sergey Sharybin | 54ba6c2 | 2017-12-23 18:18:24 +0100 | [diff] [blame] | 48 | static std::string ParamInfoToString(testing::TestParamInfo<Param> info) { |
Sameer Agarwal | efa0911 | 2017-06-07 20:59:44 -0400 | [diff] [blame] | 49 | Param param = info.param; |
| 50 | std::stringstream ss; |
| 51 | ss << LinearSolverTypeToString(::testing::get<0>(param)) << "_" |
| 52 | << DenseLinearAlgebraLibraryTypeToString(::testing::get<1>(param)) << "_" |
| 53 | << (::testing::get<2>(param) ? "Regularized" : "Unregularized") << "_" |
| 54 | << ::testing::get<3>(param); |
| 55 | return ss.str(); |
| 56 | } |
| 57 | |
| 58 | class DenseLinearSolverTest : public ::testing::TestWithParam<Param> {}; |
| 59 | |
| 60 | TEST_P(DenseLinearSolverTest, _) { |
| 61 | Param param = GetParam(); |
| 62 | const bool regularized = testing::get<2>(param); |
| 63 | |
Sameer Agarwal | ae65219 | 2022-02-02 13:17:29 -0800 | [diff] [blame] | 64 | std::unique_ptr<LinearLeastSquaresProblem> problem = |
| 65 | CreateLinearLeastSquaresProblemFromId(testing::get<3>(param)); |
Sameer Agarwal | efa0911 | 2017-06-07 20:59:44 -0400 | [diff] [blame] | 66 | DenseSparseMatrix lhs(*down_cast<TripletSparseMatrix*>(problem->A.get())); |
| 67 | |
| 68 | const int num_cols = lhs.num_cols(); |
| 69 | const int num_rows = lhs.num_rows(); |
| 70 | |
| 71 | Vector rhs = Vector::Zero(num_rows + num_cols); |
| 72 | rhs.head(num_rows) = ConstVectorRef(problem->b.get(), num_rows); |
| 73 | |
| 74 | LinearSolver::Options options; |
| 75 | options.type = ::testing::get<0>(param); |
| 76 | options.dense_linear_algebra_library_type = ::testing::get<1>(param); |
Mike Vitus | f408f89 | 2018-02-22 10:28:39 -0800 | [diff] [blame] | 77 | ContextImpl context; |
| 78 | options.context = &context; |
Keir Mierle | 7c4e8a4 | 2018-03-30 16:16:59 -0700 | [diff] [blame] | 79 | std::unique_ptr<LinearSolver> solver(LinearSolver::Create(options)); |
Sameer Agarwal | efa0911 | 2017-06-07 20:59:44 -0400 | [diff] [blame] | 80 | |
| 81 | LinearSolver::PerSolveOptions per_solve_options; |
| 82 | if (regularized) { |
| 83 | per_solve_options.D = problem->D.get(); |
| 84 | } |
| 85 | |
| 86 | Vector solution(num_cols); |
| 87 | LinearSolver::Summary summary = |
| 88 | solver->Solve(&lhs, rhs.data(), per_solve_options, solution.data()); |
Sameer Agarwal | c8493fc | 2022-05-14 14:14:22 -0700 | [diff] [blame] | 89 | EXPECT_EQ(summary.termination_type, LinearSolverTerminationType::SUCCESS); |
Sameer Agarwal | efa0911 | 2017-06-07 20:59:44 -0400 | [diff] [blame] | 90 | |
Sameer Agarwal | cab853f | 2022-01-26 11:00:48 -0800 | [diff] [blame] | 91 | Vector normal_rhs = lhs.matrix().transpose() * rhs.head(num_rows); |
| 92 | Matrix normal_lhs = lhs.matrix().transpose() * lhs.matrix(); |
Sameer Agarwal | efa0911 | 2017-06-07 20:59:44 -0400 | [diff] [blame] | 93 | |
Sameer Agarwal | cab853f | 2022-01-26 11:00:48 -0800 | [diff] [blame] | 94 | if (regularized) { |
| 95 | ConstVectorRef diagonal(problem->D.get(), num_cols); |
| 96 | normal_lhs += diagonal.array().square().matrix().asDiagonal(); |
| 97 | } |
Sameer Agarwal | efa0911 | 2017-06-07 20:59:44 -0400 | [diff] [blame] | 98 | |
Sameer Agarwal | cab853f | 2022-01-26 11:00:48 -0800 | [diff] [blame] | 99 | Vector actual_normal_rhs = normal_lhs * solution; |
Sameer Agarwal | efa0911 | 2017-06-07 20:59:44 -0400 | [diff] [blame] | 100 | |
Sameer Agarwal | cab853f | 2022-01-26 11:00:48 -0800 | [diff] [blame] | 101 | const double normalized_residual = |
| 102 | (normal_rhs - actual_normal_rhs).norm() / normal_rhs.norm(); |
| 103 | |
| 104 | EXPECT_NEAR( |
| 105 | normalized_residual, 0.0, 10 * std::numeric_limits<double>::epsilon()) |
| 106 | << "\nexpected: " << normal_rhs.transpose() |
Sameer Agarwal | 6d06e9b | 2022-01-21 18:33:16 -0800 | [diff] [blame] | 107 | << "\nactual: " << actual_normal_rhs.transpose(); |
Sameer Agarwal | efa0911 | 2017-06-07 20:59:44 -0400 | [diff] [blame] | 108 | } |
| 109 | |
Sergey Sharybin | 54ba6c2 | 2017-12-23 18:18:24 +0100 | [diff] [blame] | 110 | namespace { |
| 111 | |
Sameer Agarwal | efa0911 | 2017-06-07 20:59:44 -0400 | [diff] [blame] | 112 | // TODO(sameeragarwal): Should we move away from hard coded linear |
| 113 | // least squares problem to randomly generated ones? |
Sameer Agarwal | 15dc18a | 2017-06-12 21:30:27 -0700 | [diff] [blame] | 114 | #ifndef CERES_NO_LAPACK |
| 115 | |
Sameer Agarwal | 6e52739 | 2019-03-02 22:42:20 -0800 | [diff] [blame] | 116 | INSTANTIATE_TEST_SUITE_P( |
Sameer Agarwal | efa0911 | 2017-06-07 20:59:44 -0400 | [diff] [blame] | 117 | DenseLinearSolver, |
| 118 | DenseLinearSolverTest, |
| 119 | ::testing::Combine(::testing::Values(DENSE_QR, DENSE_NORMAL_CHOLESKY), |
Sameer Agarwal | efa0911 | 2017-06-07 20:59:44 -0400 | [diff] [blame] | 120 | ::testing::Values(EIGEN, LAPACK), |
Sameer Agarwal | efa0911 | 2017-06-07 20:59:44 -0400 | [diff] [blame] | 121 | ::testing::Values(true, false), |
| 122 | ::testing::Values(0, 1)), |
| 123 | ParamInfoToString); |
| 124 | |
Sameer Agarwal | 15dc18a | 2017-06-12 21:30:27 -0700 | [diff] [blame] | 125 | #else |
| 126 | |
Sameer Agarwal | 6e52739 | 2019-03-02 22:42:20 -0800 | [diff] [blame] | 127 | INSTANTIATE_TEST_SUITE_P( |
Sameer Agarwal | 15dc18a | 2017-06-12 21:30:27 -0700 | [diff] [blame] | 128 | DenseLinearSolver, |
| 129 | DenseLinearSolverTest, |
| 130 | ::testing::Combine(::testing::Values(DENSE_QR, DENSE_NORMAL_CHOLESKY), |
| 131 | ::testing::Values(EIGEN), |
| 132 | ::testing::Values(true, false), |
| 133 | ::testing::Values(0, 1)), |
| 134 | ParamInfoToString); |
| 135 | |
| 136 | #endif |
Sergey Sharybin | 54ba6c2 | 2017-12-23 18:18:24 +0100 | [diff] [blame] | 137 | } // namespace |
Sameer Agarwal | caf614a | 2022-04-21 17:41:10 -0700 | [diff] [blame] | 138 | } // namespace ceres::internal |