Debian Codegraph @

include/deal.II/lac/solver.h

raw
1 // ------------------------------------------------------------------------
2 //
3 // SPDX-License-Identifier: LGPL-2.1-or-later
4 // Copyright (C) 1998 - 2024 by the deal.II authors
5 //
6 // This file is part of the deal.II library.
7 //
8 // Part of the source code is dual licensed under Apache-2.0 WITH
9 // LLVM-exception OR LGPL-2.1-or-later. Detailed license information
10 // governing the source code and code contributions can be found in
11 // LICENSE.md and CONTRIBUTING.md at the top level directory of deal.II.
12 //
13 // ------------------------------------------------------------------------
14
15 #ifndef dealii_solver_h
16 #define dealii_solver_h
17
18 #include <deal.II/base/config.h>
19
20 #include <deal.II/base/enable_observer_pointer.h>
21 #include <deal.II/base/template_constraints.h>
22
23 #include <deal.II/lac/solver_control.h>
24 #include <deal.II/lac/vector_memory.h>
25
26 #include <boost/signals2.hpp>
27
28 DEAL_II_NAMESPACE_OPEN
29
30 // Forward declaration
31 #ifndef DOXYGEN
32 template <typename number>
33 class Vector;
34 #endif
35
36 /**
37 * A base class for iterative linear solvers. This class provides interfaces
38 * to a memory pool and the objects that determine whether a solver has
39 * converged.
40 *
41 *
42 * <h3>Requirements common to derived solver classes</h3>
43 *
44 * In general, iterative solvers do not rely on any special structure of
45 * matrices or the format of storage. Rather, they only require that matrices
46 * and vectors define certain operations such as matrix-vector products, or
47 * scalar products between vectors. Consequently, this class as well as the
48 * derived classes and their member functions implementing concrete linear
49 * solvers are templated on the types of matrices and vectors. However, there
50 * are some common requirements a matrix or vector type must fulfill to qualify
51 * as an acceptable type for the solvers in this hierarchy. These requirements
52 * are listed below.
53 *
54 * The classes we show below are not any concrete class. Rather, they are
55 * intended to form a "signature" which a concrete class has to conform to.
56 * Note that the matrix and vector classes within this library of course
57 * conform to this interface; therefore, SparseMatrix and Vector are good
58 * examples for these classes as they provide the necessary signatures of
59 * member functions (although they also provide many more interfaces that
60 * solvers do not in fact need -- for example, element access). In addition,
61 * you may want to take a look at step-20, step-22, or a number of classes
62 * in the LinearSolvers namespace for examples of how one can define
63 * matrix-like classes that can serve as linear operators for linear solvers.
64 *
65 * Concretely, matrix and vector classes that can be passed to a linear
66 * solver need to provide the following interfaces:
67 * @code
68 * class Matrix
69 * {
70 * public:
71 * // Application of matrix to vector src. Write result into dst.
72 * void vmult (VectorType &dst,
73 * const VectorType &src) const;
74 *
75 * // Application of transpose to a vector. This function is,
76 * // however, only used by some iterative methods.
77 * void Tvmult (VectorType &dst,
78 * const VectorType &src) const;
79 * };
80 *
81 *
82 * class Vector
83 * {
84 * public:
85 * // Define value type of the entries
86 * using value_type = double;
87 *
88 * // Resize the current object to have the same size and layout as
89 * // the model_vector argument provided. The second argument
90 * // indicates whether to clear the current object after resizing.
91 * // The second argument must have a default value equal to false.
92 * void reinit (const Vector &model_vector,
93 * const bool leave_elements_uninitialized = false);
94 *
95 * // Inner product between the current object and the argument.
96 * double operator * (const Vector &v) const;
97 *
98 * // Set all the vector entries to a constant scalar.
99 * Vector & operator = (const double a);
100 *
101 * // Deep copy of the vector.
102 * // Important if Vector contains pointers to data to duplicate data.
103 * Vector & operator = (const Vector &x);
104 *
105 * // Addition of vectors
106 * void add (const Vector &x);
107 *
108 * // Scaled addition of vectors
109 * void add (const double a,
110 * const Vector &x);
111 *
112 * // Scaled addition of vectors
113 * void sadd (const double a,
114 * const double b,
115 * const Vector &x);
116 *
117 * // Scaled assignment of a vector
118 * void equ (const double a,
119 * const Vector &x);
120 *
121 * // Combined scaled addition of vector x into the current object and
122 * // subsequent inner product of the current object with v.
123 * double add_and_dot (const double a,
124 * const Vector &x,
125 * const Vector &v);
126 *
127 * // Multiply the elements of the current object by a fixed value.
128 * Vector & operator *= (const double a);
129 *
130 * // Return the l2 norm of the vector.
131 * double l2_norm () const;
132 * };
133 * @endcode
134 *
135 * In addition, for some solvers there has to be a global function
136 * <tt>swap(VectorType &a, VectorType &b)</tt> that exchanges the values of
137 * the two vectors.
138 *
139 * Finally, the solvers also expect an instantiation of
140 * GrowingVectorMemory@<VectorType@>. These instantiations are provided by the
141 * deal.II library for the built-in vector types, but must be explicitly added
142 * for user-provided vector classes. Otherwise, the linker will complain that
143 * it cannot find the constructors and destructors of GrowingVectorMemory that
144 * happen in the @p SolverBase class.
145 *
146 * @code
147 * // Definition and implementation of vector class
148 * class UserVector { ... };
149 *
150 * // Create explicit instantiation for the vector class. If your project
151 * // consists of multiple files, including header files, this instantiation
152 * // must be put in a <code>.cc</code> file in order to instantiate only
153 * // once.
154 * #include <deal.II/lac/vector_memory.templates.h>
155 *
156 * template class VectorMemory<UserVector>;
157 * template class GrowingVectorMemory<UserVector>;
158 * @endcode
159 *
160 * The preconditioners used must have the same interface as matrices, i.e. in
161 * particular they have to provide a member function @p vmult which denotes
162 * the application of the preconditioner.
163 *
164 *
165 * <h3>AdditionalData</h3>
166 *
167 * Several solvers need additional data, like the damping parameter @p omega
168 * of the @p SolverRichardson class or the maximum number of temporary vectors
169 * of @p SolverGMRES. To have a standardized way of constructing solvers,
170 * each solver class has a <tt>struct AdditionalData</tt> as a member, and
171 * constructors of all solver classes take such an argument. Some solvers need
172 * no additional data, or may not at the current time. For these solvers the
173 * struct @p AdditionalData is empty and calling the constructor may be done
174 * without giving the additional structure as an argument as a default @p
175 * AdditionalData is set by default.
176 *
177 * With this, creating a solver looks like one of the following blocks:
178 * @code
179 * // GMRES with restart every 50 iterations
180 * SolverGMRES solver_gmres (solver_control, vector_memory,
181 * SolverGMRES::AdditionalData(50));
182 *
183 * // Richardson with omega=0.8
184 * SolverRichardson solver_richardson (solver_control, vector_memory,
185 * SolverGMRES::AdditionalData(0.8));
186 *
187 * // CG with default AdditionalData
188 * SolverCG solver_cg (solver_control, vector_memory);
189 * @endcode
190 *
191 * Using a unified constructor parameter list for all solvers supports the @p
192 * SolverSelector class; the unified interface enables us to use this class
193 * unchanged even if the number of types of parameters to a certain solver
194 * changes and it is still possible in a simple way to give these additional
195 * data to the @p SolverSelector object for each solver which it may use.
196 *
197 *
198 * <h3>Observing the progress of linear solver iterations</h3>
199 *
200 * The SolverBase class, being the base class for all of the iterative solvers
201 * such as SolverCG, SolverGMRES, etc, provides the facilities by which actual
202 * solver implementations determine whether the iteration is converged, not
203 * yet converged, or has failed. Typically, this is done using an object of
204 * type SolverControl that is passed to the solver classes's constructors and
205 * from them down to the constructor of this base class. Every one of the
206 * tutorial programs that solves a linear problem (starting with step-3) uses
207 * this method and it is described in detail there. However, the underlying
208 * mechanism is more general and allows for many other uses to observe how the
209 * linear solver iterations progress.
210 *
211 * The basic approach is that the iterative solvers invoke a <i>signal</i> at
212 * the end of each iteration to determine whether the solution is converged. A
213 * signal is a class that has, conceptually, a list of pointers to functions
214 * and every time the signal is invoked, each of these functions are called.
215 * In the language of signals, the functions called are called <i>slots</i>
216 * and one can attach any number of slots to a signal. (The implementation of
217 * signals and slots we use here is the one from the BOOST.signals2 library.)
218 * A number of details may clarify what is happening underneath:
219 * - In reality, the signal object does not store pointers to functions, but
220 * function objects as slots. Each slot must conform to a particular signature:
221 * here, it is an object that can be called with three arguments (the number of
222 * the current linear iteration, the current residual, and the current iterate;
223 * more specifics are discussed in the documentation of the connect()
224 * function). A pointer to a function with this argument list satisfies the
225 * requirements, but you can also pass a member function whose
226 * <code>this</code> argument has been bound using a lambda function
227 * (see the example below).
228 * - Each of the slots will return a value that indicates whether the iteration
229 * should continue, should stop because it has succeeded, or stop because it has
230 * failed. The return type of slots is therefore of type SolverControl::State.
231 * The returned values from all of the slots will then have to be combined
232 * before they are returned to the iterative solver that invoked the signal.
233 * The way this works is that if at least one slot returned
234 * SolverControl::failure, then the combined value is SolverControl::failure;
235 * otherwise, if at least one slot returned SolverControl::iterate, then this
236 * is going to be the return value of the signal; finally, only if all slots
237 * return SolverControl::success will the signal's return value be
238 * SolverControl::success.
239 * - It may of course be that a particular slot has
240 * been connected to the signal only to observe how the solution or a specific
241 * part of it converges, but has no particular opinion on whether the
242 * iteration should continue or not. In such cases, the slot should just
243 * return SolverControl::success, which is the weakest of all return values
244 * according to the rules laid out above.
245 *
246 * Given all this, it should now be obvious how the SolverControl object fits
247 * into this scheme: when a SolverControl object is passed to the constructor
248 * of the current class, we simply connect the SolverControl::check() function
249 * of that object as a slot to the signal we maintain here. In other words,
250 * since a SolverBase object is always constructed using a SolverControl object,
251 * there is always at least one slot associated with the signal, namely the
252 * one that determines convergence.
253 *
254 * On the other hand, using the connect() member function, it is possible to
255 * connect any number of other slots to the signal to observe whatever it is
256 * you want to observe. The connect() function also returns an object that
257 * describes the connection from the signal to the slot, and the corresponding
258 * BOOST functions then allow you to disconnect the slot if you want.
259 *
260 * An example may illuminate these issues. In the step-3 tutorial program, let
261 * us add a member function as follows to the main class:
262 * @code
263 * SolverControl::State
264 * Step3::write_intermediate_solution (
265 * const unsigned int iteration,
266 * const double , //check_value
267 * const Vector<double> &current_iterate) const
268 * {
269 * DataOut<2> data_out;
270 * data_out.attach_dof_handler (dof_handler);
271 * data_out.add_data_vector (current_iterate, "solution");
272 * data_out.build_patches ();
273 *
274 * std::ofstream output ("solution-"
275 * + Utilities::int_to_string(iteration,4)
276 * + ".vtu");
277 * data_out.write_vtu (output);
278 *
279 * return SolverControl::success;
280 * }
281 * @endcode
282 * The function satisfies the signature necessary to be a slot for the signal
283 * discussed above, with the exception that it is a member function and
284 * consequently requires a <code>this</code> pointer. What the function does
285 * is to take the vector given as last argument and write it into a file in
286 * VTU format with a file name derived from the number of the iteration.
287 *
288 * This function can then be hooked into the CG solver by modifying the
289 * <code>Step3::solve()</code> function as follows:
290 * @code
291 * void Step3::solve ()
292 * {
293 * SolverControl solver_control (1000, 1e-12);
294 * SolverCG<> solver (solver_control);
295 *
296 * solver.connect ([this](const unsigned int iteration,
297 * const double check_value,
298 * const Vector<double> *current_iterate){
299 * this->write_intermediate_solution(
300 * iteration, check_value, current_iterate);
301 * });
302 * solver.solve (system_matrix, solution, system_rhs,
303 * PreconditionIdentity());
304 * }
305 * @endcode
306 * The use of a lambda function here ensures that we convert the
307 * member function with its three arguments plus the <code>this</code>
308 * pointer, to a function that only takes three arguments, by fixing the
309 * implicit <code>this</code> argument of the function to the
310 * <code>this</code> pointer in the current function.
311 *
312 * It is well understood that the CG method is a smoothing iteration (in the
313 * same way as the more commonly used Jacobi or SSOR iterations are
314 * smoothers). The code above therefore allows to observe how the solution
315 * becomes smoother and smoother in every iteration. This is best observed by
316 * initializing the solution vector with randomly distributed numbers in
317 * $[-1,1]$, using code such as
318 * @code
319 * for (unsigned int i=0; i<solution.size(); ++i)
320 * solution(i) = 2.*rand()/RAND_MAX-1;
321 * @endcode
322 * Using this, the slot will then generate files that when visualized look
323 * like this over the course of iterations zero to five: <table> <tr> <td>
324 * @image html "cg-monitor-smoothing-0.png"
325 * </td> <td>
326 * @image html "cg-monitor-smoothing-1.png"
327 * </td> <td>
328 * @image html "cg-monitor-smoothing-2.png"
329 * </td> </tr> <tr> <td>
330 * @image html "cg-monitor-smoothing-3.png"
331 * </td> <td>
332 * @image html "cg-monitor-smoothing-4.png"
333 * </td> <td>
334 * @image html "cg-monitor-smoothing-5.png"
335 * </td> </tr> </table>
336 *
337 * @ingroup Solvers
338 */
339 template <typename VectorType = Vector<double>>
340 DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>)
341 class SolverBase : public EnableObserverPointer
342 {
343 public:
344 /**
345 * An alias for the underlying vector type
346 */
347 using vector_type = VectorType;
348
349 /**
350 * Constructor. Takes a control object which evaluates the conditions for
351 * convergence, and an object that allows solvers to allocate memory for
352 * temporary objects.
353 *
354 * Of both objects, a reference is stored, so it is the user's
355 * responsibility to guarantee that the lifetime of the two arguments is at
356 * least as long as that of the solver object.
357 */
358 SolverBase(SolverControl &solver_control,
359 VectorMemory<VectorType> &vector_memory);
360
361 /**
362 * Constructor. Takes a control object which evaluates the conditions for
363 * convergence. In contrast to the other constructor, this constructor
364 * designates an internal object of type GrowingVectorMemory to allocate
365 * memory.
366 *
367 * A reference to the control object is stored, so it is the user's
368 * responsibility to guarantee that the lifetime of the argument is at least
369 * as long as that of the solver object.
370 */
371 SolverBase(SolverControl &solver_control);
372
373 /**
374 * Connect a function object that will be called periodically within
375 * iterative solvers. This function is used to attach monitors to iterative
376 * solvers, either to determine when convergence has happened, or simply to
377 * observe the progress of an iteration. See the documentation of this class
378 * for more information.
379 *
380 * @param slot A function object specified here will, with each call,
381 * receive the number of the current iteration, the value that is used to
382 * check for convergence (typically the residual of the current iterate with
383 * respect to the linear system to be solved) and the currently best
384 * available guess for the current iterate. Note that some solvers do not
385 * update the approximate solution in every iteration but only after
386 * convergence or failure has been determined (GMRES is an example); in such
387 * cases, the vector passed as the last argument to the signal is simply the
388 * best approximate at the time the signal is called, but not the vector
389 * that will be returned if the signal's return value indicates that the
390 * iteration should be terminated. The function object must return a
391 * SolverControl::State value that indicates whether the iteration should
392 * continue, has failed, or has succeeded. The results of all connected
393 * functions will then be combined to determine what should happen with the
394 * iteration.
395 *
396 * @return A connection object that represents the connection from the
397 * signal to the function object. It can be used to disconnect the function
398 * object again from the signal. See the documentation of the BOOST Signals2
399 * library for more information on connection management.
400 */
401 boost::signals2::connection
402 connect(
403 const std::function<SolverControl::State(const unsigned int iteration,
404 const double check_value,
405 const VectorType &current_iterate)>
406 &slot);
407
408
409
410 protected:
411 /**
412 * A static vector memory object to be used whenever no such object has been
413 * given to the constructor.
414 */
415 mutable GrowingVectorMemory<VectorType> static_vector_memory;
416
417 /**
418 * A reference to an object that provides memory for auxiliary vectors.
419 */
420 VectorMemory<VectorType> &memory;
421
422 private:
423 /**
424 * A class whose operator() combines two states indicating whether we should
425 * continue iterating or stop, and returns a state that dominates. The rules
426 * are:
427 * - If one of the two states indicates failure, return failure.
428 * - Otherwise, if one of the two states indicates to continue iterating, then
429 * continue iterating.
430 * - Otherwise, return success.
431 */
432 struct StateCombiner
433 {
434 using result_type = SolverControl::State;
435
436 SolverControl::State
437 operator()(const SolverControl::State state1,
438 const SolverControl::State state2) const;
439
440 template <typename Iterator>
441 SolverControl::State
442 operator()(const Iterator begin, const Iterator end) const;
443 };
444
445 protected:
446 /**
447 * A signal that iterative solvers can execute at the end of every iteration
448 * (or in an otherwise periodic fashion) to find out whether we should
449 * continue iterating or not. The signal may call one or more slots that
450 * each will make this determination by themselves, and the result over all
451 * slots (function calls) will be determined by the StateCombiner object.
452 *
453 * The arguments passed to the signal are (i) the number of the current
454 * iteration; (ii) the value that is used to determine convergence
455 * (oftentimes the residual, but in other cases other quantities may be used
456 * as long as they converge to zero as the iterate approaches the solution
457 * of the linear system); and (iii) a vector that corresponds to the current
458 * best guess for the solution at the point where the signal is called. Note
459 * that some solvers do not update the approximate solution in every
460 * iteration but only after convergence or failure has been determined
461 * (GMRES is an example); in such cases, the vector passed as the last
462 * argument to the signal is simply the best approximate at the time the
463 * signal is called, but not the vector that will be returned if the
464 * signal's return value indicates that the iteration should be terminated.
465 */
466 boost::signals2::signal<
467 SolverControl::State(const unsigned int iteration,
468 const double check_value,
469 const VectorType &current_iterate),
470 StateCombiner>
471 iteration_status;
472 };
473
474
475
476 /*-------------------------------- Inline functions ------------------------*/
477 #ifndef DOXYGEN
478
479 template <typename VectorType>
480 DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>)
481 inline SolverControl::State SolverBase<VectorType>::StateCombiner::operator()(
482 const SolverControl::State state1,
483 const SolverControl::State state2) const
484 {
485 if ((state1 == SolverControl::failure) || (state2 == SolverControl::failure))
486 return SolverControl::failure;
487 else if ((state1 == SolverControl::iterate) ||
488 (state2 == SolverControl::iterate))
489 return SolverControl::iterate;
490 else
491 return SolverControl::success;
492 }
493
494
495 template <typename VectorType>
496 DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>)
497 template <typename Iterator>
498 inline SolverControl::State
499 SolverBase<VectorType>::StateCombiner::operator()(const Iterator begin,
500 const Iterator end) const
501 {
502 Assert(begin != end,
503 ExcMessage("You can't combine iterator states if no state is given."));
504
505 // combine the first with all of the following states
506 SolverControl::State state = *begin;
507 Iterator p = begin;
508 ++p;
509 for (; p != end; ++p)
510 state = this->operator()(state, *p);
511
512 return state;
513 }
514
515
516 template <typename VectorType>
517 DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>)
518 inline SolverBase<VectorType>::SolverBase(
519 SolverControl &solver_control,
520 VectorMemory<VectorType> &vector_memory)
521 : memory(vector_memory)
522 {
523 // connect the solver control object to the signal. SolverControl::check
524 // only takes two arguments, the iteration and the check_value, and so
525 // we simply ignore the third argument that is passed in whenever the
526 // signal is executed
527 connect([&solver_control](const unsigned int iteration,
528 const double check_value,
529 const VectorType &) {
530 return solver_control.check(iteration, check_value);
531 });
532 }
533
534
535
536 template <typename VectorType>
537 DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>)
538 inline SolverBase<VectorType>::SolverBase(SolverControl &solver_control)
539 : // use the static memory object this class owns
540 memory(static_vector_memory)
541 {
542 // connect the solver control object to the signal. SolverControl::check
543 // only takes two arguments, the iteration and the check_value, and so
544 // we simply ignore the third argument that is passed in whenever the
545 // signal is executed
546 connect([&solver_control](const unsigned int iteration,
547 const double check_value,
548 const VectorType &) {
549 return solver_control.check(iteration, check_value);
550 });
551 }
552
553
554
555 template <typename VectorType>
556 DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>)
557 inline boost::signals2::connection SolverBase<VectorType>::connect(
558 const std::function<SolverControl::State(const unsigned int iteration,
559 const double check_value,
560 const VectorType &current_iterate)>
561 &slot)
562 {
563 return iteration_status.connect(slot);
564 }
565
566 #endif
567
568 DEAL_II_NAMESPACE_CLOSE
569
570 #endif