// SPDX-FileCopyrightText: Copyright © DUNE Project contributors, see file LICENSE.md in module root // SPDX-License-Identifier: LicenseRef-GPL-2.0-only-with-DUNE-exception // -*- tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- // vi: set et ts=4 sw=2 sts=2: #ifndef DUNE_ISTL_SOLVERS_HH #define DUNE_ISTL_SOLVERS_HH #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include namespace Dune { /** @addtogroup ISTL_Solvers @{ */ /** \file \brief Implementations of the inverse operator interface. This file provides various preconditioned Krylov methods. */ //===================================================================== // Implementation of this interface //===================================================================== /*! \brief Preconditioned loop solver. Implements a preconditioned loop. Using this class every Preconditioner can be turned into a solver. The solver will apply one preconditioner step in each iteration loop. */ template class LoopSolver : public IterativeSolver { public: using typename IterativeSolver::domain_type; using typename IterativeSolver::range_type; using typename IterativeSolver::field_type; using typename IterativeSolver::real_type; // copy base class constructors using IterativeSolver::IterativeSolver; // don't shadow four-argument version of apply defined in the base class using IterativeSolver::apply; //! \copydoc InverseOperator::apply(X&,Y&,InverseOperatorResult&) void apply (X& x, X& b, InverseOperatorResult& res) override { Iteration iteration(*this, res); _prec->pre(x,b); // overwrite b with defect _op->applyscaleadd(-1,x,b); // compute norm, \todo parallelization real_type def = _sp->norm(b); if(iteration.step(0, def)){ _prec->post(x); return; } // prepare preconditioner // allocate correction vector X v(x); // iteration loop int i=1; for ( ; i<=_maxit; i++ ) { v = 0; // clear correction _prec->apply(v,b); // apply preconditioner x += v; // update solution _op->applyscaleadd(-1,v,b); // update defect def=_sp->norm(b); // comp defect norm if(iteration.step(i, def)) break; } // postprocess preconditioner _prec->post(x); } protected: using IterativeSolver::_op; using IterativeSolver::_prec; using IterativeSolver::_sp; using IterativeSolver::_reduction; using IterativeSolver::_maxit; using IterativeSolver::_verbose; using Iteration = typename IterativeSolver::template Iteration; }; DUNE_REGISTER_SOLVER("loopsolver", defaultIterativeSolverCreator()); // all these solvers are taken from the SUMO library //! gradient method template class GradientSolver : public IterativeSolver { public: using typename IterativeSolver::domain_type; using typename IterativeSolver::range_type; using typename IterativeSolver::field_type; using typename IterativeSolver::real_type; // copy base class constructors using IterativeSolver::IterativeSolver; // don't shadow four-argument version of apply defined in the base class using IterativeSolver::apply; /*! \brief Apply inverse operator. \copydoc InverseOperator::apply(X&,Y&,InverseOperatorResult&) */ void apply (X& x, X& b, InverseOperatorResult& res) override { Iteration iteration(*this, res); _prec->pre(x,b); // prepare preconditioner _op->applyscaleadd(-1,x,b); // overwrite b with defec real_type def = _sp->norm(b); // compute norm if(iteration.step(0, def)){ _prec->post(x); return; } X p(x); // create local vectors X q(b); int i=1; // loop variables field_type lambda; for ( ; i<=_maxit; i++ ) { p = 0; // clear correction _prec->apply(p,b); // apply preconditioner _op->apply(p,q); // q=Ap auto alpha = _sp->dot(q,p); lambda = Simd::cond(def==field_type(0.), field_type(0.), // no need for minimization if def is already 0 field_type(_sp->dot(p,b)/alpha)); // minimization x.axpy(lambda,p); // update solution b.axpy(-lambda,q); // update defect def =_sp->norm(b); // comp defect norm if(iteration.step(i, def)) break; } // postprocess preconditioner _prec->post(x); } protected: using IterativeSolver::_op; using IterativeSolver::_prec; using IterativeSolver::_sp; using IterativeSolver::_reduction; using IterativeSolver::_maxit; using IterativeSolver::_verbose; using Iteration = typename IterativeSolver::template Iteration; }; DUNE_REGISTER_SOLVER("gradientsolver", defaultIterativeSolverCreator()); //! \brief conjugate gradient method template class CGSolver : public IterativeSolver { public: using typename IterativeSolver::domain_type; using typename IterativeSolver::range_type; using typename IterativeSolver::field_type; using typename IterativeSolver::real_type; // copy base class constructors using IterativeSolver::IterativeSolver; private: using typename IterativeSolver::scalar_real_type; protected: static constexpr bool enableConditionEstimate = (std::is_same_v || std::is_same_v); public: // don't shadow four-argument version of apply defined in the base class using IterativeSolver::apply; /*! \brief Constructor to initialize a CG solver. \copydetails IterativeSolver::IterativeSolver(const LinearOperator&, Preconditioner&, scalar_real_type, int, int) \param condition_estimate Whether to calculate an estimate of the condition number. The estimate is given in the InverseOperatorResult returned by apply(). This is only supported for float and double field types. */ CGSolver (const LinearOperator& op, Preconditioner& prec, scalar_real_type reduction, int maxit, int verbose, bool condition_estimate) : IterativeSolver(op, prec, reduction, maxit, verbose), condition_estimate_(condition_estimate) { if (condition_estimate && !enableConditionEstimate) { condition_estimate_ = false; std::cerr << "WARNING: Condition estimate was disabled. It is only available for double and float field types!" << std::endl; } } /*! \brief Constructor to initialize a CG solver. \copydetails IterativeSolver::IterativeSolver(const LinearOperator&, const ScalarProduct&, Preconditioner&, scalar_real_type, int, int) \param condition_estimate Whether to calculate an estimate of the condition number. The estimate is given in the InverseOperatorResult returned by apply(). This is only supported for float and double field types. */ CGSolver (const LinearOperator& op, const ScalarProduct& sp, Preconditioner& prec, scalar_real_type reduction, int maxit, int verbose, bool condition_estimate) : IterativeSolver(op, sp, prec, reduction, maxit, verbose), condition_estimate_(condition_estimate) { if (condition_estimate && !(std::is_same::value || std::is_same::value)) { condition_estimate_ = false; std::cerr << "WARNING: Condition estimate was disabled. It is only available for double and float field types!" << std::endl; } } /*! \brief Constructor to initialize a CG solver. \copydetails IterativeSolver::IterativeSolver(std::shared_ptr>,std::shared_ptr>,std::shared_ptr>,scalar_real_type,int,int) \param condition_estimate Whether to calculate an estimate of the condition number. The estimate is given in the InverseOperatorResult returned by apply(). This is only supported for float and double field types. */ CGSolver (std::shared_ptr> op, std::shared_ptr> sp, std::shared_ptr> prec, scalar_real_type reduction, int maxit, int verbose, bool condition_estimate) : IterativeSolver(op, sp, prec, reduction, maxit, verbose), condition_estimate_(condition_estimate) { if (condition_estimate && !(std::is_same::value || std::is_same::value)) { condition_estimate_ = false; std::cerr << "WARNING: Condition estimate was disabled. It is only available for double and float field types!" << std::endl; } } /*! \brief Apply inverse operator. \copydoc InverseOperator::apply(X&,Y&,InverseOperatorResult&) \note Currently, the CGSolver aborts when a NaN or infinite defect is detected. However, -ffinite-math-only (implied by -ffast-math) can inhibit a result from becoming NaN that really should be NaN. E.g. numeric_limits::quiet_NaN()*0.0==0.0 with gcc-5.3 -ffast-math. */ void apply (X& x, X& b, InverseOperatorResult& res) override { Iteration iteration(*this,res); _prec->pre(x,b); // prepare preconditioner _op->applyscaleadd(-1,x,b); // overwrite b with defect real_type def = _sp->norm(b); // compute norm if(iteration.step(0, def)){ _prec->post(x); return; } X p(x); // the search direction X q(x); // a temporary vector // Remember lambda and beta values for condition estimate std::vector lambdas(0); std::vector betas(0); // some local variables field_type rho,rholast,lambda,alpha,beta; // determine initial search direction p = 0; // clear correction _prec->apply(p,b); // apply preconditioner rholast = _sp->dot(p,b); // orthogonalization // the loop int i=1; for ( ; i<=_maxit; i++ ) { // minimize in given search direction p _op->apply(p,q); // q=Ap alpha = _sp->dot(p,q); // scalar product lambda = Simd::cond(def==field_type(0.), field_type(0.), field_type(rholast/alpha)); // minimization if constexpr (enableConditionEstimate) if (condition_estimate_) lambdas.push_back(std::real(lambda)); x.axpy(lambda,p); // update solution b.axpy(-lambda,q); // update defect // convergence test def=_sp->norm(b); // comp defect norm if(iteration.step(i, def)) break; // determine new search direction q = 0; // clear correction _prec->apply(q,b); // apply preconditioner rho = _sp->dot(q,b); // orthogonalization beta = Simd::cond(def==field_type(0.), field_type(0.), field_type(rho/rholast)); // scaling factor if constexpr (enableConditionEstimate) if (condition_estimate_) betas.push_back(std::real(beta)); p *= beta; // scale old search direction p += q; // orthogonalization with correction rholast = rho; // remember rho for recurrence } _prec->post(x); // postprocess preconditioner if (condition_estimate_) { #if HAVE_ARPACKPP if constexpr (enableConditionEstimate) { using std::sqrt; // Build T matrix which has extreme eigenvalues approximating // those of the original system // (see Y. Saad, Iterative methods for sparse linear systems) COND_MAT T(i, i, COND_MAT::row_wise); for (auto row = T.createbegin(); row != T.createend(); ++row) { if (row.index() > 0) row.insert(row.index()-1); row.insert(row.index()); if (row.index() < T.N() - 1) row.insert(row.index()+1); } for (int row = 0; row < i; ++row) { if (row > 0) { T[row][row-1] = sqrt(betas[row-1]) / lambdas[row-1]; } T[row][row] = 1.0 / lambdas[row]; if (row > 0) { T[row][row] += betas[row-1] / lambdas[row-1]; } if (row < i - 1) { T[row][row+1] = sqrt(betas[row]) / lambdas[row]; } } // Compute largest and smallest eigenvalue of T matrix and return as estimate Dune::ArPackPlusPlus_Algorithms arpack(T); real_type eps = 0.0; COND_VEC eigv; real_type min_eigv, max_eigv; arpack.computeSymMinMagnitude (eps, eigv, min_eigv); arpack.computeSymMaxMagnitude (eps, eigv, max_eigv); res.condition_estimate = max_eigv / min_eigv; if (this->_verbose > 0) { std::cout << "Min eigv estimate: " << Simd::io(min_eigv) << '\n'; std::cout << "Max eigv estimate: " << Simd::io(max_eigv) << '\n'; std::cout << "Condition estimate: " << Simd::io(max_eigv / min_eigv) << std::endl; } } #else std::cerr << "WARNING: Condition estimate was requested. This requires ARPACK, but ARPACK was not found!" << std::endl; #endif } } private: bool condition_estimate_ = false; // Matrix and vector types used for condition estimate typedef Dune::BCRSMatrix > COND_MAT; typedef Dune::BlockVector > COND_VEC; protected: using IterativeSolver::_op; using IterativeSolver::_prec; using IterativeSolver::_sp; using IterativeSolver::_reduction; using IterativeSolver::_maxit; using IterativeSolver::_verbose; using Iteration = typename IterativeSolver::template Iteration; }; DUNE_REGISTER_SOLVER("cgsolver", defaultIterativeSolverCreator()); // Ronald Kriemanns BiCG-STAB implementation from Sumo //! \brief Bi-conjugate Gradient Stabilized (BiCG-STAB) template class BiCGSTABSolver : public IterativeSolver { public: using typename IterativeSolver::domain_type; using typename IterativeSolver::range_type; using typename IterativeSolver::field_type; using typename IterativeSolver::real_type; // copy base class constructors using IterativeSolver::IterativeSolver; // don't shadow four-argument version of apply defined in the base class using IterativeSolver::apply; /*! \brief Apply inverse operator. \copydoc InverseOperator::apply(X&,Y&,InverseOperatorResult&) \note Currently, the BiCGSTABSolver aborts when it detects a breakdown. */ void apply (X& x, X& b, InverseOperatorResult& res) override { using std::abs; const Simd::Scalar EPSILON=1e-80; using std::abs; double it; field_type rho, rho_new, alpha, beta, h, omega; real_type norm; // // get vectors and matrix // X& r=b; X p(x); X v(x); X t(x); X y(x); X rt(x); // // begin iteration // // r = r - Ax; rt = r Iteration iteration(*this,res); _prec->pre(x,r); // prepare preconditioner _op->applyscaleadd(-1,x,r); // overwrite b with defect rt=r; norm = _sp->norm(r); if(iteration.step(0, norm)){ _prec->post(x); return; } p=0; v=0; rho = 1; alpha = 1; omega = 1; // // iteration // for (it = 0.5; it < _maxit; it+=.5) { // // preprocess, set vecsizes etc. // // rho_new = < rt , r > rho_new = _sp->dot(rt,r); // look if breakdown occurred if (Simd::allTrue(abs(rho) <= EPSILON)) DUNE_THROW(SolverAbort,"breakdown in BiCGSTAB - rho " << Simd::io(rho) << " <= EPSILON " << EPSILON << " after " << it << " iterations"); if (Simd::allTrue(abs(omega) <= EPSILON)) DUNE_THROW(SolverAbort,"breakdown in BiCGSTAB - omega " << Simd::io(omega) << " <= EPSILON " << EPSILON << " after " << it << " iterations"); if (it<1) p = r; else { beta = Simd::cond(norm==field_type(0.), field_type(0.), // no need for orthogonalization if norm is already 0 field_type(( rho_new / rho ) * ( alpha / omega ))); p.axpy(-omega,v); // p = r + beta (p - omega*v) p *= beta; p += r; } // y = W^-1 * p y = 0; _prec->apply(y,p); // apply preconditioner // v = A * y _op->apply(y,v); // alpha = rho_new / < rt, v > h = _sp->dot(rt,v); if ( Simd::allTrue(abs(h) < EPSILON) ) DUNE_THROW(SolverAbort,"abs(h) < EPSILON in BiCGSTAB - abs(h) " << Simd::io(abs(h)) << " < EPSILON " << EPSILON << " after " << it << " iterations"); alpha = Simd::cond(norm==field_type(0.), field_type(0.), field_type(rho_new / h)); // apply first correction to x // x <- x + alpha y x.axpy(alpha,y); // r = r - alpha*v r.axpy(-alpha,v); // // test stop criteria // norm = _sp->norm(r); if(iteration.step(it, norm)){ break; } it+=.5; // y = W^-1 * r y = 0; _prec->apply(y,r); // t = A * y _op->apply(y,t); // omega = < t, r > / < t, t > h = _sp->dot(t,t); omega = Simd::cond(norm==field_type(0.), field_type(0.), field_type(_sp->dot(t,r)/h)); // apply second correction to x // x <- x + omega y x.axpy(omega,y); // r = s - omega*t (remember : r = s) r.axpy(-omega,t); rho = rho_new; // // test stop criteria // norm = _sp->norm(r); if(iteration.step(it, norm)){ break; } } // end for _prec->post(x); // postprocess preconditioner } protected: using IterativeSolver::_op; using IterativeSolver::_prec; using IterativeSolver::_sp; using IterativeSolver::_reduction; using IterativeSolver::_maxit; using IterativeSolver::_verbose; template using Iteration = typename IterativeSolver::template Iteration; }; DUNE_REGISTER_SOLVER("bicgstabsolver", defaultIterativeSolverCreator()); /*! \brief Minimal Residual Method (MINRES) Symmetrically Preconditioned MINRES as in A. Greenbaum, 'Iterative Methods for Solving Linear Systems', pp. 121 Iterative solver for symmetric indefinite operators. Note that in order to ensure the (symmetrically) preconditioned system to remain symmetric, the preconditioner has to be spd. */ template class MINRESSolver : public IterativeSolver { public: using typename IterativeSolver::domain_type; using typename IterativeSolver::range_type; using typename IterativeSolver::field_type; using typename IterativeSolver::real_type; // copy base class constructors using IterativeSolver::IterativeSolver; // don't shadow four-argument version of apply defined in the base class using IterativeSolver::apply; /*! \brief Apply inverse operator. \copydoc InverseOperator::apply(X&,Y&,InverseOperatorResult&) */ void apply (X& x, X& b, InverseOperatorResult& res) override { using std::sqrt; using std::abs; Iteration iteration(*this, res); // prepare preconditioner _prec->pre(x,b); // overwrite rhs with defect _op->applyscaleadd(-1.0,x,b); // b -= Ax // some temporary vectors X z(b), dummy(b); z = 0.0; // calculate preconditioned defect _prec->apply(z,b); // r = W^-1 (b - Ax) real_type def = _sp->norm(z); if (iteration.step(0, def)){ _prec->post(x); return; } // recurrence coefficients as computed in Lanczos algorithm field_type alpha, beta; // diagonal entries of givens rotation std::array c{{0.0,0.0}}; // off-diagonal entries of givens rotation std::array s{{0.0,0.0}}; // recurrence coefficients (column k of tridiag matrix T_k) std::array T{{0.0,0.0,0.0}}; // the rhs vector of the min problem std::array xi{{1.0,0.0}}; // beta is real and positive in exact arithmetic // since it is the norm of the basis vectors (in unpreconditioned case) beta = sqrt(_sp->dot(b,z)); field_type beta0 = beta; // the search directions std::array p{{b,b,b}}; p[0] = 0.0; p[1] = 0.0; p[2] = 0.0; // orthonormal basis vectors (in unpreconditioned case) std::array q{{b,b,b}}; q[0] = 0.0; q[1] *= Simd::cond(def==field_type(0.), field_type(0.), field_type(real_type(1.0)/beta)); q[2] = 0.0; z *= Simd::cond(def==field_type(0.), field_type(0.), field_type(real_type(1.0)/beta)); // the loop int i = 1; for( ; i<=_maxit; i++) { dummy = z; int i1 = i%3, i0 = (i1+2)%3, i2 = (i1+1)%3; // symmetrically preconditioned Lanczos algorithm (see Greenbaum p.121) _op->apply(z,q[i2]); // q[i2] = Az q[i2].axpy(-beta,q[i0]); // alpha is real since it is the diagonal entry of the hermitian tridiagonal matrix // from the Lanczos Algorithm // so the order in the scalar product doesn't matter even for the complex case alpha = _sp->dot(z,q[i2]); q[i2].axpy(-alpha,q[i1]); z = 0.0; _prec->apply(z,q[i2]); // beta is real and positive in exact arithmetic // since it is the norm of the basis vectors (in unpreconditioned case) beta = sqrt(_sp->dot(q[i2],z)); q[i2] *= Simd::cond(def==field_type(0.), field_type(0.), field_type(real_type(1.0)/beta)); z *= Simd::cond(def==field_type(0.), field_type(0.), field_type(real_type(1.0)/beta)); // QR Factorization of recurrence coefficient matrix // apply previous givens rotations to last column of T T[1] = T[2]; if(i>2) { T[0] = s[i%2]*T[1]; T[1] = c[i%2]*T[1]; } if(i>1) { T[2] = c[(i+1)%2]*alpha - s[(i+1)%2]*T[1]; T[1] = c[(i+1)%2]*T[1] + s[(i+1)%2]*alpha; } else T[2] = alpha; // update QR factorization generateGivensRotation(T[2],beta,c[i%2],s[i%2]); // to last column of T_k T[2] = c[i%2]*T[2] + s[i%2]*beta; // and to the rhs xi of the min problem xi[i%2] = -s[i%2]*xi[(i+1)%2]; xi[(i+1)%2] *= c[i%2]; // compute correction direction p[i2] = dummy; p[i2].axpy(-T[1],p[i1]); p[i2].axpy(-T[0],p[i0]); p[i2] *= real_type(1.0)/T[2]; // apply correction/update solution x.axpy(beta0*xi[(i+1)%2],p[i2]); // remember beta_old T[2] = beta; // check for convergence // the last entry in the rhs of the min-problem is the residual def = abs(beta0*xi[i%2]); if(iteration.step(i, def)){ break; } } // end for // postprocess preconditioner _prec->post(x); } private: void generateGivensRotation(field_type &dx, field_type &dy, real_type &cs, field_type &sn) { using std::sqrt; using std::abs; using std::max; using std::min; const real_type eps = 1e-15; real_type norm_dx = abs(dx); real_type norm_dy = abs(dy); real_type norm_max = max(norm_dx, norm_dy); real_type norm_min = min(norm_dx, norm_dy); real_type temp = norm_min/norm_max; // we rewrite the code in a vectorizable fashion cs = Simd::cond(norm_dy < eps, real_type(1.0), real_type(Simd::cond(norm_dx < eps, real_type(0.0), real_type(Simd::cond(norm_dy > norm_dx, real_type(1.0)/sqrt(real_type(1.0) + temp*temp)*temp, real_type(1.0)/sqrt(real_type(1.0) + temp*temp) ))))); sn = Simd::cond(norm_dy < eps, field_type(0.0), field_type(Simd::cond(norm_dx < eps, field_type(1.0), field_type(Simd::cond(norm_dy > norm_dx, // dy and dx are real in exact arithmetic // thus dx*dy is real so we can explicitly enforce it field_type(1.0)/sqrt(real_type(1.0) + temp*temp)*dx*dy/norm_dx/norm_dy, // dy and dx is real in exact arithmetic // so we don't have to conjugate both of them field_type(1.0)/sqrt(real_type(1.0) + temp*temp)*dy/dx ))))); } protected: using IterativeSolver::_op; using IterativeSolver::_prec; using IterativeSolver::_sp; using IterativeSolver::_reduction; using IterativeSolver::_maxit; using IterativeSolver::_verbose; using Iteration = typename IterativeSolver::template Iteration; }; DUNE_REGISTER_SOLVER("minressolver", defaultIterativeSolverCreator()); /** \brief implements the Generalized Minimal Residual (GMRes) method GMRes solves the unsymmetric linear system Ax = b using the Generalized Minimal Residual method as described the SIAM Templates book (http://www.netlib.org/templates/templates.pdf). \tparam X trial vector, vector type of the solution \tparam Y test vector, vector type of the RHS \tparam F vector type for orthonormal basis of Krylov space */ template class RestartedGMResSolver : public IterativeSolver { public: using typename IterativeSolver::domain_type; using typename IterativeSolver::range_type; using typename IterativeSolver::field_type; using typename IterativeSolver::real_type; protected: using typename IterativeSolver::scalar_real_type; //! \brief field_type Allocator retrieved from domain type using fAlloc = ReboundAllocatorType; //! \brief real_type Allocator retrieved from domain type using rAlloc = ReboundAllocatorType; public: /*! \brief Set up RestartedGMResSolver solver. \copydoc IterativeSolver::IterativeSolver(const LinearOperator&,Preconditioner&,scalar_real_type,int,int) \param restart number of GMRes cycles before restart */ RestartedGMResSolver (const LinearOperator& op, Preconditioner& prec, scalar_real_type reduction, int restart, int maxit, int verbose) : IterativeSolver::IterativeSolver(op,prec,reduction,maxit,verbose), _restart(restart) {} /*! \brief Set up RestartedGMResSolver solver. \copydoc IterativeSolver::IterativeSolver(const LinearOperator&,const ScalarProduct&,Preconditioner&,scalar_real_type,int,int) \param restart number of GMRes cycles before restart */ RestartedGMResSolver (const LinearOperator& op, const ScalarProduct& sp, Preconditioner& prec, scalar_real_type reduction, int restart, int maxit, int verbose) : IterativeSolver::IterativeSolver(op,sp,prec,reduction,maxit,verbose), _restart(restart) {} /*! \brief Constructor. \copydoc IterativeSolver::IterativeSolver(std::shared_ptr>,std::shared_ptr>,const ParameterTree&) Additional parameter: ParameterTree Key | Meaning ------------------|------------ restart | number of GMRes cycles before restart See \ref ISTL_Factory for the ParameterTree layout and examples. */ RestartedGMResSolver (std::shared_ptr > op, std::shared_ptr > prec, const ParameterTree& configuration) : IterativeSolver::IterativeSolver(op,prec,configuration), _restart(configuration.get("restart")) {} RestartedGMResSolver (std::shared_ptr > op, std::shared_ptr > sp, std::shared_ptr > prec, const ParameterTree& configuration) : IterativeSolver::IterativeSolver(op,sp,prec,configuration), _restart(configuration.get("restart")) {} /*! \brief Set up RestartedGMResSolver solver. \copydetails IterativeSolver::IterativeSolver(std::shared_ptr>,std::shared_ptr>,std::shared_ptr>,scalar_real_type,int,int) \param restart number of GMRes cycles before restart */ RestartedGMResSolver (std::shared_ptr> op, std::shared_ptr> sp, std::shared_ptr> prec, scalar_real_type reduction, int restart, int maxit, int verbose) : IterativeSolver::IterativeSolver(op,sp,prec,reduction,maxit,verbose), _restart(restart) {} /*! \brief Apply inverse operator. \copydoc InverseOperator::apply(X&,Y&,InverseOperatorResult&) \note Currently, the RestartedGMResSolver aborts when it detects a breakdown. */ void apply (X& x, Y& b, InverseOperatorResult& res) override { apply(x,b,Simd::max(_reduction),res); } /*! \brief Apply inverse operator. \copydoc InverseOperator::apply(X&,Y&,double,InverseOperatorResult&) \note Currently, the RestartedGMResSolver aborts when it detects a breakdown. */ void apply (X& x, Y& b, [[maybe_unused]] double reduction, InverseOperatorResult& res) override { using std::abs; const Simd::Scalar EPSILON = 1e-80; const int m = _restart; real_type norm = 0.0; int j = 1; std::vector s(m+1), sn(m); std::vector cs(m); // need copy of rhs if GMRes has to be restarted Y b2(b); // helper vector Y w(b); std::vector< std::vector > H(m+1,s); std::vector v(m+1,b); Iteration iteration(*this,res); // clear solver statistics and set res.converged to false _prec->pre(x,b); // calculate defect and overwrite rhs with it _op->applyscaleadd(-1.0,x,b); // b -= Ax // calculate preconditioned defect v[0] = 0.0; _prec->apply(v[0],b); // r = W^-1 b norm = _sp->norm(v[0]); if(iteration.step(0, norm)){ _prec->post(x); return; } while(j <= _maxit && res.converged != true) { int i = 0; v[0] *= Simd::cond(norm==real_type(0.), real_type(0.), real_type(real_type(1.0)/norm)); s[0] = norm; for(i=1; iapply(v[i],v[i+1]); _prec->apply(w,v[i+1]); for(int k=0; kdot(v[k],w) = v[k]\adjoint w // so one has to pay attention to the order // in the scalar product for the complex case // doing the modified Gram-Schmidt algorithm H[k][i] = _sp->dot(v[k],w); // w -= H[k][i] * v[k] w.axpy(-H[k][i],v[k]); } H[i+1][i] = _sp->norm(w); if(Simd::allTrue(abs(H[i+1][i]) < EPSILON)) DUNE_THROW(SolverAbort, "breakdown in GMRes - |w| == 0.0 after " << j << " iterations"); // normalize new vector v[i+1] = w; v[i+1] *= Simd::cond(norm==real_type(0.), field_type(0.), field_type(real_type(1.0)/H[i+1][i])); // update QR factorization for(int k=0; k 0) std::cout << "=== GMRes::restart" << std::endl; // get saved rhs b = b2; // calculate new defect _op->applyscaleadd(-1.0,x,b); // b -= Ax; // calculate preconditioned defect v[0] = 0.0; _prec->apply(v[0],b); norm = _sp->norm(v[0]); } } //end while // postprocess preconditioner _prec->post(x); } protected : void update(X& w, int i, const std::vector >& H, const std::vector& s, const std::vector& v) { // solution vector of the upper triangular system std::vector y(s); // backsolve for(int a=i-1; a>=0; a--) { field_type rhs(s[a]); for(int b=a+1; b typename std::enable_if::value,T>::type conjugate(const T& t) { return t; } template typename std::enable_if::value,T>::type conjugate(const T& t) { using std::conj; return conj(t); } void generatePlaneRotation(field_type &dx, field_type &dy, real_type &cs, field_type &sn) { using std::sqrt; using std::abs; using std::max; using std::min; const real_type eps = 1e-15; real_type norm_dx = abs(dx); real_type norm_dy = abs(dy); real_type norm_max = max(norm_dx, norm_dy); real_type norm_min = min(norm_dx, norm_dy); real_type temp = norm_min/norm_max; // we rewrite the code in a vectorizable fashion cs = Simd::cond(norm_dy < eps, real_type(1.0), Simd::cond(norm_dx < eps, real_type(0.0), real_type(Simd::cond(norm_dy > norm_dx, real_type(1.0)/sqrt(real_type(1.0) + temp*temp)*temp, real_type(1.0)/sqrt(real_type(1.0) + temp*temp) )))); sn = Simd::cond(norm_dy < eps, field_type(0.0), Simd::cond(norm_dx < eps, field_type(1.0), field_type(Simd::cond(norm_dy > norm_dx, field_type(1.0)/sqrt(real_type(1.0) + temp*temp)*dx*conjugate(dy)/norm_dx/norm_dy, field_type(1.0)/sqrt(real_type(1.0) + temp*temp)*conjugate(dy/dx) )))); } void applyPlaneRotation(field_type &dx, field_type &dy, real_type &cs, field_type &sn) { field_type temp = cs * dx + sn * dy; dy = -conjugate(sn) * dx + cs * dy; dx = temp; } using IterativeSolver::_op; using IterativeSolver::_prec; using IterativeSolver::_sp; using IterativeSolver::_reduction; using IterativeSolver::_maxit; using IterativeSolver::_verbose; using Iteration = typename IterativeSolver::template Iteration; int _restart; }; DUNE_REGISTER_SOLVER("restartedgmressolver", defaultIterativeSolverCreator()); /** \brief implements the Flexible Generalized Minimal Residual (FGMRes) method (right preconditioned) FGMRes solves the right-preconditioned unsymmetric linear system Ax = b using the Flexible Generalized Minimal Residual method. It is flexible because the preconditioner can change in every iteration, which allows to use Krylov solvers without fixed number of iterations as preconditioners. Needs more memory than GMRes. \tparam X trial vector, vector type of the solution \tparam Y test vector, vector type of the RHS \tparam F vector type for orthonormal basis of Krylov space */ template class RestartedFlexibleGMResSolver : public RestartedGMResSolver { public: using typename RestartedGMResSolver::domain_type; using typename RestartedGMResSolver::range_type; using typename RestartedGMResSolver::field_type; using typename RestartedGMResSolver::real_type; private: using typename RestartedGMResSolver::scalar_real_type; //! \brief field_type Allocator retrieved from domain type using fAlloc = typename RestartedGMResSolver::fAlloc; //! \brief real_type Allocator retrieved from domain type using rAlloc = typename RestartedGMResSolver::rAlloc; public: // copy base class constructors using RestartedGMResSolver::RestartedGMResSolver; // don't shadow four-argument version of apply defined in the base class using RestartedGMResSolver::apply; /*! \brief Apply inverse operator. \copydoc InverseOperator::apply(X&,Y&,double,InverseOperatorResult&) \note Currently, the RestartedFlexibleGMResSolver aborts when it detects a breakdown. */ void apply (X& x, Y& b, [[maybe_unused]] double reduction, InverseOperatorResult& res) override { using std::abs; const Simd::Scalar EPSILON = 1e-80; const int m = _restart; real_type norm = 0.0; int i, j = 1, k; std::vector s(m+1), sn(m); std::vector cs(m); // helper vector Y tmp(b); std::vector< std::vector > H(m+1,s); std::vector v(m+1,b); std::vector w(m+1,b); Iteration iteration(*this,res); // setup preconditioner if it does something in pre // calculate residual and overwrite a copy of the rhs with it _prec->pre(x, b); v[0] = b; _op->applyscaleadd(-1.0, x, v[0]); // b -= Ax norm = _sp->norm(v[0]); // the residual norm if(iteration.step(0, norm)){ _prec->post(x); return; } // start iterations res.converged = false;; while(j <= _maxit && res.converged != true) { v[0] *= (1.0 / norm); s[0] = norm; for(i=1; iapply(w[i], v[i]); // compute vi = A*wi // use v[i+1] as temporary vector for w _op->apply(w[i], v[i+1]); // do Arnoldi algorithm for(int kk=0; kkdot(v[k],v[i+1]) = v[k]\adjoint v[i+1] // so one has to pay attention to the order // in the scalar product for the complex case // doing the modified Gram-Schmidt algorithm H[kk][i] = _sp->dot(v[kk],v[i+1]); // w -= H[k][i] * v[kk] v[i+1].axpy(-H[kk][i], v[kk]); } H[i+1][i] = _sp->norm(v[i+1]); if(Simd::allTrue(abs(H[i+1][i]) < EPSILON)) DUNE_THROW(SolverAbort, "breakdown in fGMRes - |w| (-> " << w[i] << ") == 0.0 after " << j << " iterations"); // v[i+1] = w*1/H[i+1][i] v[i+1] *= real_type(1.0)/H[i+1][i]; // update QR factorization for(k=0; kapplyPlaneRotation(H[k][i],H[k+1][i],cs[k],sn[k]); // compute new givens rotation this->generatePlaneRotation(H[i][i],H[i+1][i],cs[i],sn[i]); // finish updating QR factorization this->applyPlaneRotation(H[i][i],H[i+1][i],cs[i],sn[i]); this->applyPlaneRotation(s[i],s[i+1],cs[i],sn[i]); // norm of the residual is the last component of vector s using std::abs; norm = abs(s[i+1]); iteration.step(j, norm); } // end inner for loop // calculate update vector tmp = 0.0; this->update(tmp, i, H, s, w); // and update current iterate x += tmp; // restart fGMRes if convergence was not achieved, // i.e. linear residual has not reached desired reduction // and if still j < _maxit (do not restart on last iteration) if( res.converged != true && j < _maxit) { if (_verbose > 0) std::cout << "=== fGMRes::restart" << std::endl; // get rhs v[0] = b; // calculate new defect _op->applyscaleadd(-1.0, x,v[0]); // b -= Ax; // calculate preconditioned defect norm = _sp->norm(v[0]); // update the residual norm } } // end outer while loop // post-process preconditioner _prec->post(x); } private: using RestartedGMResSolver::_op; using RestartedGMResSolver::_prec; using RestartedGMResSolver::_sp; using RestartedGMResSolver::_reduction; using RestartedGMResSolver::_maxit; using RestartedGMResSolver::_verbose; using RestartedGMResSolver::_restart; using Iteration = typename IterativeSolver::template Iteration; }; DUNE_REGISTER_SOLVER("restartedflexiblegmressolver", defaultIterativeSolverCreator()); /** * @brief Generalized preconditioned conjugate gradient solver. * * A preconditioned conjugate gradient that allows * the preconditioner to change between iterations. * * One example for such preconditioner is AMG when used without * a direct coarse solver. In this case the number of iterations * performed on the coarsest level might change between applications. * * In contrast to CGSolver the search directions are stored and * the orthogonalization is done explicitly. */ template class GeneralizedPCGSolver : public IterativeSolver { public: using typename IterativeSolver::domain_type; using typename IterativeSolver::range_type; using typename IterativeSolver::field_type; using typename IterativeSolver::real_type; private: using typename IterativeSolver::scalar_real_type; //! \brief field_type Allocator retrieved from domain type using fAlloc = ReboundAllocatorType; public: // don't shadow four-argument version of apply defined in the base class using IterativeSolver::apply; /*! \brief Set up nonlinear preconditioned conjugate gradient solver. \copydetails IterativeSolver::IterativeSolver(const LinearOperator&,Preconditioner&,scalar_real_type,int,int) \param restart number of GMRes cycles before restart */ GeneralizedPCGSolver (const LinearOperator& op, Preconditioner& prec, scalar_real_type reduction, int maxit, int verbose, int restart = 10) : IterativeSolver::IterativeSolver(op,prec,reduction,maxit,verbose), _restart(restart) {} /*! \brief Set up nonlinear preconditioned conjugate gradient solver. \copydetails IterativeSolver::IterativeSolver(const LinearOperator&,const ScalarProduct&,Preconditioner&,scalar_real_type,int,int) \param restart When to restart the construction of the Krylov search space. */ GeneralizedPCGSolver (const LinearOperator& op, const ScalarProduct& sp, Preconditioner& prec, scalar_real_type reduction, int maxit, int verbose, int restart = 10) : IterativeSolver::IterativeSolver(op,sp,prec,reduction,maxit,verbose), _restart(restart) {} /*! \brief Set up nonlinear preconditioned conjugate gradient solver. \copydetails IterativeSolver::IterativeSolver(std::shared_ptr>,std::shared_ptr>,const ParameterTree&) Additional parameter: ParameterTree Key | Meaning ------------------|------------ restart | number of PCG cycles before restart See \ref ISTL_Factory for the ParameterTree layout and examples. */ GeneralizedPCGSolver (std::shared_ptr > op, std::shared_ptr > prec, const ParameterTree& configuration) : IterativeSolver::IterativeSolver(op,prec,configuration), _restart(configuration.get("restart")) {} GeneralizedPCGSolver (std::shared_ptr > op, std::shared_ptr > sp, std::shared_ptr > prec, const ParameterTree& configuration) : IterativeSolver::IterativeSolver(op,sp,prec,configuration), _restart(configuration.get("restart")) {} /*! \brief Set up nonlinear preconditioned conjugate gradient solver. \copydetails IterativeSolver::IterativeSolver(std::shared_ptr>,std::shared_ptr>,std::shared_ptr>,scalar_real_type,int,int) \param restart When to restart the construction of the Krylov search space. */ GeneralizedPCGSolver (std::shared_ptr> op, std::shared_ptr> sp, std::shared_ptr> prec, scalar_real_type reduction, int maxit, int verbose, int restart = 10) : IterativeSolver::IterativeSolver(op,sp,prec,reduction,maxit,verbose), _restart(restart) {} /*! \brief Apply inverse operator. \copydoc InverseOperator::apply(X&,Y&,InverseOperatorResult&) */ void apply (X& x, X& b, InverseOperatorResult& res) override { Iteration iteration(*this, res); _prec->pre(x,b); // prepare preconditioner _op->applyscaleadd(-1,x,b); // overwrite b with defect std::vector > p(_restart); std::vector pp(_restart); X q(x); // a temporary vector X prec_res(x); // a temporary vector for preconditioner output p[0].reset(new X(x)); real_type def = _sp->norm(b); // compute norm if(iteration.step(0, def)){ _prec->post(x); return; } // some local variables field_type rho, lambda; int i=0; // determine initial search direction *(p[0]) = 0; // clear correction _prec->apply(*(p[0]),b); // apply preconditioner rho = _sp->dot(*(p[0]),b); // orthogonalization _op->apply(*(p[0]),q); // q=Ap pp[0] = _sp->dot(*(p[0]),q); // scalar product lambda = rho/pp[0]; // minimization x.axpy(lambda,*(p[0])); // update solution b.axpy(-lambda,q); // update defect // convergence test def=_sp->norm(b); // comp defect norm ++i; if(iteration.step(i, def)){ _prec->post(x); return; } while(i<_maxit) { // the loop int end=std::min(_restart, _maxit-i+1); for (int ii = 1; ii < end; ++ii) { //std::cout<<" ii="<()); /*! \brief Accelerated flexible conjugate gradient method Flexible conjugate gradient method as in Y. Notay 'Flexible conjugate Gradients', SIAM J. Sci. Comput Vol. 22, No.4, pp. 1444-1460 This solver discard cyclic all old directions to speed up computing. In exact arithmetic it is exactly the same as the GeneralizedPCGSolver, but it is much faster, depending on the operator and dimension. On the other hand for large mmax it uses noticeably more memory. */ template class RestartedFCGSolver : public IterativeSolver { public: using typename IterativeSolver::domain_type; using typename IterativeSolver::range_type; using typename IterativeSolver::field_type; using typename IterativeSolver::real_type; private: using typename IterativeSolver::scalar_real_type; public: // don't shadow four-argument version of apply defined in the base class using IterativeSolver::apply; /*! \brief Constructor to initialize a RestartedFCG solver. \copydetails IterativeSolver::IterativeSolver(const LinearOperator&, Preconditioner&, scalar_real_type, int, int) \param mmax is the maximal number of previous vectors which are orthogonalized against the new search direction. */ RestartedFCGSolver (const LinearOperator& op, Preconditioner& prec, scalar_real_type reduction, int maxit, int verbose, int mmax = 10) : IterativeSolver(op, prec, reduction, maxit, verbose), _mmax(mmax) { } /*! \brief Constructor to initialize a RestartedFCG solver. \copydetails IterativeSolver::IterativeSolver(const LinearOperator&, const ScalarProduct&, Preconditioner&, scalar_real_type, int, int) \param mmax is the maximal number of previous vectors which are orthogonalized against the new search direction. */ RestartedFCGSolver (const LinearOperator& op, const ScalarProduct& sp, Preconditioner& prec, scalar_real_type reduction, int maxit, int verbose, int mmax = 10) : IterativeSolver(op, sp, prec, reduction, maxit, verbose), _mmax(mmax) { } /*! \brief Constructor to initialize a RestartedFCG solver. \copydetails IterativeSolver::IterativeSolver(std::shared_ptr>, std::shared_ptr>, std::shared_ptr>, scalar_real_type, int, int) \param mmax is the maximal number of previous vectors which are orthogonalized against the new search direction. */ RestartedFCGSolver (std::shared_ptr> op, std::shared_ptr> sp, std::shared_ptr> prec, scalar_real_type reduction, int maxit, int verbose, int mmax = 10) : IterativeSolver(op, sp, prec, reduction, maxit, verbose), _mmax(mmax) {} /*! \brief Constructor to initialize a RestartedFCG solver. \copydoc IterativeSolver::IterativeSolver(std::shared_ptr>,std::shared_ptr>,const ParameterTree&) Additional parameter: ParameterTree Key | Meaning ------------------|------------ mmax | number of FCG cycles before restart. default=10 See \ref ISTL_Factory for the ParameterTree layout and examples. */ RestartedFCGSolver (std::shared_ptr> op, std::shared_ptr> prec, const ParameterTree& configuration) : IterativeSolver(op, prec, configuration), _mmax(configuration.get("mmax", 10)) {} RestartedFCGSolver (std::shared_ptr> op, std::shared_ptr> sp, std::shared_ptr> prec, const ParameterTree& config) : IterativeSolver(op, sp, prec, config), _mmax(config.get("mmax", 10)) {} /*! \brief Apply inverse operator. \copydoc InverseOperator::apply(X&,Y&,InverseOperatorResult&) \note Currently, the RestartedFCGSolver aborts when a NaN or infinite defect is detected. However, -ffinite-math-only (implied by -ffast-math) can inhibit a result from becoming NaN that really should be NaN. E.g. numeric_limits::quiet_NaN()*0.0==0.0 with gcc-5.3 -ffast-math. */ void apply (X& x, X& b, InverseOperatorResult& res) override { using rAlloc = ReboundAllocatorType; res.clear(); Iteration iteration(*this,res); _prec->pre(x,b); // prepare preconditioner _op->applyscaleadd(-1,x,b); // overwrite b with defect //arrays for interim values: std::vector d(_mmax+1, x); // array for directions std::vector Ad(_mmax+1, x); // array for Ad[i] std::vector ddotAd(_mmax+1,0); // array for X w(x); real_type def = _sp->norm(b); // compute norm if(iteration.step(0, def)){ _prec->post(x); return; } // some local variables field_type alpha; // the loop int i=1; int i_bounded=0; while(i<=_maxit && !res.converged) { for (; i_bounded <= _mmax && i<= _maxit; i_bounded++) { d[i_bounded] = 0; // reset search direction _prec->apply(d[i_bounded], b); // apply preconditioner w = d[i_bounded]; // copy of current d[i] // orthogonalization with previous directions orthogonalizations(i_bounded,Ad,w,ddotAd,d); //saving interim values for future calculating _op->apply(d[i_bounded], Ad[i_bounded]); // save Ad[i] ddotAd[i_bounded]=_sp->dot(d[i_bounded],Ad[i_bounded]); // save alpha = _sp->dot(d[i_bounded], b)/ddotAd[i_bounded]; // / //update solution and defect x.axpy(alpha, d[i_bounded]); b.axpy(-alpha, Ad[i_bounded]); // convergence test def = _sp->norm(b); // comp defect norm iteration.step(i, def); i++; } //restart: exchange first and last stored values cycle(Ad,d,ddotAd,i_bounded); } //correct i which is wrong if convergence was not achieved. i=std::min(_maxit,i); _prec->post(x); // postprocess preconditioner } private: //This function is called every iteration to orthogonalize against the last search directions virtual void orthogonalizations(const int& i_bounded,const std::vector& Ad, const X& w, const std::vector>& ddotAd,std::vector& d) { // The RestartedFCGSolver uses only values with lower array index; for (int k = 0; k < i_bounded; k++) { d[i_bounded].axpy(-_sp->dot(Ad[k], w) / ddotAd[k], d[k]); // d[i] -= </>d[k] } } // This function is called every mmax iterations to handle limited array sizes. virtual void cycle(std::vector& Ad,std::vector& d,std::vector >& ddotAd,int& i_bounded) { // Reset loop index and exchange the first and last arrays i_bounded = 1; std::swap(Ad[0], Ad[_mmax]); std::swap(d[0], d[_mmax]); std::swap(ddotAd[0], ddotAd[_mmax]); } protected: int _mmax; using IterativeSolver::_op; using IterativeSolver::_prec; using IterativeSolver::_sp; using IterativeSolver::_reduction; using IterativeSolver::_maxit; using IterativeSolver::_verbose; using Iteration = typename IterativeSolver::template Iteration; }; DUNE_REGISTER_SOLVER("restartedfcgsolver", defaultIterativeSolverCreator()); /*! \brief Complete flexible conjugate gradient method This solver is a simple modification of the RestartedFCGSolver and, if possible, uses mmax old directions. It uses noticeably more memory, but provides more stability for preconditioner changes. */ template class CompleteFCGSolver : public RestartedFCGSolver { public: using typename RestartedFCGSolver::domain_type; using typename RestartedFCGSolver::range_type; using typename RestartedFCGSolver::field_type; using typename RestartedFCGSolver::real_type; // copy base class constructors using RestartedFCGSolver::RestartedFCGSolver; // don't shadow four-argument version of apply defined in the base class using RestartedFCGSolver::apply; // just a minor part of the RestartedFCGSolver apply method will be modified void apply (X& x, X& b, InverseOperatorResult& res) override { // reset limiter of orthogonalization loop _k_limit = 0; this->RestartedFCGSolver::apply(x,b,res); }; private: // This function is called every iteration to orthogonalize against the last search directions. void orthogonalizations(const int& i_bounded,const std::vector& Ad, const X& w, const std::vector>& ddotAd,std::vector& d) override { // This FCGSolver uses values with higher array indexes too, if existent. for (int k = 0; k < _k_limit; k++) { if(i_bounded!=k) d[i_bounded].axpy(-_sp->dot(Ad[k], w) / ddotAd[k], d[k]); // d[i] -= </>d[k] } // The loop limit increase, if array is not completely filled. if(_k_limit<=i_bounded) _k_limit++; }; // This function is called every mmax iterations to handle limited array sizes. void cycle(std::vector& Ad, [[maybe_unused]] std::vector& d, [[maybe_unused]] std::vector >& ddotAd,int& i_bounded) override { // Only the loop index i_bounded return to 0, if it reached mmax. i_bounded = 0; // Now all arrays are filled and the loop in void orthogonalizations can use the whole arrays. _k_limit = Ad.size(); }; int _k_limit = 0; protected: using RestartedFCGSolver::_mmax; using RestartedFCGSolver::_op; using RestartedFCGSolver::_prec; using RestartedFCGSolver::_sp; using RestartedFCGSolver::_reduction; using RestartedFCGSolver::_maxit; using RestartedFCGSolver::_verbose; }; DUNE_REGISTER_SOLVER("completefcgsolver", defaultIterativeSolverCreator()); /** @} end documentation */ } // end namespace #endif