Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
GMRES.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// Copyright (C) 2011 Gael Guennebaud <gael.guennebaud@inria.fr>
5// Copyright (C) 2012, 2014 Kolja Brix <brix@igpm.rwth-aaachen.de>
6//
7// This Source Code Form is subject to the terms of the Mozilla
8// Public License v. 2.0. If a copy of the MPL was not distributed
9// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
10// SPDX-License-Identifier: MPL-2.0
11
12#ifndef EIGEN_GMRES_H
13#define EIGEN_GMRES_H
14
15// IWYU pragma: private
16#include "./InternalHeaderCheck.h"
17
18namespace Eigen {
19
20namespace internal {
21
60template <typename MatrixType, typename Rhs, typename Dest, typename Preconditioner>
61bool gmres(const MatrixType& mat, const Rhs& rhs, Dest& x, const Preconditioner& precond, Index& iters,
62 const Index& restart_, typename Dest::RealScalar& tol_error) {
63 using RealScalar = typename Dest::RealScalar;
64 using Scalar = typename Dest::Scalar;
65 using VectorType = Matrix<Scalar, Dynamic, 1>;
66 using FMatrixType = Matrix<Scalar, Dynamic, Dynamic, ColMajor>;
67
68 const RealScalar considerAsZero = (std::numeric_limits<RealScalar>::min)();
69
70 if (rhs.norm() <= considerAsZero) {
71 x.setZero();
72 iters = 0;
73 tol_error = 0;
74 return true;
75 }
76
77 RealScalar tol = tol_error;
78 const Index maxIters = iters;
79 iters = 0;
80
81 const Index m = mat.rows();
82 // A GMRES cycle cannot use more Krylov vectors than the problem dimension, so cap the internal workspace even if
83 // the user requests a larger restart value.
84 const Index restart = numext::mini(numext::maxi(restart_, Index(1)), m);
85
86 // residual and preconditioned residual
87 VectorType p0 = rhs - mat * x;
88 VectorType r0 = precond.solve(p0);
89
90 const RealScalar r0Norm = r0.norm();
91 // w(k) tracks the residual norm of the left-preconditioned system. Normalize it by the matching right-hand
92 // side, not by the initial residual, so solveWithGuess() uses the same relative-residual criterion as solve().
93 const RealScalar rhsNorm = numext::maxi((x.squaredNorm() == 0) ? r0Norm : precond.solve(rhs).norm(), considerAsZero);
94 const RealScalar threshold = numext::maxi(tol * rhsNorm, considerAsZero);
95
96 // is initial guess already good enough?
97 if (r0Norm < threshold) {
98 tol_error = r0Norm / rhsNorm;
99 return true;
100 }
101
102 // storage for Hessenberg matrix and Householder data
103 FMatrixType H = FMatrixType::Zero(m, restart + 1);
104 VectorType w = VectorType::Zero(restart + 1);
105 VectorType tau = VectorType::Zero(restart + 1);
106
107 // storage for Jacobi rotations
108 std::vector<JacobiRotation<Scalar> > G(restart);
109
110 // storage for temporaries
111 VectorType t(m), v(m), workspace(m), x_new(m);
112
113 // generate first Householder vector
114 Ref<VectorType> H0_tail = H.col(0).tail(m - 1);
115 RealScalar beta;
116 r0.makeHouseholder(H0_tail, tau.coeffRef(0), beta);
117 w(0) = Scalar(beta);
118
119 for (Index k = 1; k <= restart; ++k) {
120 ++iters;
121
122 v = VectorType::Unit(m, k - 1);
123
124 // apply Householder reflections H_{1} ... H_{k-1} to v
125 // TODO: use a HouseholderSequence
126 for (Index i = k - 1; i >= 0; --i) {
127 v.tail(m - i).applyHouseholderOnTheLeft(H.col(i).tail(m - i - 1), tau.coeffRef(i), workspace.data());
128 }
129
130 // apply matrix M to v: v = mat * v;
131 t.noalias() = mat * v;
132 v = precond.solve(t);
133
134 // apply Householder reflections H_{k-1} ... H_{1} to v
135 // TODO: use a HouseholderSequence
136 for (Index i = 0; i < k; ++i) {
137 v.tail(m - i).applyHouseholderOnTheLeft(H.col(i).tail(m - i - 1), tau.coeffRef(i), workspace.data());
138 }
139
140 if (v.tail(m - k).norm() != 0.0 && k <= restart) {
141 // generate new Householder vector
142 Ref<VectorType> Hk_tail = H.col(k).tail(m - k - 1);
143 v.tail(m - k).makeHouseholder(Hk_tail, tau.coeffRef(k), beta);
144
145 // apply Householder reflection H_{k} to v
146 v.tail(m - k).applyHouseholderOnTheLeft(Hk_tail, tau.coeffRef(k), workspace.data());
147 }
148
149 // apply old Givens rotations to v
150 for (Index i = 0; i < k - 1; ++i) {
151 v.applyOnTheLeft(i, i + 1, G[i].adjoint());
152 }
153
154 if (k < m && v(k) != (Scalar)0) {
155 // determine next Givens rotation
156 G[k - 1].makeGivens(v(k - 1), v(k));
157
158 // apply Givens rotation to v and w
159 v.applyOnTheLeft(k - 1, k, G[k - 1].adjoint());
160 w.applyOnTheLeft(k - 1, k, G[k - 1].adjoint());
161 }
162
163 // insert coefficients into upper matrix triangle
164 H.col(k - 1).head(k) = v.head(k);
165
166 tol_error = numext::abs(w(k)) / rhsNorm;
167 bool stop = (k == m || tol_error < tol || iters == maxIters);
168
169 if (stop || k == restart) {
170 // solve upper triangular system
171 Ref<VectorType> y = w.head(k);
172 H.topLeftCorner(k, k).template triangularView<Upper>().solveInPlace(y);
173
174 // use Horner-like scheme to calculate solution vector
175 x_new.setZero();
176 for (Index i = k - 1; i >= 0; --i) {
177 x_new(i) += y(i);
178 // apply Householder reflection H_{i} to x_new
179 x_new.tail(m - i).applyHouseholderOnTheLeft(H.col(i).tail(m - i - 1), tau.coeffRef(i), workspace.data());
180 }
181
182 x += x_new;
183
184 if (stop) {
185 return true;
186 } else {
187 k = 0;
188
189 // reset data for restart
190 p0.noalias() = rhs - mat * x;
191 r0 = precond.solve(p0);
192
193 // clear Hessenberg matrix and Householder data
194 H.setZero();
195 w.setZero();
196 tau.setZero();
197
198 // generate first Householder vector
199 r0.makeHouseholder(H0_tail, tau.coeffRef(0), beta);
200 w(0) = Scalar(beta);
201 }
202 }
203 }
204
205 return false;
206}
207
208} // namespace internal
209
210template <typename MatrixType_, typename Preconditioner_ = DiagonalPreconditioner<typename MatrixType_::Scalar> >
211class GMRES;
212
213namespace internal {
214
215template <typename MatrixType_, typename Preconditioner_>
216struct traits<GMRES<MatrixType_, Preconditioner_> > {
217 using MatrixType = MatrixType_;
218 using Preconditioner = Preconditioner_;
219};
220
221} // namespace internal
222
261template <typename MatrixType_, typename Preconditioner_>
262class GMRES : public IterativeSolverBase<GMRES<MatrixType_, Preconditioner_> > {
263 protected:
264 using Base = IterativeSolverBase<GMRES>;
265 using Base::m_error;
266 using Base::m_info;
267 using Base::m_isInitialized;
268 using Base::m_iterations;
269 using Base::matrix;
270
271 private:
272 Index m_restart = 30;
273
274 public:
275 using Base::_solve_impl;
276 using MatrixType = MatrixType_;
277 using Scalar = typename MatrixType::Scalar;
278 using RealScalar = typename MatrixType::RealScalar;
279 using Preconditioner = Preconditioner_;
280
281 public:
283 GMRES() : Base(), m_restart(30) {}
284
295 template <typename MatrixDerived>
296 explicit GMRES(const EigenBase<MatrixDerived>& A) : Base(A.derived()), m_restart(30) {}
297
300 Index get_restart() const { return m_restart; }
301
305 void set_restart(const Index restart) { m_restart = restart; }
306
308 template <typename Rhs, typename Dest>
309 void _solve_vector_with_guess_impl(const Rhs& b, Dest& x) const {
310 m_iterations = Base::maxIterations();
311 m_error = Base::m_tolerance;
312 bool ret = internal::gmres(matrix(), b, x, Base::m_preconditioner, m_iterations, m_restart, m_error);
313 m_info = (!ret) ? NumericalIssue : m_error <= Base::m_tolerance ? Success : NoConvergence;
314 }
315
316 protected:
317};
318
319} // end namespace Eigen
320
321#endif // EIGEN_GMRES_H
A GMRES solver for sparse square problems.
Definition GMRES.h:262
GMRES(const EigenBase< MatrixDerived > &A)
Definition GMRES.h:296
Index get_restart() const
Definition GMRES.h:300
GMRES()
Definition GMRES.h:283
void set_restart(const Index restart)
Definition GMRES.h:305
Index maxIterations() const
Definition IterativeSolverBase.h:246
@ NumericalIssue
Definition Constants.h:459
@ Success
Definition Constants.h:457
@ NoConvergence
Definition Constants.h:461
Definition EigenBase.h:34