Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
LeastSquareConjugateGradient.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// Copyright (C) 2015 Gael Guennebaud <gael.guennebaud@inria.fr>
5//
6// This Source Code Form is subject to the terms of the Mozilla
7// Public License v. 2.0. If a copy of the MPL was not distributed
8// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
9// SPDX-License-Identifier: MPL-2.0
10
11#ifndef EIGEN_LEAST_SQUARE_CONJUGATE_GRADIENT_H
12#define EIGEN_LEAST_SQUARE_CONJUGATE_GRADIENT_H
13
14// IWYU pragma: private
15#include "./InternalHeaderCheck.h"
16
17namespace Eigen {
18
19namespace internal {
20
30template <typename MatrixType, typename Rhs, typename Dest, typename Preconditioner>
31EIGEN_DONT_INLINE void least_square_conjugate_gradient(const MatrixType& mat, const Rhs& rhs, Dest& x,
32 const Preconditioner& precond, Index& iters,
33 typename Dest::RealScalar& tol_error) {
34 using RealScalar = typename Dest::RealScalar;
35 using Scalar = typename Dest::Scalar;
36 using VectorType = Matrix<Scalar, Dynamic, 1>;
37
38 RealScalar tol = tol_error;
39 Index maxIters = iters;
40
41 Index m = mat.rows(), n = mat.cols();
42
43 VectorType residual = rhs - mat * x;
44 VectorType normal_residual = mat.adjoint() * residual;
45 VectorType normal_rhs = mat.adjoint() * rhs;
46
47 RealScalar rhsNorm = normal_rhs.stableNorm();
48 if (rhsNorm == 0) {
49 x.setZero();
50 iters = 0;
51 tol_error = 0;
52 return;
53 }
54 RealScalar threshold = tol * rhsNorm;
55 RealScalar residualNorm = normal_residual.stableNorm();
56 if (residualNorm == 0 || residualNorm < threshold) {
57 iters = 0;
58 tol_error = residualNorm / rhsNorm;
59 return;
60 }
61
62 // Keep the quadratic recurrence terms representable for very small or large residuals.
63 const RealScalar residualScale = internal::iterative_solver_scaling_factor(residualNorm);
64 normal_residual /= residualScale;
65 threshold /= residualScale;
66
67 VectorType p(n);
68 p = precond.solve(normal_residual); // initial search direction
69
70 VectorType z(n), tmp(m);
71 RealScalar absNew = numext::real(normal_residual.dot(p)); // the square of the absolute value of r scaled by invM
72 Index i = 0;
73 while (i < maxIters) {
74 tmp.noalias() = mat * p;
75
76 Scalar alpha = absNew / tmp.squaredNorm(); // the amount we travel on dir
77 x += (residualScale * alpha) * p; // update solution
78 residual -= (residualScale * alpha) * tmp; // update residual
79 normal_residual.noalias() = mat.adjoint() * residual; // update residual of the normal equation
80 normal_residual /= residualScale;
81
82 residualNorm = normal_residual.stableNorm();
83 if (residualNorm < threshold) break;
84
85 z = precond.solve(normal_residual); // approximately solve for "A'A z = normal_residual"
86
87 RealScalar absOld = absNew;
88 absNew = numext::real(normal_residual.dot(z)); // update the absolute value of r
89 RealScalar beta = absNew / absOld; // calculate the Gram-Schmidt value used to create the new search direction
90 p = z + beta * p; // update search direction
91 i++;
92 }
93 tol_error = residualNorm / (rhsNorm / residualScale);
94 iters = i;
95}
96
97} // namespace internal
98
99template <typename MatrixType_,
102
103namespace internal {
104
105template <typename MatrixType_, typename Preconditioner_>
106struct traits<LeastSquaresConjugateGradient<MatrixType_, Preconditioner_> > {
107 using MatrixType = MatrixType_;
108 using Preconditioner = Preconditioner_;
109};
110
111} // namespace internal
112
151template <typename MatrixType_, typename Preconditioner_>
153 : public IterativeSolverBase<LeastSquaresConjugateGradient<MatrixType_, Preconditioner_> > {
154 protected:
156 using Base::m_error;
157 using Base::m_info;
158 using Base::m_isInitialized;
159 using Base::m_iterations;
160 using Base::matrix;
161
162 public:
163 using MatrixType = MatrixType_;
164 using Scalar = typename MatrixType::Scalar;
165 using RealScalar = typename MatrixType::RealScalar;
166 using Preconditioner = Preconditioner_;
167
168 public:
171
182 template <typename MatrixDerived>
183 explicit LeastSquaresConjugateGradient(const EigenBase<MatrixDerived>& A) : Base(A.derived()) {}
184
186 template <typename Rhs, typename Dest>
187 void _solve_vector_with_guess_impl(const Rhs& b, Dest& x) const {
188 m_iterations = Base::maxIterations();
189 m_error = Base::m_tolerance;
190
191 internal::least_square_conjugate_gradient(matrix(), b, x, Base::m_preconditioner, m_iterations, m_error);
192 m_info = m_error <= Base::m_tolerance ? Success : NoConvergence;
193 }
194};
195
196} // end namespace Eigen
197
198#endif // EIGEN_LEAST_SQUARE_CONJUGATE_GRADIENT_H
Index maxIterations() const
Definition IterativeSolverBase.h:246
Jacobi preconditioner for LeastSquaresConjugateGradient.
Definition BasicPreconditioners.h:122
A conjugate gradient solver for sparse (or dense) least-square problems.
Definition LeastSquareConjugateGradient.h:153
LeastSquaresConjugateGradient()
Definition LeastSquareConjugateGradient.h:170
LeastSquaresConjugateGradient(const EigenBase< MatrixDerived > &A)
Definition LeastSquareConjugateGradient.h:183
@ Success
Definition Constants.h:457
@ NoConvergence
Definition Constants.h:461
Definition EigenBase.h:34