Debian Codegraph @

include/deal.II/lac/precondition.h

raw
1 // ------------------------------------------------------------------------
2 //
3 // SPDX-License-Identifier: LGPL-2.1-or-later
4 // Copyright (C) 1999 - 2025 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_precondition_h
16 #define dealii_precondition_h
17
18 #include <deal.II/base/config.h>
19
20 #include <deal.II/base/memory_space.h>
21 #include <deal.II/base/mutex.h>
22 #include <deal.II/base/observer_pointer.h>
23 #include <deal.II/base/parallel.h>
24 #include <deal.II/base/template_constraints.h>
25
26 #include <deal.II/lac/affine_constraints.h>
27 #include <deal.II/lac/block_vector_base.h>
28 #include <deal.II/lac/diagonal_matrix.h>
29 #include <deal.II/lac/identity_matrix.h>
30 #include <deal.II/lac/solver_cg.h>
31 #include <deal.II/lac/vector_memory.h>
32
33 #include <Kokkos_Core.hpp>
34
35 #include <limits>
36
37 DEAL_II_NAMESPACE_OPEN
38
39 // forward declarations
40 #ifndef DOXYGEN
41 template <typename number>
42 class Vector;
43 template <typename number>
44 class SparseMatrix;
45 namespace LinearAlgebra
46 {
47 namespace distributed
48 {
49 template <typename, typename>
50 class Vector;
51 template <typename, typename>
52 class BlockVector;
53 } // namespace distributed
54 } // namespace LinearAlgebra
55 #endif
56
57
58 /**
59 * @addtogroup Preconditioners
60 * @{
61 */
62
63 namespace internal
64 {
65 /**
66 * An enum to define the available types of eigenvalue estimation
67 * algorithms.
68 */
69 enum class EigenvalueAlgorithm
70 {
71 /**
72 * This option runs the conjugate gradient solver and computes an
73 * eigenvalue estimation from the underlying Lanczos space. This only
74 * works for symmetric positive definite matrices.
75 */
76 lanczos,
77 /**
78 * This option runs a power iteration to estimate the largest
79 * eigenvalue. This algorithm also works for non-symmetric matrices,
80 * but typically gives less accurate estimates than the option 'lanczos'
81 * for the same number of iterations because it does not take the
82 * relation between vectors in the iterations into account
83 * (roughly speaking the off-diagonal entries in the
84 * tri-diagonal matrix of the Lanczos iteration).
85 */
86 power_iteration
87 };
88
89 /**
90 * A struct that contains information about the eigenvalue estimation
91 * performed by the PreconditionChebyshev class.
92 */
93 struct EigenvalueInformation
94 {
95 /**
96 * Estimate for the smallest eigenvalue.
97 */
98 double min_eigenvalue_estimate;
99 /**
100 * Estimate for the largest eigenvalue.
101 */
102 double max_eigenvalue_estimate;
103 /**
104 * Number of CG iterations performed or 0.
105 */
106 unsigned int cg_iterations;
107 /**
108 * The degree of the Chebyshev polynomial (either as set using
109 * AdditionalData::degree or estimated as described there).
110 */
111 unsigned int degree;
112 /**
113 * Constructor initializing with invalid values.
114 */
115 EigenvalueInformation()
116 : min_eigenvalue_estimate{std::numeric_limits<double>::max()}
117 , max_eigenvalue_estimate{std::numeric_limits<double>::lowest()}
118 , cg_iterations{0}
119 , degree{0}
120 {}
121 };
122
123 /**
124 * Base class for PreconditionRelaxation::AdditionalData and
125 * PreconditionChebyshev::AdditionalData with relevant information
126 * for estimating the eigenvalues.
127 */
128 template <typename PreconditionerType>
129 struct EigenvalueAlgorithmAdditionalData
130 {
131 /**
132 * Constructor.
133 */
134 EigenvalueAlgorithmAdditionalData(
135 const double smoothing_range,
136 const unsigned int eig_cg_n_iterations,
137 const double eig_cg_residual,
138 const double max_eigenvalue,
139 const EigenvalueAlgorithm eigenvalue_algorithm);
140
141 /**
142 * Copy assignment operator.
143 */
144 EigenvalueAlgorithmAdditionalData<PreconditionerType> &
145 operator=(
146 const EigenvalueAlgorithmAdditionalData<PreconditionerType> &other_data);
147
148 /**
149 * This sets the range between the largest eigenvalue in the matrix and
150 * the smallest eigenvalue to be treated. If the parameter is set to a
151 * number less than 1, an estimate for the largest and for the smallest
152 * eigenvalue will be calculated internally. For a smoothing range larger
153 * than one, the preconditioner will act in the interval
154 * $[\lambda_\mathrm{max}/ \tt{smoothing\_range}, \lambda_\mathrm{max}]$,
155 * where $\lambda_\mathrm{max}$ is an estimate of the maximum eigenvalue
156 * of the matrix. A choice of <tt>smoothing_range</tt> between 5 and 20 is
157 * useful in case the preconditioner is used as a smoother in multigrid.
158 */
159 double smoothing_range;
160
161 /**
162 * Maximum number of CG iterations performed for finding the maximum
163 * eigenvalue. If set to zero, no computations are performed. Instead, the
164 * user must supply a largest eigenvalue via the variable
165 * PreconditionRelaxation::AdditionalData::max_eigenvalue.
166 */
167 unsigned int eig_cg_n_iterations;
168
169 /**
170 * Tolerance for iterations performed for finding the maximum
171 * eigenvalue by the eigenvalue algorithm (Lanczos or power iteration).
172 */
173 double eig_cg_residual;
174
175 /**
176 * Maximum eigenvalue to work with. Only in effect if @p
177 * eig_cg_n_iterations is set to zero, otherwise this parameter is
178 * ignored.
179 */
180 double max_eigenvalue;
181
182 /**
183 * Constraints to be used for the operator given. This variable is used to
184 * zero out the correct entries when creating an initial guess.
185 */
186 dealii::AffineConstraints<double> constraints;
187
188 /**
189 * Stores the preconditioner object that the Chebyshev is wrapped around.
190 */
191 EigenvalueAlgorithm eigenvalue_algorithm;
192
193 /**
194 * Preconditioner.
195 */
196 std::shared_ptr<PreconditionerType> preconditioner;
197 };
198 } // namespace internal
199
200
201 /**
202 * This preconditioner implements the identity operator.
203 * This class can be used you if you want to use a linear
204 * solver without preconditioning, because all linear solvers
205 * require the usage of a preconditioner.
206 *
207 * It can be used in the following way:
208 *
209 * @code
210 * SolverControl solver_control (1000, 1e-12);
211 * SolverCG<> cg (solver_control);
212 * cg.solve (system_matrix, solution, system_rhs, PreconditionIdentity());
213 * @endcode
214 *
215 * See the step-3 tutorial program for an example and additional explanations.
216 *
217 * Alternatively, the IdentityMatrix class can be used to precondition in this
218 * way.
219 */
220 class PreconditionIdentity : public EnableObserverPointer
221 {
222 public:
223 /**
224 * Declare type for container size.
225 */
226 using size_type = types::global_dof_index;
227
228 /**
229 * This function is only present to provide the interface of a
230 * preconditioner to be handed to a smoother. This does nothing.
231 */
232 struct AdditionalData
233 {
234 /**
235 * Constructor.
236 */
237 AdditionalData() = default;
238 };
239
240 /**
241 * Constructor, sets the domain and range sizes to their defaults.
242 */
243 PreconditionIdentity();
244
245 /**
246 * The matrix argument is ignored and here just for compatibility with more
247 * complex preconditioners.
248 */
249 template <typename MatrixType>
250 void
251 initialize(const MatrixType &matrix,
252 const AdditionalData &additional_data = AdditionalData());
253
254 /**
255 * Apply preconditioner.
256 */
257 template <typename VectorType>
258 void
259 vmult(VectorType &, const VectorType &) const;
260
261 /**
262 * Apply transpose preconditioner. Since this is the identity, this function
263 * is the same as vmult().
264 */
265 template <typename VectorType>
266 void
267 Tvmult(VectorType &, const VectorType &) const;
268
269 /**
270 * Apply preconditioner, adding to the previous value.
271 */
272 template <typename VectorType>
273 void
274 vmult_add(VectorType &, const VectorType &) const;
275
276 /**
277 * Apply transpose preconditioner, adding. Since this is the identity, this
278 * function is the same as vmult_add().
279 */
280 template <typename VectorType>
281 void
282 Tvmult_add(VectorType &, const VectorType &) const;
283
284 /**
285 * This function is only present to provide the interface of a
286 * preconditioner to be handed to a smoother. This does nothing.
287 */
288 void
289 clear();
290
291 /**
292 * Return the dimension of the codomain (or range) space. Note that the
293 * matrix is of dimension $m \times n$.
294 *
295 * @note This function should only be called if the preconditioner has been
296 * initialized.
297 */
298 size_type
299 m() const;
300
301 /**
302 * Return the dimension of the domain space. Note that the matrix is of
303 * dimension $m \times n$.
304 *
305 * @note This function should only be called if the preconditioner has been
306 * initialized.
307 */
308 size_type
309 n() const;
310
311 private:
312 /**
313 * The dimension of the range space.
314 */
315 size_type n_rows;
316
317 /**
318 * The dimension of the domain space.
319 */
320 size_type n_columns;
321 };
322
323
324
325 /**
326 * Preconditioning with Richardson's method. This preconditioner just scales
327 * the vector with a constant relaxation factor provided by the AdditionalData
328 * object.
329 *
330 * In Krylov-space methods, this preconditioner should not have any effect.
331 * Using SolverRichardson, the two relaxation parameters will be just
332 * multiplied. Still, this class is useful in multigrid smoother objects
333 * (MGSmootherRelaxation).
334 */
335 class PreconditionRichardson : public EnableObserverPointer
336 {
337 public:
338 /**
339 * Declare type for container size.
340 */
341 using size_type = types::global_dof_index;
342
343 /**
344 * Parameters for Richardson preconditioner.
345 */
346 class AdditionalData
347 {
348 public:
349 /**
350 * Constructor. Block size must be given since there is no reasonable
351 * default parameter.
352 */
353 AdditionalData(const double relaxation = 1.);
354
355 /**
356 * Relaxation parameter.
357 */
358 double relaxation;
359 };
360
361 /**
362 * Constructor, sets the relaxation parameter, domain and range sizes to
363 * their default.
364 */
365 PreconditionRichardson();
366
367 /**
368 * Change the relaxation parameter.
369 */
370 void
371 initialize(const AdditionalData &parameters);
372
373 /**
374 * Change the relaxation parameter in a way consistent with other
375 * preconditioners. The matrix argument is ignored and here just for
376 * compatibility with more complex preconditioners.
377 */
378 template <typename MatrixType>
379 void
380 initialize(const MatrixType &matrix, const AdditionalData &parameters);
381
382 /**
383 * Apply preconditioner.
384 */
385 template <typename VectorType>
386 void
387 vmult(VectorType &, const VectorType &) const;
388
389 /**
390 * Apply transpose preconditioner. Since this is the identity, this function
391 * is the same as vmult().
392 */
393 template <typename VectorType>
394 void
395 Tvmult(VectorType &, const VectorType &) const;
396 /**
397 * Apply preconditioner, adding to the previous value.
398 */
399 template <typename VectorType>
400 void
401 vmult_add(VectorType &, const VectorType &) const;
402
403 /**
404 * Apply transpose preconditioner, adding. Since this is the identity, this
405 * function is the same as vmult_add().
406 */
407 template <typename VectorType>
408 void
409 Tvmult_add(VectorType &, const VectorType &) const;
410
411 /**
412 * This function is only present to provide the interface of a
413 * preconditioner to be handed to a smoother. This does nothing.
414 */
415 void
416 clear()
417 {}
418
419 /**
420 * Return the dimension of the codomain (or range) space. Note that the
421 * matrix is of dimension $m \times n$.
422 *
423 * @note This function should only be called if the preconditioner has been
424 * initialized.
425 */
426 size_type
427 m() const;
428
429 /**
430 * Return the dimension of the domain space. Note that the matrix is of
431 * dimension $m \times n$.
432 *
433 * @note This function should only be called if the preconditioner has been
434 * initialized.
435 */
436 size_type
437 n() const;
438
439 private:
440 /**
441 * The relaxation parameter multiplied with the vectors.
442 */
443 double relaxation;
444
445 /**
446 * The dimension of the range space.
447 */
448 size_type n_rows;
449
450 /**
451 * The dimension of the domain space.
452 */
453 size_type n_columns;
454 };
455
456
457
458 /**
459 * Preconditioner using a matrix-builtin function. This class forms a
460 * preconditioner suitable for the LAC solver classes. Since many
461 * preconditioning methods are based on matrix entries, these have to be
462 * implemented as member functions of the underlying matrix implementation.
463 * This class now is intended to allow easy access to these member functions
464 * from LAC solver classes.
465 *
466 * It seems that all builtin preconditioners have a relaxation parameter, so
467 * please use PreconditionRelaxation for these.
468 *
469 * You will usually not want to create a named object of this type, although
470 * possible. The most common use is like this:
471 * @code
472 * SolverGMRES<SparseMatrix<double> Vector<double>> gmres(control,memory,500);
473 *
474 * gmres.solve(
475 * matrix, solution, right_hand_side,
476 * PreconditionUseMatrix<SparseMatrix<double>,Vector<double> >(
477 * matrix, &SparseMatrix<double>::template precondition_Jacobi<double>));
478 * @endcode
479 * This creates an unnamed object to be passed as the fourth parameter to the
480 * solver function of the SolverGMRES class. It assumes that the SparseMatrix
481 * class has a function <tt>precondition_Jacobi</tt> taking two vectors
482 * (source and destination) as parameters (Actually, there is no function like
483 * that, the existing function takes a third parameter, denoting the
484 * relaxation parameter; this example is therefore only meant to illustrate
485 * the general idea).
486 *
487 * Note that due to the default template parameters, the above example could
488 * be written shorter as follows:
489 * @code
490 * ...
491 * gmres.solve(
492 * matrix, solution, right_hand_side,
493 * PreconditionUseMatrix<>(
494 * matrix,&SparseMatrix<double>::template precondition_Jacobi<double>));
495 * @endcode
496 */
497 template <typename MatrixType = SparseMatrix<double>,
498 typename VectorType = Vector<double>>
499 class PreconditionUseMatrix : public EnableObserverPointer
500 {
501 public:
502 /**
503 * Type of the preconditioning function of the matrix.
504 */
505 using function_ptr = void (MatrixType::*)(VectorType &,
506 const VectorType &) const;
507
508 /**
509 * Constructor. This constructor stores a reference to the matrix object
510 * for later use and selects a preconditioning method, which must be a
511 * member function of that matrix.
512 */
513 PreconditionUseMatrix(const MatrixType &M, const function_ptr method);
514
515 /**
516 * Execute preconditioning. Calls the function passed to the constructor of
517 * this object with the two arguments given here.
518 */
519 void
520 vmult(VectorType &dst, const VectorType &src) const;
521
522 private:
523 /**
524 * Pointer to the matrix in use.
525 */
526 const MatrixType &matrix;
527
528 /**
529 * Pointer to the preconditioning function.
530 */
531 const function_ptr precondition;
532 };
533
534
535
536 /**
537 * Base class for other preconditioners. Here, only some common features
538 * Jacobi, SOR and SSOR preconditioners are implemented. For preconditioning,
539 * refer to derived classes.
540 *
541 * One iteration is given as:
542 * @f[
543 * x^{n+1} = x^{n} + \alpha P^{-1} (b-Ax^n).
544 * @f]
545 *
546 * The relaxation parameter $\alpha$ has to be in the range:
547 * @f[
548 * 0 < \alpha < \frac{2}{\lambda_{\max}(P^{-1}A)}.
549 * @f]
550 * Its theoretically optimal value is given by:
551 * @f[
552 * \alpha := \frac{2}{\lambda_{\min}(P^{-1}A)+\lambda_{\max}(P^{-1}A)}.
553 * @f]
554 *
555 * For details on the algorithm, see @cite Varga2009.
556 *
557 * The relaxation parameter can be set manually or can be automatically
558 * determined, for which we use the theoretically optimal value.
559 * For this purpose, the user needs to set the relaxation parameter
560 * to zero. Internally, the minimum and maximum eigenvalues of the
561 * preconditioned system are estimated by an eigenvalue algorithm, and the
562 * resulting estimate is multiplied by the 1.2 for safety reasons. For more
563 * details on the underlying algorithms, see PreconditionChebyshev.
564 */
565 template <typename MatrixType = SparseMatrix<double>,
566 typename PreconditionerType = IdentityMatrix>
567 class PreconditionRelaxation : public EnableObserverPointer
568 {
569 public:
570 /**
571 * Declare type for container size.
572 */
573 using size_type = types::global_dof_index;
574
575 /**
576 * Class for parameters.
577 */
578 class AdditionalData
579 : public internal::EigenvalueAlgorithmAdditionalData<PreconditionerType>
580 {
581 public:
582 using EigenvalueAlgorithm = internal::EigenvalueAlgorithm;
583
584 /**
585 * Constructor.
586 */
587 AdditionalData(const double relaxation = 1.,
588 const unsigned int n_iterations = 1,
589 const double smoothing_range = 0.,
590 const unsigned int eig_cg_n_iterations = 8,
591 const double eig_cg_residual = 1e-2,
592 const double max_eigenvalue = 1,
593 const EigenvalueAlgorithm eigenvalue_algorithm =
594 EigenvalueAlgorithm::lanczos);
595
596 /**
597 * Relaxation parameter.
598 */
599 double relaxation;
600
601 /**
602 * Number of smoothing steps to be performed in an
603 * invocation of vmult() or step().
604 */
605 unsigned int n_iterations;
606 };
607
608 /**
609 * Initialize matrix and relaxation parameter. The matrix is just stored in
610 * the preconditioner object. The relaxation parameter should be larger than
611 * zero and smaller than 2 for numerical reasons. It defaults to 1.
612 */
613 void
614 initialize(const MatrixType &A,
615 const AdditionalData &parameters = AdditionalData());
616
617 /**
618 * Release the matrix and reset its pointer.
619 */
620 void
621 clear();
622
623 /**
624 * Return the dimension of the codomain (or range) space. Note that the
625 * matrix is of dimension $m \times n$.
626 */
627 size_type
628 m() const;
629
630 /**
631 * Return the dimension of the domain space. Note that the matrix is of
632 * dimension $m \times n$.
633 */
634 size_type
635 n() const;
636
637 /**
638 * Apply preconditioner.
639 */
640 template <typename VectorType>
641 void
642 vmult(VectorType &, const VectorType &) const;
643
644 /**
645 * Apply transpose preconditioner. Since this is a symmetric preconditioner,
646 * this function is the same as vmult().
647 */
648 template <typename VectorType>
649 void
650 Tvmult(VectorType &, const VectorType &) const;
651
652 /**
653 * Perform one step of the preconditioned Richardson iteration
654 */
655 template <typename VectorType>
656 void
657 step(VectorType &x, const VectorType &rhs) const;
658
659 /**
660 * Perform one transposed step of the preconditioned Richardson iteration.
661 */
662 template <typename VectorType>
663 void
664 Tstep(VectorType &x, const VectorType &rhs) const;
665
666 using EigenvalueInformation = internal::EigenvalueInformation;
667
668 /**
669 * Estimate eigenvalues and set relaxation parameter.
670 */
671 template <typename VectorType>
672 EigenvalueInformation
673 estimate_eigenvalues(const VectorType &src) const;
674
675 /**
676 * Return the relaxation parameter. This function also allows to return
677 * the parameter in case it was internally determined by running an eigenvalue
678 * algorithm.
679 */
680 double
681 get_relaxation() const;
682
683 protected:
684 /**
685 * Pointer to the matrix object.
686 */
687 ObserverPointer<const MatrixType, PreconditionRelaxation<MatrixType>> A;
688
689 /**
690 * Stores the additional data passed to the initialize function, obtained
691 * through a copy operation.
692 */
693 AdditionalData data;
694
695 /**
696 * Preconditioner.
697 */
698 std::shared_ptr<PreconditionerType> preconditioner;
699
700 /**
701 * Stores whether the preconditioner has been set up and eigenvalues have
702 * been computed.
703 */
704 bool eigenvalues_are_initialized;
705 };
706
707
708
709 #ifndef DOXYGEN
710
711 namespace internal
712 {
713 // a helper type-trait that leverage SFINAE to figure out if MatrixType has
714 // ... MatrixType::vmult(VectorType &, const VectorType&,
715 // std::function<...>, std::function<...>) const
716 template <typename MatrixType, typename VectorType>
717 using vmult_functions_t = decltype(std::declval<const MatrixType>().vmult(
718 std::declval<VectorType &>(),
719 std::declval<const VectorType &>(),
720 std::declval<
721 const std::function<void(const unsigned int, const unsigned int)> &>(),
722 std::declval<
723 const std::function<void(const unsigned int, const unsigned int)> &>()));
724
725 template <typename MatrixType,
726 typename VectorType,
727 typename PreconditionerType>
728 constexpr bool has_vmult_with_std_functions =
729 is_supported_operation<vmult_functions_t, MatrixType, VectorType> &&
730 std::is_same_v<PreconditionerType, dealii::DiagonalMatrix<VectorType>> &&
731 (std::is_same_v<VectorType,
732 dealii::Vector<typename VectorType::value_type>> ||
733 std::is_same_v<
734 VectorType,
735 LinearAlgebra::distributed::Vector<typename VectorType::value_type,
736 MemorySpace::Host>>);
737
738
739 template <typename MatrixType, typename VectorType>
740 constexpr bool has_vmult_with_std_functions_for_precondition =
741 is_supported_operation<vmult_functions_t, MatrixType, VectorType>;
742
743 namespace PreconditionRelaxation
744 {
745 template <typename T, typename VectorType>
746 using Tvmult_t = decltype(std::declval<const T>().Tvmult(
747 std::declval<VectorType &>(),
748 std::declval<const VectorType &>()));
749
750 template <typename T, typename VectorType>
751 constexpr bool has_Tvmult = is_supported_operation<Tvmult_t, T, VectorType>;
752
753 template <typename T, typename VectorType>
754 using step_t = decltype(std::declval<const T>().step(
755 std::declval<VectorType &>(),
756 std::declval<const VectorType &>()));
757
758 template <typename T, typename VectorType>
759 constexpr bool has_step = is_supported_operation<step_t, T, VectorType>;
760
761 template <typename T, typename VectorType>
762 using step_omega_t =
763 decltype(std::declval<const T>().step(std::declval<VectorType &>(),
764 std::declval<const VectorType &>(),
765 std::declval<const double>()));
766
767 template <typename T, typename VectorType>
768 constexpr bool has_step_omega =
769 is_supported_operation<step_omega_t, T, VectorType>;
770
771 template <typename T, typename VectorType>
772 using Tstep_t = decltype(std::declval<const T>().Tstep(
773 std::declval<VectorType &>(),
774 std::declval<const VectorType &>()));
775
776 template <typename T, typename VectorType>
777 constexpr bool has_Tstep = is_supported_operation<Tstep_t, T, VectorType>;
778
779 template <typename T, typename VectorType>
780 using Tstep_omega_t =
781 decltype(std::declval<const T>().Tstep(std::declval<VectorType &>(),
782 std::declval<const VectorType &>(),
783 std::declval<const double>()));
784
785 template <typename T, typename VectorType>
786 constexpr bool has_Tstep_omega =
787 is_supported_operation<Tstep_omega_t, T, VectorType>;
788
789 template <typename T, typename VectorType>
790 using jacobi_step_t = decltype(std::declval<const T>().Jacobi_step(
791 std::declval<VectorType &>(),
792 std::declval<const VectorType &>(),
793 std::declval<const double>()));
794
795 template <typename T, typename VectorType>
796 constexpr bool has_jacobi_step =
797 is_supported_operation<jacobi_step_t, T, VectorType>;
798
799 template <typename T, typename VectorType>
800 using SOR_step_t = decltype(std::declval<const T>().SOR_step(
801 std::declval<VectorType &>(),
802 std::declval<const VectorType &>(),
803 std::declval<const double>()));
804
805 template <typename T, typename VectorType>
806 constexpr bool has_SOR_step =
807 is_supported_operation<SOR_step_t, T, VectorType>;
808
809 template <typename T, typename VectorType>
810 using SSOR_step_t = decltype(std::declval<const T>().SSOR_step(
811 std::declval<VectorType &>(),
812 std::declval<const VectorType &>(),
813 std::declval<const double>()));
814
815 template <typename T, typename VectorType>
816 constexpr bool has_SSOR_step =
817 is_supported_operation<SSOR_step_t, T, VectorType>;
818
819 template <typename MatrixType>
820 class PreconditionJacobiImpl
821 {
822 public:
823 PreconditionJacobiImpl(const MatrixType &A, const double relaxation)
824 : A(&A)
825 , relaxation(relaxation)
826 {}
827
828 template <typename VectorType>
829 void
830 vmult(VectorType &dst, const VectorType &src) const
831 {
832 this->A->precondition_Jacobi(dst, src, this->relaxation);
833 }
834
835 template <typename VectorType>
836 void
837 Tvmult(VectorType &dst, const VectorType &src) const
838 {
839 // call vmult, since preconditioner is symmetrical
840 this->vmult(dst, src);
841 }
842
843 template <typename VectorType,
844 std::enable_if_t<has_jacobi_step<MatrixType, VectorType>,
845 MatrixType> * = nullptr>
846 void
847 step(VectorType &dst, const VectorType &src) const
848 {
849 this->A->Jacobi_step(dst, src, this->relaxation);
850 }
851
852 template <typename VectorType,
853 std::enable_if_t<!has_jacobi_step<MatrixType, VectorType>,
854 MatrixType> * = nullptr>
855 void
856 step(VectorType &, const VectorType &) const
857 {
858 AssertThrow(false,
859 ExcMessage(
860 "Matrix A does not provide a Jacobi_step() function!"));
861 }
862
863 template <typename VectorType>
864 void
865 Tstep(VectorType &dst, const VectorType &src) const
866 {
867 // call step, since preconditioner is symmetrical
868 this->step(dst, src);
869 }
870
871 private:
872 const ObserverPointer<const MatrixType> A;
873 const double relaxation;
874 };
875
876 template <typename MatrixType>
877 class PreconditionSORImpl
878 {
879 public:
880 PreconditionSORImpl(const MatrixType &A, const double relaxation)
881 : A(&A)
882 , relaxation(relaxation)
883 {}
884
885 template <typename VectorType>
886 void
887 vmult(VectorType &dst, const VectorType &src) const
888 {
889 this->A->precondition_SOR(dst, src, this->relaxation);
890 }
891
892 template <typename VectorType>
893 void
894 Tvmult(VectorType &dst, const VectorType &src) const
895 {
896 this->A->precondition_TSOR(dst, src, this->relaxation);
897 }
898
899 template <typename VectorType,
900 std::enable_if_t<has_SOR_step<MatrixType, VectorType>,
901 MatrixType> * = nullptr>
902 void
903 step(VectorType &dst, const VectorType &src) const
904 {
905 this->A->SOR_step(dst, src, this->relaxation);
906 }
907
908 template <typename VectorType,
909 std::enable_if_t<!has_SOR_step<MatrixType, VectorType>,
910 MatrixType> * = nullptr>
911 void
912 step(VectorType &, const VectorType &) const
913 {
914 AssertThrow(false,
915 ExcMessage(
916 "Matrix A does not provide a SOR_step() function!"));
917 }
918
919 template <typename VectorType,
920 std::enable_if_t<has_SOR_step<MatrixType, VectorType>,
921 MatrixType> * = nullptr>
922 void
923 Tstep(VectorType &dst, const VectorType &src) const
924 {
925 this->A->TSOR_step(dst, src, this->relaxation);
926 }
927
928 template <typename VectorType,
929 std::enable_if_t<!has_SOR_step<MatrixType, VectorType>,
930 MatrixType> * = nullptr>
931 void
932 Tstep(VectorType &, const VectorType &) const
933 {
934 AssertThrow(false,
935 ExcMessage(
936 "Matrix A does not provide a TSOR_step() function!"));
937 }
938
939 private:
940 const ObserverPointer<const MatrixType> A;
941 const double relaxation;
942 };
943
944 template <typename MatrixType>
945 class PreconditionSSORImpl
946 {
947 public:
948 using size_type = typename MatrixType::size_type;
949
950 PreconditionSSORImpl(const MatrixType &A, const double relaxation)
951 : A(&A)
952 , relaxation(relaxation)
953 {
954 // in case we have a SparseMatrix class, we can extract information
955 // about the diagonal.
956 const SparseMatrix<typename MatrixType::value_type> *mat =
957 dynamic_cast<const SparseMatrix<typename MatrixType::value_type> *>(
958 &*this->A);
959
960 // calculate the positions first after the diagonal.
961 if (mat != nullptr)
962 {
963 const size_type n = this->A->n();
964 pos_right_of_diagonal.resize(n, static_cast<std::size_t>(-1));
965 for (size_type row = 0; row < n; ++row)
966 {
967 // find the first element in this line which is on the right of
968 // the diagonal. we need to precondition with the elements on
969 // the left only. note: the first entry in each line denotes the
970 // diagonal element, which we need not check.
971 typename SparseMatrix<
972 typename MatrixType::value_type>::const_iterator it =
973 mat->begin(row) + 1;
974 for (; it < mat->end(row); ++it)
975 if (it->column() > row)
976 break;
977 pos_right_of_diagonal[row] = it - mat->begin();
978 }
979 }
980 }
981
982 template <typename VectorType>
983 void
984 vmult(VectorType &dst, const VectorType &src) const
985 {
986 this->A->precondition_SSOR(dst,
987 src,
988 this->relaxation,
989 pos_right_of_diagonal);
990 }
991
992 template <typename VectorType>
993 void
994 Tvmult(VectorType &dst, const VectorType &src) const
995 {
996 this->A->precondition_SSOR(dst,
997 src,
998 this->relaxation,
999 pos_right_of_diagonal);
1000 }
1001
1002 template <typename VectorType,
1003 std::enable_if_t<has_SSOR_step<MatrixType, VectorType>,
1004 MatrixType> * = nullptr>
1005 void
1006 step(VectorType &dst, const VectorType &src) const
1007 {
1008 this->A->SSOR_step(dst, src, this->relaxation);
1009 }
1010
1011 template <typename VectorType,
1012 std::enable_if_t<!has_SSOR_step<MatrixType, VectorType>,
1013 MatrixType> * = nullptr>
1014 void
1015 step(VectorType &, const VectorType &) const
1016 {
1017 AssertThrow(false,
1018 ExcMessage(
1019 "Matrix A does not provide a SSOR_step() function!"));
1020 }
1021
1022 template <typename VectorType>
1023 void
1024 Tstep(VectorType &dst, const VectorType &src) const
1025 {
1026 // call step, since preconditioner is symmetrical
1027 this->step(dst, src);
1028 }
1029
1030 private:
1031 const ObserverPointer<const MatrixType> A;
1032 const double relaxation;
1033
1034 /**
1035 * An array that stores for each matrix row where the first position after
1036 * the diagonal is located.
1037 */
1038 std::vector<std::size_t> pos_right_of_diagonal;
1039 };
1040
1041 template <typename MatrixType>
1042 class PreconditionPSORImpl
1043 {
1044 public:
1045 using size_type = typename MatrixType::size_type;
1046
1047 PreconditionPSORImpl(const MatrixType &A,
1048 const double relaxation,
1049 const std::vector<size_type> &permutation,
1050 const std::vector<size_type> &inverse_permutation)
1051 : A(&A)
1052 , relaxation(relaxation)
1053 , permutation(permutation)
1054 , inverse_permutation(inverse_permutation)
1055 {}
1056
1057 template <typename VectorType>
1058 void
1059 vmult(VectorType &dst, const VectorType &src) const
1060 {
1061 dst = src;
1062 this->A->PSOR(dst, permutation, inverse_permutation, this->relaxation);
1063 }
1064
1065 template <typename VectorType>
1066 void
1067 Tvmult(VectorType &dst, const VectorType &src) const
1068 {
1069 dst = src;
1070 this->A->TPSOR(dst, permutation, inverse_permutation, this->relaxation);
1071 }
1072
1073 private:
1074 const ObserverPointer<const MatrixType> A;
1075 const double relaxation;
1076
1077 const std::vector<size_type> &permutation;
1078 const std::vector<size_type> &inverse_permutation;
1079 };
1080
1081 template <typename MatrixType,
1082 typename PreconditionerType,
1083 typename VectorType,
1084 std::enable_if_t<has_step_omega<PreconditionerType, VectorType>,
1085 PreconditionerType> * = nullptr>
1086 void
1087 step(const MatrixType &,
1088 const PreconditionerType &preconditioner,
1089 VectorType &dst,
1090 const VectorType &src,
1091 const double relaxation,
1092 VectorType &,
1093 VectorType &)
1094 {
1095 preconditioner.step(dst, src, relaxation);
1096 }
1097
1098 template <
1099 typename MatrixType,
1100 typename PreconditionerType,
1101 typename VectorType,
1102 std::enable_if_t<!has_step_omega<PreconditionerType, VectorType> &&
1103 has_step<PreconditionerType, VectorType>,
1104 PreconditionerType> * = nullptr>
1105 void
1106 step(const MatrixType &,
1107 const PreconditionerType &preconditioner,
1108 VectorType &dst,
1109 const VectorType &src,
1110 const double relaxation,
1111 VectorType &,
1112 VectorType &)
1113 {
1114 Assert(relaxation == 1.0, ExcInternalError());
1115
1116 (void)relaxation;
1117
1118 preconditioner.step(dst, src);
1119 }
1120
1121 template <
1122 typename MatrixType,
1123 typename PreconditionerType,
1124 typename VectorType,
1125 std::enable_if_t<!has_step_omega<PreconditionerType, VectorType> &&
1126 !has_step<PreconditionerType, VectorType>,
1127 PreconditionerType> * = nullptr>
1128 void
1129 step(const MatrixType &A,
1130 const PreconditionerType &preconditioner,
1131 VectorType &dst,
1132 const VectorType &src,
1133 const double relaxation,
1134 VectorType &residual,
1135 VectorType &tmp)
1136 {
1137 residual.reinit(dst, true);
1138 tmp.reinit(dst, true);
1139
1140 A.vmult(residual, dst);
1141 residual.sadd(-1.0, 1.0, src);
1142
1143 preconditioner.vmult(tmp, residual);
1144 dst.add(relaxation, tmp);
1145 }
1146
1147 template <typename MatrixType,
1148 typename PreconditionerType,
1149 typename VectorType,
1150 std::enable_if_t<has_Tstep_omega<PreconditionerType, VectorType>,
1151 PreconditionerType> * = nullptr>
1152 void
1153 Tstep(const MatrixType &,
1154 const PreconditionerType &preconditioner,
1155 VectorType &dst,
1156 const VectorType &src,
1157 const double relaxation,
1158 VectorType &,
1159 VectorType &)
1160 {
1161 preconditioner.Tstep(dst, src, relaxation);
1162 }
1163
1164 template <
1165 typename MatrixType,
1166 typename PreconditionerType,
1167 typename VectorType,
1168 std::enable_if_t<!has_Tstep_omega<PreconditionerType, VectorType> &&
1169 has_Tstep<PreconditionerType, VectorType>,
1170 PreconditionerType> * = nullptr>
1171 void
1172 Tstep(const MatrixType &,
1173 const PreconditionerType &preconditioner,
1174 VectorType &dst,
1175 const VectorType &src,
1176 const double relaxation,
1177 VectorType &,
1178 VectorType &)
1179 {
1180 Assert(relaxation == 1.0, ExcInternalError());
1181
1182 (void)relaxation;
1183
1184 preconditioner.Tstep(dst, src);
1185 }
1186
1187 template <typename MatrixType,
1188 typename VectorType,
1189 std::enable_if_t<has_Tvmult<MatrixType, VectorType>, MatrixType>
1190 * = nullptr>
1191 void
1192 Tvmult(const MatrixType &A, VectorType &dst, const VectorType &src)
1193 {
1194 A.Tvmult(dst, src);
1195 }
1196
1197 template <typename MatrixType,
1198 typename VectorType,
1199 std::enable_if_t<!has_Tvmult<MatrixType, VectorType>, MatrixType>
1200 * = nullptr>
1201 void
1202 Tvmult(const MatrixType &, VectorType &, const VectorType &)
1203 {
1204 AssertThrow(false,
1205 ExcMessage("Matrix A does not provide a Tvmult() function!"));
1206 }
1207
1208 template <
1209 typename MatrixType,
1210 typename PreconditionerType,
1211 typename VectorType,
1212 std::enable_if_t<!has_Tstep_omega<PreconditionerType, VectorType> &&
1213 !has_Tstep<PreconditionerType, VectorType>,
1214 PreconditionerType> * = nullptr>
1215 void
1216 Tstep(const MatrixType &A,
1217 const PreconditionerType &preconditioner,
1218 VectorType &dst,
1219 const VectorType &src,
1220 const double relaxation,
1221 VectorType &residual,
1222 VectorType &tmp)
1223 {
1224 residual.reinit(dst, true);
1225 tmp.reinit(dst, true);
1226
1227 Tvmult(A, residual, dst);
1228 residual.sadd(-1.0, 1.0, src);
1229
1230 Tvmult(preconditioner, tmp, residual);
1231 dst.add(relaxation, tmp);
1232 }
1233
1234 // 0) general implementation
1235 template <typename MatrixType,
1236 typename PreconditionerType,
1237 typename VectorType,
1238 std::enable_if_t<!has_vmult_with_std_functions_for_precondition<
1239 PreconditionerType,
1240 VectorType>,
1241 int> * = nullptr>
1242 void
1243 step_operations(const MatrixType &A,
1244 const PreconditionerType &preconditioner,
1245 VectorType &dst,
1246 const VectorType &src,
1247 const double relaxation,
1248 VectorType &tmp1,
1249 VectorType &tmp2,
1250 const unsigned int i,
1251 const bool transposed)
1252 {
1253 if (i == 0)
1254 {
1255 if (transposed)
1256 Tvmult(preconditioner, dst, src);
1257 else
1258 preconditioner.vmult(dst, src);
1259
1260 if (relaxation != 1.0)
1261 dst *= relaxation;
1262 }
1263 else
1264 {
1265 if (transposed)
1266 Tstep(A, preconditioner, dst, src, relaxation, tmp1, tmp2);
1267 else
1268 step(A, preconditioner, dst, src, relaxation, tmp1, tmp2);
1269 }
1270 }
1271
1272 // 1) specialized implementation with a preconditioner that accepts
1273 // ranges
1274 template <
1275 typename MatrixType,
1276 typename PreconditionerType,
1277 typename VectorType,
1278 std::enable_if_t<
1279 has_vmult_with_std_functions_for_precondition<PreconditionerType,
1280 VectorType> &&
1281 !has_vmult_with_std_functions_for_precondition<MatrixType,
1282 VectorType>,
1283 int> * = nullptr>
1284 void
1285 step_operations(const MatrixType &A,
1286 const PreconditionerType &preconditioner,
1287 VectorType &dst,
1288 const VectorType &src,
1289 const double relaxation,
1290 VectorType &tmp,
1291 VectorType &,
1292 const unsigned int i,
1293 const bool transposed)
1294 {
1295 (void)transposed;
1296 using Number = typename VectorType::value_type;
1297 Number *dst_ptr = dst.begin();
1298 const Number *src_ptr = src.begin();
1299
1300 if (i == 0)
1301 {
1302 preconditioner.vmult(
1303 dst,
1304 src,
1305 [&](const unsigned int start_range, const unsigned int end_range) {
1306 // zero 'dst' before running the vmult operation
1307 if (end_range > start_range)
1308 std::memset(dst_ptr + start_range,
1309 0,
1310 sizeof(Number) * (end_range - start_range));
1311 },
1312 [&](const unsigned int start_range, const unsigned int end_range) {
1313 if (relaxation == 1.0)
1314 return; // nothing to do
1315
1316 DEAL_II_OPENMP_SIMD_PRAGMA
1317 for (std::size_t i = start_range; i < end_range; ++i)
1318 dst_ptr[i] *= relaxation;
1319 });
1320 }
1321 else
1322 {
1323 tmp.reinit(src, true);
1324
1325 Assert(transposed == false, ExcNotImplemented());
1326
1327 A.vmult(tmp, dst);
1328
1329 preconditioner.vmult(
1330 dst,
1331 tmp,
1332 [&](const unsigned int start_range, const unsigned int end_range) {
1333 const auto tmp_ptr = tmp.begin();
1334
1335 if (relaxation == 1.0)
1336 {
1337 DEAL_II_OPENMP_SIMD_PRAGMA
1338 for (std::size_t i = start_range; i < end_range; ++i)
1339 tmp_ptr[i] = src_ptr[i] - tmp_ptr[i];
1340 }
1341 else
1342 {
1343 // note: we scale the residual here to be able to add into
1344 // the dst vector, which contains the solution from the last
1345 // iteration
1346 DEAL_II_OPENMP_SIMD_PRAGMA
1347 for (std::size_t i = start_range; i < end_range; ++i)
1348 tmp_ptr[i] = relaxation * (src_ptr[i] - tmp_ptr[i]);
1349 }
1350 },
1351 [&](const unsigned int, const unsigned int) {
1352 // nothing to do, since scaling by the relaxation factor
1353 // has been done in the pre operation
1354 });
1355 }
1356 }
1357
1358 // 2) specialized implementation with a preconditioner and a matrix that
1359 // accepts ranges
1360 template <
1361 typename MatrixType,
1362 typename PreconditionerType,
1363 typename VectorType,
1364 std::enable_if_t<
1365 has_vmult_with_std_functions_for_precondition<PreconditionerType,
1366 VectorType> &&
1367 has_vmult_with_std_functions_for_precondition<MatrixType, VectorType>,
1368 int> * = nullptr>
1369 void
1370 step_operations(const MatrixType &A,
1371 const PreconditionerType &preconditioner,
1372 VectorType &dst,
1373 const VectorType &src,
1374 const double relaxation,
1375 VectorType &tmp,
1376 VectorType &,
1377 const unsigned int i,
1378 const bool transposed)
1379 {
1380 (void)transposed;
1381 using Number = typename VectorType::value_type;
1382
1383 Number *dst_ptr = dst.begin();
1384 const Number *src_ptr = src.begin();
1385
1386 if (i == 0)
1387 {
1388 preconditioner.vmult(
1389 dst,
1390 src,
1391 [&](const unsigned int start_range, const unsigned int end_range) {
1392 // zero 'dst' before running the vmult operation
1393 if (end_range > start_range)
1394 std::memset(dst_ptr + start_range,
1395 0,
1396 sizeof(Number) * (end_range - start_range));
1397 },
1398 [&](const unsigned int start_range, const unsigned int end_range) {
1399 if (relaxation == 1.0)
1400 return; // nothing to do
1401
1402 DEAL_II_OPENMP_SIMD_PRAGMA
1403 for (std::size_t i = start_range; i < end_range; ++i)
1404 dst_ptr[i] *= relaxation;
1405 });
1406 }
1407 else
1408 {
1409 tmp.reinit(src, true);
1410 const auto tmp_ptr = tmp.begin();
1411
1412 Assert(transposed == false, ExcNotImplemented());
1413
1414 A.vmult(
1415 tmp,
1416 dst,
1417 [&](const unsigned int start_range, const unsigned int end_range) {
1418 // zero 'tmp' before running the vmult
1419 // operation
1420 if (end_range > start_range)
1421 std::memset(tmp_ptr + start_range,
1422 0,
1423 sizeof(Number) * (end_range - start_range));
1424 },
1425 [&](const unsigned int start_range, const unsigned int end_range) {
1426 if (relaxation == 1.0)
1427 {
1428 DEAL_II_OPENMP_SIMD_PRAGMA
1429 for (std::size_t i = start_range; i < end_range; ++i)
1430 tmp_ptr[i] = src_ptr[i] - tmp_ptr[i];
1431 }
1432 else
1433 {
1434 // note: we scale the residual here to be able to add into
1435 // the dst vector, which contains the solution from the last
1436 // iteration
1437 DEAL_II_OPENMP_SIMD_PRAGMA
1438 for (std::size_t i = start_range; i < end_range; ++i)
1439 tmp_ptr[i] = relaxation * (src_ptr[i] - tmp_ptr[i]);
1440 }
1441 });
1442
1443 preconditioner.vmult(dst, tmp, [](const auto, const auto) {
1444 // note: `dst` vector does not have to be zeroed out
1445 // since we add the result into it
1446 });
1447 }
1448 }
1449
1450 // 3) specialized implementation for inverse-diagonal preconditioner
1451 template <
1452 typename MatrixType,
1453 typename VectorType,
1454 std::enable_if_t<
1455 !IsBlockVector<VectorType>::value &&
1456 !std::is_same_v<
1457 VectorType,
1458 LinearAlgebra::distributed::Vector<typename VectorType::value_type,
1459 MemorySpace::Default>> &&
1460 !has_vmult_with_std_functions<MatrixType,
1461 VectorType,
1462 dealii::DiagonalMatrix<VectorType>>,
1463 VectorType> * = nullptr>
1464 void
1465 step_operations(const MatrixType &A,
1466 const dealii::DiagonalMatrix<VectorType> &preconditioner,
1467 VectorType &dst,
1468 const VectorType &src,
1469 const double relaxation,
1470 VectorType &tmp,
1471 VectorType &,
1472 const unsigned int i,
1473 const bool transposed)
1474 {
1475 using Number = typename VectorType::value_type;
1476
1477 if (i == 0)
1478 {
1479 Number *dst_ptr = dst.begin();
1480 const Number *src_ptr = src.begin();
1481 const Number *diag_ptr = preconditioner.get_vector().begin();
1482
1483 if (relaxation == 1.0)
1484 {
1485 DEAL_II_OPENMP_SIMD_PRAGMA
1486 for (unsigned int i = 0; i < dst.locally_owned_size(); ++i)
1487 dst_ptr[i] = src_ptr[i] * diag_ptr[i];
1488 }
1489 else
1490 {
1491 DEAL_II_OPENMP_SIMD_PRAGMA
1492 for (unsigned int i = 0; i < dst.locally_owned_size(); ++i)
1493 dst_ptr[i] = relaxation * src_ptr[i] * diag_ptr[i];
1494 }
1495 }
1496 else
1497 {
1498 tmp.reinit(src, true);
1499
1500 if (transposed)
1501 Tvmult(A, tmp, dst);
1502 else
1503 A.vmult(tmp, dst);
1504
1505 Number *dst_ptr = dst.begin();
1506 const Number *src_ptr = src.begin();
1507 const Number *tmp_ptr = tmp.begin();
1508 const Number *diag_ptr = preconditioner.get_vector().begin();
1509
1510 if (relaxation == 1.0)
1511 {
1512 DEAL_II_OPENMP_SIMD_PRAGMA
1513 for (unsigned int i = 0; i < dst.locally_owned_size(); ++i)
1514 dst_ptr[i] += (src_ptr[i] - tmp_ptr[i]) * diag_ptr[i];
1515 }
1516 else
1517 {
1518 DEAL_II_OPENMP_SIMD_PRAGMA
1519 for (unsigned int i = 0; i < dst.locally_owned_size(); ++i)
1520 dst_ptr[i] +=
1521 relaxation * (src_ptr[i] - tmp_ptr[i]) * diag_ptr[i];
1522 }
1523 }
1524 }
1525
1526 // 4) specialized implementation for inverse-diagonal preconditioner and
1527 // matrix that accepts ranges
1528 template <typename MatrixType,
1529 typename VectorType,
1530 std::enable_if_t<!IsBlockVector<VectorType>::value &&
1531 has_vmult_with_std_functions<
1532 MatrixType,
1533 VectorType,
1534 dealii::DiagonalMatrix<VectorType>>,
1535 VectorType> * = nullptr>
1536 void
1537 step_operations(const MatrixType &A,
1538 const dealii::DiagonalMatrix<VectorType> &preconditioner,
1539 VectorType &dst,
1540 const VectorType &src,
1541 const double relaxation,
1542 VectorType &tmp,
1543 VectorType &,
1544 const unsigned int i,
1545 const bool transposed)
1546 {
1547 (void)transposed;
1548 using Number = typename VectorType::value_type;
1549
1550 if (i == 0)
1551 {
1552 Number *dst_ptr = dst.begin();
1553 const Number *src_ptr = src.begin();
1554 const Number *diag_ptr = preconditioner.get_vector().begin();
1555
1556 if (relaxation == 1.0)
1557 {
1558 DEAL_II_OPENMP_SIMD_PRAGMA
1559 for (unsigned int i = 0; i < dst.locally_owned_size(); ++i)
1560 dst_ptr[i] = src_ptr[i] * diag_ptr[i];
1561 }
1562 else
1563 {
1564 DEAL_II_OPENMP_SIMD_PRAGMA
1565 for (unsigned int i = 0; i < dst.locally_owned_size(); ++i)
1566 dst_ptr[i] = relaxation * src_ptr[i] * diag_ptr[i];
1567 }
1568 }
1569 else
1570 {
1571 tmp.reinit(src, true);
1572
1573 Assert(transposed == false, ExcNotImplemented());
1574
1575 A.vmult(
1576 tmp,
1577 dst,
1578 [&](const unsigned int start_range, const unsigned int end_range) {
1579 // zero 'tmp' before running the vmult operation
1580 if (end_range > start_range)
1581 std::memset(tmp.begin() + start_range,
1582 0,
1583 sizeof(Number) * (end_range - start_range));
1584 },
1585 [&](const unsigned int begin, const unsigned int end) {
1586 const Number *dst_ptr = dst.begin();
1587 const Number *src_ptr = src.begin();
1588 Number *tmp_ptr = tmp.begin();
1589 const Number *diag_ptr = preconditioner.get_vector().begin();
1590
1591 // for efficiency reason, write back to temp_vector that is
1592 // already read (avoid read-for-ownership)
1593 if (relaxation == 1.0)
1594 {
1595 DEAL_II_OPENMP_SIMD_PRAGMA
1596 for (std::size_t i = begin; i < end; ++i)
1597 tmp_ptr[i] =
1598 dst_ptr[i] + (src_ptr[i] - tmp_ptr[i]) * diag_ptr[i];
1599 }
1600 else
1601 {
1602 DEAL_II_OPENMP_SIMD_PRAGMA
1603 for (std::size_t i = begin; i < end; ++i)
1604 tmp_ptr[i] = dst_ptr[i] + relaxation *
1605 (src_ptr[i] - tmp_ptr[i]) *
1606 diag_ptr[i];
1607 }
1608 });
1609
1610 tmp.swap(dst);
1611 }
1612 }
1613
1614 } // namespace PreconditionRelaxation
1615 } // namespace internal
1616
1617 #endif
1618
1619
1620
1621 /**
1622 * Jacobi preconditioner using matrix built-in function. The
1623 * <tt>MatrixType</tt> class used is required to have a function
1624 * <tt>precondition_Jacobi(VectorType&, const VectorType&, double</tt>). This
1625 * class satisfies the
1626 * @ref ConceptRelaxationType "relaxation concept".
1627 *
1628 * @code
1629 * // Declare related objects
1630 *
1631 * SparseMatrix<double> A;
1632 * Vector<double> x;
1633 * Vector<double> b;
1634 * SolverCG<> solver(...);
1635 *
1636 * //...initialize and build A
1637 *
1638 * // Define and initialize preconditioner:
1639 *
1640 * PreconditionJacobi<SparseMatrix<double> > precondition;
1641 * precondition.initialize(
1642 * A, PreconditionJacobi<SparseMatrix<double>>::AdditionalData(.6));
1643 *
1644 * solver.solve (A, x, b, precondition);
1645 * @endcode
1646 */
1647 template <typename MatrixType = SparseMatrix<double>>
1648 class PreconditionJacobi
1649 : public PreconditionRelaxation<
1650 MatrixType,
1651 internal::PreconditionRelaxation::PreconditionJacobiImpl<MatrixType>>
1652 {
1653 using PreconditionerType =
1654 internal::PreconditionRelaxation::PreconditionJacobiImpl<MatrixType>;
1655 using BaseClass = PreconditionRelaxation<MatrixType, PreconditionerType>;
1656
1657 public:
1658 /**
1659 * An alias to the base class AdditionalData.
1660 */
1661 using AdditionalData = typename BaseClass::AdditionalData;
1662
1663 /**
1664 * @copydoc PreconditionRelaxation::initialize()
1665 */
1666 void
1667 initialize(const MatrixType &A,
1668 const AdditionalData &parameters = AdditionalData());
1669 };
1670
1671
1672 /**
1673 * SOR preconditioner using matrix built-in function.
1674 *
1675 * Assuming the matrix <i>A = D + L + U</i> is split into its diagonal
1676 * <i>D</i> as well as the strict lower and upper triangles <i>L</i> and
1677 * <i>U</i>, then the SOR preconditioner with relaxation parameter <i>r</i> is
1678 * @f[
1679 * P^{-1} = r (D+rL)^{-1}.
1680 * @f]
1681 * It is this operator <i>P<sup>-1</sup></i>, which is implemented by vmult()
1682 * through forward substitution. Analogously, Tvmult() implements the
1683 * operation of <i>r(D+rU)<sup>-1</sup></i>.
1684 *
1685 * The SOR iteration itself can be directly written as
1686 * @f[
1687 * x^{k+1} = x^k - r D^{-1} \bigl(L x^{k+1} + U x^k - b\bigr).
1688 * @f]
1689 * Using the right hand side <i>b</i> and the previous iterate <i>x</i>, this
1690 * is the operation implemented by step().
1691 *
1692 * The MatrixType class used is required to have functions
1693 * <tt>precondition_SOR(VectorType&, const VectorType&, double)</tt> and
1694 * <tt>precondition_TSOR(VectorType&, const VectorType&, double)</tt>. This
1695 * class satisfies the
1696 * @ref ConceptRelaxationType "relaxation concept".
1697 *
1698 * @code
1699 * // Declare related objects
1700 *
1701 * SparseMatrix<double> A;
1702 * Vector<double> x;
1703 * Vector<double> b;
1704 * SolverCG<> solver(...);
1705 *
1706 * //...initialize and build A
1707 *
1708 * // Define and initialize preconditioner
1709 *
1710 * PreconditionSOR<SparseMatrix<double> > precondition;
1711 * precondition.initialize(
1712 * A, PreconditionSOR<SparseMatrix<double>>::AdditionalData(.6));
1713 *
1714 * solver.solve (A, x, b, precondition);
1715 * @endcode
1716 */
1717 template <typename MatrixType = SparseMatrix<double>>
1718 class PreconditionSOR
1719 : public PreconditionRelaxation<
1720 MatrixType,
1721 internal::PreconditionRelaxation::PreconditionSORImpl<MatrixType>>
1722 {
1723 using PreconditionerType =
1724 internal::PreconditionRelaxation::PreconditionSORImpl<MatrixType>;
1725 using BaseClass = PreconditionRelaxation<MatrixType, PreconditionerType>;
1726
1727 public:
1728 /**
1729 * An alias to the base class AdditionalData.
1730 */
1731 using AdditionalData = typename BaseClass::AdditionalData;
1732
1733 /**
1734 * @copydoc PreconditionRelaxation::initialize()
1735 */
1736 void
1737 initialize(const MatrixType &A,
1738 const AdditionalData &parameters = AdditionalData());
1739 };
1740
1741
1742
1743 /**
1744 * SSOR preconditioner using matrix built-in function. The
1745 * <tt>MatrixType</tt> class used is required to have a function
1746 * <tt>precondition_SSOR(VectorType&, const VectorType&, double)</tt>. This
1747 * class satisfies the
1748 * @ref ConceptRelaxationType "relaxation concept".
1749 *
1750 * @code
1751 * // Declare related objects
1752 *
1753 * SparseMatrix<double> A;
1754 * Vector<double> x;
1755 * Vector<double> b;
1756 * SolverCG<> solver(...);
1757 *
1758 * //...initialize and build A
1759 *
1760 * // Define and initialize preconditioner
1761 *
1762 * PreconditionSSOR<SparseMatrix<double> > precondition;
1763 * precondition.initialize(
1764 * A, PreconditionSSOR<SparseMatrix<double>>::AdditionalData(.6));
1765 *
1766 * solver.solve (A, x, b, precondition);
1767 * @endcode
1768 */
1769 template <typename MatrixType = SparseMatrix<double>>
1770 class PreconditionSSOR
1771 : public PreconditionRelaxation<
1772 MatrixType,
1773 internal::PreconditionRelaxation::PreconditionSSORImpl<MatrixType>>
1774 {
1775 using PreconditionerType =
1776 internal::PreconditionRelaxation::PreconditionSSORImpl<MatrixType>;
1777 using BaseClass = PreconditionRelaxation<MatrixType, PreconditionerType>;
1778
1779 public:
1780 /**
1781 * An alias to the base class AdditionalData.
1782 */
1783 using AdditionalData = typename BaseClass::AdditionalData;
1784
1785 /**
1786 * Initialize matrix and relaxation parameter. The matrix is just stored in
1787 * the preconditioner object. The relaxation parameter should be larger than
1788 * zero and smaller than 2 for numerical reasons. It defaults to 1.
1789 */
1790 void
1791 initialize(const MatrixType &A,
1792 const AdditionalData &parameters = AdditionalData());
1793 };
1794
1795
1796 /**
1797 * Permuted SOR preconditioner using matrix built-in function. The
1798 * <tt>MatrixType</tt> class used is required to have functions
1799 * <tt>PSOR(VectorType&, const VectorType&, double)</tt> and
1800 * <tt>TPSOR(VectorType&, const VectorType&, double)</tt>.
1801 *
1802 * @code
1803 * // Declare related objects
1804 *
1805 * SparseMatrix<double> A;
1806 * Vector<double> x;
1807 * Vector<double> b;
1808 * SolverCG<> solver(...);
1809 *
1810 * //...initialize and build A
1811 *
1812 * std::vector<unsigned int> permutation(x.size());
1813 * std::vector<unsigned int> inverse_permutation(x.size());
1814 *
1815 * //...fill permutation and its inverse with reasonable values
1816 *
1817 * // Define and initialize preconditioner
1818 *
1819 * PreconditionPSOR<SparseMatrix<double> > precondition;
1820 * precondition.initialize (A, permutation, inverse_permutation, .6);
1821 *
1822 * solver.solve (A, x, b, precondition);
1823 * @endcode
1824 */
1825 template <typename MatrixType = SparseMatrix<double>>
1826 class PreconditionPSOR
1827 : public PreconditionRelaxation<
1828 MatrixType,
1829 internal::PreconditionRelaxation::PreconditionPSORImpl<MatrixType>>
1830 {
1831 using PreconditionerType =
1832 internal::PreconditionRelaxation::PreconditionPSORImpl<MatrixType>;
1833 using BaseClass = PreconditionRelaxation<MatrixType, PreconditionerType>;
1834
1835 public:
1836 /**
1837 * Declare type for container size.
1838 */
1839 using size_type = typename BaseClass::size_type;
1840
1841 /**
1842 * Parameters for PreconditionPSOR.
1843 */
1844 class AdditionalData
1845 {
1846 public:
1847 /**
1848 * Constructor. For the parameters' description, see below.
1849 *
1850 * The permutation vectors are stored as a reference. Therefore, it has to
1851 * be assured that the lifetime of the vector exceeds the lifetime of the
1852 * preconditioner.
1853 *
1854 * The relaxation parameter should be larger than zero and smaller than 2
1855 * for numerical reasons. It defaults to 1.
1856 */
1857 AdditionalData(const std::vector<size_type> &permutation,
1858 const std::vector<size_type> &inverse_permutation,
1859 const typename BaseClass::AdditionalData &parameters =
1860 typename BaseClass::AdditionalData());
1861
1862 /**
1863 * Storage for the permutation vector.
1864 */
1865 const std::vector<size_type> &permutation;
1866 /**
1867 * Storage for the inverse permutation vector.
1868 */
1869 const std::vector<size_type> &inverse_permutation;
1870 /**
1871 * Relaxation parameters
1872 */
1873 typename BaseClass::AdditionalData parameters;
1874 };
1875
1876 /**
1877 * Initialize matrix and relaxation parameter. The matrix is just stored in
1878 * the preconditioner object.
1879 *
1880 * The permutation vector is stored as a pointer. Therefore, it has to be
1881 * assured that the lifetime of the vector exceeds the lifetime of the
1882 * preconditioner.
1883 *
1884 * The relaxation parameter should be larger than zero and smaller than 2
1885 * for numerical reasons. It defaults to 1.
1886 */
1887 void
1888 initialize(const MatrixType &A,
1889 const std::vector<size_type> &permutation,
1890 const std::vector<size_type> &inverse_permutation,
1891 const typename BaseClass::AdditionalData &parameters =
1892 typename BaseClass::AdditionalData());
1893
1894 /**
1895 * Initialize matrix and relaxation parameter. The matrix is just stored in
1896 * the preconditioner object.
1897 *
1898 * For more detail about possible parameters, see the class documentation
1899 * and the documentation of the PreconditionPSOR::AdditionalData class.
1900 *
1901 * After this function is called the preconditioner is ready to be used
1902 * (using the <code>vmult</code> function of derived classes).
1903 */
1904 void
1905 initialize(const MatrixType &A, const AdditionalData &additional_data);
1906 };
1907
1908
1909
1910 /**
1911 * Preconditioning with a Chebyshev polynomial for symmetric positive definite
1912 * matrices. This preconditioner is based on an iteration of an inner
1913 * preconditioner of type @p PreconditionerType with coefficients that are
1914 * adapted to optimally cover an eigenvalue range between the largest
1915 * eigenvalue $\lambda_{\max{}}$ down to a given lower eigenvalue
1916 * $\lambda_{\min{}}$ specified by the optional parameter
1917 * @p smoothing_range. The algorithm is based on the following three-term
1918 * recurrence:
1919 * @f[
1920 * x^{n+1} = x^{n} + \alpha^n_0 (x^{n} - x^{n-1}) + \alpha^n_1 P^{-1} (b-Ax^n)
1921 * \quad\text{with}\quad
1922 * \alpha^0_0 := 0,\;
1923 * \alpha^0_1 := \frac{2\rho_0}{\lambda_{\max}-\lambda_{\min}}\;
1924 * \alpha^n_0 := \rho_n \rho_{n-1},\;\text{and}\;
1925 * \alpha^n_1 := \frac{4\rho_n}{\lambda_{\max}-\lambda_{\min}},
1926 * @f]
1927 * where the parameter $\rho_0$ is set to $\rho_0 =
1928 * \frac{\lambda_{\max{}}-\lambda_{\min{}}}{\lambda_{\max{}}+\lambda_{\min{}}}$
1929 * for the maximal eigenvalue $\lambda_{\max{}}$ and updated via $\rho_n =
1930 * \left(2\frac{\lambda_{\max{}}+\lambda_{\min{}}}
1931 * {\lambda_{\max{}}-\lambda_{\min{}}} - \rho_{n-1}\right)^{-1}$. The
1932 * Chebyshev polynomial is constructed to strongly damp the eigenvalue range
1933 * between $\lambda_{\min{}}$ and $\lambda_{\max{}}$ and is visualized e.g. in
1934 * Utilities::LinearAlgebra::chebyshev_filter().
1935 *
1936 * The typical use case for the preconditioner is a Jacobi preconditioner
1937 * specified through DiagonalMatrix, which is also the default value for the
1938 * preconditioner. Note that if the degree variable is set to one, the
1939 * Chebyshev iteration corresponds to a Jacobi preconditioner (or the
1940 * underlying preconditioner type) with relaxation parameter according to the
1941 * specified smoothing range.
1942 *
1943 * Besides the default choice of a pointwise Jacobi preconditioner, this class
1944 * also allows for more advanced types of preconditioners, for example
1945 * iterating block-Jacobi preconditioners in DG methods.
1946 *
1947 * Apart from the inner preconditioner object, this iteration does not need
1948 * access to matrix entries, which makes it an ideal ingredient for
1949 * matrix-free computations. In that context, this class can be used as a
1950 * multigrid smoother that is trivially %parallel (assuming that matrix-vector
1951 * products are %parallel and the inner preconditioner is %parallel). Its use
1952 * is demonstrated in the step-37 and step-59 tutorial programs.
1953 *
1954 * <h4>Estimation of the eigenvalues</h4>
1955 *
1956 * The Chebyshev method relies on an estimate of the eigenvalues of the matrix
1957 * which are computed during the first invocation of vmult(). This class
1958 * offers several algorithms to this end, see
1959 * PreconditionChebyshev::AdditionalData::EigenvalueAlgorithm. The default
1960 * algorithm invokes the Lanczos method via the SolverCG class, which requires
1961 * symmetry and positive definiteness of the (preconditioned) matrix system
1962 * are required. Also note that deal.II needs to be configured with LAPACK
1963 * support to use this option. The eigenvalue algorithm can be controlled by
1964 * PreconditionChebyshev::AdditionalData::eig_cg_n_iterations specifying how
1965 * many iterations should be performed. For all algorithms, the iterative
1966 * process is started from an initial vector that depends on the vector
1967 * type. For the classes dealii::Vector or
1968 * dealii::LinearAlgebra::distributed::Vector, which have fast element access,
1969 * it is a vector with entries `(-5.5, -4.5, -3.5, -2.5, ..., 3.5, 4.5, 5.5)`
1970 * with appropriate epilogue and adjusted such that its mean is always zero,
1971 * which works well for the Laplacian. This setup is stable in parallel in the
1972 * sense that for a different number of processors but the same ordering of
1973 * unknowns, the same initial vector and thus eigenvalue distribution will be
1974 * computed, apart from roundoff errors. For other vector types, the initial
1975 * vector contains all ones, scaled by the length of the vector, except for
1976 * the very first entry that is zero, triggering high-frequency content again.
1977 *
1978 * The computation of eigenvalues happens the first time one of the vmult(),
1979 * Tvmult(), step() or Tstep() functions is called or when
1980 * estimate_eigenvalues() is called directly. In the latter case, it is
1981 * necessary to provide a temporary vector of the same layout as the source
1982 * and destination vectors used during application of the preconditioner.
1983 *
1984 * The estimates for minimum and maximum eigenvalue are taken from the
1985 * underlying solver or eigenvalue algorithm in the given number of
1986 * iterations, even if the solver did not converge in the requested number of
1987 * iterations. Finally, the maximum eigenvalue is multiplied by a safety
1988 * factor of 1.2.
1989 *
1990 * Due to the cost of the eigenvalue estimate, this class is most appropriate
1991 * if it is applied repeatedly, e.g. in a smoother for a geometric multigrid
1992 * solver, that can in turn be used to solve several linear systems.
1993 *
1994 * <h4>Bypassing the eigenvalue computation</h4>
1995 *
1996 * In some contexts, the automatic eigenvalue computation of this class may
1997 * result in a bad quality, e.g. when the polynomial basis or numbering of
1998 * unknowns is such that the initial vector described above is a bad
1999 * choice. It is possible to bypass the automatic eigenvalue computation by
2000 * setting AdditionalData::eig_cg_n_iterations to zero, and provide the
2001 * variable AdditionalData::max_eigenvalue instead. The minimal eigenvalue is
2002 * implicitly specified via `max_eigenvalue/smoothing_range`.
2003 *
2004 * <h4>Using the PreconditionChebyshev as a solver</h4>
2005 *
2006 * If the range <tt>[max_eigenvalue/smoothing_range, max_eigenvalue]</tt>
2007 * contains all eigenvalues of the preconditioned matrix system and the degree
2008 * (i.e., number of iterations) is high enough, this class can also be used as
2009 * a direct solver. For an error estimation of the Chebyshev iteration that
2010 * can be used to determine the number of iteration, see @cite Varga2009.
2011 *
2012 * In order to use Chebyshev as a solver, set the degree to
2013 * numbers::invalid_unsigned_int to force the automatic computation of the
2014 * number of iterations needed to reach a given target tolerance. Note that
2015 * this currently only works for symmetric positive definite matrices with the
2016 * eigenvalue algorithm set to the conjugate gradient algorithm. In this case,
2017 * the target tolerance is read from the variable
2018 * PreconditionChebyshev::AdditionalData::smoothing_range (it needs to be a
2019 * number less than one to force any iterations obviously).
2020 *
2021 * For details on the algorithm, see section 5.1 of @cite Varga2009.
2022 *
2023 * <h4>Requirements on the templated classes</h4>
2024 *
2025 * The class `MatrixType` must be derived from
2026 * EnableObserverPointer because a ObserverPointer to `MatrixType`
2027 * is held in the class. In particular, this means that the matrix object needs
2028 * to persist during the lifetime of PreconditionChebyshev. The preconditioner
2029 * is held in a shared_ptr that is copied into the AdditionalData member
2030 * variable of the class, so the variable used for initialization can safely be
2031 * discarded after calling initialize(). Both the matrix and the preconditioner
2032 * need to provide
2033 * @p vmult() functions for the matrix-vector product and @p m() functions for
2034 * accessing the number of rows in the (square) matrix. Furthermore, the
2035 * matrix must provide <tt>el(i,i)</tt> methods for accessing the matrix
2036 * diagonal in case the preconditioner type is DiagonalMatrix. Even though
2037 * it is highly recommended to pass the inverse diagonal entries inside a
2038 * separate preconditioner object for implementing the Jacobi method (which is
2039 * the only possible way to operate this class when computing in %parallel
2040 * with MPI because there is no knowledge about the locally stored range of
2041 * entries that would be needed from the matrix alone), there is a backward
2042 * compatibility function that can extract the diagonal in case of a serial
2043 * computation.
2044 *
2045 * <h4>Optimized operations with specific `MatrixType` argument</h4>
2046 *
2047 * This class enables to embed the vector updates into the matrix-vector
2048 * product in case the `MatrixType` supports this. To this end, the
2049 * `VectorType` needs to be of type LinearAlgebra::distributed::Vector, the
2050 * `PreconditionerType` needs to be DiagonalMatrix, and the class `MatrixType`
2051 * needs to provide a function with the signature
2052 * @code
2053 * void MatrixType::vmult(
2054 * VectorType &,
2055 * const VectorType &,
2056 * const std::function<void(const unsigned int, const unsigned int)> &,
2057 * const std::function<void(const unsigned int, const unsigned int)> &) const
2058 * @endcode
2059 * where the two given functions run before and after the matrix-vector
2060 * product, respectively. They take as arguments a sub-range among the locally
2061 * owned elements of the vector, defined as half-open intervals. The intervals
2062 * are designed to be scheduled close to the time the matrix-vector product
2063 * touches upon the entries in the `src` and `dst` vectors, respectively, with
2064 * the requirement that
2065 * <ul>
2066 * <li> the matrix-vector product may only access an entry in `src` or `dst`
2067 * once the `operation_before_matrix_vector_product` has been run on that
2068 * vector entry; </li>
2069 * <li> `operation_after_matrix_vector_product` may run on a range of entries
2070 * `[i,j)` once the matrix-vector product does not access the entries `[i,j)`
2071 * in `src` and `dst` any more. </li>
2072 * </ul>
2073 * The motivation for this function is to increase data locality and hence
2074 * cache usage. For the example of a class similar to the one in the step-37
2075 * tutorial program, the implementation is
2076 * @code
2077 * void
2078 * vmult(LinearAlgebra::distributed::Vector<number> & dst,
2079 * const LinearAlgebra::distributed::Vector<number> &src,
2080 * const std::function<void(const unsigned int, const unsigned int)>
2081 * &operation_before_matrix_vector_product,
2082 * const std::function<void(const unsigned int, const unsigned int)>
2083 * &operation_after_matrix_vector_product) const
2084 * {
2085 * data.cell_loop(&LaplaceOperator::local_apply,
2086 * this,
2087 * dst,
2088 * src,
2089 * operation_before_matrix_vector_product,
2090 * operation_after_matrix_vector_product);
2091 * }
2092 * @endcode
2093 * In terms of the Chebyshev iteration, the operation before the loop will
2094 * set `dst` to zero, whereas the operation after the loop performs the
2095 * iteration leading to $x^{n+1}$ described above, modifying the `dst` and
2096 * `src` vectors.
2097 */
2098 template <typename MatrixType = SparseMatrix<double>,
2099 typename VectorType = Vector<double>,
2100 typename PreconditionerType = DiagonalMatrix<VectorType>>
2101 class PreconditionChebyshev : public EnableObserverPointer
2102 {
2103 public:
2104 /**
2105 * Declare type for container size.
2106 */
2107 using size_type = types::global_dof_index;
2108
2109 /**
2110 * Standardized data struct to pipe additional parameters to the
2111 * preconditioner.
2112 */
2113 struct AdditionalData
2114 : public internal::EigenvalueAlgorithmAdditionalData<PreconditionerType>
2115 {
2116 using EigenvalueAlgorithm = internal::EigenvalueAlgorithm;
2117
2118 /**
2119 * An enum to define the available types of polynomial types.
2120 */
2121 enum class PolynomialType
2122 {
2123 /**
2124 * First-kind Chebyshev polynomials.
2125 */
2126 first_kind,
2127 /**
2128 * Fourth-kind Chebyshev polynomials according to @cite lottes2022optimal
2129 * and @cite phillips2022optimal.
2130 */
2131 fourth_kind
2132 };
2133
2134 /**
2135 * Constructor.
2136 */
2137 AdditionalData(
2138 const unsigned int degree = 1,
2139 const double smoothing_range = 0.,
2140 const unsigned int eig_cg_n_iterations = 8,
2141 const double eig_cg_residual = 1e-2,
2142 const double max_eigenvalue = 1,
2143 const EigenvalueAlgorithm eigenvalue_algorithm =
2144 EigenvalueAlgorithm::lanczos,
2145 const PolynomialType polynomial_type = PolynomialType::first_kind);
2146
2147 /**
2148 * This determines the degree of the Chebyshev polynomial. The degree of
2149 * the polynomial gives the number of matrix-vector products to be
2150 * performed for one application of the step() operation. During vmult(),
2151 * the method performs `(degree-1)` matrix-vector products. Degree one
2152 * corresponds to a damped Jacobi method.
2153 *
2154 * If the degree is set to numbers::invalid_unsigned_int, the algorithm
2155 * will automatically determine the number of necessary iterations based
2156 * on the usual Chebyshev error formula as mentioned in the discussion of
2157 * the main class.
2158 */
2159 unsigned int degree;
2160
2161 /**
2162 * Specifies the polynomial type to be used.
2163 */
2164 PolynomialType polynomial_type;
2165 };
2166
2167
2168 /**
2169 * Constructor.
2170 */
2171 PreconditionChebyshev();
2172
2173 /**
2174 * Initialize function. Takes the matrix which is used to form the
2175 * preconditioner, and additional flags if there are any. This function
2176 * works only if the input matrix has an operator <tt>el(i,i)</tt> for
2177 * accessing all the elements in the diagonal. Alternatively, the diagonal
2178 * can be supplied with the help of the AdditionalData field.
2179 *
2180 * This function calculates an estimate of the eigenvalue range of the
2181 * matrix weighted by its diagonal using a modified CG iteration in case the
2182 * given number of iterations is positive.
2183 */
2184 void
2185 initialize(const MatrixType &matrix,
2186 const AdditionalData &additional_data = AdditionalData());
2187
2188 /**
2189 * Compute the action of the preconditioner on <tt>src</tt>, storing the
2190 * result in <tt>dst</tt>.
2191 */
2192 void
2193 vmult(VectorType &dst, const VectorType &src) const;
2194
2195 /**
2196 * Compute the action of the transposed preconditioner on <tt>src</tt>,
2197 * storing the result in <tt>dst</tt>.
2198 */
2199 void
2200 Tvmult(VectorType &dst, const VectorType &src) const;
2201
2202 /**
2203 * Perform one step of the preconditioned Richardson iteration.
2204 */
2205 void
2206 step(VectorType &dst, const VectorType &src) const;
2207
2208 /**
2209 * Perform one transposed step of the preconditioned Richardson iteration.
2210 */
2211 void
2212 Tstep(VectorType &dst, const VectorType &src) const;
2213
2214 /**
2215 * Resets the preconditioner.
2216 */
2217 void
2218 clear();
2219
2220 /**
2221 * Return the dimension of the codomain (or range) space. Note that the
2222 * matrix is of dimension $m \times n$.
2223 */
2224 size_type
2225 m() const;
2226
2227 /**
2228 * Return the dimension of the domain space. Note that the matrix is of
2229 * dimension $m \times n$.
2230 */
2231 size_type
2232 n() const;
2233
2234 using EigenvalueInformation = internal::EigenvalueInformation;
2235
2236 /**
2237 * Compute eigenvalue estimates required for the preconditioner.
2238 *
2239 * This function is called automatically on first use of the preconditioner
2240 * if it is not called by the user. The layout of the vector @p src is used
2241 * to create internal temporary vectors and its content does not matter.
2242 *
2243 * Initializes the factors theta and delta based on an eigenvalue
2244 * computation. If the user set provided values for the largest eigenvalue
2245 * in AdditionalData, no computation is performed and the information given
2246 * by the user is used.
2247 */
2248 EigenvalueInformation
2249 estimate_eigenvalues(const VectorType &src) const;
2250
2251 private:
2252 /**
2253 * A pointer to the underlying matrix.
2254 */
2255 ObserverPointer<
2256 const MatrixType,
2257 PreconditionChebyshev<MatrixType, VectorType, PreconditionerType>>
2258 matrix_ptr;
2259
2260 /**
2261 * Internal vector used for the <tt>vmult</tt> operation.
2262 */
2263 mutable VectorType solution_old;
2264
2265 /**
2266 * Internal vector used for the <tt>vmult</tt> operation.
2267 */
2268 mutable VectorType temp_vector1;
2269
2270 /**
2271 * Internal vector used for the <tt>vmult</tt> operation.
2272 */
2273 mutable VectorType temp_vector2;
2274
2275 /**
2276 * Stores the additional data passed to the initialize function, obtained
2277 * through a copy operation.
2278 */
2279 AdditionalData data;
2280
2281 /**
2282 * Average of the largest and smallest eigenvalue under consideration.
2283 */
2284 double theta;
2285
2286 /**
2287 * Half the interval length between the largest and smallest eigenvalue
2288 * under consideration.
2289 */
2290 double delta;
2291
2292 /**
2293 * Stores whether the preconditioner has been set up and eigenvalues have
2294 * been computed.
2295 */
2296 bool eigenvalues_are_initialized;
2297
2298 /**
2299 * A mutex to avoid that multiple vmult() invocations by different threads
2300 * overwrite the temporary vectors.
2301 */
2302 mutable Threads::Mutex mutex;
2303 };
2304
2305
2306
2307 /** @} */
2308 /* ---------------------------------- Inline functions ------------------- */
2309
2310 #ifndef DOXYGEN
2311
2312
2313 namespace internal
2314 {
2315 template <typename VectorType>
2316 void
2317 set_initial_guess(VectorType &vector)
2318 {
2319 vector = 1. / std::sqrt(static_cast<double>(vector.size()));
2320 if (vector.locally_owned_elements().is_element(0))
2321 vector(0) = 0.;
2322 }
2323
2324 template <typename Number>
2325 void
2326 set_initial_guess(::dealii::Vector<Number> &vector)
2327 {
2328 // Choose a high-frequency mode consisting of numbers between 0 and 1
2329 // that is cheap to compute (cheaper than random numbers) but avoids
2330 // obviously re-occurring numbers in multi-component systems by choosing
2331 // a period of 11
2332 for (unsigned int i = 0; i < vector.size(); ++i)
2333 vector(i) = i % 11;
2334
2335 const Number mean_value = vector.mean_value();
2336 vector.add(-mean_value);
2337 }
2338
2339 template <typename Number, typename MemorySpace>
2340 void
2341 set_initial_guess(
2342 ::dealii::LinearAlgebra::distributed::BlockVector<Number, MemorySpace>
2343 &vector)
2344 {
2345 for (unsigned int block = 0; block < vector.n_blocks(); ++block)
2346 set_initial_guess(vector.block(block));
2347 }
2348
2349 template <typename Number, typename MemorySpace>
2350 void
2351 set_initial_guess(
2352 ::dealii::LinearAlgebra::distributed::Vector<Number, MemorySpace> &vector)
2353 {
2354 // Choose a high-frequency mode consisting of numbers between 0 and 1
2355 // that is cheap to compute (cheaper than random numbers) but avoids
2356 // obviously re-occurring numbers in multi-component systems by choosing
2357 // a period of 11.
2358 // Make initial guess robust with respect to number of processors
2359 // by operating on the global index.
2360 types::global_dof_index first_local_range = 0;
2361 if (!vector.locally_owned_elements().is_empty())
2362 first_local_range = vector.locally_owned_elements().nth_index_in_set(0);
2363
2364 const auto n_local_elements = vector.locally_owned_size();
2365 Number *values_ptr = vector.get_values();
2366 Kokkos::RangePolicy<typename MemorySpace::kokkos_space::execution_space,
2367 Kokkos::IndexType<types::global_dof_index>>
2368 policy(0, n_local_elements);
2369 Kokkos::parallel_for(
2370 "dealii::PreconditionChebyshev::set_initial_guess",
2371 policy,
2372 KOKKOS_LAMBDA(types::global_dof_index i) {
2373 values_ptr[i] = (i + first_local_range) % 11;
2374 });
2375 const Number mean_value = vector.mean_value();
2376 vector.add(-mean_value);
2377 }
2378
2379 struct EigenvalueTracker
2380 {
2381 public:
2382 void
2383 slot(const std::vector<double> &eigenvalues)
2384 {
2385 values = eigenvalues;
2386 }
2387
2388 std::vector<double> values;
2389 };
2390
2391
2392
2393 template <typename MatrixType,
2394 typename VectorType,
2395 typename PreconditionerType>
2396 double
2397 power_iteration(const MatrixType &matrix,
2398 VectorType &eigenvector,
2399 const PreconditionerType &preconditioner,
2400 const unsigned int n_iterations)
2401 {
2402 typename VectorType::value_type eigenvalue_estimate = 0.;
2403 eigenvector /= eigenvector.l2_norm();
2404 VectorType vector1, vector2;
2405 vector1.reinit(eigenvector, true);
2406 if (!std::is_same_v<PreconditionerType, PreconditionIdentity>)
2407 vector2.reinit(eigenvector, true);
2408 for (unsigned int i = 0; i < n_iterations; ++i)
2409 {
2410 if (!std::is_same_v<PreconditionerType, PreconditionIdentity>)
2411 {
2412 matrix.vmult(vector2, eigenvector);
2413 preconditioner.vmult(vector1, vector2);
2414 }
2415 else
2416 matrix.vmult(vector1, eigenvector);
2417
2418 eigenvalue_estimate = eigenvector * vector1;
2419
2420 vector1 /= vector1.l2_norm();
2421 eigenvector.swap(vector1);
2422 }
2423 return std::abs(eigenvalue_estimate);
2424 }
2425
2426
2427
2428 template <typename MatrixType,
2429 typename VectorType,
2430 typename PreconditionerType>
2431 EigenvalueInformation
2432 estimate_eigenvalues(
2433 const EigenvalueAlgorithmAdditionalData<PreconditionerType> &data,
2434 const MatrixType *matrix_ptr,
2435 VectorType &solution_old,
2436 VectorType &temp_vector1,
2437 const unsigned int degree)
2438 {
2439 Assert(data.preconditioner.get() != nullptr, ExcNotInitialized());
2440
2441 EigenvalueInformation info{};
2442
2443 if (data.eig_cg_n_iterations > 0)
2444 {
2445 Assert(data.eig_cg_n_iterations > 2,
2446 ExcMessage(
2447 "Need to set at least two iterations to find eigenvalues."));
2448
2449 internal::EigenvalueTracker eigenvalue_tracker;
2450
2451 // set an initial guess that contains some high-frequency parts (to the
2452 // extent possible without knowing the discretization and the numbering)
2453 // to trigger high eigenvalues according to the external function
2454 internal::set_initial_guess(temp_vector1);
2455 data.constraints.set_zero(temp_vector1);
2456
2457 if (data.eigenvalue_algorithm == internal::EigenvalueAlgorithm::lanczos)
2458 {
2459 // set a very strict tolerance to force at least two iterations
2460 IterationNumberControl control(data.eig_cg_n_iterations,
2461 1e-10,
2462 false,
2463 false);
2464
2465 dealii::SolverCG<VectorType> solver(control);
2466 solver.connect_eigenvalues_slot(
2467 [&eigenvalue_tracker](const std::vector<double> &eigenvalues) {
2468 eigenvalue_tracker.slot(eigenvalues);
2469 });
2470
2471 solver.solve(*matrix_ptr,
2472 solution_old,
2473 temp_vector1,
2474 *data.preconditioner);
2475
2476 info.cg_iterations = control.last_step();
2477 }
2478 else if (data.eigenvalue_algorithm ==
2479 internal::EigenvalueAlgorithm::power_iteration)
2480 {
2481 (void)degree;
2482
2483 Assert(degree != numbers::invalid_unsigned_int,
2484 ExcMessage("Cannot estimate the minimal eigenvalue with the "
2485 "power iteration"));
2486
2487 eigenvalue_tracker.values.push_back(
2488 internal::power_iteration(*matrix_ptr,
2489 temp_vector1,
2490 *data.preconditioner,
2491 data.eig_cg_n_iterations));
2492 }
2493 else
2494 DEAL_II_NOT_IMPLEMENTED();
2495
2496 // read the eigenvalues from the attached eigenvalue tracker
2497 if (eigenvalue_tracker.values.empty())
2498 info.min_eigenvalue_estimate = info.max_eigenvalue_estimate = 1.;
2499 else
2500 {
2501 info.min_eigenvalue_estimate = eigenvalue_tracker.values.front();
2502
2503 // include a safety factor since the CG method will in general not
2504 // be converged
2505 info.max_eigenvalue_estimate =
2506 1.2 * eigenvalue_tracker.values.back();
2507 }
2508 }
2509 else
2510 {
2511 info.max_eigenvalue_estimate = data.max_eigenvalue;
2512 info.min_eigenvalue_estimate =
2513 data.max_eigenvalue / data.smoothing_range;
2514 }
2515
2516 return info;
2517 }
2518 } // namespace internal
2519
2520
2521
2522 inline PreconditionIdentity::PreconditionIdentity()
2523 : n_rows(0)
2524 , n_columns(0)
2525 {}
2526
2527 template <typename MatrixType>
2528 inline void
2529 PreconditionIdentity::initialize(const MatrixType &matrix,
2530 const PreconditionIdentity::AdditionalData &)
2531 {
2532 n_rows = matrix.m();
2533 n_columns = matrix.n();
2534 }
2535
2536
2537 template <typename VectorType>
2538 inline void
2539 PreconditionIdentity::vmult(VectorType &dst, const VectorType &src) const
2540 {
2541 dst = src;
2542 }
2543
2544
2545
2546 template <typename VectorType>
2547 inline void
2548 PreconditionIdentity::Tvmult(VectorType &dst, const VectorType &src) const
2549 {
2550 dst = src;
2551 }
2552
2553 template <typename VectorType>
2554 inline void
2555 PreconditionIdentity::vmult_add(VectorType &dst, const VectorType &src) const
2556 {
2557 dst += src;
2558 }
2559
2560
2561
2562 template <typename VectorType>
2563 inline void
2564 PreconditionIdentity::Tvmult_add(VectorType &dst, const VectorType &src) const
2565 {
2566 dst += src;
2567 }
2568
2569
2570
2571 inline void
2572 PreconditionIdentity::clear()
2573 {}
2574
2575
2576
2577 inline PreconditionIdentity::size_type
2578 PreconditionIdentity::m() const
2579 {
2580 Assert(n_rows != 0, ExcNotInitialized());
2581 return n_rows;
2582 }
2583
2584 inline PreconditionIdentity::size_type
2585 PreconditionIdentity::n() const
2586 {
2587 Assert(n_columns != 0, ExcNotInitialized());
2588 return n_columns;
2589 }
2590
2591 //---------------------------------------------------------------------------
2592
2593 inline PreconditionRichardson::AdditionalData::AdditionalData(
2594 const double relaxation)
2595 : relaxation(relaxation)
2596 {}
2597
2598
2599 inline PreconditionRichardson::PreconditionRichardson()
2600 : relaxation(0)
2601 , n_rows(0)
2602 , n_columns(0)
2603 {
2604 AdditionalData add_data;
2605 relaxation = add_data.relaxation;
2606 }
2607
2608
2609
2610 inline void
2611 PreconditionRichardson::initialize(
2612 const PreconditionRichardson::AdditionalData &parameters)
2613 {
2614 relaxation = parameters.relaxation;
2615 }
2616
2617
2618
2619 template <typename MatrixType>
2620 inline void
2621 PreconditionRichardson::initialize(
2622 const MatrixType &matrix,
2623 const PreconditionRichardson::AdditionalData &parameters)
2624 {
2625 relaxation = parameters.relaxation;
2626 n_rows = matrix.m();
2627 n_columns = matrix.n();
2628 }
2629
2630
2631
2632 template <typename VectorType>
2633 inline void
2634 PreconditionRichardson::vmult(VectorType &dst, const VectorType &src) const
2635 {
2636 static_assert(
2637 std::is_same_v<size_type, typename VectorType::size_type>,
2638 "PreconditionRichardson and VectorType must have the same size_type.");
2639
2640 dst.equ(relaxation, src);
2641 }
2642
2643
2644
2645 template <typename VectorType>
2646 inline void
2647 PreconditionRichardson::Tvmult(VectorType &dst, const VectorType &src) const
2648 {
2649 static_assert(
2650 std::is_same_v<size_type, typename VectorType::size_type>,
2651 "PreconditionRichardson and VectorType must have the same size_type.");
2652
2653 dst.equ(relaxation, src);
2654 }
2655
2656 template <typename VectorType>
2657 inline void
2658 PreconditionRichardson::vmult_add(VectorType &dst, const VectorType &src) const
2659 {
2660 static_assert(
2661 std::is_same_v<size_type, typename VectorType::size_type>,
2662 "PreconditionRichardson and VectorType must have the same size_type.");
2663
2664 dst.add(relaxation, src);
2665 }
2666
2667
2668
2669 template <typename VectorType>
2670 inline void
2671 PreconditionRichardson::Tvmult_add(VectorType &dst, const VectorType &src) const
2672 {
2673 static_assert(
2674 std::is_same_v<size_type, typename VectorType::size_type>,
2675 "PreconditionRichardson and VectorType must have the same size_type.");
2676
2677 dst.add(relaxation, src);
2678 }
2679
2680 inline PreconditionRichardson::size_type
2681 PreconditionRichardson::m() const
2682 {
2683 Assert(n_rows != 0, ExcNotInitialized());
2684 return n_rows;
2685 }
2686
2687 inline PreconditionRichardson::size_type
2688 PreconditionRichardson::n() const
2689 {
2690 Assert(n_columns != 0, ExcNotInitialized());
2691 return n_columns;
2692 }
2693
2694 //---------------------------------------------------------------------------
2695
2696 template <typename MatrixType, typename PreconditionerType>
2697 inline void
2698 PreconditionRelaxation<MatrixType, PreconditionerType>::initialize(
2699 const MatrixType &rA,
2700 const AdditionalData &parameters)
2701 {
2702 A = &rA;
2703 eigenvalues_are_initialized = false;
2704
2705 Assert(parameters.preconditioner, ExcNotInitialized());
2706
2707 this->data = parameters;
2708 }
2709
2710
2711 template <typename MatrixType, typename PreconditionerType>
2712 inline void
2713 PreconditionRelaxation<MatrixType, PreconditionerType>::clear()
2714 {
2715 eigenvalues_are_initialized = false;
2716 A = nullptr;
2717 data.relaxation = 1.0;
2718 data.preconditioner = nullptr;
2719 }
2720
2721 template <typename MatrixType, typename PreconditionerType>
2722 inline
2723 typename PreconditionRelaxation<MatrixType, PreconditionerType>::size_type
2724 PreconditionRelaxation<MatrixType, PreconditionerType>::m() const
2725 {
2726 Assert(A != nullptr, ExcNotInitialized());
2727 return A->m();
2728 }
2729
2730 template <typename MatrixType, typename PreconditionerType>
2731 inline
2732 typename PreconditionRelaxation<MatrixType, PreconditionerType>::size_type
2733 PreconditionRelaxation<MatrixType, PreconditionerType>::n() const
2734 {
2735 Assert(A != nullptr, ExcNotInitialized());
2736 return A->n();
2737 }
2738
2739 template <typename MatrixType, typename PreconditionerType>
2740 template <typename VectorType>
2741 inline void
2742 PreconditionRelaxation<MatrixType, PreconditionerType>::vmult(
2743 VectorType &dst,
2744 const VectorType &src) const
2745 {
2746 Assert(this->A != nullptr, ExcNotInitialized());
2747 Assert(data.preconditioner != nullptr, ExcNotInitialized());
2748
2749 if (eigenvalues_are_initialized == false)
2750 estimate_eigenvalues(src);
2751
2752 VectorType tmp1, tmp2;
2753
2754 for (unsigned int i = 0; i < data.n_iterations; ++i)
2755 internal::PreconditionRelaxation::step_operations(*A,
2756 *data.preconditioner,
2757 dst,
2758 src,
2759 data.relaxation,
2760 tmp1,
2761 tmp2,
2762 i,
2763 false);
2764 }
2765
2766 template <typename MatrixType, typename PreconditionerType>
2767 template <typename VectorType>
2768 inline void
2769 PreconditionRelaxation<MatrixType, PreconditionerType>::Tvmult(
2770 VectorType &dst,
2771 const VectorType &src) const
2772 {
2773 Assert(this->A != nullptr, ExcNotInitialized());
2774 Assert(data.preconditioner != nullptr, ExcNotInitialized());
2775
2776 if (eigenvalues_are_initialized == false)
2777 estimate_eigenvalues(src);
2778
2779 VectorType tmp1, tmp2;
2780
2781 for (unsigned int i = 0; i < data.n_iterations; ++i)
2782 internal::PreconditionRelaxation::step_operations(
2783 *A, *data.preconditioner, dst, src, data.relaxation, tmp1, tmp2, i, true);
2784 }
2785
2786 template <typename MatrixType, typename PreconditionerType>
2787 template <typename VectorType>
2788 inline void
2789 PreconditionRelaxation<MatrixType, PreconditionerType>::step(
2790 VectorType &dst,
2791 const VectorType &src) const
2792 {
2793 Assert(this->A != nullptr, ExcNotInitialized());
2794 Assert(data.preconditioner != nullptr, ExcNotInitialized());
2795
2796 if (eigenvalues_are_initialized == false)
2797 estimate_eigenvalues(src);
2798
2799 VectorType tmp1, tmp2;
2800
2801 for (unsigned int i = 1; i <= data.n_iterations; ++i)
2802 internal::PreconditionRelaxation::step_operations(*A,
2803 *data.preconditioner,
2804 dst,
2805 src,
2806 data.relaxation,
2807 tmp1,
2808 tmp2,
2809 i,
2810 false);
2811 }
2812
2813 template <typename MatrixType, typename PreconditionerType>
2814 template <typename VectorType>
2815 inline void
2816 PreconditionRelaxation<MatrixType, PreconditionerType>::Tstep(
2817 VectorType &dst,
2818 const VectorType &src) const
2819 {
2820 Assert(this->A != nullptr, ExcNotInitialized());
2821 Assert(data.preconditioner != nullptr, ExcNotInitialized());
2822
2823 if (eigenvalues_are_initialized == false)
2824 estimate_eigenvalues(src);
2825
2826 VectorType tmp1, tmp2;
2827
2828 for (unsigned int i = 1; i <= data.n_iterations; ++i)
2829 internal::PreconditionRelaxation::step_operations(
2830 *A, *data.preconditioner, dst, src, data.relaxation, tmp1, tmp2, i, true);
2831 }
2832
2833 template <typename MatrixType, typename PreconditionerType>
2834 template <typename VectorType>
2835 inline internal::EigenvalueInformation
2836 PreconditionRelaxation<MatrixType, PreconditionerType>::estimate_eigenvalues(
2837 const VectorType &src) const
2838 {
2839 Assert(eigenvalues_are_initialized == false, ExcInternalError());
2840
2841 EigenvalueInformation info;
2842
2843 if (data.relaxation == 0.0)
2844 {
2845 VectorType solution_old, temp_vector1;
2846
2847 solution_old.reinit(src);
2848 temp_vector1.reinit(src, true);
2849
2850 info = internal::estimate_eigenvalues<MatrixType>(
2851 data, A, solution_old, temp_vector1, data.n_iterations);
2852
2853 const double alpha =
2854 (data.smoothing_range > 1. ?
2855 info.max_eigenvalue_estimate / data.smoothing_range :
2856 std::min(0.9 * info.max_eigenvalue_estimate,
2857 info.min_eigenvalue_estimate));
2858
2859 const_cast<PreconditionRelaxation<MatrixType, PreconditionerType> *>(this)
2860 ->data.relaxation = 2.0 / (alpha + info.max_eigenvalue_estimate);
2861 }
2862
2863 const_cast<PreconditionRelaxation<MatrixType, PreconditionerType> *>(this)
2864 ->eigenvalues_are_initialized = true;
2865
2866 return info;
2867 }
2868
2869 template <typename MatrixType, typename PreconditionerType>
2870 double
2871 PreconditionRelaxation<MatrixType, PreconditionerType>::get_relaxation() const
2872 {
2873 return data.relaxation;
2874 }
2875
2876
2877 //---------------------------------------------------------------------------
2878
2879 template <typename MatrixType>
2880 inline void
2881 PreconditionJacobi<MatrixType>::initialize(const MatrixType &A,
2882 const AdditionalData &parameters_in)
2883 {
2884 Assert(parameters_in.preconditioner == nullptr, ExcInternalError());
2885 Assert(
2886 parameters_in.relaxation != 0.0,
2887 ExcMessage(
2888 "Relaxation cannot automatically be determined by PreconditionJacobi."));
2889
2890 AdditionalData parameters;
2891 parameters.relaxation = 1.0;
2892 parameters.n_iterations = parameters_in.n_iterations;
2893 parameters.preconditioner =
2894 std::make_shared<PreconditionerType>(A, parameters_in.relaxation);
2895
2896 this->BaseClass::initialize(A, parameters);
2897 }
2898
2899 //---------------------------------------------------------------------------
2900
2901 template <typename MatrixType>
2902 inline void
2903 PreconditionSOR<MatrixType>::initialize(const MatrixType &A,
2904 const AdditionalData &parameters_in)
2905 {
2906 Assert(parameters_in.preconditioner == nullptr, ExcInternalError());
2907 Assert(
2908 parameters_in.relaxation != 0.0,
2909 ExcMessage(
2910 "Relaxation cannot automatically be determined by PreconditionSOR."));
2911
2912 AdditionalData parameters;
2913 parameters.relaxation = 1.0;
2914 parameters.n_iterations = parameters_in.n_iterations;
2915 parameters.preconditioner =
2916 std::make_shared<PreconditionerType>(A, parameters_in.relaxation);
2917
2918 this->BaseClass::initialize(A, parameters);
2919 }
2920
2921 //---------------------------------------------------------------------------
2922
2923 template <typename MatrixType>
2924 inline void
2925 PreconditionSSOR<MatrixType>::initialize(const MatrixType &A,
2926 const AdditionalData &parameters_in)
2927 {
2928 Assert(parameters_in.preconditioner == nullptr, ExcInternalError());
2929 Assert(
2930 parameters_in.relaxation != 0.0,
2931 ExcMessage(
2932 "Relaxation cannot automatically be determined by PreconditionSSOR."));
2933
2934 AdditionalData parameters;
2935 parameters.relaxation = 1.0;
2936 parameters.n_iterations = parameters_in.n_iterations;
2937 parameters.preconditioner =
2938 std::make_shared<PreconditionerType>(A, parameters_in.relaxation);
2939
2940 this->BaseClass::initialize(A, parameters);
2941 }
2942
2943
2944
2945 //---------------------------------------------------------------------------
2946
2947 template <typename MatrixType>
2948 inline void
2949 PreconditionPSOR<MatrixType>::initialize(
2950 const MatrixType &A,
2951 const std::vector<size_type> &p,
2952 const std::vector<size_type> &ip,
2953 const typename BaseClass::AdditionalData &parameters_in)
2954 {
2955 Assert(parameters_in.preconditioner == nullptr, ExcInternalError());
2956 Assert(
2957 parameters_in.relaxation != 0.0,
2958 ExcMessage(
2959 "Relaxation cannot automatically be determined by PreconditionPSOR."));
2960
2961 typename BaseClass::AdditionalData parameters;
2962 parameters.relaxation = 1.0;
2963 parameters.n_iterations = parameters_in.n_iterations;
2964 parameters.preconditioner =
2965 std::make_shared<PreconditionerType>(A, parameters_in.relaxation, p, ip);
2966
2967 this->BaseClass::initialize(A, parameters);
2968 }
2969
2970
2971 template <typename MatrixType>
2972 inline void
2973 PreconditionPSOR<MatrixType>::initialize(const MatrixType &A,
2974 const AdditionalData &additional_data)
2975 {
2976 initialize(A,
2977 additional_data.permutation,
2978 additional_data.inverse_permutation,
2979 additional_data.parameters);
2980 }
2981
2982 template <typename MatrixType>
2983 PreconditionPSOR<MatrixType>::AdditionalData::AdditionalData(
2984 const std::vector<size_type> &permutation,
2985 const std::vector<size_type> &inverse_permutation,
2986 const typename PreconditionPSOR<MatrixType>::BaseClass::AdditionalData
2987 &parameters)
2988 : permutation(permutation)
2989 , inverse_permutation(inverse_permutation)
2990 , parameters(parameters)
2991 {}
2992
2993
2994 //---------------------------------------------------------------------------
2995
2996
2997 template <typename MatrixType, typename VectorType>
2998 PreconditionUseMatrix<MatrixType, VectorType>::PreconditionUseMatrix(
2999 const MatrixType &M,
3000 const function_ptr method)
3001 : matrix(M)
3002 , precondition(method)
3003 {}
3004
3005
3006
3007 template <typename MatrixType, typename VectorType>
3008 void
3009 PreconditionUseMatrix<MatrixType, VectorType>::vmult(
3010 VectorType &dst,
3011 const VectorType &src) const
3012 {
3013 (matrix.*precondition)(dst, src);
3014 }
3015
3016 //---------------------------------------------------------------------------
3017
3018 namespace internal
3019 {
3020
3021 template <typename PreconditionerType>
3022 inline EigenvalueAlgorithmAdditionalData<PreconditionerType>::
3023 EigenvalueAlgorithmAdditionalData(
3024 const double smoothing_range,
3025 const unsigned int eig_cg_n_iterations,
3026 const double eig_cg_residual,
3027 const double max_eigenvalue,
3028 const EigenvalueAlgorithm eigenvalue_algorithm)
3029 : smoothing_range(smoothing_range)
3030 , eig_cg_n_iterations(eig_cg_n_iterations)
3031 , eig_cg_residual(eig_cg_residual)
3032 , max_eigenvalue(max_eigenvalue)
3033 , eigenvalue_algorithm(eigenvalue_algorithm)
3034 {}
3035
3036
3037
3038 template <typename PreconditionerType>
3039 inline EigenvalueAlgorithmAdditionalData<PreconditionerType> &
3040 EigenvalueAlgorithmAdditionalData<PreconditionerType>::operator=(
3041 const EigenvalueAlgorithmAdditionalData &other_data)
3042 {
3043 smoothing_range = other_data.smoothing_range;
3044 eig_cg_n_iterations = other_data.eig_cg_n_iterations;
3045 eig_cg_residual = other_data.eig_cg_residual;
3046 max_eigenvalue = other_data.max_eigenvalue;
3047 preconditioner = other_data.preconditioner;
3048 eigenvalue_algorithm = other_data.eigenvalue_algorithm;
3049 constraints.copy_from(other_data.constraints);
3050
3051 return *this;
3052 }
3053 } // namespace internal
3054
3055 template <typename MatrixType, typename PreconditionerType>
3056 inline PreconditionRelaxation<MatrixType, PreconditionerType>::AdditionalData::
3057 AdditionalData(const double relaxation,
3058 const unsigned int n_iterations,
3059 const double smoothing_range,
3060 const unsigned int eig_cg_n_iterations,
3061 const double eig_cg_residual,
3062 const double max_eigenvalue,
3063 const EigenvalueAlgorithm eigenvalue_algorithm)
3064 : internal::EigenvalueAlgorithmAdditionalData<PreconditionerType>(
3065 smoothing_range,
3066 eig_cg_n_iterations,
3067 eig_cg_residual,
3068 max_eigenvalue,
3069 eigenvalue_algorithm)
3070 , relaxation(relaxation)
3071 , n_iterations(n_iterations)
3072 {}
3073
3074
3075
3076 //---------------------------------------------------------------------------
3077
3078 namespace internal
3079 {
3080 namespace PreconditionChebyshevImplementation
3081 {
3082 // for deal.II vectors, perform updates for Chebyshev preconditioner all
3083 // at once to reduce memory transfer. Here, we select between general
3084 // vectors and deal.II vectors where we expand the loop over the (local)
3085 // size of the vector
3086
3087 // generic part for non-deal.II vectors
3088 template <typename VectorType, typename PreconditionerType>
3089 inline void
3090 vector_updates(const VectorType &rhs,
3091 const PreconditionerType &preconditioner,
3092 const unsigned int iteration_index,
3093 const double factor1,
3094 const double factor2,
3095 VectorType &solution_old,
3096 VectorType &temp_vector1,
3097 VectorType &temp_vector2,
3098 VectorType &solution)
3099 {
3100 if (iteration_index == 0)
3101 {
3102 solution.equ(factor2, rhs);
3103 preconditioner.vmult(solution_old, solution);
3104 }
3105 else if (iteration_index == 1)
3106 {
3107 // compute t = P^{-1} * (b-A*x^{n})
3108 temp_vector1.sadd(-1.0, 1.0, rhs);
3109 preconditioner.vmult(solution_old, temp_vector1);
3110
3111 // compute x^{n+1} = x^{n} + f_1 * x^{n} + f_2 * t
3112 solution_old.sadd(factor2, 1 + factor1, solution);
3113 }
3114 else
3115 {
3116 // compute t = P^{-1} * (b-A*x^{n})
3117 temp_vector1.sadd(-1.0, 1.0, rhs);
3118 preconditioner.vmult(temp_vector2, temp_vector1);
3119
3120 // compute x^{n+1} = x^{n} + f_1 * (x^{n}-x^{n-1}) + f_2 * t
3121 solution_old.sadd(-factor1, factor2, temp_vector2);
3122 solution_old.add(1 + factor1, solution);
3123 }
3124
3125 solution.swap(solution_old);
3126 }
3127
3128 // generic part for deal.II vectors
3129 template <
3130 typename Number,
3131 typename PreconditionerType,
3132 std::enable_if_t<
3133 !has_vmult_with_std_functions_for_precondition<
3134 PreconditionerType,
3135 LinearAlgebra::distributed::Vector<Number, MemorySpace::Host>>,
3136 int> * = nullptr>
3137 inline void
3138 vector_updates(
3139 const LinearAlgebra::distributed::Vector<Number, MemorySpace::Host> &rhs,
3140 const PreconditionerType &preconditioner,
3141 const unsigned int iteration_index,
3142 const double factor1_,
3143 const double factor2_,
3144 LinearAlgebra::distributed::Vector<Number, MemorySpace::Host>
3145 &solution_old,
3146 LinearAlgebra::distributed::Vector<Number, MemorySpace::Host>
3147 &temp_vector1,
3148 LinearAlgebra::distributed::Vector<Number, MemorySpace::Host>
3149 &temp_vector2,
3150 LinearAlgebra::distributed::Vector<Number, MemorySpace::Host> &solution)
3151 {
3152 const Number factor1 = factor1_;
3153 const Number factor1_plus_1 = 1. + factor1_;
3154 const Number factor2 = factor2_;
3155
3156 if (iteration_index == 0)
3157 {
3158 // compute t = P^{-1} * (b)
3159 preconditioner.vmult(solution_old, rhs);
3160
3161 // compute x^{n+1} = f_2 * t
3162 const auto solution_old_ptr = solution_old.begin();
3163 DEAL_II_OPENMP_SIMD_PRAGMA
3164 for (unsigned int i = 0; i < solution_old.locally_owned_size(); ++i)
3165 solution_old_ptr[i] = solution_old_ptr[i] * factor2;
3166 }
3167 else if (iteration_index == 1)
3168 {
3169 // compute t = P^{-1} * (b-A*x^{n})
3170 temp_vector1.sadd(-1.0, 1.0, rhs);
3171
3172 preconditioner.vmult(solution_old, temp_vector1);
3173
3174 // compute x^{n+1} = x^{n} + f_1 * x^{n} + f_2 * t
3175 const auto solution_ptr = solution.begin();
3176 const auto solution_old_ptr = solution_old.begin();
3177 DEAL_II_OPENMP_SIMD_PRAGMA
3178 for (unsigned int i = 0; i < solution_old.locally_owned_size(); ++i)
3179 solution_old_ptr[i] =
3180 factor1_plus_1 * solution_ptr[i] + solution_old_ptr[i] * factor2;
3181 }
3182 else
3183 {
3184 // compute t = P^{-1} * (b-A*x^{n})
3185 temp_vector1.sadd(-1.0, 1.0, rhs);
3186
3187 preconditioner.vmult(temp_vector2, temp_vector1);
3188
3189 // compute x^{n+1} = x^{n} + f_1 * (x^{n}-x^{n-1}) + f_2 * t
3190 const auto solution_ptr = solution.begin();
3191 const auto solution_old_ptr = solution_old.begin();
3192 const auto temp_vector2_ptr = temp_vector2.begin();
3193 DEAL_II_OPENMP_SIMD_PRAGMA
3194 for (unsigned int i = 0; i < solution_old.locally_owned_size(); ++i)
3195 solution_old_ptr[i] = factor1_plus_1 * solution_ptr[i] -
3196 factor1 * solution_old_ptr[i] +
3197 temp_vector2_ptr[i] * factor2;
3198 }
3199
3200 solution.swap(solution_old);
3201 }
3202
3203 template <
3204 typename Number,
3205 typename PreconditionerType,
3206 std::enable_if_t<
3207 has_vmult_with_std_functions_for_precondition<
3208 PreconditionerType,
3209 LinearAlgebra::distributed::Vector<Number, MemorySpace::Host>>,
3210 int> * = nullptr>
3211 inline void
3212 vector_updates(
3213 const LinearAlgebra::distributed::Vector<Number, MemorySpace::Host> &rhs,
3214 const PreconditionerType &preconditioner,
3215 const unsigned int iteration_index,
3216 const double factor1_,
3217 const double factor2_,
3218 LinearAlgebra::distributed::Vector<Number, MemorySpace::Host>
3219 &solution_old,
3220 LinearAlgebra::distributed::Vector<Number, MemorySpace::Host>
3221 &temp_vector1,
3222 LinearAlgebra::distributed::Vector<Number, MemorySpace::Host>
3223 &temp_vector2,
3224 LinearAlgebra::distributed::Vector<Number, MemorySpace::Host> &solution)
3225 {
3226 const Number factor1 = factor1_;
3227 const Number factor1_plus_1 = 1. + factor1_;
3228 const Number factor2 = factor2_;
3229
3230 const auto rhs_ptr = rhs.begin();
3231 const auto temp_vector1_ptr = temp_vector1.begin();
3232 const auto temp_vector2_ptr = temp_vector2.begin();
3233 const auto solution_ptr = solution.begin();
3234 const auto solution_old_ptr = solution_old.begin();
3235
3236 if (iteration_index == 0)
3237 {
3238 preconditioner.vmult(
3239 solution,
3240 rhs,
3241 [&](const auto start_range, const auto end_range) {
3242 if (end_range > start_range)
3243 std::memset(solution_ptr + start_range,
3244 0,
3245 sizeof(Number) * (end_range - start_range));
3246 },
3247 [&](const auto begin, const auto end) {
3248 DEAL_II_OPENMP_SIMD_PRAGMA
3249 for (std::size_t i = begin; i < end; ++i)
3250 solution_ptr[i] *= factor2;
3251 });
3252 }
3253 else
3254 {
3255 preconditioner.vmult(
3256 temp_vector2,
3257 temp_vector1,
3258 [&](const auto begin, const auto end) {
3259 if (end > begin)
3260 std::memset(temp_vector2_ptr + begin,
3261 0,
3262 sizeof(Number) * (end - begin));
3263
3264 DEAL_II_OPENMP_SIMD_PRAGMA
3265 for (std::size_t i = begin; i < end; ++i)
3266 temp_vector1_ptr[i] = rhs_ptr[i] - temp_vector1_ptr[i];
3267 },
3268 [&](const auto begin, const auto end) {
3269 if (iteration_index == 1)
3270 {
3271 DEAL_II_OPENMP_SIMD_PRAGMA
3272 for (std::size_t i = begin; i < end; ++i)
3273 temp_vector2_ptr[i] = factor1_plus_1 * solution_ptr[i] +
3274 factor2 * temp_vector2_ptr[i];
3275 }
3276 else
3277 {
3278 DEAL_II_OPENMP_SIMD_PRAGMA
3279 for (std::size_t i = begin; i < end; ++i)
3280 temp_vector2_ptr[i] = factor1_plus_1 * solution_ptr[i] -
3281 factor1 * solution_old_ptr[i] +
3282 factor2 * temp_vector2_ptr[i];
3283 }
3284 });
3285 }
3286
3287 if (iteration_index > 0)
3288 {
3289 solution_old.swap(temp_vector2);
3290 solution_old.swap(solution);
3291 }
3292 }
3293
3294 // worker routine for deal.II vectors. Because of vectorization, we need
3295 // to put the loop into an extra structure because the virtual function of
3296 // VectorUpdatesRange prevents the compiler from applying vectorization.
3297 template <typename Number>
3298 struct VectorUpdater
3299 {
3300 VectorUpdater(const Number *rhs,
3301 const Number *matrix_diagonal_inverse,
3302 const unsigned int iteration_index,
3303 const Number factor1,
3304 const Number factor2,
3305 Number *solution_old,
3306 Number *tmp_vector,
3307 Number *solution)
3308 : rhs(rhs)
3309 , matrix_diagonal_inverse(matrix_diagonal_inverse)
3310 , iteration_index(iteration_index)
3311 , factor1(factor1)
3312 , factor2(factor2)
3313 , solution_old(solution_old)
3314 , tmp_vector(tmp_vector)
3315 , solution(solution)
3316 {}
3317
3318 void
3319 apply_to_subrange(const std::size_t begin, const std::size_t end) const
3320 {
3321 // To circumvent a bug in gcc
3322 // (https://gcc.gnu.org/bugzilla/show_bug.cgi?id=63945), we create
3323 // copies of the variables factor1 and factor2 and do not check based on
3324 // factor1.
3325 const Number factor1 = this->factor1;
3326 const Number factor1_plus_1 = 1. + this->factor1;
3327 const Number factor2 = this->factor2;
3328 if (iteration_index == 0)
3329 {
3330 DEAL_II_OPENMP_SIMD_PRAGMA
3331 for (std::size_t i = begin; i < end; ++i)
3332 solution[i] = factor2 * matrix_diagonal_inverse[i] * rhs[i];
3333 }
3334 else if (iteration_index == 1)
3335 {
3336 // x^{n+1} = x^{n} + f_1 * x^{n} + f_2 * P^{-1} * (b-A*x^{n})
3337 DEAL_II_OPENMP_SIMD_PRAGMA
3338 for (std::size_t i = begin; i < end; ++i)
3339 // for efficiency reason, write back to temp_vector that is
3340 // already read (avoid read-for-ownership)
3341 tmp_vector[i] =
3342 factor1_plus_1 * solution[i] +
3343 factor2 * matrix_diagonal_inverse[i] * (rhs[i] - tmp_vector[i]);
3344 }
3345 else
3346 {
3347 // x^{n+1} = x^{n} + f_1 * (x^{n}-x^{n-1})
3348 // + f_2 * P^{-1} * (b-A*x^{n})
3349 DEAL_II_OPENMP_SIMD_PRAGMA
3350 for (std::size_t i = begin; i < end; ++i)
3351 // for efficiency reason, write back to temp_vector, which is
3352 // already modified during vmult (in best case, the modified
3353 // values are not written back to main memory yet so that
3354 // we do not have to pay additional costs for writing and
3355 // read-for-ownership)
3356 tmp_vector[i] =
3357 factor1_plus_1 * solution[i] - factor1 * solution_old[i] +
3358 factor2 * matrix_diagonal_inverse[i] * (rhs[i] - tmp_vector[i]);
3359 }
3360 }
3361
3362 const Number *rhs;
3363 const Number *matrix_diagonal_inverse;
3364 const unsigned int iteration_index;
3365 const Number factor1;
3366 const Number factor2;
3367 mutable Number *solution_old;
3368 mutable Number *tmp_vector;
3369 mutable Number *solution;
3370 };
3371
3372 template <typename Number>
3373 struct VectorUpdatesRange : public ::dealii::parallel::ParallelForInteger
3374 {
3375 VectorUpdatesRange(const VectorUpdater<Number> &updater,
3376 const std::size_t size)
3377 : updater(updater)
3378 {
3379 if (size < internal::VectorImplementation::minimum_parallel_grain_size)
3380 VectorUpdatesRange::apply_to_subrange(0, size);
3381 else
3382 apply_parallel(
3383 0,
3384 size,
3385 internal::VectorImplementation::minimum_parallel_grain_size);
3386 }
3387
3388 ~VectorUpdatesRange() override = default;
3389
3390 virtual void
3391 apply_to_subrange(const std::size_t begin,
3392 const std::size_t end) const override
3393 {
3394 updater.apply_to_subrange(begin, end);
3395 }
3396
3397 const VectorUpdater<Number> &updater;
3398 };
3399
3400 // selection for diagonal matrix around deal.II vector
3401 template <typename Number>
3402 inline void
3403 vector_updates(
3404 const ::dealii::Vector<Number> &rhs,
3405 const dealii::DiagonalMatrix<::dealii::Vector<Number>> &jacobi,
3406 const unsigned int iteration_index,
3407 const double factor1,
3408 const double factor2,
3409 ::dealii::Vector<Number> &solution_old,
3410 ::dealii::Vector<Number> &temp_vector1,
3411 ::dealii::Vector<Number> &,
3412 ::dealii::Vector<Number> &solution)
3413 {
3414 VectorUpdater<Number> upd(rhs.begin(),
3415 jacobi.get_vector().begin(),
3416 iteration_index,
3417 factor1,
3418 factor2,
3419 solution_old.begin(),
3420 temp_vector1.begin(),
3421 solution.begin());
3422 VectorUpdatesRange<Number>(upd, rhs.size());
3423
3424 // swap vectors x^{n+1}->x^{n}, given the updates in the function above
3425 if (iteration_index == 0)
3426 {
3427 // nothing to do here because we can immediately write into the
3428 // solution vector without remembering any of the other vectors
3429 }
3430 else
3431 {
3432 solution.swap(temp_vector1);
3433 solution_old.swap(temp_vector1);
3434 }
3435 }
3436
3437 // selection for diagonal matrix around parallel deal.II vector
3438 template <typename Number>
3439 inline void
3440 vector_updates(
3441 const LinearAlgebra::distributed::Vector<Number, MemorySpace::Host> &rhs,
3442 const dealii::DiagonalMatrix<
3443 LinearAlgebra::distributed::Vector<Number, MemorySpace::Host>> &jacobi,
3444 const unsigned int iteration_index,
3445 const double factor1,
3446 const double factor2,
3447 LinearAlgebra::distributed::Vector<Number, MemorySpace::Host>
3448 &solution_old,
3449 LinearAlgebra::distributed::Vector<Number, MemorySpace::Host>
3450 &temp_vector1,
3451 LinearAlgebra::distributed::Vector<Number, MemorySpace::Host> &,
3452 LinearAlgebra::distributed::Vector<Number, MemorySpace::Host> &solution)
3453 {
3454 VectorUpdater<Number> upd(rhs.begin(),
3455 jacobi.get_vector().begin(),
3456 iteration_index,
3457 factor1,
3458 factor2,
3459 solution_old.begin(),
3460 temp_vector1.begin(),
3461 solution.begin());
3462 VectorUpdatesRange<Number>(upd, rhs.locally_owned_size());
3463
3464 // swap vectors x^{n+1}->x^{n}, given the updates in the function above
3465 if (iteration_index == 0)
3466 {
3467 // nothing to do here because we can immediately write into the
3468 // solution vector without remembering any of the other vectors
3469 }
3470 else
3471 {
3472 solution.swap(temp_vector1);
3473 solution_old.swap(temp_vector1);
3474 }
3475 }
3476
3477 // We need to have a separate declaration for static const members
3478
3479 // general case and the case that the preconditioner can work on
3480 // ranges (covered by vector_updates())
3481 template <
3482 typename MatrixType,
3483 typename VectorType,
3484 typename PreconditionerType,
3485 std::enable_if_t<
3486 !has_vmult_with_std_functions<MatrixType,
3487 VectorType,
3488 PreconditionerType> &&
3489 !(has_vmult_with_std_functions_for_precondition<PreconditionerType,
3490 VectorType> &&
3491 has_vmult_with_std_functions_for_precondition<MatrixType,
3492 VectorType>),
3493 int> * = nullptr>
3494 inline void
3495 vmult_and_update(const MatrixType &matrix,
3496 const PreconditionerType &preconditioner,
3497 const VectorType &rhs,
3498 const unsigned int iteration_index,
3499 const double factor1,
3500 const double factor2,
3501 VectorType &solution,
3502 VectorType &solution_old,
3503 VectorType &temp_vector1,
3504 VectorType &temp_vector2)
3505 {
3506 if (iteration_index > 0)
3507 matrix.vmult(temp_vector1, solution);
3508 vector_updates(rhs,
3509 preconditioner,
3510 iteration_index,
3511 factor1,
3512 factor2,
3513 solution_old,
3514 temp_vector1,
3515 temp_vector2,
3516 solution);
3517 }
3518
3519 // case that both the operator and the preconditioner can work on
3520 // subranges
3521 template <
3522 typename MatrixType,
3523 typename VectorType,
3524 typename PreconditionerType,
3525 std::enable_if_t<
3526 !has_vmult_with_std_functions<MatrixType,
3527 VectorType,
3528 PreconditionerType> &&
3529 (has_vmult_with_std_functions_for_precondition<PreconditionerType,
3530 VectorType> &&
3531 has_vmult_with_std_functions_for_precondition<MatrixType,
3532 VectorType>),
3533 int> * = nullptr>
3534 inline void
3535 vmult_and_update(const MatrixType &matrix,
3536 const PreconditionerType &preconditioner,
3537 const VectorType &rhs,
3538 const unsigned int iteration_index,
3539 const double factor1_,
3540 const double factor2_,
3541 VectorType &solution,
3542 VectorType &solution_old,
3543 VectorType &temp_vector1,
3544 VectorType &temp_vector2)
3545 {
3546 using Number = typename VectorType::value_type;
3547
3548 const Number factor1 = factor1_;
3549 const Number factor1_plus_1 = 1. + factor1_;
3550 const Number factor2 = factor2_;
3551
3552 if (iteration_index == 0)
3553 {
3554 preconditioner.vmult(
3555 solution,
3556 rhs,
3557 [&](const unsigned int start_range, const unsigned int end_range) {
3558 // zero 'solution' before running the vmult operation
3559 if (end_range > start_range)
3560 std::memset(solution.begin() + start_range,
3561 0,
3562 sizeof(Number) * (end_range - start_range));
3563 },
3564 [&](const unsigned int start_range, const unsigned int end_range) {
3565 const auto solution_ptr = solution.begin();
3566
3567 DEAL_II_OPENMP_SIMD_PRAGMA
3568 for (std::size_t i = start_range; i < end_range; ++i)
3569 solution_ptr[i] *= factor2;
3570 });
3571 }
3572 else
3573 {
3574 temp_vector1.reinit(rhs, true);
3575 temp_vector2.reinit(rhs, true);
3576
3577 // 1) compute residual (including operator application)
3578 matrix.vmult(
3579 temp_vector1,
3580 solution,
3581 [&](const unsigned int start_range, const unsigned int end_range) {
3582 // zero 'temp_vector1' before running the vmult
3583 // operation
3584 if (end_range > start_range)
3585 std::memset(temp_vector1.begin() + start_range,
3586 0,
3587 sizeof(Number) * (end_range - start_range));
3588 },
3589 [&](const unsigned int start_range, const unsigned int end_range) {
3590 const auto rhs_ptr = rhs.begin();
3591 const auto tmp_ptr = temp_vector1.begin();
3592
3593 DEAL_II_OPENMP_SIMD_PRAGMA
3594 for (std::size_t i = start_range; i < end_range; ++i)
3595 tmp_ptr[i] = rhs_ptr[i] - tmp_ptr[i];
3596 });
3597
3598 // 2) perform vector updates (including preconditioner application)
3599 preconditioner.vmult(
3600 temp_vector2,
3601 temp_vector1,
3602 [&](const unsigned int start_range, const unsigned int end_range) {
3603 // zero 'temp_vector2' before running the vmult
3604 // operation
3605 if (end_range > start_range)
3606 std::memset(temp_vector2.begin() + start_range,
3607 0,
3608 sizeof(Number) * (end_range - start_range));
3609 },
3610 [&](const unsigned int start_range, const unsigned int end_range) {
3611 const auto solution_ptr = solution.begin();
3612 const auto solution_old_ptr = solution_old.begin();
3613 const auto tmp_ptr = temp_vector2.begin();
3614
3615 if (iteration_index == 1)
3616 {
3617 DEAL_II_OPENMP_SIMD_PRAGMA
3618 for (std::size_t i = start_range; i < end_range; ++i)
3619 tmp_ptr[i] =
3620 factor1_plus_1 * solution_ptr[i] + factor2 * tmp_ptr[i];
3621 }
3622 else
3623 {
3624 DEAL_II_OPENMP_SIMD_PRAGMA
3625 for (std::size_t i = start_range; i < end_range; ++i)
3626 tmp_ptr[i] = factor1_plus_1 * solution_ptr[i] -
3627 factor1 * solution_old_ptr[i] +
3628 factor2 * tmp_ptr[i];
3629 }
3630 });
3631
3632 solution.swap(temp_vector2);
3633 solution_old.swap(temp_vector2);
3634 }
3635 }
3636
3637 // case that the operator can work on subranges and the preconditioner
3638 // is a diagonal
3639 template <typename MatrixType,
3640 typename VectorType,
3641 typename PreconditionerType,
3642 std::enable_if_t<has_vmult_with_std_functions<MatrixType,
3643 VectorType,
3644 PreconditionerType>,
3645 int> * = nullptr>
3646 inline void
3647 vmult_and_update(const MatrixType &matrix,
3648 const PreconditionerType &preconditioner,
3649 const VectorType &rhs,
3650 const unsigned int iteration_index,
3651 const double factor1,
3652 const double factor2,
3653 VectorType &solution,
3654 VectorType &solution_old,
3655 VectorType &temp_vector1,
3656 VectorType &)
3657 {
3658 using Number = typename VectorType::value_type;
3659 VectorUpdater<Number> updater(rhs.begin(),
3660 preconditioner.get_vector().begin(),
3661 iteration_index,
3662 factor1,
3663 factor2,
3664 solution_old.begin(),
3665 temp_vector1.begin(),
3666 solution.begin());
3667 if (iteration_index > 0)
3668 matrix.vmult(
3669 temp_vector1,
3670 solution,
3671 [&](const unsigned int start_range, const unsigned int end_range) {
3672 // zero 'temp_vector1' before running the vmult
3673 // operation
3674 if (end_range > start_range)
3675 std::memset(temp_vector1.begin() + start_range,
3676 0,
3677 sizeof(Number) * (end_range - start_range));
3678 },
3679 [&](const unsigned int start_range, const unsigned int end_range) {
3680 if (end_range > start_range)
3681 updater.apply_to_subrange(start_range, end_range);
3682 });
3683 else
3684 updater.apply_to_subrange(0U, solution.locally_owned_size());
3685
3686 // swap vectors x^{n+1}->x^{n}, given the updates in the function above
3687 if (iteration_index == 0)
3688 {
3689 // nothing to do here because we can immediately write into the
3690 // solution vector without remembering any of the other vectors
3691 }
3692 else
3693 {
3694 solution.swap(temp_vector1);
3695 solution_old.swap(temp_vector1);
3696 }
3697 }
3698
3699 template <typename MatrixType, typename PreconditionerType>
3700 inline void
3701 initialize_preconditioner(
3702 const MatrixType & /*matrix*/,
3703 std::shared_ptr<PreconditionerType> &preconditioner)
3704 {
3705 (void)preconditioner;
3706 AssertThrow(preconditioner.get() != nullptr, ExcNotInitialized());
3707 }
3708
3709 template <typename MatrixType, typename VectorType>
3710 inline void
3711 initialize_preconditioner(
3712 const MatrixType &matrix,
3713 std::shared_ptr<dealii::DiagonalMatrix<VectorType>> &preconditioner)
3714 {
3715 if (preconditioner.get() == nullptr || preconditioner->m() != matrix.m())
3716 {
3717 if (preconditioner.get() == nullptr)
3718 preconditioner =
3719 std::make_shared<dealii::DiagonalMatrix<VectorType>>();
3720
3721 Assert(
3722 preconditioner->m() == 0,
3723 ExcMessage(
3724 "Preconditioner appears to be initialized but not sized correctly"));
3725
3726 // This part only works in serial
3727 if (preconditioner->m() != matrix.m())
3728 {
3729 preconditioner->get_vector().reinit(matrix.m());
3730 for (typename VectorType::size_type i = 0; i < matrix.m(); ++i)
3731 preconditioner->get_vector()(i) = 1. / matrix.el(i, i);
3732 }
3733 }
3734 }
3735 } // namespace PreconditionChebyshevImplementation
3736 } // namespace internal
3737
3738
3739
3740 template <typename MatrixType, typename VectorType, typename PreconditionerType>
3741 inline PreconditionChebyshev<MatrixType, VectorType, PreconditionerType>::
3742 AdditionalData::AdditionalData(const unsigned int degree,
3743 const double smoothing_range,
3744 const unsigned int eig_cg_n_iterations,
3745 const double eig_cg_residual,
3746 const double max_eigenvalue,
3747 const EigenvalueAlgorithm eigenvalue_algorithm,
3748 const PolynomialType polynomial_type)
3749 : internal::EigenvalueAlgorithmAdditionalData<PreconditionerType>(
3750 smoothing_range,
3751 eig_cg_n_iterations,
3752 eig_cg_residual,
3753 max_eigenvalue,
3754 eigenvalue_algorithm)
3755 , degree(degree)
3756 , polynomial_type(polynomial_type)
3757 {}
3758
3759
3760
3761 template <typename MatrixType, typename VectorType, typename PreconditionerType>
3762 inline PreconditionChebyshev<MatrixType, VectorType, PreconditionerType>::
3763 PreconditionChebyshev()
3764 : theta(1.)
3765 , delta(1.)
3766 , eigenvalues_are_initialized(false)
3767 {
3768 static_assert(
3769 std::is_same_v<size_type, typename VectorType::size_type>,
3770 "PreconditionChebyshev and VectorType must have the same size_type.");
3771 }
3772
3773
3774
3775 template <typename MatrixType, typename VectorType, typename PreconditionerType>
3776 inline void
3777 PreconditionChebyshev<MatrixType, VectorType, PreconditionerType>::initialize(
3778 const MatrixType &matrix,
3779 const AdditionalData &additional_data)
3780 {
3781 matrix_ptr = &matrix;
3782 data = additional_data;
3783 Assert(data.degree > 0,
3784 ExcMessage("The degree of the Chebyshev method must be positive."));
3785 internal::PreconditionChebyshevImplementation::initialize_preconditioner(
3786 matrix, data.preconditioner);
3787 eigenvalues_are_initialized = false;
3788 }
3789
3790
3791
3792 template <typename MatrixType, typename VectorType, typename PreconditionerType>
3793 inline void
3794 PreconditionChebyshev<MatrixType, VectorType, PreconditionerType>::clear()
3795 {
3796 eigenvalues_are_initialized = false;
3797 theta = delta = 1.0;
3798 matrix_ptr = nullptr;
3799 {
3800 VectorType empty_vector;
3801 solution_old.reinit(empty_vector);
3802 temp_vector1.reinit(empty_vector);
3803 temp_vector2.reinit(empty_vector);
3804 }
3805 data.preconditioner.reset();
3806 }
3807
3808
3809
3810 template <typename MatrixType, typename VectorType, typename PreconditionerType>
3811 inline typename internal::EigenvalueInformation
3812 PreconditionChebyshev<MatrixType, VectorType, PreconditionerType>::
3813 estimate_eigenvalues(const VectorType &src) const
3814 {
3815 Assert(eigenvalues_are_initialized == false, ExcInternalError());
3816
3817 solution_old.reinit(src);
3818 temp_vector1.reinit(src, true);
3819
3820 auto info = internal::estimate_eigenvalues<MatrixType>(
3821 data, matrix_ptr, solution_old, temp_vector1, data.degree);
3822
3823 const double alpha = (data.smoothing_range > 1. ?
3824 info.max_eigenvalue_estimate / data.smoothing_range :
3825 std::min(0.9 * info.max_eigenvalue_estimate,
3826 info.min_eigenvalue_estimate));
3827
3828 // in case the user set the degree to invalid unsigned int, we have to
3829 // determine the number of necessary iterations from the Chebyshev error
3830 // estimate, given the target tolerance specified by smoothing_range. This
3831 // estimate is based on the error formula given in section 5.1 of
3832 // R. S. Varga, Matrix iterative analysis, 2nd ed., Springer, 2009
3833 if (data.degree == numbers::invalid_unsigned_int)
3834 {
3835 const double actual_range = info.max_eigenvalue_estimate / alpha;
3836 const double sigma = (1. - std::sqrt(1. / actual_range)) /
3837 (1. + std::sqrt(1. / actual_range));
3838 const double eps = data.smoothing_range;
3839 const_cast<
3840 PreconditionChebyshev<MatrixType, VectorType, PreconditionerType> *>(
3841 this)
3842 ->data.degree =
3843 1 + static_cast<unsigned int>(
3844 std::log(1. / eps + std::sqrt(1. / eps / eps - 1.)) /
3845 std::log(1. / sigma));
3846 }
3847
3848 info.degree = data.degree;
3849
3850 const_cast<
3851 PreconditionChebyshev<MatrixType, VectorType, PreconditionerType> *>(this)
3852 ->delta =
3853 (data.polynomial_type == AdditionalData::PolynomialType::fourth_kind) ?
3854 (info.max_eigenvalue_estimate) :
3855 ((info.max_eigenvalue_estimate - alpha) * 0.5);
3856 const_cast<
3857 PreconditionChebyshev<MatrixType, VectorType, PreconditionerType> *>(this)
3858 ->theta = (info.max_eigenvalue_estimate + alpha) * 0.5;
3859
3860 // We do not need the second temporary vector in case we have a
3861 // DiagonalMatrix as preconditioner and use deal.II's own vectors
3862 using NumberType = typename VectorType::value_type;
3863 if (std::is_same_v<PreconditionerType, dealii::DiagonalMatrix<VectorType>> ==
3864 false ||
3865 (std::is_same_v<VectorType, dealii::Vector<NumberType>> == false &&
3866 ((std::is_same_v<
3867 VectorType,
3868 LinearAlgebra::distributed::Vector<NumberType, MemorySpace::Host>> ==
3869 false) ||
3870 (std::is_same_v<VectorType,
3871 LinearAlgebra::distributed::
3872 Vector<NumberType, MemorySpace::Default>> == false))))
3873 temp_vector2.reinit(src, true);
3874 else
3875 {
3876 VectorType empty_vector;
3877 temp_vector2.reinit(empty_vector);
3878 }
3879
3880 const_cast<
3881 PreconditionChebyshev<MatrixType, VectorType, PreconditionerType> *>(this)
3882 ->eigenvalues_are_initialized = true;
3883
3884 return info;
3885 }
3886
3887
3888
3889 template <typename MatrixType, typename VectorType, typename PreconditionerType>
3890 inline void
3891 PreconditionChebyshev<MatrixType, VectorType, PreconditionerType>::vmult(
3892 VectorType &solution,
3893 const VectorType &rhs) const
3894 {
3895 std::lock_guard<std::mutex> lock(mutex);
3896 if (eigenvalues_are_initialized == false)
3897 estimate_eigenvalues(rhs);
3898
3899 internal::PreconditionChebyshevImplementation::vmult_and_update(
3900 *matrix_ptr,
3901 *data.preconditioner,
3902 rhs,
3903 0,
3904 0.,
3905 (data.polynomial_type == AdditionalData::PolynomialType::fourth_kind) ?
3906 (4. / (3. * delta)) :
3907 (1. / theta),
3908 solution,
3909 solution_old,
3910 temp_vector1,
3911 temp_vector2);
3912
3913 // if delta is zero, we do not need to iterate because the updates will be
3914 // zero
3915 if (data.degree < 2 || std::abs(delta) < 1e-40)
3916 return;
3917
3918 double rhok = delta / theta, sigma = theta / delta;
3919 for (unsigned int k = 0; k < data.degree - 1; ++k)
3920 {
3921 double factor1 = 0.0;
3922 double factor2 = 0.0;
3923
3924 if (data.polynomial_type == AdditionalData::PolynomialType::fourth_kind)
3925 {
3926 factor1 = (2 * k + 1.) / (2 * k + 5.);
3927 factor2 = (8 * k + 12.) / (delta * (2 * k + 5.));
3928 }
3929 else
3930 {
3931 const double rhokp = 1. / (2. * sigma - rhok);
3932 factor1 = rhokp * rhok;
3933 factor2 = 2. * rhokp / delta;
3934 rhok = rhokp;
3935 }
3936
3937 internal::PreconditionChebyshevImplementation::vmult_and_update(
3938 *matrix_ptr,
3939 *data.preconditioner,
3940 rhs,
3941 k + 1,
3942 factor1,
3943 factor2,
3944 solution,
3945 solution_old,
3946 temp_vector1,
3947 temp_vector2);
3948 }
3949 }
3950
3951
3952
3953 template <typename MatrixType, typename VectorType, typename PreconditionerType>
3954 inline void
3955 PreconditionChebyshev<MatrixType, VectorType, PreconditionerType>::Tvmult(
3956 VectorType &solution,
3957 const VectorType &rhs) const
3958 {
3959 std::lock_guard<std::mutex> lock(mutex);
3960 if (eigenvalues_are_initialized == false)
3961 estimate_eigenvalues(rhs);
3962
3963 internal::PreconditionChebyshevImplementation::vector_updates(
3964 rhs,
3965 *data.preconditioner,
3966 0,
3967 0.,
3968 (data.polynomial_type == AdditionalData::PolynomialType::fourth_kind) ?
3969 (4. / (3. * delta)) :
3970 (1. / theta),
3971 solution_old,
3972 temp_vector1,
3973 temp_vector2,
3974 solution);
3975
3976 if (data.degree < 2 || std::abs(delta) < 1e-40)
3977 return;
3978
3979 double rhok = delta / theta, sigma = theta / delta;
3980 for (unsigned int k = 0; k < data.degree - 1; ++k)
3981 {
3982 double factor1 = 0.0;
3983 double factor2 = 0.0;
3984
3985 if (data.polynomial_type == AdditionalData::PolynomialType::fourth_kind)
3986 {
3987 factor1 = (2 * k + 1.) / (2 * k + 5.);
3988 factor2 = (8 * k + 12.) / (delta * (2 * k + 5.));
3989 }
3990 else
3991 {
3992 const double rhokp = 1. / (2. * sigma - rhok);
3993 factor1 = rhokp * rhok;
3994 factor2 = 2. * rhokp / delta;
3995 rhok = rhokp;
3996 }
3997
3998 matrix_ptr->Tvmult(temp_vector1, solution);
3999 internal::PreconditionChebyshevImplementation::vector_updates(
4000 rhs,
4001 *data.preconditioner,
4002 k + 1,
4003 factor1,
4004 factor2,
4005 solution_old,
4006 temp_vector1,
4007 temp_vector2,
4008 solution);
4009 }
4010 }
4011
4012
4013
4014 template <typename MatrixType, typename VectorType, typename PreconditionerType>
4015 inline void
4016 PreconditionChebyshev<MatrixType, VectorType, PreconditionerType>::step(
4017 VectorType &solution,
4018 const VectorType &rhs) const
4019 {
4020 std::lock_guard<std::mutex> lock(mutex);
4021 if (eigenvalues_are_initialized == false)
4022 estimate_eigenvalues(rhs);
4023
4024 internal::PreconditionChebyshevImplementation::vmult_and_update(
4025 *matrix_ptr,
4026 *data.preconditioner,
4027 rhs,
4028 1,
4029 0.,
4030 (data.polynomial_type == AdditionalData::PolynomialType::fourth_kind) ?
4031 (4. / (3. * delta)) :
4032 (1. / theta),
4033 solution,
4034 solution_old,
4035 temp_vector1,
4036 temp_vector2);
4037
4038 if (data.degree < 2 || std::abs(delta) < 1e-40)
4039 return;
4040
4041 double rhok = delta / theta, sigma = theta / delta;
4042 for (unsigned int k = 0; k < data.degree - 1; ++k)
4043 {
4044 double factor1 = 0.0;
4045 double factor2 = 0.0;
4046
4047 if (data.polynomial_type == AdditionalData::PolynomialType::fourth_kind)
4048 {
4049 factor1 = (2 * k + 1.) / (2 * k + 5.);
4050 factor2 = (8 * k + 12.) / (delta * (2 * k + 5.));
4051 }
4052 else
4053 {
4054 const double rhokp = 1. / (2. * sigma - rhok);
4055 factor1 = rhokp * rhok;
4056 factor2 = 2. * rhokp / delta;
4057 rhok = rhokp;
4058 }
4059
4060 internal::PreconditionChebyshevImplementation::vmult_and_update(
4061 *matrix_ptr,
4062 *data.preconditioner,
4063 rhs,
4064 k + 2,
4065 factor1,
4066 factor2,
4067 solution,
4068 solution_old,
4069 temp_vector1,
4070 temp_vector2);
4071 }
4072 }
4073
4074
4075
4076 template <typename MatrixType, typename VectorType, typename PreconditionerType>
4077 inline void
4078 PreconditionChebyshev<MatrixType, VectorType, PreconditionerType>::Tstep(
4079 VectorType &solution,
4080 const VectorType &rhs) const
4081 {
4082 std::lock_guard<std::mutex> lock(mutex);
4083 if (eigenvalues_are_initialized == false)
4084 estimate_eigenvalues(rhs);
4085
4086 matrix_ptr->Tvmult(temp_vector1, solution);
4087 internal::PreconditionChebyshevImplementation::vector_updates(
4088 rhs,
4089 *data.preconditioner,
4090 1,
4091 0.,
4092 (data.polynomial_type == AdditionalData::PolynomialType::fourth_kind) ?
4093 (4. / (3. * delta)) :
4094 (1. / theta),
4095 solution_old,
4096 temp_vector1,
4097 temp_vector2,
4098 solution);
4099
4100 if (data.degree < 2 || std::abs(delta) < 1e-40)
4101 return;
4102
4103 double rhok = delta / theta, sigma = theta / delta;
4104 for (unsigned int k = 0; k < data.degree - 1; ++k)
4105 {
4106 double factor1 = 0.0;
4107 double factor2 = 0.0;
4108
4109 if (data.polynomial_type == AdditionalData::PolynomialType::fourth_kind)
4110 {
4111 factor1 = (2 * k + 1.) / (2 * k + 5.);
4112 factor2 = (8 * k + 12.) / (delta * (2 * k + 5.));
4113 }
4114 else
4115 {
4116 const double rhokp = 1. / (2. * sigma - rhok);
4117 factor1 = rhokp * rhok;
4118 factor2 = 2. * rhokp / delta;
4119 rhok = rhokp;
4120 }
4121
4122 matrix_ptr->Tvmult(temp_vector1, solution);
4123 internal::PreconditionChebyshevImplementation::vector_updates(
4124 rhs,
4125 *data.preconditioner,
4126 k + 2,
4127 factor1,
4128 factor2,
4129 solution_old,
4130 temp_vector1,
4131 temp_vector2,
4132 solution);
4133 }
4134 }
4135
4136
4137
4138 template <typename MatrixType, typename VectorType, typename PreconditionerType>
4139 inline typename PreconditionChebyshev<MatrixType,
4140 VectorType,
4141 PreconditionerType>::size_type
4142 PreconditionChebyshev<MatrixType, VectorType, PreconditionerType>::m() const
4143 {
4144 Assert(matrix_ptr != nullptr, ExcNotInitialized());
4145 return matrix_ptr->m();
4146 }
4147
4148
4149
4150 template <typename MatrixType, typename VectorType, typename PreconditionerType>
4151 inline typename PreconditionChebyshev<MatrixType,
4152 VectorType,
4153 PreconditionerType>::size_type
4154 PreconditionChebyshev<MatrixType, VectorType, PreconditionerType>::n() const
4155 {
4156 Assert(matrix_ptr != nullptr, ExcNotInitialized());
4157 return matrix_ptr->n();
4158 }
4159
4160 #endif // DOXYGEN
4161
4162 DEAL_II_NAMESPACE_CLOSE
4163
4164 #endif