Debian Codegraph @

dune/istl/solver.hh

raw
1 // SPDX-FileCopyrightText: Copyright © DUNE Project contributors, see file LICENSE.md in module root
2 // SPDX-License-Identifier: LicenseRef-GPL-2.0-only-with-DUNE-exception
3 // -*- tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*-
4 // vi: set et ts=4 sw=2 sts=2:
5
6 #ifndef DUNE_ISTL_SOLVER_HH
7 #define DUNE_ISTL_SOLVER_HH
8
9 #include <dune-istl-config.hh> // DUNE_ISTL_SUPPORT_OLD_CATEGORY_INTERFACE
10
11 #include <iomanip>
12 #include <ostream>
13 #include <string>
14 #include <functional>
15
16 #include <dune/common/exceptions.hh>
17 #include <dune/common/shared_ptr.hh>
18 #include <dune/common/simd/io.hh>
19 #include <dune/common/simd/simd.hh>
20 #include <dune/common/parametertree.hh>
21 #include <dune/common/timer.hh>
22
23 #include "solvertype.hh"
24 #include "preconditioner.hh"
25 #include "operators.hh"
26 #include "scalarproducts.hh"
27
28 namespace Dune
29 {
30 /**
31 * @addtogroup ISTL_Solvers
32 * @{
33 */
34 /** \file
35
36 \brief Define general, extensible interface for inverse operators.
37
38 Implementation here covers only inversion of linear operators,
39 but the implementation might be used for nonlinear operators
40 as well.
41 */
42 /**
43 \brief Statistics about the application of an inverse operator
44
45 The return value of an application of the inverse
46 operator delivers some important information about
47 the iteration.
48 */
49 struct InverseOperatorResult
50 {
51 /** \brief Default constructor */
52 InverseOperatorResult ()
53 {
54 clear();
55 }
56
57 /** \brief Resets all data */
58 void clear ()
59 {
60 iterations = 0;
61 reduction = 0;
62 converged = false;
63 conv_rate = 1;
64 elapsed = 0;
65 condition_estimate = -1;
66 }
67
68 /** \brief Number of iterations */
69 int iterations;
70
71 /** \brief Reduction achieved: \f$ \|b-A(x^n)\|/\|b-A(x^0)\|\f$ */
72 double reduction;
73
74 /** \brief True if convergence criterion has been met */
75 bool converged;
76
77 /** \brief Convergence rate (average reduction per step) */
78 double conv_rate;
79
80 /** \brief Estimate of condition number */
81 double condition_estimate = -1;
82
83 /** \brief Elapsed time in seconds */
84 double elapsed;
85 };
86
87
88 //=====================================================================
89 /*!
90 \brief Abstract base class for all solvers.
91
92 An InverseOperator computes the solution of \f$ A(x)=b\f$ where
93 \f$ A : X \to Y \f$ is an operator.
94 Note that the solver "knows" which operator
95 to invert and which preconditioner to apply (if any). The
96 user is only interested in inverting the operator.
97 InverseOperator might be a Newton scheme, a Krylov subspace method,
98 or a direct solver or just anything.
99 */
100 template<class X, class Y>
101 class InverseOperator {
102 public:
103 //! \brief Type of the domain of the operator to be inverted.
104 typedef X domain_type;
105
106 //! \brief Type of the range of the operator to be inverted.
107 typedef Y range_type;
108
109 /** \brief The field type of the operator. */
110 typedef typename X::field_type field_type;
111
112 //! \brief The real type of the field type (is the same if using real numbers, but differs for std::complex)
113 typedef typename FieldTraits<field_type>::real_type real_type;
114
115 //! \brief scalar type underlying the field_type
116 typedef Simd::Scalar<real_type> scalar_real_type;
117
118 /**
119 \brief Apply inverse operator,
120
121 \warning Note: right hand side b may be overwritten!
122
123 \param x The left hand side to store the result in.
124 \param b The right hand side
125 \param res Object to store the statistics about applying the operator.
126
127 \throw SolverAbort When the solver detects a problem and cannot
128 continue
129 */
130 virtual void apply (X& x, Y& b, InverseOperatorResult& res) = 0;
131
132 /*!
133 \brief apply inverse operator, with given convergence criteria.
134
135 \warning Right hand side b may be overwritten!
136
137 \param x The left hand side to store the result in.
138 \param b The right hand side
139 \param reduction The minimum defect reduction to achieve.
140 \param res Object to store the statistics about applying the operator.
141
142 \throw SolverAbort When the solver detects a problem and cannot
143 continue
144 */
145 virtual void apply (X& x, Y& b, double reduction, InverseOperatorResult& res) = 0;
146
147 //! Category of the solver (see SolverCategory::Category)
148 virtual SolverCategory::Category category() const
149 #ifdef DUNE_ISTL_SUPPORT_OLD_CATEGORY_INTERFACE
150 {
151 DUNE_THROW(Dune::Exception,"It is necessary to implement the category method in a derived classes, in the future this method will pure virtual.");
152 }
153 #else
154 = 0;
155 #endif
156
157 //! \brief Destructor
158 virtual ~InverseOperator () {}
159
160 protected:
161 // spacing values
162 enum { iterationSpacing = 5 , normSpacing = 16 };
163
164 //! helper function for printing header of solver output
165 void printHeader(std::ostream& s) const
166 {
167 s << std::setw(iterationSpacing) << " Iter";
168 s << std::setw(normSpacing) << "Defect";
169 s << std::setw(normSpacing) << "Rate" << std::endl;
170 }
171
172 //! helper function for printing solver output
173 template <typename CountType, typename DataType>
174 void printOutput(std::ostream& s,
175 const CountType& iter,
176 const DataType& norm,
177 const DataType& norm_old) const
178 {
179 const DataType rate = norm/norm_old;
180 s << std::setw(iterationSpacing) << iter << " ";
181 s << std::setw(normSpacing) << Simd::io(norm) << " ";
182 s << std::setw(normSpacing) << Simd::io(rate) << std::endl;
183 }
184
185 //! helper function for printing solver output
186 template <typename CountType, typename DataType>
187 void printOutput(std::ostream& s,
188 const CountType& iter,
189 const DataType& norm) const
190 {
191 s << std::setw(iterationSpacing) << iter << " ";
192 s << std::setw(normSpacing) << Simd::io(norm) << std::endl;
193 }
194 };
195
196 /*!
197 \brief Base class for all implementations of iterative solvers
198
199 This class provides all storage, which is needed by the usual
200 iterative solvers. In additional it provides all the necessary
201 constructors, which are then only imported in the actual solver
202 implementation.
203 */
204 template<class X, class Y>
205 class IterativeSolver : public InverseOperator<X,Y>{
206 public:
207 using typename InverseOperator<X,Y>::domain_type;
208 using typename InverseOperator<X,Y>::range_type;
209 using typename InverseOperator<X,Y>::field_type;
210 using typename InverseOperator<X,Y>::real_type;
211 using typename InverseOperator<X,Y>::scalar_real_type;
212
213 /*!
214 \brief General constructor to initialize an iterative solver.
215
216 \param op The operator we solve.
217 \param prec The preconditioner to apply in each iteration of the loop.
218 Has to inherit from Preconditioner.
219 \param reduction The relative defect reduction to achieve when applying
220 the operator.
221 \param maxit The maximum number of iteration steps allowed when applying
222 the operator.
223 \param verbose The verbosity level.
224
225 Verbose levels are:
226 <ul>
227 <li> 0 : print nothing </li>
228 <li> 1 : print initial and final defect and statistics </li>
229 <li> 2 : print line for each iteration </li>
230 </ul>
231 */
232 IterativeSolver (const LinearOperator<X,Y>& op, Preconditioner<X,Y>& prec, scalar_real_type reduction, int maxit, int verbose) :
233 _op(stackobject_to_shared_ptr(op)),
234 _prec(stackobject_to_shared_ptr(prec)),
235 _sp(new SeqScalarProduct<X>),
236 _reduction(reduction), _maxit(maxit), _verbose(verbose), _category(SolverCategory::sequential)
237 {
238 if(SolverCategory::category(op) != SolverCategory::sequential)
239 DUNE_THROW(InvalidSolverCategory, "LinearOperator has to be sequential!");
240 if(SolverCategory::category(prec) != SolverCategory::sequential)
241 DUNE_THROW(InvalidSolverCategory, "Preconditioner has to be sequential!");
242 }
243
244 /**
245 \brief General constructor to initialize an iterative solver
246
247 \param op The operator we solve.
248 \param sp The scalar product to use, e. g. SeqScalarproduct.
249 \param prec The preconditioner to apply in each iteration of the loop.
250 Has to inherit from Preconditioner.
251 \param reduction The relative defect reduction to achieve when applying
252 the operator.
253 \param maxit The maximum number of iteration steps allowed when applying
254 the operator.
255 \param verbose The verbosity level.
256
257 Verbose levels are:
258 <ul>
259 <li> 0 : print nothing </li>
260 <li> 1 : print initial and final defect and statistics </li>
261 <li> 2 : print line for each iteration </li>
262 </ul>
263 */
264 IterativeSolver (const LinearOperator<X,Y>& op, const ScalarProduct<X>& sp, Preconditioner<X,Y>& prec,
265 scalar_real_type reduction, int maxit, int verbose) :
266 _op(stackobject_to_shared_ptr(op)),
267 _prec(stackobject_to_shared_ptr(prec)),
268 _sp(stackobject_to_shared_ptr(sp)),
269 _reduction(reduction), _maxit(maxit), _verbose(verbose), _category(SolverCategory::category(op))
270 {
271 if(SolverCategory::category(op) != SolverCategory::category(prec))
272 DUNE_THROW(InvalidSolverCategory, "LinearOperator and Preconditioner must have the same SolverCategory!");
273 if(SolverCategory::category(op) != SolverCategory::category(sp))
274 DUNE_THROW(InvalidSolverCategory, "LinearOperator and ScalarProduct must have the same SolverCategory!");
275 }
276
277 /*!
278 \brief Constructor.
279
280 \param op The operator we solve
281 \param prec The preconditioner to apply in each iteration of the loop.
282 \param configuration ParameterTree containing iterative solver parameters.
283
284 ParameterTree Key | Meaning
285 ------------------|------------
286 reduction | The relative defect reduction to achieve when applying the operator
287 maxit | The maximum number of iteration steps allowed when applying the operator
288 verbose | The verbosity level
289
290 See \ref ISTL_Factory for the ParameterTree layout and examples.
291 */
292 IterativeSolver (std::shared_ptr<const LinearOperator<X,Y> > op, std::shared_ptr<Preconditioner<X,X> > prec, const ParameterTree& configuration) :
293 IterativeSolver(op,std::make_shared<SeqScalarProduct<X>>(),prec,
294 configuration.get<real_type>("reduction"),
295 configuration.get<int>("maxit"),
296 configuration.get<int>("verbose"))
297 {}
298
299 /*!
300 \brief Constructor.
301
302 \param op The operator we solve
303 \param sp The scalar product to use, e. g. SeqScalarproduct.
304 \param prec The preconditioner to apply in each iteration of the loop.
305 \param configuration ParameterTree containing iterative solver parameters.
306
307 ParameterTree Key | Meaning
308 ------------------|------------
309 reduction | The relative defect reduction to achieve when applying the operator
310 maxit | The maximum number of iteration steps allowed when applying the operator
311 verbose | The verbosity level
312
313 See \ref ISTL_Factory for the ParameterTree layout and examples.
314 */
315 IterativeSolver (std::shared_ptr<const LinearOperator<X,Y> > op, std::shared_ptr<const ScalarProduct<X> > sp, std::shared_ptr<Preconditioner<X,X> > prec, const ParameterTree& configuration) :
316 IterativeSolver(op,sp,prec,
317 configuration.get<scalar_real_type>("reduction"),
318 configuration.get<int>("maxit"),
319 configuration.get<int>("verbose"))
320 {}
321
322 /**
323 \brief General constructor to initialize an iterative solver
324
325 \param op The operator we solve.
326 \param sp The scalar product to use, e. g. SeqScalarproduct.
327 \param prec The preconditioner to apply in each iteration of the loop.
328 Has to inherit from Preconditioner.
329 \param reduction The relative defect reduction to achieve when applying
330 the operator.
331 \param maxit The maximum number of iteration steps allowed when applying
332 the operator.
333 \param verbose The verbosity level.
334
335 Verbose levels are:
336 <ul>
337 <li> 0 : print nothing </li>
338 <li> 1 : print initial and final defect and statistics </li>
339 <li> 2 : print line for each iteration </li>
340 </ul>
341 */
342 IterativeSolver (std::shared_ptr<const LinearOperator<X,Y>> op,
343 std::shared_ptr<const ScalarProduct<X>> sp,
344 std::shared_ptr<Preconditioner<X,Y>> prec,
345 scalar_real_type reduction, int maxit, int verbose) :
346 _op(op),
347 _prec(prec),
348 _sp(sp),
349 _reduction(reduction), _maxit(maxit), _verbose(verbose),
350 _category(SolverCategory::category(*op))
351 {
352 if(SolverCategory::category(*op) != SolverCategory::category(*prec))
353 DUNE_THROW(InvalidSolverCategory, "LinearOperator and Preconditioner must have the same SolverCategory!");
354 if(SolverCategory::category(*op) != SolverCategory::category(*sp))
355 DUNE_THROW(InvalidSolverCategory, "LinearOperator and ScalarProduct must have the same SolverCategory!");
356 }
357
358 // #warning actually we want to have this as the default and just implement the second one
359 // //! \copydoc InverseOperator::apply(X&,Y&,InverseOperatorResult&)
360 // virtual void apply (X& x, Y& b, InverseOperatorResult& res)
361 // {
362 // apply(x,b,_reduction,res);
363 // }
364
365 #ifndef DOXYGEN
366 // make sure the three-argument apply from the base class does not get shadowed
367 // by the redefined four-argument version below
368 using InverseOperator<X,Y>::apply;
369 #endif
370
371 /*!
372 \brief Apply inverse operator with given reduction factor.
373
374 \copydoc InverseOperator::apply(X&,Y&,double,InverseOperatorResult&)
375 */
376 void apply (X& x, X& b, double reduction, InverseOperatorResult& res) override
377 {
378 scalar_real_type saved_reduction = _reduction;
379 _reduction = reduction;
380 this->apply(x,b,res);
381 _reduction = saved_reduction;
382 }
383
384 //! Category of the solver (see SolverCategory::Category)
385 SolverCategory::Category category() const override
386 {
387 return _category;
388 }
389
390 std::string name() const{
391 std::string name = className(*this);
392 return name.substr(0, name.find("<"));
393 }
394
395 /*!
396 \brief Class for controlling iterative methods
397
398 This class provides building blocks for a iterative method. It does all
399 things that have to do with output, residual checking (NaN, infinite,
400 convergence) and sets also the fields of InverseOperatorResult.
401
402 Instances of this class are meant to create with
403 IterativeSolver::startIteration and stored as a local variable in the apply
404 method. If the scope of the apply method is left the destructor of this
405 class sets all the solver statistics in the InverseOperatorResult and
406 prints the final output.
407
408 During the iteration in every step Iteration::step should be called with
409 the current iteration count and norm of the residual. It returns true if
410 convergence is achieved.
411 */
412 template<class CountType = unsigned int>
413 class Iteration {
414 public:
415 Iteration(const IterativeSolver& parent, InverseOperatorResult& res)
416 : _i(0)
417 , _res(res)
418 , _parent(parent)
419 , _valid(true)
420 {
421 res.clear();
422 if(_parent._verbose>0){
423 std::cout << "=== " << parent.name() << std::endl;
424 if(_parent._verbose > 1)
425 _parent.printHeader(std::cout);
426 }
427 }
428
429 Iteration(const Iteration&) = delete;
430 Iteration(Iteration&& other)
431 : _def0(other._def0)
432 , _def(other._def)
433 , _i(other._i)
434 , _watch(other._watch)
435 , _res(other._res)
436 , _parent(other._parent)
437 , _valid(other._valid)
438 {
439 other._valid = false;
440 }
441
442 ~Iteration(){
443 if(_valid)
444 finalize();
445 }
446
447 /*! \brief registers the iteration step, checks for invalid defect norm
448 and convergence.
449
450 \param i The current iteration count
451 \param def The current norm of the defect
452
453 \return true is convergence is achieved
454
455 \throw SolverAbort when `def` contains inf or NaN
456 */
457 bool step(CountType i, real_type def){
458 if (!Simd::allTrue(isFinite(def))) // check for inf or NaN
459 {
460 if (_parent._verbose>0)
461 std::cout << "=== " << _parent.name() << ": abort due to infinite or NaN defect"
462 << std::endl;
463 DUNE_THROW(SolverAbort,
464 _parent.name() << ": defect=" << Simd::io(def)
465 << " is infinite or NaN");
466 }
467 if(i == 0)
468 _def0 = def;
469 if(_parent._verbose > 1){
470 if(i!=0)
471 _parent.printOutput(std::cout,i,def,_def);
472 else
473 _parent.printOutput(std::cout,i,def);
474 }
475 _def = def;
476 _i = i;
477 _res.converged = (Simd::allTrue(def<_def0*_parent._reduction || def<real_type(1E-30))); // convergence check
478 return _res.converged;
479 }
480
481 protected:
482 void finalize(){
483 _res.converged = (Simd::allTrue(_def<_def0*_parent._reduction || _def<real_type(1E-30)));
484 _res.iterations = _i;
485 _res.reduction = static_cast<double>(Simd::max(_def/_def0));
486 _res.conv_rate = pow(_res.reduction,1.0/_i);
487 _res.elapsed = _watch.elapsed();
488 if (_parent._verbose>0) // final print
489 {
490 std::cout << "=== rate=" << _res.conv_rate
491 << ", T=" << _res.elapsed
492 << ", TIT=" << _res.elapsed/_res.iterations
493 << ", IT=" << _res.iterations << std::endl;
494 }
495 }
496
497 real_type _def0 = 0.0, _def = 0.0;
498 CountType _i;
499 Timer _watch;
500 InverseOperatorResult& _res;
501 const IterativeSolver& _parent;
502 bool _valid;
503 };
504
505 protected:
506 std::shared_ptr<const LinearOperator<X,Y>> _op;
507 std::shared_ptr<Preconditioner<X,Y>> _prec;
508 std::shared_ptr<const ScalarProduct<X>> _sp;
509 scalar_real_type _reduction;
510 int _maxit;
511 int _verbose;
512 SolverCategory::Category _category;
513 };
514
515 /**
516 * \brief Helper class for notifying a DUNE-ISTL linear solver about
517 * a change of the iteration matrix object in a unified way,
518 * i.e. independent from the solver's type (direct/iterative).
519 *
520 * \author Sebastian Westerheide.
521 */
522 template <typename ISTLLinearSolver, typename BCRSMatrix>
523 class SolverHelper
524 {
525 public:
526 static void setMatrix (ISTLLinearSolver& solver,
527 const BCRSMatrix& matrix)
528 {
529 static const bool is_direct_solver
530 = Dune::IsDirectSolver<ISTLLinearSolver>::value;
531 SolverHelper<ISTLLinearSolver,BCRSMatrix>::
532 Implementation<is_direct_solver>::setMatrix(solver,matrix);
533 }
534
535 protected:
536 /**
537 * \brief Implementation that works together with iterative ISTL
538 * solvers, e.g. Dune::CGSolver or Dune::BiCGSTABSolver.
539 */
540 template <bool is_direct_solver, typename Dummy = void>
541 struct Implementation
542 {
543 static void setMatrix (ISTLLinearSolver&,
544 const BCRSMatrix&)
545 {}
546 };
547
548 /**
549 * \brief Implementation that works together with direct ISTL
550 * solvers, e.g. Dune::SuperLU or Dune::UMFPack.
551 */
552 template <typename Dummy>
553 struct Implementation<true,Dummy>
554 {
555 static void setMatrix (ISTLLinearSolver& solver,
556 const BCRSMatrix& matrix)
557 {
558 solver.setMatrix(matrix);
559 }
560 };
561 };
562
563 /**
564 * @}
565 */
566 }
567
568 #endif