1 // Ceres Solver - A fast non-linear least squares minimizer
2 // Copyright 2017 Google Inc. All rights reserved.
3 // http://ceres-solver.org/
5 // Redistribution and use in source and binary forms, with or without
6 // modification, are permitted provided that the following conditions are met:
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.
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.
29 // Author: sameeragarwal@google.com (Sameer Agarwal)
31 #include "ceres/casts.h"
32 #include "ceres/compressed_row_sparse_matrix.h"
33 #include "ceres/internal/scoped_ptr.h"
34 #include "ceres/linear_least_squares_problems.h"
35 #include "ceres/linear_solver.h"
36 #include "ceres/triplet_sparse_matrix.h"
37 #include "ceres/types.h"
38 #include "glog/logging.h"
39 #include "gtest/gtest.h"
41 #include "Eigen/Cholesky"
46 // TODO(sameeragarwal): These tests needs to be re-written to be more
47 // thorough, they do not really test the dynamic nature of the
49 class DynamicSparseNormalCholeskySolverTest : public ::testing::Test {
51 virtual void SetUp() {
52 scoped_ptr<LinearLeastSquaresProblem> problem(
53 CreateLinearLeastSquaresProblemFromId(1));
54 A_.reset(CompressedRowSparseMatrix::FromTripletSparseMatrix(
55 *down_cast<TripletSparseMatrix*>(problem->A.get())));
56 b_.reset(problem->b.release());
57 D_.reset(problem->D.release());
60 void TestSolver(const LinearSolver::Options& options, double* D) {
62 A_->ToDenseMatrix(&dense_A);
63 Matrix lhs = dense_A.transpose() * dense_A;
65 lhs += (ConstVectorRef(D, A_->num_cols()).array() *
66 ConstVectorRef(D, A_->num_cols()).array())
71 Vector rhs(A_->num_cols());
73 A_->LeftMultiply(b_.get(), rhs.data());
74 Vector expected_solution = lhs.llt().solve(rhs);
76 scoped_ptr<LinearSolver> solver(LinearSolver::Create(options));
77 LinearSolver::PerSolveOptions per_solve_options;
78 per_solve_options.D = D;
79 Vector actual_solution(A_->num_cols());
80 LinearSolver::Summary summary;
81 summary = solver->Solve(
82 A_.get(), b_.get(), per_solve_options, actual_solution.data());
84 EXPECT_EQ(summary.termination_type, LINEAR_SOLVER_SUCCESS);
86 for (int i = 0; i < A_->num_cols(); ++i) {
87 EXPECT_NEAR(expected_solution(i), actual_solution(i), 1e-8)
88 << "\nExpected: " << expected_solution.transpose()
89 << "\nActual: " << actual_solution.transpose();
94 const SparseLinearAlgebraLibraryType sparse_linear_algebra_library_type) {
95 LinearSolver::Options options;
96 options.type = SPARSE_NORMAL_CHOLESKY;
97 options.dynamic_sparsity = true;
98 options.sparse_linear_algebra_library_type =
99 sparse_linear_algebra_library_type;
100 TestSolver(options, NULL);
101 TestSolver(options, D_.get());
104 scoped_ptr<CompressedRowSparseMatrix> A_;
105 scoped_array<double> b_;
106 scoped_array<double> D_;
109 #ifndef CERES_NO_SUITESPARSE
110 TEST_F(DynamicSparseNormalCholeskySolverTest, SuiteSparse) {
111 TestSolver(SUITE_SPARSE);
115 #ifndef CERES_NO_CXSPARSE
116 TEST_F(DynamicSparseNormalCholeskySolverTest, CXSparse) {
117 TestSolver(CX_SPARSE);
121 #ifdef CERES_USE_EIGEN_SPARSE
122 TEST_F(DynamicSparseNormalCholeskySolverTest, Eigen) {
123 TestSolver(EIGEN_SPARSE);
125 #endif // CERES_USE_EIGEN_SPARSE
127 } // namespace internal