Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
DGMRES.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// Copyright (C) 2012 Désiré Nuentsa-Wakam <desire.nuentsa_wakam@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_DGMRES_H
12#define EIGEN_DGMRES_H
13
14#include "../../Eigenvalues"
15
16// IWYU pragma: private
17#include "./InternalHeaderCheck.h"
18
19namespace Eigen {
20
21template <typename MatrixType_, typename Preconditioner_ = DiagonalPreconditioner<typename MatrixType_::Scalar> >
22class DGMRES;
23
24namespace internal {
25
26template <typename MatrixType_, typename Preconditioner_>
27struct traits<DGMRES<MatrixType_, Preconditioner_> > {
28 using MatrixType = MatrixType_;
29 using Preconditioner = Preconditioner_;
30};
31
40template <typename VectorType, typename IndexType>
41void sortWithPermutation(VectorType& vec, IndexType& perm, typename IndexType::Scalar& ncut) {
42 EIGEN_INTERNAL_ASSERT_SAME_SIZE(vec, perm);
43 for (Index k = 0; k < ncut; k++) {
44 bool flag = false;
45 for (Index j = 0; j < vec.size() - 1; j++) {
46 if (vec(perm(j)) < vec(perm(j + 1))) {
47 std::swap(perm(j), perm(j + 1));
48 flag = true;
49 }
50 }
51 if (!flag) break; // The vector is in sorted order
52 }
53}
54
55} // namespace internal
97template <typename MatrixType_, typename Preconditioner_>
98class DGMRES : public IterativeSolverBase<DGMRES<MatrixType_, Preconditioner_> > {
99 protected:
100 using Base = IterativeSolverBase<DGMRES>;
101 using Base::m_error;
102 using Base::m_info;
103 using Base::m_isInitialized;
104 using Base::m_iterations;
105 using Base::m_tolerance;
106 using Base::matrix;
107
108 public:
109 using Base::_solve_impl;
110 using Base::_solve_with_guess_impl;
111 using MatrixType = MatrixType_;
112 using Scalar = typename MatrixType::Scalar;
113 using StorageIndex = typename MatrixType::StorageIndex;
114 using RealScalar = typename MatrixType::RealScalar;
115 using ComplexScalar = internal::make_complex_t<Scalar>;
116 using Preconditioner = Preconditioner_;
117 using DenseMatrix = Matrix<Scalar, Dynamic, Dynamic>;
118 using DenseRealMatrix = Matrix<RealScalar, Dynamic, Dynamic>;
119 using DenseVector = Matrix<Scalar, Dynamic, 1>;
120 using DenseRealVector = Matrix<RealScalar, Dynamic, 1>;
121 using ComplexVector = Matrix<ComplexScalar, Dynamic, 1>;
122
124 DGMRES() : Base(), m_restart(30), m_neig(0), m_r(0), m_maxNeig(5), m_isDeflInitialized(false) {}
125
136 template <typename MatrixDerived>
138 : Base(A.derived()), m_restart(30), m_neig(0), m_r(0), m_maxNeig(5), m_isDeflInitialized(false) {}
139
141 template <typename Rhs, typename Dest>
142 void _solve_vector_with_guess_impl(const Rhs& b, Dest& x) const {
143 EIGEN_STATIC_ASSERT(Rhs::ColsAtCompileTime == 1 || Dest::ColsAtCompileTime == 1,
144 YOU_TRIED_CALLING_A_VECTOR_METHOD_ON_A_MATRIX);
145
146 m_iterations = Base::maxIterations();
147 m_error = Base::m_tolerance;
148
149 dgmres(matrix(), b, x, Base::m_preconditioner);
150 }
151
155 Index restart() const { return m_restart; }
156
160 void set_restart(const Index restart) { m_restart = restart; }
161
165 void setEigenv(const Index neig) {
166 m_neig = internal::convert_index<StorageIndex>(neig);
167 if (neig + 1 > m_maxNeig) m_maxNeig = neig + 1; // To allow for complex conjugates
168 }
169
173 Index deflSize() const { return m_r; }
174
178 void setMaxEigenv(const Index maxNeig) { m_maxNeig = maxNeig; }
179
180 protected:
181 // DGMRES algorithm
182 template <typename Rhs, typename Dest>
183 void dgmres(const MatrixType& mat, const Rhs& rhs, Dest& x, const Preconditioner& precond) const;
184 // Perform one cycle of GMRES
185 template <typename Dest>
186 Index dgmresCycle(const MatrixType& mat, const Preconditioner& precond, Dest& x, DenseVector& r0, RealScalar& beta,
187 const RealScalar& normRhs, Index& nbIts) const;
188 // Compute data to use for deflation
189 Index dgmresComputeDeflationData(const MatrixType& mat, const Preconditioner& precond, const Index& it,
190 StorageIndex& neig) const;
191 // Apply deflation to a vector
192 template <typename RhsType, typename DestType>
193 Index dgmresApplyDeflation(const RhsType& In, DestType& Out) const;
194 // Ritz vectors of the Hessenberg matrix; for a real conjugate pair, its real and imaginary parts in adjacent columns
195 const DenseMatrix& ritzVectors(const ComplexEigenSolver<DenseMatrix>& eigH) const { return eigH.eigenvectors(); }
196 const DenseMatrix& ritzVectors(const EigenSolver<DenseMatrix>& eigH) const { return eigH.pseudoEigenvectors(); }
197 // Init data for deflation
198 void dgmresInitDeflation(Index& rows) const;
199 mutable DenseMatrix m_V; // Krylov basis vectors
200 mutable DenseMatrix m_H; // Hessenberg matrix
201 mutable DenseMatrix m_Hes; // Initial hessenberg matrix without Givens rotations applied
202 mutable Index m_restart; // Maximum size of the Krylov subspace
203 mutable DenseMatrix m_U; // Vectors that form the basis of the invariant subspace
204 mutable DenseMatrix m_MU; // A*M^{-1}*U, the preconditioned operator applied to m_U
205 mutable DenseMatrix m_T; /* T=U^H*A*M^{-1}*U */
206 mutable PartialPivLU<DenseMatrix> m_luT; // LU factorization of m_T
207 mutable StorageIndex m_neig; // Number of eigenvalues to extract at each restart
208 mutable Index m_r; // Current number of deflated eigenvalues, size of m_U
209 mutable Index m_maxNeig; // Maximum number of eigenvalues to deflate
210 mutable RealScalar m_lambdaN = 0; // Modulus of the largest eigenvalue of A
211 mutable bool m_isDeflInitialized;
212
213 // Adaptive strategy
214 mutable RealScalar m_smv; // Smaller multiple of the remaining number of steps allowed
215 mutable bool m_force; // Force the use of deflation at each restart
216};
217
223template <typename MatrixType_, typename Preconditioner_>
224template <typename Rhs, typename Dest>
225void DGMRES<MatrixType_, Preconditioner_>::dgmres(const MatrixType& mat, const Rhs& rhs, Dest& x,
226 const Preconditioner& precond) const {
227 const RealScalar considerAsZero = (std::numeric_limits<RealScalar>::min)();
228
229 // The deflation subspace is rebuilt for every right-hand side.
230 m_isDeflInitialized = false;
231 m_r = 0;
232 m_lambdaN = 0;
233
234 RealScalar normRhs = rhs.norm();
235 if (normRhs <= considerAsZero) {
236 x.setZero();
237 m_error = 0;
238 m_iterations = 0;
239 m_info = Success;
240 return;
241 }
242
243 // Initialization
244 Index n = mat.rows();
245 DenseVector r0(n);
246 Index nbIts = 0;
247 m_H.resize(m_restart + 1, m_restart);
248 m_Hes.setZero(m_restart, m_restart);
249 m_V.resize(n, m_restart + 1);
250 // Initial residual vector and initial norm
251 if (x.squaredNorm() == 0) x = precond.solve(rhs);
252 r0.noalias() = rhs - mat * x;
253 RealScalar beta = r0.norm();
254
255 m_error = beta / normRhs;
256 if (m_error < m_tolerance)
257 m_info = Success;
258 else
259 m_info = NoConvergence;
260
261 // Iterative process
262 while (nbIts < m_iterations && m_info == NoConvergence) {
263 dgmresCycle(mat, precond, x, r0, beta, normRhs, nbIts);
264
265 // Compute the new residual vector for the restart
266 if (nbIts < m_iterations && m_info == NoConvergence) {
267 r0.noalias() = rhs - mat * x;
268 beta = r0.norm();
269 }
270 }
271 // m_iterations carried the iteration cap for the loops above; report the number actually performed.
272 m_iterations = nbIts;
273}
274
285template <typename MatrixType_, typename Preconditioner_>
286template <typename Dest>
287Index DGMRES<MatrixType_, Preconditioner_>::dgmresCycle(const MatrixType& mat, const Preconditioner& precond, Dest& x,
288 DenseVector& r0, RealScalar& beta, const RealScalar& normRhs,
289 Index& nbIts) const {
290 // Initialization
291 DenseVector g(m_restart + 1); // Right hand side of the least square problem
292 g.setZero();
293 g(0) = Scalar(beta);
294 m_V.col(0) = r0 / beta;
295 m_info = NoConvergence;
296 std::vector<JacobiRotation<Scalar> > gr(m_restart); // Givens rotations
297 Index it = 0; // Number of inner iterations
298 Index n = mat.rows();
299 DenseVector tv1(n), tv2(n); // Temporary vectors
300 while (m_info == NoConvergence && it < m_restart && nbIts < m_iterations) {
301 // Apply preconditioner(s) at right
302 if (m_isDeflInitialized) {
303 dgmresApplyDeflation(m_V.col(it), tv1); // Deflation
304 tv2 = precond.solve(tv1);
305 } else {
306 tv2 = precond.solve(m_V.col(it)); // User's selected preconditioner
307 }
308 tv1.noalias() = mat * tv2;
309
310 // Orthogonalize it with the previous basis in the basis using modified Gram-Schmidt
311 Scalar coef;
312 for (Index i = 0; i <= it; ++i) {
313 coef = m_V.col(i).dot(tv1);
314 tv1 = tv1 - coef * m_V.col(i);
315 m_H(i, it) = coef;
316 m_Hes(i, it) = coef;
317 }
318 // Normalize the vector. coef == 0 is an Arnoldi happy breakdown: the new
319 // direction lies in span(V[0..it]), so skip the division (which would
320 // poison m_V.col(it+1) with NaN) and fall through to the termination
321 // check below.
322 coef = tv1.norm();
323 const bool happy_breakdown = numext::is_exactly_zero(coef);
324 if (!happy_breakdown) {
325 m_V.col(it + 1) = tv1 / coef;
326 }
327 m_H(it + 1, it) = coef;
328 if (it + 1 < m_restart) m_Hes(it + 1, it) = coef;
329
330 // Update Hessenberg matrix with Givens rotations
331 for (Index i = 1; i <= it; ++i) {
332 m_H.col(it).applyOnTheLeft(i - 1, i, gr[i - 1].adjoint());
333 }
334
335 // If the rotated diagonal is also zero, the reduced triangular system
336 // becomes singular and the back-substitution below would produce Inf/NaN.
337 // Stop with NumericalIssue instead of polluting x.
338 if (happy_breakdown && numext::is_exactly_zero(m_H(it, it))) {
339 m_info = NumericalIssue;
340 break;
341 }
342
343 // Compute the new plane rotation
344 gr[it].makeGivens(m_H(it, it), m_H(it + 1, it));
345 // Apply the new rotation
346 m_H.col(it).applyOnTheLeft(it, it + 1, gr[it].adjoint());
347 g.applyOnTheLeft(it, it + 1, gr[it].adjoint());
348
349 beta = numext::abs(g(it + 1));
350 m_error = beta / normRhs;
351 it++;
352 nbIts++;
353
354 if (m_error < m_tolerance || happy_breakdown) {
355 // Happy breakdown: residual on the current subspace is exactly zero, so
356 // the it-dim triangular system yields the exact solution.
357 m_info = Success;
358 break;
359 }
360 }
361
362 // Compute the new coefficients by solving the least square problem.
363 DenseVector nrs = m_H.topLeftCorner(it, it).template triangularView<Upper>().solve(g.head(it));
364
365 // Form the new solution
366 if (m_isDeflInitialized) {
367 tv1.noalias() = m_V.leftCols(it) * nrs;
368 dgmresApplyDeflation(tv1, tv2);
369 x = x + precond.solve(tv2);
370 } else
371 x = x + precond.solve(m_V.leftCols(it) * nrs);
372
373 // Go for a new cycle and compute data for deflation. A conjugate pair adds m_neig + 1 columns to m_U, which has
374 // m_maxNeig columns, at most n of them independent.
375 if (nbIts < m_iterations && m_info == NoConvergence && m_neig > 0 && (m_r + m_neig) < (std::min)(m_maxNeig, n))
376 dgmresComputeDeflationData(mat, precond, it, m_neig);
377 return 0;
378}
379
380template <typename MatrixType_, typename Preconditioner_>
381void DGMRES<MatrixType_, Preconditioner_>::dgmresInitDeflation(Index& rows) const {
382 m_U.resize(rows, m_maxNeig);
383 m_MU.resize(rows, m_maxNeig);
384 m_T.resize(m_maxNeig, m_maxNeig);
385}
386
387template <typename MatrixType_, typename Preconditioner_>
388Index DGMRES<MatrixType_, Preconditioner_>::dgmresComputeDeflationData(const MatrixType& mat,
389 const Preconditioner& precond, const Index& it,
390 StorageIndex& neig) const {
391 // Ritz pairs of the Hessenberg matrix H; perm ends with the neig Ritz values of smallest modulus, smallest last
392 std::conditional_t<NumTraits<Scalar>::IsComplex, ComplexEigenSolver<DenseMatrix>, EigenSolver<DenseMatrix> > eigH(
393 m_Hes.topLeftCorner(it, it));
394 if (eigH.info() != Success) return 0;
395 const ComplexVector& eig = eigH.eigenvalues();
396 DenseRealVector modulEig = eig.cwiseAbs();
397 Matrix<StorageIndex, Dynamic, 1> perm(it);
398 perm.setLinSpaced(it, 0, internal::convert_index<StorageIndex>(it - 1));
399 internal::sortWithPermutation(modulEig, perm, neig);
400
401 if (!m_lambdaN) {
402 m_lambdaN = modulEig.maxCoeff();
403 }
404 // Basis of the invariant subspace of H for those Ritz values. A real conjugate pair is taken whole, so up to
405 // neig + 1 columns are extracted; each position visited adds a column or holds the partner of a pair already taken,
406 // so the loop reads only the neig sorted positions.
407 const DenseMatrix& ritzVecs = ritzVectors(eigH);
408 DenseMatrix Y(it, neig + 1);
409 std::vector<bool> taken(it, false);
410 Index nbrEig = 0;
411 for (Index k = it - 1; k >= 0 && nbrEig < neig; --k) {
412 Index first = perm(k), count = 1;
413 if (taken[first]) continue;
414 if (!NumTraits<Scalar>::IsComplex && numext::imag(eig(first)) != RealScalar(0)) {
415 // The pair's eigenvalue with positive imaginary part comes first.
416 if (numext::imag(eig(first)) < RealScalar(0)) --first;
417 count = 2;
418 }
419 Y.middleCols(nbrEig, count) = ritzVecs.middleCols(first, count);
420 for (Index j = first; j < first + count; ++j) taken[j] = true;
421 nbrEig += count;
422 }
423
424 // Lift to the Krylov basis, orthogonalize against the current deflation vectors, and orthonormalize. QR leaves
425 // ||U^H X|| ~ eps cond(X), so a second pass restores orthogonality when the Ritz vectors are nearly dependent.
426 Index m = m_V.rows();
427 DenseMatrix X = m_V.leftCols(it) * Y.leftCols(nbrEig);
428 for (int pass = 0; pass < (m_r > 0 ? 2 : 1); ++pass) {
429 if (m_r > 0) X -= m_U.leftCols(m_r) * (m_U.leftCols(m_r).adjoint() * X);
430 X = HouseholderQR<DenseMatrix>(X).householderQ() * DenseMatrix::Identity(m, nbrEig);
431 }
432
433 // Compute MX = A * M^-1 * X: deflation acts on the right-preconditioned operator
434 if (m_r == 0) dgmresInitDeflation(m);
435 DenseMatrix MX(m, nbrEig);
436 DenseVector tv1(m);
437 for (Index j = 0; j < nbrEig; j++) {
438 tv1 = precond.solve(X.col(j));
439 MX.col(j).noalias() = mat * tv1;
440 }
441
442 // Update m_T = [U'MU U'MX; X'MU X'MX]
443 m_T.block(m_r, m_r, nbrEig, nbrEig).noalias() = X.adjoint() * MX;
444 if (m_r) {
445 m_T.block(0, m_r, m_r, nbrEig).noalias() = m_U.leftCols(m_r).adjoint() * MX;
446 m_T.block(m_r, 0, nbrEig, m_r).noalias() = X.adjoint() * m_MU.leftCols(m_r);
447 }
448
449 // Save X into m_U and m_MX in m_MU
450 for (Index j = 0; j < nbrEig; j++) m_U.col(m_r + j) = X.col(j);
451 for (Index j = 0; j < nbrEig; j++) m_MU.col(m_r + j) = MX.col(j);
452 // Increase the size of the invariant subspace
453 m_r += nbrEig;
454
455 // Factorize m_T into m_luT
456 m_luT.compute(m_T.topLeftCorner(m_r, m_r));
457
458 // FIXME: Check if the factorization was correctly done (nonsingular matrix).
459 m_isDeflInitialized = true;
460 return 0;
461}
462template <typename MatrixType_, typename Preconditioner_>
463template <typename RhsType, typename DestType>
464Index DGMRES<MatrixType_, Preconditioner_>::dgmresApplyDeflation(const RhsType& x, DestType& y) const {
465 DenseVector x1 = m_U.leftCols(m_r).adjoint() * x;
466 y = x + m_U.leftCols(m_r) * (m_lambdaN * m_luT.solve(x1) - x1);
467 return 0;
468}
469
470} // end namespace Eigen
471#endif
Computes eigenvalues and eigenvectors of general complex matrices.
Definition ComplexEigenSolver.h:50
const EigenvectorType & eigenvectors() const
Returns the eigenvectors of given matrix.
Definition ComplexEigenSolver.h:167
const EigenvalueType & eigenvalues() const
Returns the eigenvalues of given matrix.
Definition ComplexEigenSolver.h:191
ComputationInfo info() const
Reports whether previous computation was successful.
Definition ComplexEigenSolver.h:227
A Restarted GMRES with deflation. This class implements a modification of the GMRES solver for sparse...
Definition DGMRES.h:98
Index dgmresCycle(const MatrixType &mat, const Preconditioner &precond, Dest &x, DenseVector &r0, RealScalar &beta, const RealScalar &normRhs, Index &nbIts) const
Perform one restart cycle of DGMRES.
Definition DGMRES.h:287
DGMRES(const EigenBase< MatrixDerived > &A)
Definition DGMRES.h:137
void setMaxEigenv(const Index maxNeig)
Definition DGMRES.h:178
DGMRES()
Definition DGMRES.h:124
Index restart() const
Definition DGMRES.h:155
void dgmres(const MatrixType &mat, const Rhs &rhs, Dest &x, const Preconditioner &precond) const
Perform several cycles of restarted GMRES with modified Gram Schmidt,.
Definition DGMRES.h:225
void set_restart(const Index restart)
Definition DGMRES.h:160
void setEigenv(const Index neig)
Definition DGMRES.h:165
Index deflSize() const
Definition DGMRES.h:173
Householder QR decomposition of a matrix.
Definition HouseholderQR.h:77
HouseholderSequenceType householderQ() const
Definition HouseholderQR.h:189
Index maxIterations() const
Definition IterativeSolverBase.h:246
The matrix class, also used for vectors and row-vectors.
Definition Matrix.h:188
Derived & setZero(Index size)
Definition CwiseNullaryOp.h:536
@ NumericalIssue
Definition Constants.h:459
@ Success
Definition Constants.h:457
@ NoConvergence
Definition Constants.h:461
Definition EigenBase.h:34