Debian Codegraph @

include/deal.II/lac/solver_bicgstab.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_bicgstab_h
16 #define dealii_solver_bicgstab_h
17
18
19 #include <deal.II/base/config.h>
20
21 #include <deal.II/base/enable_observer_pointer.h>
22 #include <deal.II/base/logstream.h>
23 #include <deal.II/base/signaling_nan.h>
24 #include <deal.II/base/template_constraints.h>
25
26 #include <deal.II/lac/solver.h>
27 #include <deal.II/lac/solver_control.h>
28
29 #include <cmath>
30 #include <limits>
31
32 DEAL_II_NAMESPACE_OPEN
33
34 /**
35 * @addtogroup Solvers
36 * @{
37 */
38
39 /**
40 * Bicgstab algorithm by van der Vorst.
41 *
42 * For the requirements on matrices and vectors in order to work with this
43 * class, see the documentation of the SolverBase base class.
44 *
45 * Like all other solver classes, this class has a local structure called @p
46 * AdditionalData which is used to pass additional parameters to the solver,
47 * like damping parameters or the number of temporary vectors. We use this
48 * additional structure instead of passing these values directly to the
49 * constructor because this makes the use of the @p SolverSelector and other
50 * classes much easier and guarantees that these will continue to work even if
51 * number or type of the additional parameters for a certain solver changes.
52 *
53 * The Bicgstab method has two additional parameters found in the
54 * SolverBicgstab::AdditionalData struct: the first, @p exact_residual is a boolean,
55 * deciding whether to compute the actual residual in each step (@p true) or
56 * to use the length of the computed orthogonal residual (@p false). Note that
57 * computing the residual causes a third matrix-vector multiplication, though
58 * no additional preconditioning, in each step. The reason for doing this is,
59 * that the size of the orthogonalized residual computed during the iteration
60 * may be larger by orders of magnitude than the true residual. This is due to
61 * numerical instabilities related to badly conditioned matrices. Since this
62 * instability results in a bad stopping criterion, the default for this
63 * parameter is @p true. Whenever the user knows that the estimated residual
64 * works reasonably as well, the flag should be set to @p false in order to
65 * increase the performance of the solver.
66 *
67 * The second parameter @p breakdown is the size of a breakdown criterion. It is difficult
68 * to find a general good criterion, so if things do not work for you, try to
69 * change this value.
70 *
71 *
72 * <h3>Observing the progress of linear solver iterations</h3>
73 *
74 * The solve() function of this class uses the mechanism described in the
75 * Solver base class to determine convergence. This mechanism can also be used
76 * to observe the progress of the iteration.
77 */
78 template <typename VectorType = Vector<double>>
79 DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>)
80 class SolverBicgstab : public SolverBase<VectorType>
81 {
82 public:
83 /**
84 * There are two possibilities to compute the residual: one is an estimate
85 * using the computed value @p tau. The other is exact computation using
86 * another matrix vector multiplication. This increases the costs of the
87 * algorithm, so it is should be set to false whenever the problem allows
88 * it.
89 *
90 * Bicgstab is susceptible to breakdowns, so we need a parameter telling us,
91 * which numbers are considered zero.
92 */
93 struct AdditionalData
94 {
95 /**
96 * Constructor.
97 *
98 * The default is to perform an exact residual computation and breakdown
99 * parameter is the minimum finite value representable by the value_type of
100 * VectorType.
101 */
102 explicit AdditionalData(
103 const bool exact_residual = true,
104 const double breakdown =
105 std::numeric_limits<typename VectorType::value_type>::min())
106 : exact_residual(exact_residual)
107 , breakdown(breakdown)
108 {}
109 /**
110 * Flag for exact computation of residual.
111 */
112 bool exact_residual;
113 /**
114 * Breakdown threshold.
115 */
116 double breakdown;
117 };
118
119 /**
120 * Constructor.
121 */
122 SolverBicgstab(SolverControl &cn,
123 VectorMemory<VectorType> &mem,
124 const AdditionalData &data = AdditionalData());
125
126 /**
127 * Constructor. Use an object of type GrowingVectorMemory as a default to
128 * allocate memory.
129 */
130 SolverBicgstab(SolverControl &cn,
131 const AdditionalData &data = AdditionalData());
132
133 /**
134 * Virtual destructor.
135 */
136 virtual ~SolverBicgstab() override = default;
137
138 /**
139 * Solve primal problem only.
140 */
141 template <typename MatrixType, typename PreconditionerType>
142 DEAL_II_CXX20_REQUIRES(
143 (concepts::is_linear_operator_on<MatrixType, VectorType> &&
144 concepts::is_linear_operator_on<PreconditionerType, VectorType>))
145 void solve(const MatrixType &A,
146 VectorType &x,
147 const VectorType &b,
148 const PreconditionerType &preconditioner);
149
150 protected:
151 /**
152 * Computation of the stopping criterion.
153 */
154 template <typename MatrixType>
155 double
156 criterion(const MatrixType &A,
157 const VectorType &x,
158 const VectorType &b,
159 VectorType &t);
160
161 /**
162 * Interface for derived class. This function gets the current iteration
163 * vector, the residual and the update vector in each step. It can be used
164 * for graphical output of the convergence history.
165 */
166 virtual void
167 print_vectors(const unsigned int step,
168 const VectorType &x,
169 const VectorType &r,
170 const VectorType &d) const;
171
172 /**
173 * Additional parameters.
174 */
175 AdditionalData additional_data;
176
177 private:
178 /**
179 * A structure returned by the iterate() function representing what it found
180 * is happening during the iteration.
181 */
182 struct IterationResult
183 {
184 bool breakdown;
185 SolverControl::State state;
186 unsigned int last_step;
187 double last_residual;
188
189 IterationResult(const bool breakdown,
190 const SolverControl::State state,
191 const unsigned int last_step,
192 const double last_residual);
193 };
194
195 /**
196 * The iteration loop itself. The function returns a structure indicating
197 * what happened in this function.
198 */
199 template <typename MatrixType, typename PreconditionerType>
200 IterationResult
201 iterate(const MatrixType &A,
202 VectorType &x,
203 const VectorType &b,
204 const PreconditionerType &preconditioner,
205 const unsigned int step);
206 };
207
208
209 /** @} */
210 /*-------------------------Inline functions -------------------------------*/
211
212 #ifndef DOXYGEN
213
214
215 template <typename VectorType>
216 DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>)
217 SolverBicgstab<VectorType>::IterationResult::IterationResult(
218 const bool breakdown,
219 const SolverControl::State state,
220 const unsigned int last_step,
221 const double last_residual)
222 : breakdown(breakdown)
223 , state(state)
224 , last_step(last_step)
225 , last_residual(last_residual)
226 {}
227
228
229
230 template <typename VectorType>
231 DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>)
232 SolverBicgstab<VectorType>::SolverBicgstab(SolverControl &cn,
233 VectorMemory<VectorType> &mem,
234 const AdditionalData &data)
235 : SolverBase<VectorType>(cn, mem)
236 , additional_data(data)
237 {}
238
239
240
241 template <typename VectorType>
242 DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>)
243 SolverBicgstab<VectorType>::SolverBicgstab(SolverControl &cn,
244 const AdditionalData &data)
245 : SolverBase<VectorType>(cn)
246 , additional_data(data)
247 {}
248
249
250
251 template <typename VectorType>
252 DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>)
253 template <typename MatrixType>
254 double SolverBicgstab<VectorType>::criterion(const MatrixType &A,
255 const VectorType &x,
256 const VectorType &b,
257 VectorType &t)
258 {
259 A.vmult(t, x);
260 return std::sqrt(t.add_and_dot(-1.0, b, t));
261 }
262
263
264
265 template <typename VectorType>
266 DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>)
267 void SolverBicgstab<VectorType>::print_vectors(const unsigned int,
268 const VectorType &,
269 const VectorType &,
270 const VectorType &) const
271 {}
272
273
274
275 template <typename VectorType>
276 DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>)
277 template <typename MatrixType, typename PreconditionerType>
278 typename SolverBicgstab<VectorType>::IterationResult
279 SolverBicgstab<VectorType>::iterate(const MatrixType &A,
280 VectorType &x,
281 const VectorType &b,
282 const PreconditionerType &preconditioner,
283 const unsigned int last_step)
284 {
285 // Allocate temporary memory.
286 typename VectorMemory<VectorType>::Pointer Vr(this->memory);
287 typename VectorMemory<VectorType>::Pointer Vrbar(this->memory);
288 typename VectorMemory<VectorType>::Pointer Vp(this->memory);
289 typename VectorMemory<VectorType>::Pointer Vy(this->memory);
290 typename VectorMemory<VectorType>::Pointer Vz(this->memory);
291 typename VectorMemory<VectorType>::Pointer Vt(this->memory);
292 typename VectorMemory<VectorType>::Pointer Vv(this->memory);
293
294 // Define a few aliases for simpler use of the vectors
295 VectorType &r = *Vr;
296 VectorType &rbar = *Vrbar;
297 VectorType &p = *Vp;
298 VectorType &y = *Vy;
299 VectorType &z = *Vz;
300 VectorType &t = *Vt;
301 VectorType &v = *Vv;
302
303 r.reinit(x, true);
304 rbar.reinit(x, true);
305 p.reinit(x, true);
306 y.reinit(x, true);
307 z.reinit(x, true);
308 t.reinit(x, true);
309 v.reinit(x, true);
310
311 using value_type = typename VectorType::value_type;
312 using real_type = typename numbers::NumberTraits<value_type>::real_type;
313
314 A.vmult(r, x);
315 r.sadd(-1., 1., b);
316 value_type res = r.l2_norm();
317
318 unsigned int step = last_step;
319
320 SolverControl::State state = this->iteration_status(step, res, x);
321 if (state == SolverControl::State::success)
322 return IterationResult(false, state, step, res);
323
324 rbar = r;
325
326 value_type alpha = 1.;
327 value_type rho = 1.;
328 value_type omega = 1.;
329
330 do
331 {
332 ++step;
333
334 const value_type rhobar = (step == 1 + last_step) ? res * res : r * rbar;
335
336 if (std::fabs(rhobar) < additional_data.breakdown)
337 {
338 return IterationResult(true, state, step, res);
339 }
340
341 const value_type beta = rhobar * alpha / (rho * omega);
342 rho = rhobar;
343 if (step == last_step + 1)
344 {
345 p = r;
346 }
347 else
348 {
349 p.sadd(beta, 1., r);
350 p.add(-beta * omega, v);
351 }
352
353 preconditioner.vmult(y, p);
354 A.vmult(v, y);
355 const value_type rbar_dot_v = rbar * v;
356 if (std::fabs(rbar_dot_v) < additional_data.breakdown)
357 {
358 return IterationResult(true, state, step, res);
359 }
360
361 alpha = rho / rbar_dot_v;
362
363 res = std::sqrt(real_type(r.add_and_dot(-alpha, v, r)));
364
365 // check for early success, see the lac/bicgstab_early testcase as to
366 // why this is necessary
367 //
368 // note: the vector *Vx we pass to the iteration_status signal here is
369 // only the current approximation, not the one we will return with, which
370 // will be x=*Vx + alpha*y
371 if (this->iteration_status(step, res, x) == SolverControl::success)
372 {
373 x.add(alpha, y);
374 print_vectors(step, x, r, y);
375 return IterationResult(false, SolverControl::success, step, res);
376 }
377
378 preconditioner.vmult(z, r);
379 A.vmult(t, z);
380 const value_type t_dot_r = t * r;
381 const real_type t_squared = t * t;
382 if (t_squared < additional_data.breakdown)
383 {
384 return IterationResult(true, state, step, res);
385 }
386 omega = t_dot_r / t_squared;
387 x.add(alpha, y, omega, z);
388
389 if (additional_data.exact_residual)
390 {
391 r.add(-omega, t);
392 res = criterion(A, x, b, t);
393 }
394 else
395 res = std::sqrt(real_type(r.add_and_dot(-omega, t, r)));
396
397 state = this->iteration_status(step, res, x);
398 print_vectors(step, x, r, y);
399 }
400 while (state == SolverControl::iterate);
401
402 return IterationResult(false, state, step, res);
403 }
404
405
406
407 template <typename VectorType>
408 DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>)
409 template <typename MatrixType, typename PreconditionerType>
410 DEAL_II_CXX20_REQUIRES(
411 (concepts::is_linear_operator_on<MatrixType, VectorType> &&
412 concepts::is_linear_operator_on<PreconditionerType, VectorType>))
413 void SolverBicgstab<VectorType>::solve(const MatrixType &A,
414 VectorType &x,
415 const VectorType &b,
416 const PreconditionerType &preconditioner)
417 {
418 LogStream::Prefix prefix("Bicgstab");
419
420 IterationResult state(false, SolverControl::failure, 0, 0);
421 do
422 {
423 state = iterate(A, x, b, preconditioner, state.last_step);
424 }
425 while (state.state == SolverControl::iterate);
426
427 // In case of failure: throw exception
428 AssertThrow(state.state == SolverControl::success,
429 SolverControl::NoConvergence(state.last_step,
430 state.last_residual));
431 // Otherwise exit as normal
432 }
433
434 #endif // DOXYGEN
435
436 DEAL_II_NAMESPACE_CLOSE
437
438 #endif