Debian Codegraph @

include/deal.II/lac/solver_qmrs.h

raw
1 // ------------------------------------------------------------------------
2 //
3 // SPDX-License-Identifier: LGPL-2.1-or-later
4 // Copyright (C) 1999 - 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_qmrs_h
16 #define dealii_solver_qmrs_h
17
18 #include <deal.II/base/config.h>
19
20 #include <deal.II/base/enable_observer_pointer.h>
21 #include <deal.II/base/logstream.h>
22 #include <deal.II/base/template_constraints.h>
23
24 #include <deal.II/lac/solver.h>
25 #include <deal.II/lac/solver_control.h>
26
27 #include <cmath>
28
29 DEAL_II_NAMESPACE_OPEN
30
31 /**
32 * @addtogroup Solvers
33 * @{
34 */
35
36 /**
37 * <h3>Quasi-minimal method for symmetric matrices (SQMR)</h3>
38 *
39 * The SQMR (symmetric quasi-minimal residual) method is supposed to solve
40 * symmetric indefinite linear systems with symmetric, not necessarily definite
41 * preconditioners. It is a variant of the original quasi-minimal residual
42 * method (QMR) and produces the same iterative solution. This version of SQMR
43 * is adapted from the respective symmetric QMR-from-BiCG algorithm given by
44 * both Freund/Nachtigal: A new Krylov-subspace method for symmetric indefinite
45 * linear systems, NASA STI/Recon Technical Report N, 95 (1994) and
46 * Freund/Nachtigal: Software for simplified Lanczos and QMR algorithms, Appl.
47 * Num. Math. 19 (1995), pp. 319-341 and provides both right and left (but not
48 * split) preconditioning.
49 *
50 *
51 * <h3>Trade off of stability to simplicity</h3>
52 *
53 * Note, that the QMR implementation that the given algorithm is based on is
54 * derived from classical BiCG. It can be shown (Freund/Szeto: A transpose-free
55 * quasi-minimal residual squared algorithm for non-Hermitian linear systems,
56 * Advances in Computer Methods for Partial Differential Equations VII
57 * (IMACS, New Brunswick, NJ, 1992) pp. 258-264) that the QMR iterates can
58 * be generated from the BiCG iteration through one additional vector and
59 * some scalar updates. Possible breakdowns (or precisely, divisions by
60 * zero) of BiCG therefore obviously transfer to this simple no-look-ahead
61 * algorithm.
62 *
63 * In return the algorithm is cheap compared to classical QMR or BiCGStab,
64 * using only one matrix-vector product with the system matrix and
65 * one application of the preconditioner per iteration respectively.
66 *
67 * The residual used for measuring convergence is only approximately calculated
68 * by an upper bound. If this value comes below a threshold prescribed within
69 * the AdditionalData struct, then the exact residual of the current QMR iterate
70 * will be calculated using another multiplication with the system matrix. By
71 * experience (according to Freund and Nachtigal) this technique is useful for a
72 * threshold that is ten times the solving tolerance, and in that case will be
73 * only used in the last one or two steps of the complete iteration.
74 *
75 * For the requirements on matrices and vectors in order to work with this
76 * class, see the documentation of the Solver base class.
77 *
78 * Like all other solver classes, this class has a local structure called @p
79 * AdditionalData which is used to pass additional parameters to the solver,
80 * like damping parameters or the number of temporary vectors. We use this
81 * additional structure instead of passing these values directly to the
82 * constructor because this makes the use of the @p SolverSelector and other
83 * classes much easier and guarantees that these will continue to work even if
84 * number or type of the additional parameters for a certain solver changes.
85 *
86 *
87 * <h3>Observing the progress of linear solver iterations</h3>
88 *
89 * The solve() function of this class uses the mechanism described in the
90 * Solver base class to determine convergence. This mechanism can also be used
91 * to observe the progress of the iteration.
92 */
93 template <typename VectorType = Vector<double>>
94 DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>)
95 class SolverQMRS : public SolverBase<VectorType>
96 {
97 public:
98 /**
99 * Standardized data struct to pipe additional data to the solver.
100 *
101 * The user is able to switch between right and left preconditioning, that
102 * means solving the systems <i>P<sup>-1</sup>A</i> and <i>AP<sup>-1</sup></i>
103 * respectively, using the corresponding parameter. Note that left
104 * preconditioning means to employ the preconditioned (BiCG-)residual and
105 * otherwise the unpreconditioned one. The default is the application from the
106 * right side.
107 *
108 * The @p solver_tolerance threshold is used to define the said bound below which the residual
109 * is computed exactly. See the class documentation for more information. The
110 * default value is 1e-9, that is the default solving precision multiplied by
111 * ten.
112 *
113 * SQMR is susceptible to breakdowns (divisions by zero), so we need a
114 * parameter telling us which numbers are considered zero. The proper
115 * breakdown criterion is very unclear, so experiments may be necessary here.
116 * It is even possible to achieve convergence despite of dividing through by
117 * small numbers. There are even cases in which it is advantageous to accept
118 * such divisions because the cheap iteration cost makes the algorithm the
119 * fastest of all available indefinite iterative solvers. Nonetheless, the
120 * default breakdown threshold value is 1e-16.
121 */
122 struct AdditionalData
123 {
124 /**
125 * Constructor.
126 *
127 * The default is right preconditioning, with the @p solver_tolerance chosen to be 1e-9 and
128 * the @p breakdown_threshold set at 1e-16.
129 */
130 explicit AdditionalData(const bool left_preconditioning = false,
131 const double solver_tolerance = 1.e-9,
132 const bool breakdown_testing = true,
133 const double breakdown_threshold = 1.e-16)
134 : left_preconditioning(left_preconditioning)
135 , solver_tolerance(solver_tolerance)
136 , breakdown_testing(breakdown_testing)
137 , breakdown_threshold(breakdown_threshold)
138 {}
139
140 /**
141 * Flag for using a left-preconditioned version.
142 */
143 bool left_preconditioning;
144
145 /**
146 * The threshold below which the current residual is computed exactly.
147 */
148 double solver_tolerance;
149
150 /**
151 * Flag for breakdown testing.
152 */
153 bool breakdown_testing;
154
155 /**
156 * Breakdown threshold. Scalars measured to this bound are used for
157 * divisions.
158 */
159 double breakdown_threshold;
160 };
161
162 /**
163 * Constructor.
164 */
165 SolverQMRS(SolverControl &cn,
166 VectorMemory<VectorType> &mem,
167 const AdditionalData &data = AdditionalData());
168
169 /**
170 * Constructor. Use an object of type GrowingVectorMemory as a default to
171 * allocate memory.
172 */
173 SolverQMRS(SolverControl &cn, const AdditionalData &data = AdditionalData());
174
175 /**
176 * Solve the linear system $Ax=b$ for x.
177 */
178 template <typename MatrixType, typename PreconditionerType>
179 DEAL_II_CXX20_REQUIRES(
180 (concepts::is_linear_operator_on<MatrixType, VectorType> &&
181 concepts::is_linear_operator_on<PreconditionerType, VectorType>))
182 void solve(const MatrixType &A,
183 VectorType &x,
184 const VectorType &b,
185 const PreconditionerType &preconditioner);
186
187 /**
188 * Interface for derived class. This function gets the current iteration
189 * vector, the residual and the update vector in each step. It can be used
190 * for a graphical output of the convergence history.
191 */
192 virtual void
193 print_vectors(const unsigned int step,
194 const VectorType &x,
195 const VectorType &r,
196 const VectorType &d) const;
197
198 protected:
199 /**
200 * Additional parameters.
201 */
202 AdditionalData additional_data;
203
204 private:
205 /**
206 * A structure returned by the iterate() function representing what it found
207 * is happening during the iteration.
208 */
209 struct IterationResult
210 {
211 SolverControl::State state;
212 double last_residual;
213
214 IterationResult(const SolverControl::State state,
215 const double last_residual);
216 };
217
218 /**
219 * The iteration loop itself. The function returns a structure indicating
220 * what happened in this function.
221 */
222 template <typename MatrixType, typename PreconditionerType>
223 IterationResult
224 iterate(const MatrixType &A,
225 VectorType &x,
226 const VectorType &b,
227 const PreconditionerType &preconditioner,
228 VectorType &r,
229 VectorType &u,
230 VectorType &q,
231 VectorType &t,
232 VectorType &d);
233
234 /**
235 * Number of the current iteration (accumulated over restarts)
236 */
237 unsigned int step;
238 };
239
240 /** @} */
241 /*------------------------- Implementation ----------------------------*/
242
243 #ifndef DOXYGEN
244
245
246 template <typename VectorType>
247 DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>)
248 SolverQMRS<VectorType>::IterationResult::IterationResult(
249 const SolverControl::State state,
250 const double last_residual)
251 : state(state)
252 , last_residual(last_residual)
253 {}
254
255
256
257 template <typename VectorType>
258 DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>)
259 SolverQMRS<VectorType>::SolverQMRS(SolverControl &cn,
260 VectorMemory<VectorType> &mem,
261 const AdditionalData &data)
262 : SolverBase<VectorType>(cn, mem)
263 , additional_data(data)
264 , step(0)
265 {}
266
267
268
269 template <typename VectorType>
270 DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>)
271 SolverQMRS<VectorType>::SolverQMRS(SolverControl &cn,
272 const AdditionalData &data)
273 : SolverBase<VectorType>(cn)
274 , additional_data(data)
275 , step(0)
276 {}
277
278
279
280 template <typename VectorType>
281 DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>)
282 void SolverQMRS<VectorType>::print_vectors(const unsigned int,
283 const VectorType &,
284 const VectorType &,
285 const VectorType &) const
286 {}
287
288
289
290 template <typename VectorType>
291 DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>)
292 template <typename MatrixType, typename PreconditionerType>
293 DEAL_II_CXX20_REQUIRES(
294 (concepts::is_linear_operator_on<MatrixType, VectorType> &&
295 concepts::is_linear_operator_on<PreconditionerType, VectorType>))
296 void SolverQMRS<VectorType>::solve(const MatrixType &A,
297 VectorType &x,
298 const VectorType &b,
299 const PreconditionerType &preconditioner)
300 {
301 LogStream::Prefix prefix("SQMR");
302
303
304 // temporary vectors, allocated through the @p VectorMemory object at the
305 // start of the actual solution process and deallocated at the end.
306 typename VectorMemory<VectorType>::Pointer Vr(this->memory);
307 typename VectorMemory<VectorType>::Pointer Vu(this->memory);
308 typename VectorMemory<VectorType>::Pointer Vq(this->memory);
309 typename VectorMemory<VectorType>::Pointer Vt(this->memory);
310 typename VectorMemory<VectorType>::Pointer Vd(this->memory);
311
312
313 // resize the vectors, but do not set
314 // the values since they'd be overwritten
315 // soon anyway.
316 Vr->reinit(x, true);
317 Vu->reinit(x, true);
318 Vq->reinit(x, true);
319 Vt->reinit(x, true);
320 Vd->reinit(x, true);
321
322 step = 0;
323
324 IterationResult state(SolverControl::failure, 0);
325
326 do
327 {
328 if (step > 0)
329 deallog << "Restart step " << step << std::endl;
330 state = iterate(A, x, b, preconditioner, *Vr, *Vu, *Vq, *Vt, *Vd);
331 }
332 while (state.state == SolverControl::iterate);
333
334
335 // in case of failure: throw exception
336 AssertThrow(state.state == SolverControl::success,
337 SolverControl::NoConvergence(step, state.last_residual));
338 // otherwise exit as normal
339 }
340
341
342
343 template <typename VectorType>
344 DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>)
345 template <typename MatrixType, typename PreconditionerType>
346 typename SolverQMRS<VectorType>::IterationResult
347 SolverQMRS<VectorType>::iterate(const MatrixType &A,
348 VectorType &x,
349 const VectorType &b,
350 const PreconditionerType &preconditioner,
351 VectorType &r,
352 VectorType &u,
353 VectorType &q,
354 VectorType &t,
355 VectorType &d)
356 {
357 SolverControl::State state = SolverControl::iterate;
358
359 int it = 0;
360
361 double tau, rho, theta = 0;
362 double res;
363
364 // Compute the start residual
365 A.vmult(r, x);
366 r.sadd(-1., 1., b);
367
368 // Doing the initial preconditioning
369 if (additional_data.left_preconditioning)
370 {
371 // Left preconditioning
372 preconditioner.vmult(t, r);
373 q = t;
374 }
375 else
376 {
377 // Right preconditioning
378 t = r;
379 preconditioner.vmult(q, t);
380 }
381
382 tau = t.norm_sqr();
383 res = std::sqrt(tau);
384
385 if (this->iteration_status(step, res, x) == SolverControl::success)
386 return IterationResult(SolverControl::success, res);
387
388 rho = q * r;
389
390 while (state == SolverControl::iterate)
391 {
392 ++step;
393 ++it;
394 //--------------------------------------------------------------
395 // Step 1: apply the system matrix and compute one inner product
396 //--------------------------------------------------------------
397 A.vmult(t, q);
398 const double sigma = q * t;
399
400 // Check the breakdown criterion
401 if (additional_data.breakdown_testing == true &&
402 std::fabs(sigma) < additional_data.breakdown_threshold)
403 return IterationResult(SolverControl::iterate, res);
404 // Update the residual
405 const double alpha = rho / sigma;
406 r.add(-alpha, t);
407
408 //--------------------------------------------------------------
409 // Step 2: update the solution vector
410 //--------------------------------------------------------------
411 const double theta_old = theta;
412
413 // Apply the preconditioner
414 if (additional_data.left_preconditioning)
415 {
416 // Left Preconditioning
417 preconditioner.vmult(t, r);
418 }
419 else
420 {
421 // Right Preconditioning
422 t = r;
423 }
424
425 // Double updates
426 theta = t * t / tau;
427 const double psi = 1. / (1. + theta);
428 tau *= theta * psi;
429
430 // Actual update of the solution vector
431 d.sadd(psi * theta_old, psi * alpha, q);
432 x += d;
433
434 print_vectors(step, x, r, d);
435
436 // Check for convergence
437 // Compute a simple and cheap upper bound of the norm of the residual
438 // vector b-Ax
439 res = std::sqrt((it + 1) * tau);
440 // If res lies close enough, within the desired tolerance, calculate the
441 // exact residual
442 if (res < additional_data.solver_tolerance)
443 {
444 A.vmult(u, x);
445 u.sadd(-1., 1., b);
446 res = u.l2_norm();
447 }
448 state = this->iteration_status(step, res, x);
449 if ((state == SolverControl::success) ||
450 (state == SolverControl::failure))
451 return IterationResult(state, res);
452
453 //--------------------------------------------------------------
454 // Step 3: check breakdown criterion and update the vectors
455 //--------------------------------------------------------------
456 if (additional_data.breakdown_testing == true &&
457 std::fabs(sigma) < additional_data.breakdown_threshold)
458 return IterationResult(SolverControl::iterate, res);
459
460 const double rho_old = rho;
461
462 // Applying the preconditioner
463 if (additional_data.left_preconditioning)
464 {
465 // Left preconditioning
466 u = t;
467 }
468 else
469 {
470 // Right preconditioning
471 preconditioner.vmult(u, t);
472 }
473
474 // Double and vector updates
475 rho = u * r;
476 const double beta = rho / rho_old;
477 q.sadd(beta, 1., u);
478 }
479 return IterationResult(SolverControl::success, res);
480 }
481
482 #endif // DOXYGEN
483
484 DEAL_II_NAMESPACE_CLOSE
485
486 #endif