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