1 // ---------------------------------------------------------------------
2 //
3 // Copyright (C) 1998 - 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_cg_h
17 #define dealii_solver_cg_h
18
19
20 #include <deal.II/base/config.h>
21
22 #include <deal.II/base/exceptions.h>
23 #include <deal.II/base/logstream.h>
24 #include <deal.II/base/subscriptor.h>
25
26 #include <deal.II/lac/solver.h>
27 #include <deal.II/lac/solver_control.h>
28 #include <deal.II/lac/tridiagonal_matrix.h>
29
30 #include <cmath>
31
32 DEAL_II_NAMESPACE_OPEN
33
34 // forward declaration
35 #ifndef DOXYGEN
36 class PreconditionIdentity;
37 #endif
38
39
40 /*!@addtogroup Solvers */
41 /*@{*/
42
43 /**
44 * This class implements the preconditioned Conjugate Gradients (CG)
45 * method that can be used to solve linear systems with a symmetric positive
46 * definite matrix. This
47 * class is used first in step-3 and step-4, but is used in many other
48 * tutorial programs as well. Like all other solver classes, it can work on
49 * any kind of vector and matrix as long as they satisfy certain requirements
50 * (for the requirements on matrices and vectors in order to work with this
51 * class, see the documentation of the Solver base class). The type of the
52 * solution vector must be passed as template argument, and defaults to
53 * dealii::Vector<double>.
54 *
55 * @note This version of CG is taken from D. Braess's book "Finite Elements".
56 * It requires a symmetric preconditioner (i.e., for example, SOR is not a
57 * possible choice).
58 *
59 *
60 * <h3>Eigenvalue computation</h3>
61 *
62 * The cg-method performs an orthogonal projection of the original
63 * preconditioned linear system to another system of smaller dimension.
64 * Furthermore, the projected matrix @p T is tri-diagonal. Since the
65 * projection is orthogonal, the eigenvalues of @p T approximate those of the
66 * original preconditioned matrix @p PA. In fact, after @p n steps, where @p n
67 * is the dimension of the original system, the eigenvalues of both matrices
68 * are equal. But, even for small numbers of iteration steps, the condition
69 * number of @p T is a good estimate for the one of @p PA.
70 *
71 * After @p m steps the matrix T_m can be written in terms of the coefficients
72 * @p alpha and @p beta as the tri-diagonal matrix with diagonal elements
73 * <tt>1/alpha_0</tt>, <tt>1/alpha_1 + beta_0/alpha_0</tt>, ...,
74 * <tt>1/alpha_{m-1</tt>+beta_{m-2}/alpha_{m-2}} and off-diagonal elements
75 * <tt>sqrt(beta_0)/alpha_0</tt>, ..., <tt>sqrt(beta_{m-2</tt>)/alpha_{m-2}}.
76 * The eigenvalues of this matrix can be computed by postprocessing.
77 *
78 * @see Y. Saad: "Iterative methods for Sparse Linear Systems", section 6.7.3
79 * for details.
80 *
81 * The coefficients, eigenvalues and condition number (computed as the ratio
82 * of the largest over smallest eigenvalue) can be obtained by connecting a
83 * function as a slot to the solver using one of the functions @p
84 * connect_coefficients_slot, @p connect_eigenvalues_slot and @p
85 * connect_condition_number_slot. These slots will then be called from the
86 * solver with the estimates as argument.
87 *
88 * <h3>Observing the progress of linear solver iterations</h3>
89 *
90 * The solve() function of this class uses the mechanism described in the
91 * Solver base class to determine convergence. This mechanism can also be used
92 * to observe the progress of the iteration.
93 */
94 template <typename VectorType = Vector<double>>
95 class SolverCG : public SolverBase<VectorType>
96 {
97 public:
98 /**
99 * Declare type for container size.
100 */
101 using size_type = types::global_dof_index;
102
103 /**
104 * Standardized data struct to pipe additional data to the solver.
105 * Here, it doesn't store anything but just exists for consistency
106 * with the other solver classes.
107 */
108 struct AdditionalData
109 {};
110
111 /**
112 * Constructor.
113 */
114 SolverCG(SolverControl & cn,
115 VectorMemory<VectorType> &mem,
116 const AdditionalData & data = AdditionalData());
117
118 /**
119 * Constructor. Use an object of type GrowingVectorMemory as a default to
120 * allocate memory.
121 */
122 SolverCG(SolverControl &cn, const AdditionalData &data = AdditionalData());
123
124 /**
125 * Virtual destructor.
126 */
127 virtual ~SolverCG() override = default;
128
129 /**
130 * Solve the linear system $Ax=b$ for x.
131 */
132 template <typename MatrixType, typename PreconditionerType>
133 void
134 solve(const MatrixType & A,
135 VectorType & x,
136 const VectorType & b,
137 const PreconditionerType &preconditioner);
138
139 /**
140 * Connect a slot to retrieve the CG coefficients. The slot will be called
141 * with alpha as the first argument and with beta as the second argument,
142 * where alpha and beta follow the notation in Y. Saad: "Iterative methods
143 * for Sparse Linear Systems", section 6.7. Called once per iteration
144 */
145 boost::signals2::connection
146 connect_coefficients_slot(
147 const std::function<void(typename VectorType::value_type,
148 typename VectorType::value_type)> &slot);
149
150 /**
151 * Connect a slot to retrieve the estimated condition number. Called on each
152 * iteration if every_iteration=true, otherwise called once when iterations
153 * are ended (i.e., either because convergence has been achieved, or because
154 * divergence has been detected).
155 */
156 boost::signals2::connection
157 connect_condition_number_slot(const std::function<void(double)> &slot,
158 const bool every_iteration = false);
159
160 /**
161 * Connect a slot to retrieve the estimated eigenvalues. Called on each
162 * iteration if every_iteration=true, otherwise called once when iterations
163 * are ended (i.e., either because convergence has been achieved, or because
164 * divergence has been detected).
165 */
166 boost::signals2::connection
167 connect_eigenvalues_slot(
168 const std::function<void(const std::vector<double> &)> &slot,
169 const bool every_iteration = false);
170
171 protected:
172 /**
173 * Interface for derived class. This function gets the current iteration
174 * vector, the residual and the update vector in each step. It can be used
175 * for graphical output of the convergence history.
176 */
177 virtual void
178 print_vectors(const unsigned int step,
179 const VectorType & x,
180 const VectorType & r,
181 const VectorType & d) const;
182
183 /**
184 * Estimates the eigenvalues from diagonal and offdiagonal. Uses these
185 * estimate to compute the condition number. Calls the signals
186 * eigenvalues_signal and cond_signal with these estimates as arguments.
187 */
188 static void
189 compute_eigs_and_cond(
190 const std::vector<typename VectorType::value_type> &diagonal,
191 const std::vector<typename VectorType::value_type> &offdiagonal,
192 const boost::signals2::signal<void(const std::vector<double> &)>
193 & eigenvalues_signal,
194 const boost::signals2::signal<void(double)> &cond_signal);
195
196 /**
197 * Additional parameters.
198 */
199 AdditionalData additional_data;
200
201 /**
202 * Signal used to retrieve the CG coefficients. Called on each iteration.
203 */
204 boost::signals2::signal<void(typename VectorType::value_type,
205 typename VectorType::value_type)>
206 coefficients_signal;
207
208 /**
209 * Signal used to retrieve the estimated condition number. Called once when
210 * all iterations are ended.
211 */
212 boost::signals2::signal<void(double)> condition_number_signal;
213
214 /**
215 * Signal used to retrieve the estimated condition numbers. Called on each
216 * iteration.
217 */
218 boost::signals2::signal<void(double)> all_condition_numbers_signal;
219
220 /**
221 * Signal used to retrieve the estimated eigenvalues. Called once when all
222 * iterations are ended.
223 */
224 boost::signals2::signal<void(const std::vector<double> &)> eigenvalues_signal;
225
226 /**
227 * Signal used to retrieve the estimated eigenvalues. Called on each
228 * iteration.
229 */
230 boost::signals2::signal<void(const std::vector<double> &)>
231 all_eigenvalues_signal;
232 };
233
234 /*@}*/
235
236 /*------------------------- Implementation ----------------------------*/
237
238 #ifndef DOXYGEN
239
240 template <typename VectorType>
SolverCG(SolverControl & cn,VectorMemory<VectorType> & mem,const AdditionalData & data)241 SolverCG<VectorType>::SolverCG(SolverControl & cn,
242 VectorMemory<VectorType> &mem,
243 const AdditionalData & data)
244 : SolverBase<VectorType>(cn, mem)
245 , additional_data(data)
246 {}
247
248
249
250 template <typename VectorType>
SolverCG(SolverControl & cn,const AdditionalData & data)251 SolverCG<VectorType>::SolverCG(SolverControl &cn, const AdditionalData &data)
252 : SolverBase<VectorType>(cn)
253 , additional_data(data)
254 {}
255
256
257
258 template <typename VectorType>
259 void
print_vectors(const unsigned int,const VectorType &,const VectorType &,const VectorType &)260 SolverCG<VectorType>::print_vectors(const unsigned int,
261 const VectorType &,
262 const VectorType &,
263 const VectorType &) const
264 {}
265
266
267
268 template <typename VectorType>
269 inline void
compute_eigs_and_cond(const std::vector<typename VectorType::value_type> & diagonal,const std::vector<typename VectorType::value_type> & offdiagonal,const boost::signals2::signal<void (const std::vector<double> &)> & eigenvalues_signal,const boost::signals2::signal<void (double)> & cond_signal)270 SolverCG<VectorType>::compute_eigs_and_cond(
271 const std::vector<typename VectorType::value_type> &diagonal,
272 const std::vector<typename VectorType::value_type> &offdiagonal,
273 const boost::signals2::signal<void(const std::vector<double> &)>
274 & eigenvalues_signal,
275 const boost::signals2::signal<void(double)> &cond_signal)
276 {
277 // Avoid computing eigenvalues unless they are needed.
278 if (!cond_signal.empty() || !eigenvalues_signal.empty())
279 {
280 TridiagonalMatrix<typename VectorType::value_type> T(diagonal.size(),
281 true);
282 for (size_type i = 0; i < diagonal.size(); ++i)
283 {
284 T(i, i) = diagonal[i];
285 if (i < diagonal.size() - 1)
286 T(i, i + 1) = offdiagonal[i];
287 }
288 T.compute_eigenvalues();
289 // Need two eigenvalues to estimate the condition number.
290 if (diagonal.size() > 1)
291 {
292 auto condition_number = T.eigenvalue(T.n() - 1) / T.eigenvalue(0);
293 // Condition number is real valued and nonnegative; simply take
294 // the absolute value:
295 cond_signal(std::abs(condition_number));
296 }
297 // Avoid copying the eigenvalues of T to a vector unless a signal is
298 // connected.
299 if (!eigenvalues_signal.empty())
300 {
301 std::vector<double> eigenvalues(T.n());
302 for (unsigned int j = 0; j < T.n(); ++j)
303 {
304 // for a hermitian matrix, all eigenvalues are real-valued
305 // and non-negative, simply return the absolute value:
306 eigenvalues[j] = std::abs(T.eigenvalue(j));
307 }
308 eigenvalues_signal(eigenvalues);
309 }
310 }
311 }
312
313
314
315 template <typename VectorType>
316 template <typename MatrixType, typename PreconditionerType>
317 void
solve(const MatrixType & A,VectorType & x,const VectorType & b,const PreconditionerType & preconditioner)318 SolverCG<VectorType>::solve(const MatrixType & A,
319 VectorType & x,
320 const VectorType & b,
321 const PreconditionerType &preconditioner)
322 {
323 using number = typename VectorType::value_type;
324
325 SolverControl::State conv = SolverControl::iterate;
326
327 LogStream::Prefix prefix("cg");
328
329 // Memory allocation
330 typename VectorMemory<VectorType>::Pointer g_pointer(this->memory);
331 typename VectorMemory<VectorType>::Pointer d_pointer(this->memory);
332 typename VectorMemory<VectorType>::Pointer h_pointer(this->memory);
333
334 // define some aliases for simpler access
335 VectorType &g = *g_pointer;
336 VectorType &d = *d_pointer;
337 VectorType &h = *h_pointer;
338
339 // Should we build the matrix for eigenvalue computations?
340 const bool do_eigenvalues =
341 !condition_number_signal.empty() || !all_condition_numbers_signal.empty() ||
342 !eigenvalues_signal.empty() || !all_eigenvalues_signal.empty();
343
344 // vectors used for eigenvalue
345 // computations
346 std::vector<typename VectorType::value_type> diagonal;
347 std::vector<typename VectorType::value_type> offdiagonal;
348
349 int it = 0;
350 double res = -std::numeric_limits<double>::max();
351
352 typename VectorType::value_type eigen_beta_alpha = 0;
353
354 // resize the vectors, but do not set
355 // the values since they'd be overwritten
356 // soon anyway.
357 g.reinit(x, true);
358 d.reinit(x, true);
359 h.reinit(x, true);
360
361 number gh, beta;
362
363 // compute residual. if vector is
364 // zero, then short-circuit the
365 // full computation
366 if (!x.all_zero())
367 {
368 A.vmult(g, x);
369 g.add(-1., b);
370 }
371 else
372 g.equ(-1., b);
373 res = g.l2_norm();
374
375 conv = this->iteration_status(0, res, x);
376 if (conv != SolverControl::iterate)
377 return;
378
379 if (std::is_same<PreconditionerType, PreconditionIdentity>::value == false)
380 {
381 preconditioner.vmult(h, g);
382
383 d.equ(-1., h);
384
385 gh = g * h;
386 }
387 else
388 {
389 d.equ(-1., g);
390 gh = res * res;
391 }
392
393 while (conv == SolverControl::iterate)
394 {
395 it++;
396 A.vmult(h, d);
397
398 number alpha = d * h;
399 Assert(std::abs(alpha) != 0., ExcDivideByZero());
400 alpha = gh / alpha;
401
402 x.add(alpha, d);
403 res = std::sqrt(std::abs(g.add_and_dot(alpha, h, g)));
404
405 print_vectors(it, x, g, d);
406
407 conv = this->iteration_status(it, res, x);
408 if (conv != SolverControl::iterate)
409 break;
410
411 if (std::is_same<PreconditionerType, PreconditionIdentity>::value ==
412 false)
413 {
414 preconditioner.vmult(h, g);
415
416 beta = gh;
417 Assert(std::abs(beta) != 0., ExcDivideByZero());
418 gh = g * h;
419 beta = gh / beta;
420 d.sadd(beta, -1., h);
421 }
422 else
423 {
424 beta = gh;
425 gh = res * res;
426 beta = gh / beta;
427 d.sadd(beta, -1., g);
428 }
429
430 this->coefficients_signal(alpha, beta);
431 // set up the vectors
432 // containing the diagonal
433 // and the off diagonal of
434 // the projected matrix.
435 if (do_eigenvalues)
436 {
437 diagonal.push_back(number(1.) / alpha + eigen_beta_alpha);
438 eigen_beta_alpha = beta / alpha;
439 offdiagonal.push_back(std::sqrt(beta) / alpha);
440 }
441 compute_eigs_and_cond(diagonal,
442 offdiagonal,
443 all_eigenvalues_signal,
444 all_condition_numbers_signal);
445 }
446
447 compute_eigs_and_cond(diagonal,
448 offdiagonal,
449 eigenvalues_signal,
450 condition_number_signal);
451
452 // in case of failure: throw exception
453 if (conv != SolverControl::success)
454 AssertThrow(false, SolverControl::NoConvergence(it, res));
455 // otherwise exit as normal
456 }
457
458
459
460 template <typename VectorType>
461 boost::signals2::connection
connect_coefficients_slot(const std::function<void (typename VectorType::value_type,typename VectorType::value_type)> & slot)462 SolverCG<VectorType>::connect_coefficients_slot(
463 const std::function<void(typename VectorType::value_type,
464 typename VectorType::value_type)> &slot)
465 {
466 return coefficients_signal.connect(slot);
467 }
468
469
470
471 template <typename VectorType>
472 boost::signals2::connection
connect_condition_number_slot(const std::function<void (double)> & slot,const bool every_iteration)473 SolverCG<VectorType>::connect_condition_number_slot(
474 const std::function<void(double)> &slot,
475 const bool every_iteration)
476 {
477 if (every_iteration)
478 {
479 return all_condition_numbers_signal.connect(slot);
480 }
481 else
482 {
483 return condition_number_signal.connect(slot);
484 }
485 }
486
487
488
489 template <typename VectorType>
490 boost::signals2::connection
connect_eigenvalues_slot(const std::function<void (const std::vector<double> &)> & slot,const bool every_iteration)491 SolverCG<VectorType>::connect_eigenvalues_slot(
492 const std::function<void(const std::vector<double> &)> &slot,
493 const bool every_iteration)
494 {
495 if (every_iteration)
496 {
497 return all_eigenvalues_signal.connect(slot);
498 }
499 else
500 {
501 return eigenvalues_signal.connect(slot);
502 }
503 }
504
505
506
507 #endif // DOXYGEN
508
509 DEAL_II_NAMESPACE_CLOSE
510
511 #endif
512