14#include "../../Eigenvalues"
17#include "./InternalHeaderCheck.h"
21template <
typename MatrixType_,
typename Preconditioner_ = DiagonalPreconditioner<
typename MatrixType_::Scalar> >
26template <
typename MatrixType_,
typename Preconditioner_>
27struct traits<DGMRES<MatrixType_, Preconditioner_> > {
28 using MatrixType = MatrixType_;
29 using Preconditioner = Preconditioner_;
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++) {
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));
97template <
typename MatrixType_,
typename Preconditioner_>
103 using Base::m_isInitialized;
104 using Base::m_iterations;
105 using Base::m_tolerance;
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_;
124 DGMRES() : Base(), m_restart(30), m_neig(0), m_r(0), m_maxNeig(5), m_isDeflInitialized(false) {}
136 template <
typename MatrixDerived>
138 : Base(A.derived()), m_restart(30), m_neig(0), m_r(0), m_maxNeig(5), m_isDeflInitialized(false) {}
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);
147 m_error = Base::m_tolerance;
149 dgmres(matrix(), b, x, Base::m_preconditioner);
166 m_neig = internal::convert_index<StorageIndex>(neig);
167 if (neig + 1 > m_maxNeig) m_maxNeig = neig + 1;
182 template <
typename Rhs,
typename Dest>
183 void dgmres(
const MatrixType& mat,
const Rhs& rhs, Dest& x,
const Preconditioner& precond)
const;
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;
189 Index dgmresComputeDeflationData(
const MatrixType& mat,
const Preconditioner& precond,
const Index& it,
190 StorageIndex& neig)
const;
192 template <
typename RhsType,
typename DestType>
193 Index dgmresApplyDeflation(
const RhsType& In, DestType& Out)
const;
196 const DenseMatrix& ritzVectors(
const EigenSolver<DenseMatrix>& eigH)
const {
return eigH.pseudoEigenvectors(); }
198 void dgmresInitDeflation(Index& rows)
const;
199 mutable DenseMatrix m_V;
200 mutable DenseMatrix m_H;
201 mutable DenseMatrix m_Hes;
202 mutable Index m_restart;
203 mutable DenseMatrix m_U;
204 mutable DenseMatrix m_MU;
205 mutable DenseMatrix m_T;
206 mutable PartialPivLU<DenseMatrix> m_luT;
207 mutable StorageIndex m_neig;
209 mutable Index m_maxNeig;
210 mutable RealScalar m_lambdaN = 0;
211 mutable bool m_isDeflInitialized;
214 mutable RealScalar m_smv;
215 mutable bool m_force;
223template <
typename MatrixType_,
typename Preconditioner_>
224template <
typename Rhs,
typename Dest>
226 const Preconditioner& precond)
const {
227 const RealScalar considerAsZero = (std::numeric_limits<RealScalar>::min)();
230 m_isDeflInitialized =
false;
234 RealScalar normRhs = rhs.norm();
235 if (normRhs <= considerAsZero) {
244 Index n = mat.rows();
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);
251 if (x.squaredNorm() == 0) x = precond.solve(rhs);
252 r0.noalias() = rhs - mat * x;
253 RealScalar beta = r0.norm();
255 m_error = beta / normRhs;
256 if (m_error < m_tolerance)
263 dgmresCycle(mat, precond, x, r0, beta, normRhs, nbIts);
267 r0.noalias() = rhs - mat * x;
272 m_iterations = nbIts;
285template <
typename MatrixType_,
typename Preconditioner_>
286template <
typename Dest>
288 DenseVector& r0, RealScalar& beta,
const RealScalar& normRhs,
289 Index& nbIts)
const {
291 DenseVector g(m_restart + 1);
294 m_V.col(0) = r0 / beta;
296 std::vector<JacobiRotation<Scalar> > gr(m_restart);
298 Index n = mat.rows();
299 DenseVector tv1(n), tv2(n);
300 while (m_info ==
NoConvergence && it < m_restart && nbIts < m_iterations) {
302 if (m_isDeflInitialized) {
303 dgmresApplyDeflation(m_V.col(it), tv1);
304 tv2 = precond.solve(tv1);
306 tv2 = precond.solve(m_V.col(it));
308 tv1.noalias() = mat * tv2;
312 for (Index i = 0; i <= it; ++i) {
313 coef = m_V.col(i).dot(tv1);
314 tv1 = tv1 - coef * m_V.col(i);
323 const bool happy_breakdown = numext::is_exactly_zero(coef);
324 if (!happy_breakdown) {
325 m_V.col(it + 1) = tv1 / coef;
327 m_H(it + 1, it) = coef;
328 if (it + 1 < m_restart) m_Hes(it + 1, it) = coef;
331 for (Index i = 1; i <= it; ++i) {
332 m_H.col(it).applyOnTheLeft(i - 1, i, gr[i - 1].adjoint());
338 if (happy_breakdown && numext::is_exactly_zero(m_H(it, it))) {
344 gr[it].makeGivens(m_H(it, it), m_H(it + 1, it));
346 m_H.col(it).applyOnTheLeft(it, it + 1, gr[it].adjoint());
347 g.applyOnTheLeft(it, it + 1, gr[it].adjoint());
349 beta = numext::abs(g(it + 1));
350 m_error = beta / normRhs;
354 if (m_error < m_tolerance || happy_breakdown) {
363 DenseVector nrs = m_H.topLeftCorner(it, it).template triangularView<Upper>().solve(g.head(it));
366 if (m_isDeflInitialized) {
367 tv1.noalias() = m_V.leftCols(it) * nrs;
368 dgmresApplyDeflation(tv1, tv2);
369 x = x + precond.solve(tv2);
371 x = x + precond.solve(m_V.leftCols(it) * nrs);
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);
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);
387template <
typename MatrixType_,
typename Preconditioner_>
388Index DGMRES<MatrixType_, Preconditioner_>::dgmresComputeDeflationData(
const MatrixType& mat,
389 const Preconditioner& precond,
const Index& it,
390 StorageIndex& neig)
const {
392 std::conditional_t<NumTraits<Scalar>::IsComplex, ComplexEigenSolver<DenseMatrix>, EigenSolver<DenseMatrix> > eigH(
393 m_Hes.topLeftCorner(it, it));
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);
402 m_lambdaN = modulEig.maxCoeff();
407 const DenseMatrix& ritzVecs = ritzVectors(eigH);
408 DenseMatrix Y(it, neig + 1);
409 std::vector<bool> taken(it,
false);
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)) {
416 if (numext::imag(eig(first)) < RealScalar(0)) --first;
419 Y.middleCols(nbrEig, count) = ritzVecs.middleCols(first, count);
420 for (Index j = first; j < first + count; ++j) taken[j] =
true;
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);
434 if (m_r == 0) dgmresInitDeflation(m);
435 DenseMatrix MX(m, nbrEig);
437 for (Index j = 0; j < nbrEig; j++) {
438 tv1 = precond.solve(X.col(j));
439 MX.col(j).noalias() = mat * tv1;
443 m_T.block(m_r, m_r, nbrEig, nbrEig).noalias() = X.adjoint() * MX;
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);
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);
456 m_luT.compute(m_T.topLeftCorner(m_r, m_r));
459 m_isDeflInitialized =
true;
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);
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
IterativeSolverBase()
Definition IterativeSolverBase.h:136
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