| 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_solver_gmres_h |
| 16 |
#define dealii_solver_gmres_h |
| 17 |
|
| 18 |
|
| 19 |
|
| 20 |
#include <deal.II/base/config.h> |
| 21 |
|
| 22 |
#include <deal.II/base/enable_observer_pointer.h> |
| 23 |
#include <deal.II/base/logstream.h> |
| 24 |
#include <deal.II/base/template_constraints.h> |
| 25 |
|
| 26 |
#include <deal.II/lac/block_vector_base.h> |
| 27 |
#include <deal.II/lac/full_matrix.h> |
| 28 |
#include <deal.II/lac/lapack_full_matrix.h> |
| 29 |
#include <deal.II/lac/orthogonalization.h> |
| 30 |
#include <deal.II/lac/solver.h> |
| 31 |
#include <deal.II/lac/solver_control.h> |
| 32 |
#include <deal.II/lac/vector.h> |
| 33 |
|
| 34 |
#include <boost/signals2/signal.hpp> |
| 35 |
|
| 36 |
#include <algorithm> |
| 37 |
#include <cmath> |
| 38 |
#include <limits> |
| 39 |
#include <memory> |
| 40 |
#include <utility> |
| 41 |
#include <vector> |
| 42 |
|
| 43 |
DEAL_II_NAMESPACE_OPEN |
| 44 |
|
| 45 |
// forward declarations |
| 46 |
#ifndef DOXYGEN |
| 47 |
namespace LinearAlgebra |
| 48 |
{ |
| 49 |
namespace distributed |
| 50 |
{ |
| 51 |
template <typename, typename> |
| 52 |
class Vector; |
| 53 |
} // namespace distributed |
| 54 |
} // namespace LinearAlgebra |
| 55 |
#endif |
| 56 |
|
| 57 |
/** |
| 58 |
* @addtogroup Solvers |
| 59 |
* @{ |
| 60 |
*/ |
| 61 |
|
| 62 |
namespace internal |
| 63 |
{ |
| 64 |
/** |
| 65 |
* A namespace for helper classes and functions of the GMRES solver. |
| 66 |
*/ |
| 67 |
namespace SolverGMRESImplementation |
| 68 |
{ |
| 69 |
/** |
| 70 |
* Class to hold temporary vectors. This class automatically allocates a |
| 71 |
* new vector, once it is needed. |
| 72 |
* |
| 73 |
* A future version should also be able to shift through vectors |
| 74 |
* automatically, avoiding restart. |
| 75 |
*/ |
| 76 |
template <typename VectorType> |
| 77 |
class TmpVectors |
| 78 |
{ |
| 79 |
public: |
| 80 |
/** |
| 81 |
* Constructor. Prepares an array of @p VectorType of length @p |
| 82 |
* max_size. |
| 83 |
*/ |
| 84 |
TmpVectors(const unsigned int max_size, VectorMemory<VectorType> &vmem); |
| 85 |
|
| 86 |
/** |
| 87 |
* Destructor. Delete all allocated vectors. |
| 88 |
*/ |
| 89 |
~TmpVectors() = default; |
| 90 |
|
| 91 |
/** |
| 92 |
* Get vector number @p i. If this vector was unused before, an error |
| 93 |
* occurs. |
| 94 |
*/ |
| 95 |
VectorType & |
| 96 |
operator[](const unsigned int i) const; |
| 97 |
|
| 98 |
/** |
| 99 |
* Get vector number @p i. Allocate it if necessary. |
| 100 |
* |
| 101 |
* If a vector must be allocated, @p temp is used to reinit it to the |
| 102 |
* proper dimensions. |
| 103 |
*/ |
| 104 |
VectorType & |
| 105 |
operator()(const unsigned int i, const VectorType &temp); |
| 106 |
|
| 107 |
/** |
| 108 |
* Return size of data vector. It is used in the solver to store |
| 109 |
* the Arnoldi vectors. |
| 110 |
*/ |
| 111 |
unsigned int |
| 112 |
size() const; |
| 113 |
|
| 114 |
|
| 115 |
private: |
| 116 |
/** |
| 117 |
* Pool where vectors are obtained from. |
| 118 |
*/ |
| 119 |
VectorMemory<VectorType> &mem; |
| 120 |
|
| 121 |
/** |
| 122 |
* Field for storing the vectors. |
| 123 |
*/ |
| 124 |
std::vector<typename VectorMemory<VectorType>::Pointer> data; |
| 125 |
}; |
| 126 |
|
| 127 |
|
| 128 |
|
| 129 |
/** |
| 130 |
* Class that performs the Arnoldi orthogonalization process within the |
| 131 |
* SolverGMRES, SolverFGMRES, and SolverMPGMRES classes. It uses one of |
| 132 |
* the algorithms in LinearAlgebra::OrthogonalizationStrategy for the |
| 133 |
* work on the global vectors, transforms the resulting Hessenberg |
| 134 |
* matrix into an upper triangular matrix by Givens rotations, and |
| 135 |
* eventually solves the minimization problem in the projected Krylov |
| 136 |
* space. |
| 137 |
*/ |
| 138 |
template <typename Number> |
| 139 |
class ArnoldiProcess |
| 140 |
{ |
| 141 |
public: |
| 142 |
/** |
| 143 |
* Initialize the data structures in this class with the given |
| 144 |
* parameters for the solution process. |
| 145 |
*/ |
| 146 |
void |
| 147 |
initialize(const LinearAlgebra::OrthogonalizationStrategy |
| 148 |
orthogonalization_strategy, |
| 149 |
const unsigned int max_basis_size, |
| 150 |
const bool force_reorthogonalization); |
| 151 |
|
| 152 |
/** |
| 153 |
* Orthonormalize the vector at the position @p n within the array |
| 154 |
* @p orthogonal_vectors against the @p n orthonormal vectors with |
| 155 |
* indices <tt>0, ..., n - 1</tt> using the modified or classical |
| 156 |
* Gram-Schmidt algorithm. The class internally stores the factors used |
| 157 |
* for orthogonalization in an upper Hessenberg matrix. For the |
| 158 |
* classical Gram-Schmidt and modified Gram-Schmidt algorithms, loss of |
| 159 |
* orthogonality is checked every fifth step (in case it is not yet |
| 160 |
* already set via the initialize() function). In case this is detected, |
| 161 |
* all subsequent iterations use re-orthogonalization as stored |
| 162 |
* internally in this class, and a call to the optional signal is made. |
| 163 |
* |
| 164 |
* Note that the projected Hessenberg matrix and its factorization are |
| 165 |
* only consistent if @p n is incremented by one for each successive |
| 166 |
* call, or if @p n is zero when starting to build a new orthogonal |
| 167 |
* basis in restarted GMRES; an assertion will be raised if this |
| 168 |
* assumption is not fulfilled. |
| 169 |
* |
| 170 |
* Within this function, the factors for the QR factorization are |
| 171 |
* computed alongside the Hessenberg matrix, and an estimate of the |
| 172 |
* residual in the subspace is returned from this function. |
| 173 |
*/ |
| 174 |
template <typename VectorType> |
| 175 |
double |
| 176 |
orthonormalize_nth_vector( |
| 177 |
const unsigned int n, |
| 178 |
TmpVectors<VectorType> &orthogonal_vectors, |
| 179 |
const unsigned int accumulated_iterations = 0, |
| 180 |
const boost::signals2::signal<void(int)> &reorthogonalize_signal = |
| 181 |
boost::signals2::signal<void(int)>()); |
| 182 |
|
| 183 |
/** |
| 184 |
* Using the matrix and right hand side computed during the |
| 185 |
* factorization, solve the underlying minimization problem for the |
| 186 |
* residual in the Krylov space, returning the resulting solution as a |
| 187 |
* const reference. Note that the dimension of the vector is set to the |
| 188 |
* size of the Krylov space. |
| 189 |
*/ |
| 190 |
const Vector<double> & |
| 191 |
solve_projected_system(const bool orthogonalization_finished); |
| 192 |
|
| 193 |
/** |
| 194 |
* Return the upper Hessenberg matrix resulting from the |
| 195 |
* Gram-Schmidt orthogonalization process. |
| 196 |
*/ |
| 197 |
const FullMatrix<double> & |
| 198 |
get_hessenberg_matrix() const; |
| 199 |
|
| 200 |
/** |
| 201 |
* Temporary vector to implement work for deal.II vector types |
| 202 |
*/ |
| 203 |
std::vector<const Number *> vector_ptrs; |
| 204 |
|
| 205 |
private: |
| 206 |
/** |
| 207 |
* Projected system matrix in upper Hessenberg form. |
| 208 |
*/ |
| 209 |
FullMatrix<double> hessenberg_matrix; |
| 210 |
|
| 211 |
/** |
| 212 |
* Upper triangular matrix that results from performing the QR |
| 213 |
* factorization with Givens rotations on the upper Hessenberg matrix; the |
| 214 |
* matrix Q is contained in the array givens_rotations. |
| 215 |
*/ |
| 216 |
FullMatrix<double> triangular_matrix; |
| 217 |
|
| 218 |
/** |
| 219 |
* Representation of the factor Q in the QR factorization of the |
| 220 |
* Hessenberg matrix. |
| 221 |
*/ |
| 222 |
std::vector<std::pair<double, double>> givens_rotations; |
| 223 |
|
| 224 |
/** |
| 225 |
* Right-hand side vector for orthogonalization. |
| 226 |
*/ |
| 227 |
Vector<double> projected_rhs; |
| 228 |
|
| 229 |
/** |
| 230 |
* Solution vector when computing the minimization in the projected |
| 231 |
* Krylov space. |
| 232 |
*/ |
| 233 |
Vector<double> projected_solution; |
| 234 |
|
| 235 |
/** |
| 236 |
* Auxiliary vector for orthogonalization. |
| 237 |
*/ |
| 238 |
Vector<double> h; |
| 239 |
|
| 240 |
/** |
| 241 |
* Flag to keep track reorthogonalization, which is checked every fifth |
| 242 |
* iteration by default for |
| 243 |
* LinearAlgebra::OrthogonalizationStrategy::classical_gram_schmidt and |
| 244 |
* LinearAlgebra::OrthogonalizationStrategy::modified_gram_schmidt; for |
| 245 |
* LinearAlgebra::OrthogonalizationStrategy::delayed_classical_gram_schmidt, |
| 246 |
* no check is made. |
| 247 |
*/ |
| 248 |
bool do_reorthogonalization; |
| 249 |
|
| 250 |
/** |
| 251 |
* Selected orthogonalization algorithm. |
| 252 |
*/ |
| 253 |
LinearAlgebra::OrthogonalizationStrategy orthogonalization_strategy; |
| 254 |
|
| 255 |
/** |
| 256 |
* This is a helper function to perform the incremental computation of |
| 257 |
* the QR factorization of the Hessenberg matrix involved in the Arnoldi |
| 258 |
* process. More precisely, it transforms the member variable |
| 259 |
* @p hessenberg_matrix into an upper triangular matrix R labeled |
| 260 |
* @p matrix, an orthogonal matrix Q represented by a vector of Givens |
| 261 |
* rotations, and the associated right hand side to minimize the norm of |
| 262 |
* the solution in the Krylov subspace. |
| 263 |
* |
| 264 |
* More precisely, this function is called once a new column is added to |
| 265 |
* the Hessenberg matrix and performs all necessary steps for that |
| 266 |
* column. First, all evaluations with the Givens rotations resulting |
| 267 |
* from the previous elimination steps are performed. Then, the single |
| 268 |
* additional entry below the diagonal in the Hessenberg matrix is |
| 269 |
* eliminated by a Givens rotation, appending a new pair of Givens |
| 270 |
* factors, and the right-hand side vector in the projected system is |
| 271 |
* updated. The column number @p col for which the Gram-Schmidt should |
| 272 |
* run needs to be given, because the algorithmic variant with delayed |
| 273 |
* orthogonalization might lag by one step compared to the other sizes |
| 274 |
* in the problem, and needs to perform additional computations. |
| 275 |
* |
| 276 |
* In most cases, the matrices and vectors passed to this function are |
| 277 |
* the member variables of the present class, but also other scenarios |
| 278 |
* are supported. The function returns the modulus of the last entry in |
| 279 |
* the transformed right-hand side, which is the obtained residual of |
| 280 |
* the global vector x after minimization within the Krylov space. |
| 281 |
*/ |
| 282 |
double |
| 283 |
do_givens_rotation(const bool delayed_reorthogonalization, |
| 284 |
const int col, |
| 285 |
FullMatrix<double> &matrix, |
| 286 |
std::vector<std::pair<double, double>> &rotations, |
| 287 |
Vector<double> &rhs); |
| 288 |
}; |
| 289 |
} // namespace SolverGMRESImplementation |
| 290 |
} // namespace internal |
| 291 |
|
| 292 |
|
| 293 |
|
| 294 |
/** |
| 295 |
* Implementation of the Restarted Preconditioned Direct Generalized Minimal |
| 296 |
* Residual Method (GMRES). The stopping criterion is the norm of the residual. |
| 297 |
* |
| 298 |
* The AdditionalData structure allows to control the size of the Arnoldi |
| 299 |
* basis used for orthogonalization (default: 30 vectors). It is related to |
| 300 |
* the number of temporary vectors used, which is the basis size plus |
| 301 |
* two. Additionally, it allows you to choose between right or left |
| 302 |
* preconditioning (default: left preconditioning). Furthermore, it |
| 303 |
* includes a flag indicating whether or not the default residual is used as |
| 304 |
* stopping criterion and an option for the orthogonalization algorithm, see |
| 305 |
* LinearAlgebra::OrthogonalizationStrategy for available options. |
| 306 |
* |
| 307 |
* |
| 308 |
* <h3>Left versus right preconditioning</h3> |
| 309 |
* |
| 310 |
* @p AdditionalData allows you to choose between left and right |
| 311 |
* preconditioning. Left preconditioning, conceptually, corresponds to |
| 312 |
* replacing the linear system $Ax=b$ by $P^{-1}Ax=P^{-1}b$ where |
| 313 |
* $P^{-1}$ is the preconditioner (i.e., an approximation of |
| 314 |
* $A^{-1}$). In contrast, right preconditioning should be understood |
| 315 |
* as replacing $Ax=b$ by $AP^{-1}y=b$, solving for $y$, and then |
| 316 |
* computing the solution of the original problem as $x=P^{-1}y$. Note |
| 317 |
* that in either case, $P^{-1}$ is simply an operator that can be |
| 318 |
* applied to a vector; that is, it is not the inverse of some |
| 319 |
* operator that also separately has to be available. In practice, |
| 320 |
* $P^{-1}$ should be an operator that approximates multiplying by |
| 321 |
* $A^{-1}$. |
| 322 |
* |
| 323 |
* The choice between left and right preconditioning also affects |
| 324 |
* which kind of residual is used to measure convergence. With left |
| 325 |
* preconditioning, this is the <b>preconditioned</b> residual |
| 326 |
* $r_k=P^{-1}b-P^{-1}Ax_k$ given the approximate solution $x_k$ in |
| 327 |
* the $k$th iteration, while with right preconditioning, it is the |
| 328 |
* residual $r_k=b-Ax_k$ of the unpreconditioned system. |
| 329 |
* |
| 330 |
* Optionally, this behavior can be overridden by using the flag |
| 331 |
* AdditionalData::use_default_residual. A <tt>true</tt> value refers to the |
| 332 |
* behavior described in the previous paragraph, while <tt>false</tt> reverts |
| 333 |
* it. Be aware though that additional residuals have to be computed in this |
| 334 |
* case, impeding the overall performance of the solver. |
| 335 |
* |
| 336 |
* |
| 337 |
* <h3> Preconditioners need to be linear operators </h3> |
| 338 |
* |
| 339 |
* GMRES expects the preconditioner to be a *linear* operator, i.e., |
| 340 |
* the operator $P^{-1}$ used as preconditioner needs to satisfy |
| 341 |
* $P^{-1}(x+y) = P^{-1}x + P^{-1}y$ and $P^{-1}(\alpha x) = \alpha |
| 342 |
* P^{-1}x$. For many preconditioners, this is true. For example, if |
| 343 |
* you used Jacobi preconditioning, then $P^{-1}$ is a diagonal matrix |
| 344 |
* whose diagonal entries equal $\frac{1}{A_{ii}}$. In this case, the |
| 345 |
* operator $P^{-1}$ is clearly linear since it is simply the |
| 346 |
* multiplication of a given vector by a fixed matrix. |
| 347 |
* |
| 348 |
* On the other hand, if $P^{-1}$ involves more complicated |
| 349 |
* operations, it is sometimes *not* linear. The typical case to |
| 350 |
* illustrate this is where $A$ is a block matrix and $P^{-1}$ |
| 351 |
* involves multiplication with blocks (as done, for example, in |
| 352 |
* step-20, step-22, and several other preconditioners) where one |
| 353 |
* block involves a linear solve. For example, in a Stokes problem, |
| 354 |
* the preconditioner may involve a linear solve with the upper left |
| 355 |
* $A_{uu}$ block. If this linear solve is done exactly (e.g., via a |
| 356 |
* direct solver, or an iterative solver with a very tight tolerance), |
| 357 |
* then the linear solve corresponds to multiplying by $A^{-1}_{uu}$, |
| 358 |
* which is a linear operation. On the other hand, if one uses an |
| 359 |
* iterative solver with a loose tolerance (e.g., |
| 360 |
* `1e-3*right_hand_side.l2_norm()`), then many solvers like CG will |
| 361 |
* find the solution in a Krylov subspace of fairly low dimension; |
| 362 |
* crucially, this subspace is built iteratively starting with the |
| 363 |
* initial residual -- in other words, the *subspace depends on the |
| 364 |
* right hand side*, and consequently the solution returned by such a |
| 365 |
* solver *is not a linear operation on the given right hand side* of |
| 366 |
* the linear system being solved. |
| 367 |
* |
| 368 |
* In cases such as these, the preconditioner with its inner, inexact |
| 369 |
* linear solve is not a linear operator. This violates the |
| 370 |
* assumptions of GMRES, and often leads to unnecessarily many GMRES |
| 371 |
* iterations. The solution is to use the SolverFGMRES class instead, |
| 372 |
* which does not rely on the assumption that the preconditioner is a |
| 373 |
* linear operator, and instead explicitly does the extra work |
| 374 |
* necessary to satisfy the assumptions that lead GMRES to implicitly |
| 375 |
* require a linear operator as preconditioner. |
| 376 |
* |
| 377 |
* |
| 378 |
* <h3>The size of the Arnoldi basis</h3> |
| 379 |
* |
| 380 |
* The maximal basis size is controlled by AdditionalData::max_basis_size. If |
| 381 |
* the number of iteration steps exceeds this number, all basis vectors are |
| 382 |
* discarded and the iteration starts anew from the approximation obtained so |
| 383 |
* far. This algorithm strategy is typically called restarted GMRES method. |
| 384 |
* |
| 385 |
* Note that the minimizing property of GMRES only pertains to the Krylov |
| 386 |
* space spanned by the Arnoldi basis. Therefore, restarted GMRES is |
| 387 |
* <b>not</b> minimizing anymore. The choice of the basis length is a |
| 388 |
* trade-off between memory consumption and convergence speed, since a longer |
| 389 |
* basis means minimization over a larger space. |
| 390 |
* |
| 391 |
* For the requirements on matrices and vectors in order to work with this |
| 392 |
* class, see the documentation of the Solver base class. |
| 393 |
* |
| 394 |
* |
| 395 |
* <h3>Observing the progress of linear solver iterations</h3> |
| 396 |
* |
| 397 |
* The solve() function of this class uses the mechanism described in the |
| 398 |
* Solver base class to determine convergence. This mechanism can also be used |
| 399 |
* to observe the progress of the iteration. |
| 400 |
* |
| 401 |
* |
| 402 |
* <h3>Eigenvalue and condition number estimates</h3> |
| 403 |
* |
| 404 |
* This class can estimate eigenvalues and condition number during the |
| 405 |
* solution process. This is done by creating the Hessenberg matrix during the |
| 406 |
* inner iterations. The eigenvalues are estimated as the eigenvalues of the |
| 407 |
* Hessenberg matrix and the condition number is estimated as the ratio of the |
| 408 |
* largest and smallest singular value of the Hessenberg matrix. The estimates |
| 409 |
* can be obtained by connecting a function as a slot using @p |
| 410 |
* connect_condition_number_slot and @p connect_eigenvalues_slot. These slots |
| 411 |
* will then be called from the solver with the estimates as argument. |
| 412 |
*/ |
| 413 |
template <typename VectorType = Vector<double>> |
| 414 |
DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>) |
| 415 |
class SolverGMRES : public SolverBase<VectorType> |
| 416 |
{ |
| 417 |
public: |
| 418 |
/** |
| 419 |
* Standardized data struct to pipe additional data to the solver. |
| 420 |
*/ |
| 421 |
struct AdditionalData |
| 422 |
{ |
| 423 |
/** |
| 424 |
* Constructor. By default, set the size of the Arnoldi basis to 30. Also |
| 425 |
* set preconditioning from left, the residual of the stopping criterion |
| 426 |
* to the default residual, and re-orthogonalization only if |
| 427 |
* necessary. Also, the batched mode with reduced functionality to track |
| 428 |
* information is disabled by default. Finally, the default |
| 429 |
* orthogonalization algorithm is the classical Gram-Schmidt method with |
| 430 |
* delayed reorthogonalization, which combines stability with fast |
| 431 |
* execution, especially in parallel. |
| 432 |
*/ |
| 433 |
explicit AdditionalData(const unsigned int max_basis_size = 30, |
| 434 |
const bool right_preconditioning = false, |
| 435 |
const bool use_default_residual = true, |
| 436 |
const bool force_re_orthogonalization = false, |
| 437 |
const bool batched_mode = false, |
| 438 |
const LinearAlgebra::OrthogonalizationStrategy |
| 439 |
orthogonalization_strategy = |
| 440 |
LinearAlgebra::OrthogonalizationStrategy:: |
| 441 |
delayed_classical_gram_schmidt); |
| 442 |
|
| 443 |
/** |
| 444 |
* Maximum number of temporary vectors. Together with max_basis_size, this |
| 445 |
* parameter controls the size of the Arnoldi basis, which corresponds to |
| 446 |
* max_n_tmp_vectors-2 as used in previous versions of the deal.II |
| 447 |
* library. SolverGMRES assumes that there are at least three temporary |
| 448 |
* vectors, so this value must be greater than or equal to three. If both |
| 449 |
* this variable and max_basis_size are set to a non-zero value, the |
| 450 |
* choice in max_basis_size takes precedence. |
| 451 |
* |
| 452 |
* @deprecated Use max_basis_size instead. |
| 453 |
*/ |
| 454 |
unsigned int max_n_tmp_vectors; |
| 455 |
|
| 456 |
/** |
| 457 |
* Maximum size of the Arnoldi basis. SolverGMRES assumes that there is at |
| 458 |
* least one vector in the Arnoldi basis, so this value must be greater |
| 459 |
* than or equal to one. Note that whenever this variable is set to a |
| 460 |
* non-zero value, including the value set by the default constructor, |
| 461 |
* this variable takes precedence over max_n_tmp_vectors. |
| 462 |
*/ |
| 463 |
unsigned int max_basis_size; |
| 464 |
|
| 465 |
/** |
| 466 |
* Flag for right preconditioning. |
| 467 |
* |
| 468 |
* @note Change between left and right preconditioning will also change |
| 469 |
* the way residuals are evaluated. See the corresponding section in the |
| 470 |
* SolverGMRES. |
| 471 |
*/ |
| 472 |
bool right_preconditioning; |
| 473 |
|
| 474 |
/** |
| 475 |
* Flag for the default residual that is used to measure convergence. |
| 476 |
*/ |
| 477 |
bool use_default_residual; |
| 478 |
|
| 479 |
/** |
| 480 |
* Flag to force re-orthogonalization of orthonormal basis in every step. |
| 481 |
* If set to false, the solver automatically checks for loss of |
| 482 |
* orthogonality every 5 iterations and enables re-orthogonalization only |
| 483 |
* if necessary. |
| 484 |
*/ |
| 485 |
bool force_re_orthogonalization; |
| 486 |
|
| 487 |
/** |
| 488 |
* Flag to control whether a reduced mode of the solver should be |
| 489 |
* run. This is necessary when running (several) SolverGMRES instances |
| 490 |
* involving very small and cheap linear systems where the feedback from |
| 491 |
* all signals, eigenvalue computations, and log stream are disabled. |
| 492 |
*/ |
| 493 |
bool batched_mode; |
| 494 |
|
| 495 |
/** |
| 496 |
* Strategy to orthogonalize vectors. |
| 497 |
*/ |
| 498 |
LinearAlgebra::OrthogonalizationStrategy orthogonalization_strategy; |
| 499 |
}; |
| 500 |
|
| 501 |
/** |
| 502 |
* Constructor. |
| 503 |
*/ |
| 504 |
SolverGMRES(SolverControl &cn, |
| 505 |
VectorMemory<VectorType> &mem, |
| 506 |
const AdditionalData &data = AdditionalData()); |
| 507 |
|
| 508 |
/** |
| 509 |
* Constructor. Use an object of type GrowingVectorMemory as a default to |
| 510 |
* allocate memory. |
| 511 |
*/ |
| 512 |
SolverGMRES(SolverControl &cn, const AdditionalData &data = AdditionalData()); |
| 513 |
|
| 514 |
/** |
| 515 |
* The copy constructor is deleted. |
| 516 |
*/ |
| 517 |
SolverGMRES(const SolverGMRES<VectorType> &) = delete; |
| 518 |
|
| 519 |
/** |
| 520 |
* Solve the linear system $Ax=b$ for x. |
| 521 |
*/ |
| 522 |
template <typename MatrixType, typename PreconditionerType> |
| 523 |
DEAL_II_CXX20_REQUIRES( |
| 524 |
(concepts::is_linear_operator_on<MatrixType, VectorType> && |
| 525 |
concepts::is_linear_operator_on<PreconditionerType, VectorType>)) |
| 526 |
void solve(const MatrixType &A, |
| 527 |
VectorType &x, |
| 528 |
const VectorType &b, |
| 529 |
const PreconditionerType &preconditioner); |
| 530 |
|
| 531 |
/** |
| 532 |
* Connect a slot to retrieve the estimated condition number. Called on each |
| 533 |
* outer iteration if every_iteration=true, otherwise called once when |
| 534 |
* iterations are ended (i.e., either because convergence has been achieved, |
| 535 |
* or because divergence has been detected). |
| 536 |
*/ |
| 537 |
boost::signals2::connection |
| 538 |
connect_condition_number_slot(const std::function<void(double)> &slot, |
| 539 |
const bool every_iteration = false); |
| 540 |
|
| 541 |
/** |
| 542 |
* Connect a slot to retrieve the estimated eigenvalues. Called on each |
| 543 |
* outer iteration if every_iteration=true, otherwise called once when |
| 544 |
* iterations are ended (i.e., either because convergence has been achieved, |
| 545 |
* or because divergence has been detected). |
| 546 |
*/ |
| 547 |
boost::signals2::connection |
| 548 |
connect_eigenvalues_slot( |
| 549 |
const std::function<void(const std::vector<std::complex<double>> &)> &slot, |
| 550 |
const bool every_iteration = false); |
| 551 |
|
| 552 |
/** |
| 553 |
* Connect a slot to retrieve the Hessenberg matrix obtained by the |
| 554 |
* projection of the initial matrix on the Krylov basis. Called on each |
| 555 |
* outer iteration if every_iteration=true, otherwise called once when |
| 556 |
* iterations are ended (i.e., either because convergence has been achieved, |
| 557 |
* or because divergence has been detected). |
| 558 |
*/ |
| 559 |
boost::signals2::connection |
| 560 |
connect_hessenberg_slot( |
| 561 |
const std::function<void(const FullMatrix<double> &)> &slot, |
| 562 |
const bool every_iteration = true); |
| 563 |
|
| 564 |
/** |
| 565 |
* Connect a slot to retrieve the basis vectors of the Krylov space |
| 566 |
* generated by the Arnoldi algorithm. Called at once when iterations |
| 567 |
* are completed (i.e., either because convergence has been achieved, |
| 568 |
* or because divergence has been detected). |
| 569 |
*/ |
| 570 |
boost::signals2::connection |
| 571 |
connect_krylov_space_slot( |
| 572 |
const std::function< |
| 573 |
void(const internal::SolverGMRESImplementation::TmpVectors<VectorType> &)> |
| 574 |
&slot); |
| 575 |
|
| 576 |
|
| 577 |
/** |
| 578 |
* Connect a slot to retrieve a notification when the vectors are |
| 579 |
* re-orthogonalized. |
| 580 |
*/ |
| 581 |
boost::signals2::connection |
| 582 |
connect_re_orthogonalization_slot(const std::function<void(int)> &slot); |
| 583 |
|
| 584 |
|
| 585 |
DeclException1(ExcTooFewTmpVectors, |
| 586 |
int, |
| 587 |
<< "The number of temporary vectors you gave (" << arg1 |
| 588 |
<< ") is too small. It should be at least 10 for " |
| 589 |
<< "any results, and much more for reasonable ones."); |
| 590 |
|
| 591 |
protected: |
| 592 |
/** |
| 593 |
* Includes the maximum number of tmp vectors. |
| 594 |
*/ |
| 595 |
AdditionalData additional_data; |
| 596 |
|
| 597 |
/** |
| 598 |
* Signal used to retrieve the estimated condition number. Called once when |
| 599 |
* all iterations are ended. |
| 600 |
*/ |
| 601 |
boost::signals2::signal<void(double)> condition_number_signal; |
| 602 |
|
| 603 |
/** |
| 604 |
* Signal used to retrieve the estimated condition numbers. Called on each |
| 605 |
* outer iteration. |
| 606 |
*/ |
| 607 |
boost::signals2::signal<void(double)> all_condition_numbers_signal; |
| 608 |
|
| 609 |
/** |
| 610 |
* Signal used to retrieve the estimated eigenvalues. Called once when all |
| 611 |
* iterations are ended. |
| 612 |
*/ |
| 613 |
boost::signals2::signal<void(const std::vector<std::complex<double>> &)> |
| 614 |
eigenvalues_signal; |
| 615 |
|
| 616 |
/** |
| 617 |
* Signal used to retrieve the estimated eigenvalues. Called on each outer |
| 618 |
* iteration. |
| 619 |
*/ |
| 620 |
boost::signals2::signal<void(const std::vector<std::complex<double>> &)> |
| 621 |
all_eigenvalues_signal; |
| 622 |
|
| 623 |
/** |
| 624 |
* Signal used to retrieve the Hessenberg matrix. Called once when |
| 625 |
* all iterations are ended. |
| 626 |
*/ |
| 627 |
boost::signals2::signal<void(const FullMatrix<double> &)> hessenberg_signal; |
| 628 |
|
| 629 |
/** |
| 630 |
* Signal used to retrieve the Hessenberg matrix. Called on each outer |
| 631 |
* iteration. |
| 632 |
*/ |
| 633 |
boost::signals2::signal<void(const FullMatrix<double> &)> |
| 634 |
all_hessenberg_signal; |
| 635 |
|
| 636 |
/** |
| 637 |
* Signal used to retrieve the Krylov space basis vectors. Called once |
| 638 |
* when all iterations are ended. |
| 639 |
*/ |
| 640 |
boost::signals2::signal<void( |
| 641 |
const internal::SolverGMRESImplementation::TmpVectors<VectorType> &)> |
| 642 |
krylov_space_signal; |
| 643 |
|
| 644 |
/** |
| 645 |
* Signal used to retrieve a notification |
| 646 |
* when the vectors are re-orthogonalized. |
| 647 |
*/ |
| 648 |
boost::signals2::signal<void(int)> re_orthogonalize_signal; |
| 649 |
|
| 650 |
/** |
| 651 |
* A reference to the underlying SolverControl object. In the regular case, |
| 652 |
* this is not needed, as the signal from the base class is used, but the |
| 653 |
* batched variant cannot use those mechanisms due to the high costs. |
| 654 |
*/ |
| 655 |
SolverControl &solver_control; |
| 656 |
|
| 657 |
/** |
| 658 |
* Implementation of the computation of the norm of the residual. |
| 659 |
*/ |
| 660 |
virtual double |
| 661 |
criterion(); |
| 662 |
|
| 663 |
/** |
| 664 |
* Estimates the eigenvalues from the Hessenberg matrix, H_orig, generated |
| 665 |
* during the inner iterations for @p n vectors in total. Uses these |
| 666 |
* estimates to compute the condition number. Calls the signals |
| 667 |
* eigenvalues_signal and cond_signal with these estimates as arguments. |
| 668 |
*/ |
| 669 |
static void |
| 670 |
compute_eigs_and_cond( |
| 671 |
const FullMatrix<double> &H_orig, |
| 672 |
const unsigned int n, |
| 673 |
const boost::signals2::signal< |
| 674 |
void(const std::vector<std::complex<double>> &)> &eigenvalues_signal, |
| 675 |
const boost::signals2::signal<void(const FullMatrix<double> &)> |
| 676 |
&hessenberg_signal, |
| 677 |
const boost::signals2::signal<void(double)> &cond_signal); |
| 678 |
|
| 679 |
/** |
| 680 |
* Class that performs the actual orthogonalization process and solves the |
| 681 |
* projected linear system. |
| 682 |
*/ |
| 683 |
internal::SolverGMRESImplementation::ArnoldiProcess< |
| 684 |
typename VectorType::value_type> |
| 685 |
arnoldi_process; |
| 686 |
}; |
| 687 |
|
| 688 |
|
| 689 |
/** |
| 690 |
* Implementation of the multiple preconditioned generalized minimal |
| 691 |
* residual method (MPGMRES). |
| 692 |
* |
| 693 |
* This method is a variant of the flexible GMRES, utilizing $N$ |
| 694 |
* preconditioners to search for a solution within a multi-Krylov space. |
| 695 |
* These spaces are characterized by by all possible $N$-variate, |
| 696 |
* non-commuting polynomials of the preconditioners and system matrix |
| 697 |
* applied to a residual up to some fixed degree. In contrast, the flexible |
| 698 |
* GMRES method implemented in SolverFGMRES constructs only one "Krylov" |
| 699 |
* subspace, which is formed by univariate polynomials in one |
| 700 |
* preconditioner that may change at each iteration. |
| 701 |
* |
| 702 |
* We implement two strategies, a "full" and a "truncated" MPGMRES version |
| 703 |
* that differ in how they construct Krylov subspaces. The full MPGMRES |
| 704 |
* version constructs a Krylov subspace for every possible combination of |
| 705 |
* preconditioner application to the initial residual. For two |
| 706 |
* preconditioners $P_1$, $P_2$ this looks as follows: |
| 707 |
* @f{align*}{ |
| 708 |
* r, P_1r, P_2r, P_1AP_1r, P_2AP_1r, P_1AP_2r, P_2AP_2r, P_1AP_1AP_1r, |
| 709 |
* P_2AP_1AP_1r, P_1AP_2AP_1r, P_2AP_2AP_1r, P_1AP_1AP_2r, P_2AP_1AP_2r, |
| 710 |
* P_1AP_2AP_2r, P_2AP_2AP_2r, \ldots |
| 711 |
* @f} |
| 712 |
* The truncated version constructs independent Krylov subspaces by |
| 713 |
* dropping all "mixing" terms in the series expansion. For the example |
| 714 |
* with two preconditioners $P_1$, $P_2$ this looks as follows: |
| 715 |
* @f{align*}{ |
| 716 |
* r, P_1r, P_2r, P_1AP_1r, P_2AP_2r, P_1AP_1AP_1r, P_2AP_2AP_2r, \ldots |
| 717 |
* @f} |
| 718 |
* For reference, FGMRES uses the following construction: |
| 719 |
* @f{align*}{ |
| 720 |
* r, P_1r, P_2AP_1r, P_1AP_2AP_1r, \ldots |
| 721 |
* @f} |
| 722 |
* By default the truncated variant is used. You can switch to the full |
| 723 |
* version by setting the |
| 724 |
* AdditionalData::use_truncated_mpgmres_strategy option in the |
| 725 |
* AdditionalData object to false. |
| 726 |
* |
| 727 |
* For more details see @cite Greif2017. |
| 728 |
* |
| 729 |
* @note The present implementation of MPGMRES differs from the one |
| 730 |
* outlined in @cite Greif2017 in how one iteration is defined. Our |
| 731 |
* implementation constructs the search space one vector at a time, |
| 732 |
* producing a new iterate with each addition. In contrast, the routine |
| 733 |
* described in @cite Greif2017 constructs an iteration step by combining |
| 734 |
* all possible preconditioner applications corresponding to the total |
| 735 |
* polynomial degree of each multi-Krylov space. For the full MPGMRES |
| 736 |
* strategy this results in an exponential increase of possible |
| 737 |
* preconditioner applications that have to be computed for reach iteration |
| 738 |
* cycle; see Section 2.4 in @cite Greif2017. |
| 739 |
* |
| 740 |
* @note This method always uses right preconditioning, as opposed to |
| 741 |
* SolverGMRES, which allows the user to choose between left and right |
| 742 |
* preconditioning. |
| 743 |
* |
| 744 |
* @note The MPGMRES implementation needs two vectors in each iteration |
| 745 |
* steps yielding a total of |
| 746 |
* <tt>2*SolverMPGMRES::%AdditionalData::%max_basis_size+1</tt> auxiliary |
| 747 |
* vectors. Otherwise, FGMRES requires roughly the same number of |
| 748 |
* operations per iteration compared to GMRES, except one application of |
| 749 |
* the preconditioner less at each restart and at the end of solve(). |
| 750 |
*/ |
| 751 |
|
| 752 |
template <typename VectorType = Vector<double>> |
| 753 |
DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>) |
| 754 |
class SolverMPGMRES : public SolverBase<VectorType> |
| 755 |
{ |
| 756 |
public: |
| 757 |
/** |
| 758 |
* Standardized data struct to pipe additional data to the solver. |
| 759 |
*/ |
| 760 |
struct AdditionalData |
| 761 |
{ |
| 762 |
/** |
| 763 |
* Constructor. By default, set the maximum basis size to 30. |
| 764 |
*/ |
| 765 |
explicit AdditionalData(const unsigned int max_basis_size = 30, |
| 766 |
const LinearAlgebra::OrthogonalizationStrategy |
| 767 |
orthogonalization_strategy = |
| 768 |
LinearAlgebra::OrthogonalizationStrategy:: |
| 769 |
delayed_classical_gram_schmidt, |
| 770 |
const bool use_truncated_mpgmres_strategy = true) |
| 771 |
: max_basis_size(max_basis_size) |
| 772 |
, orthogonalization_strategy(orthogonalization_strategy) |
| 773 |
, use_truncated_mpgmres_strategy(use_truncated_mpgmres_strategy) |
| 774 |
{} |
| 775 |
|
| 776 |
/** |
| 777 |
* Maximum basis size. |
| 778 |
*/ |
| 779 |
unsigned int max_basis_size; |
| 780 |
|
| 781 |
/** |
| 782 |
* Strategy to orthogonalize vectors. |
| 783 |
*/ |
| 784 |
LinearAlgebra::OrthogonalizationStrategy orthogonalization_strategy; |
| 785 |
|
| 786 |
/** |
| 787 |
* If set to true (the default) a "truncated" search space is |
| 788 |
* constructed consisting of the span of independent Krylov space |
| 789 |
* associated with each preconditioner. If set to false, the full |
| 790 |
* MPGMRES strategy for constructing the search space is used. This |
| 791 |
* space consists of all possible combinations of iterative |
| 792 |
* preconditioner applications; see the documentation of SolverMPGMRES |
| 793 |
* for details. |
| 794 |
*/ |
| 795 |
bool use_truncated_mpgmres_strategy; |
| 796 |
}; |
| 797 |
|
| 798 |
/** |
| 799 |
* Constructor. |
| 800 |
*/ |
| 801 |
SolverMPGMRES(SolverControl &cn, |
| 802 |
VectorMemory<VectorType> &mem, |
| 803 |
const AdditionalData &data = AdditionalData()); |
| 804 |
|
| 805 |
/** |
| 806 |
* Constructor. Use an object of type GrowingVectorMemory as a default to |
| 807 |
* allocate memory. |
| 808 |
*/ |
| 809 |
SolverMPGMRES(SolverControl &cn, |
| 810 |
const AdditionalData &data = AdditionalData()); |
| 811 |
|
| 812 |
/** |
| 813 |
* Solve the linear system $Ax=b$ for x. |
| 814 |
*/ |
| 815 |
template <typename MatrixType, typename... PreconditionerTypes> |
| 816 |
DEAL_II_CXX20_REQUIRES( |
| 817 |
(concepts::is_linear_operator_on<MatrixType, VectorType> && |
| 818 |
(concepts::is_linear_operator_on<PreconditionerTypes, VectorType> && ...))) |
| 819 |
void solve(const MatrixType &A, |
| 820 |
VectorType &x, |
| 821 |
const VectorType &b, |
| 822 |
const PreconditionerTypes &...preconditioners); |
| 823 |
|
| 824 |
protected: |
| 825 |
/** |
| 826 |
* Indexing strategy to construct the search space. |
| 827 |
* |
| 828 |
* This enum class is internally used in the implementation of the |
| 829 |
* MPGMRES algorithm to switch between the strategies. |
| 830 |
*/ |
| 831 |
enum class IndexingStrategy |
| 832 |
{ |
| 833 |
fgmres, |
| 834 |
truncated_mpgmres, |
| 835 |
full_mpgmres, |
| 836 |
}; |
| 837 |
|
| 838 |
/** |
| 839 |
* Solve the linear system $Ax=b$ for x. |
| 840 |
*/ |
| 841 |
template <typename MatrixType, typename... PreconditionerTypes> |
| 842 |
void |
| 843 |
solve_internal(const MatrixType &A, |
| 844 |
VectorType &x, |
| 845 |
const VectorType &b, |
| 846 |
const IndexingStrategy &indexing_strategy, |
| 847 |
const PreconditionerTypes &...preconditioners); |
| 848 |
|
| 849 |
private: |
| 850 |
/** |
| 851 |
* Additional flags. |
| 852 |
*/ |
| 853 |
AdditionalData additional_data; |
| 854 |
|
| 855 |
/** |
| 856 |
* Class that performs the actual orthogonalization process and solves the |
| 857 |
* projected linear system. |
| 858 |
*/ |
| 859 |
internal::SolverGMRESImplementation::ArnoldiProcess< |
| 860 |
typename VectorType::value_type> |
| 861 |
arnoldi_process; |
| 862 |
}; |
| 863 |
|
| 864 |
|
| 865 |
|
| 866 |
/** |
| 867 |
* Implementation of the generalized minimal residual method with flexible |
| 868 |
* preconditioning (flexible GMRES or FGMRES). |
| 869 |
* |
| 870 |
* This flexible version of the GMRES method allows for the use of a |
| 871 |
* different preconditioner in each iteration step; in particular, |
| 872 |
* this also allows for the use of preconditioners that are not linear |
| 873 |
* operators. Therefore, it is also more robust with respect to |
| 874 |
* inaccurate evaluation of the preconditioner. An important |
| 875 |
* application is the use of a Krylov space method inside the |
| 876 |
* preconditioner with low solver tolerance. See the documentation of |
| 877 |
* the SolverGMRES class for an elaboration of the issues involved. |
| 878 |
* |
| 879 |
* For more details see @cite Saad1991. |
| 880 |
* |
| 881 |
* @note This method always uses right preconditioning, as opposed to |
| 882 |
* SolverGMRES, which allows the user to choose between left and right |
| 883 |
* preconditioning. |
| 884 |
* |
| 885 |
* @note FGMRES needs two vectors in each iteration steps yielding a total |
| 886 |
* of <tt>2*SolverFGMRES::%AdditionalData::%max_basis_size+1</tt> auxiliary |
| 887 |
* vectors. Otherwise, FGMRES requires roughly the same number of |
| 888 |
* operations per iteration compared to GMRES, except one application of |
| 889 |
* the preconditioner less at each restart and at the end of solve(). |
| 890 |
*/ |
| 891 |
template <typename VectorType = Vector<double>> |
| 892 |
DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>) |
| 893 |
class SolverFGMRES : public SolverMPGMRES<VectorType> |
| 894 |
{ |
| 895 |
public: |
| 896 |
/** |
| 897 |
* Standardized data struct to pipe additional data to the solver. |
| 898 |
*/ |
| 899 |
struct AdditionalData |
| 900 |
{ |
| 901 |
/** |
| 902 |
* Constructor. By default, set the maximum basis size to 30. |
| 903 |
*/ |
| 904 |
explicit AdditionalData( // |
| 905 |
const unsigned int max_basis_size = 30, |
| 906 |
const LinearAlgebra::OrthogonalizationStrategy |
| 907 |
orthogonalization_strategy = LinearAlgebra::OrthogonalizationStrategy:: |
| 908 |
delayed_classical_gram_schmidt) |
| 909 |
: max_basis_size(max_basis_size) |
| 910 |
, orthogonalization_strategy(orthogonalization_strategy) |
| 911 |
{} |
| 912 |
|
| 913 |
/** |
| 914 |
* Maximum basis size. |
| 915 |
*/ |
| 916 |
unsigned int max_basis_size; |
| 917 |
|
| 918 |
/** |
| 919 |
* Strategy to orthogonalize vectors. |
| 920 |
*/ |
| 921 |
LinearAlgebra::OrthogonalizationStrategy orthogonalization_strategy; |
| 922 |
}; |
| 923 |
|
| 924 |
|
| 925 |
/** |
| 926 |
* Constructor. |
| 927 |
*/ |
| 928 |
SolverFGMRES(SolverControl &cn, |
| 929 |
VectorMemory<VectorType> &mem, |
| 930 |
const AdditionalData &data = AdditionalData()); |
| 931 |
|
| 932 |
/** |
| 933 |
* Constructor. Use an object of type GrowingVectorMemory as a default to |
| 934 |
* allocate memory. |
| 935 |
*/ |
| 936 |
SolverFGMRES(SolverControl &cn, |
| 937 |
const AdditionalData &data = AdditionalData()); |
| 938 |
|
| 939 |
/** |
| 940 |
* Solve the linear system $Ax=b$ for x. |
| 941 |
*/ |
| 942 |
template <typename MatrixType, typename... PreconditionerTypes> |
| 943 |
DEAL_II_CXX20_REQUIRES( |
| 944 |
(concepts::is_linear_operator_on<MatrixType, VectorType> && |
| 945 |
(concepts::is_linear_operator_on<PreconditionerTypes, VectorType> && ...))) |
| 946 |
void solve(const MatrixType &A, |
| 947 |
VectorType &x, |
| 948 |
const VectorType &b, |
| 949 |
const PreconditionerTypes &...preconditioners); |
| 950 |
}; |
| 951 |
|
| 952 |
/** @} */ |
| 953 |
|
| 954 |
|
| 955 |
/* --------------------- Inline and template functions ------------------- */ |
| 956 |
|
| 957 |
#ifndef DOXYGEN |
| 958 |
|
| 959 |
template <typename VectorType> |
| 960 |
DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>) |
| 961 |
inline SolverGMRES<VectorType>::AdditionalData::AdditionalData( |
| 962 |
const unsigned int max_basis_size, |
| 963 |
const bool right_preconditioning, |
| 964 |
const bool use_default_residual, |
| 965 |
const bool force_re_orthogonalization, |
| 966 |
const bool batched_mode, |
| 967 |
const LinearAlgebra::OrthogonalizationStrategy orthogonalization_strategy) |
| 968 |
: max_n_tmp_vectors(0) |
| 969 |
, max_basis_size(max_basis_size) |
| 970 |
, right_preconditioning(right_preconditioning) |
| 971 |
, use_default_residual(use_default_residual) |
| 972 |
, force_re_orthogonalization(force_re_orthogonalization) |
| 973 |
, batched_mode(batched_mode) |
| 974 |
, orthogonalization_strategy(orthogonalization_strategy) |
| 975 |
{ |
| 976 |
Assert(max_basis_size >= 1, |
| 977 |
ExcMessage("SolverGMRES needs at least one vector in the " |
| 978 |
"Arnoldi basis.")); |
| 979 |
} |
| 980 |
|
| 981 |
|
| 982 |
|
| 983 |
template <typename VectorType> |
| 984 |
DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>) |
| 985 |
SolverGMRES<VectorType>::SolverGMRES(SolverControl &cn, |
| 986 |
VectorMemory<VectorType> &mem, |
| 987 |
const AdditionalData &data) |
| 988 |
: SolverBase<VectorType>(cn, mem) |
| 989 |
, additional_data(data) |
| 990 |
, solver_control(cn) |
| 991 |
{} |
| 992 |
|
| 993 |
|
| 994 |
|
| 995 |
template <typename VectorType> |
| 996 |
DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>) |
| 997 |
SolverGMRES<VectorType>::SolverGMRES(SolverControl &cn, |
| 998 |
const AdditionalData &data) |
| 999 |
: SolverBase<VectorType>(cn) |
| 1000 |
, additional_data(data) |
| 1001 |
, solver_control(cn) |
| 1002 |
{} |
| 1003 |
|
| 1004 |
|
| 1005 |
|
| 1006 |
namespace internal |
| 1007 |
{ |
| 1008 |
namespace SolverGMRESImplementation |
| 1009 |
{ |
| 1010 |
template <typename VectorType> |
| 1011 |
inline TmpVectors<VectorType>::TmpVectors(const unsigned int max_size, |
| 1012 |
VectorMemory<VectorType> &vmem) |
| 1013 |
: mem(vmem) |
| 1014 |
, data(max_size) |
| 1015 |
{} |
| 1016 |
|
| 1017 |
|
| 1018 |
|
| 1019 |
template <typename VectorType> |
| 1020 |
inline VectorType & |
| 1021 |
TmpVectors<VectorType>::operator[](const unsigned int i) const |
| 1022 |
{ |
| 1023 |
AssertIndexRange(i, data.size()); |
| 1024 |
|
| 1025 |
Assert(data[i] != nullptr, ExcNotInitialized()); |
| 1026 |
return *data[i]; |
| 1027 |
} |
| 1028 |
|
| 1029 |
|
| 1030 |
|
| 1031 |
template <typename VectorType> |
| 1032 |
inline VectorType & |
| 1033 |
TmpVectors<VectorType>::operator()(const unsigned int i, |
| 1034 |
const VectorType &temp) |
| 1035 |
{ |
| 1036 |
AssertIndexRange(i, data.size()); |
| 1037 |
if (data[i] == nullptr) |
| 1038 |
{ |
| 1039 |
data[i] = std::move(typename VectorMemory<VectorType>::Pointer(mem)); |
| 1040 |
data[i]->reinit(temp, true); |
| 1041 |
} |
| 1042 |
return *data[i]; |
| 1043 |
} |
| 1044 |
|
| 1045 |
|
| 1046 |
|
| 1047 |
template <typename VectorType> |
| 1048 |
unsigned int |
| 1049 |
TmpVectors<VectorType>::size() const |
| 1050 |
{ |
| 1051 |
return (data.size() > 0 ? data.size() - 1 : 0); |
| 1052 |
} |
| 1053 |
|
| 1054 |
|
| 1055 |
|
| 1056 |
template <typename VectorType, typename Enable = void> |
| 1057 |
struct is_dealii_compatible_vector; |
| 1058 |
|
| 1059 |
template <typename VectorType> |
| 1060 |
struct is_dealii_compatible_vector< |
| 1061 |
VectorType, |
| 1062 |
std::enable_if_t<!internal::is_block_vector<VectorType>>> |
| 1063 |
{ |
| 1064 |
static constexpr bool value = |
| 1065 |
std::is_same_v< |
| 1066 |
VectorType, |
| 1067 |
LinearAlgebra::distributed::Vector<typename VectorType::value_type, |
| 1068 |
MemorySpace::Host>> || |
| 1069 |
std::is_same_v<VectorType, Vector<typename VectorType::value_type>>; |
| 1070 |
}; |
| 1071 |
|
| 1072 |
|
| 1073 |
|
| 1074 |
template <typename VectorType> |
| 1075 |
struct is_dealii_compatible_vector< |
| 1076 |
VectorType, |
| 1077 |
std::enable_if_t<internal::is_block_vector<VectorType>>> |
| 1078 |
{ |
| 1079 |
static constexpr bool value = |
| 1080 |
std::is_same_v< |
| 1081 |
typename VectorType::BlockType, |
| 1082 |
LinearAlgebra::distributed::Vector<typename VectorType::value_type, |
| 1083 |
MemorySpace::Host>> || |
| 1084 |
std::is_same_v<VectorType, Vector<typename VectorType::value_type>>; |
| 1085 |
}; |
| 1086 |
|
| 1087 |
|
| 1088 |
|
| 1089 |
template <typename VectorType, |
| 1090 |
std::enable_if_t<!IsBlockVector<VectorType>::value, VectorType> |
| 1091 |
* = nullptr> |
| 1092 |
unsigned int |
| 1093 |
n_blocks(const VectorType &) |
| 1094 |
{ |
| 1095 |
return 1; |
| 1096 |
} |
| 1097 |
|
| 1098 |
|
| 1099 |
|
| 1100 |
template <typename VectorType, |
| 1101 |
std::enable_if_t<IsBlockVector<VectorType>::value, VectorType> * = |
| 1102 |
nullptr> |
| 1103 |
unsigned int |
| 1104 |
n_blocks(const VectorType &vector) |
| 1105 |
{ |
| 1106 |
return vector.n_blocks(); |
| 1107 |
} |
| 1108 |
|
| 1109 |
|
| 1110 |
|
| 1111 |
template <typename VectorType, |
| 1112 |
std::enable_if_t<!IsBlockVector<VectorType>::value, VectorType> |
| 1113 |
* = nullptr> |
| 1114 |
VectorType & |
| 1115 |
block(VectorType &vector, const unsigned int b) |
| 1116 |
{ |
| 1117 |
AssertDimension(b, 0); |
| 1118 |
return vector; |
| 1119 |
} |
| 1120 |
|
| 1121 |
|
| 1122 |
|
| 1123 |
template <typename VectorType, |
| 1124 |
std::enable_if_t<!IsBlockVector<VectorType>::value, VectorType> |
| 1125 |
* = nullptr> |
| 1126 |
const VectorType & |
| 1127 |
block(const VectorType &vector, const unsigned int b) |
| 1128 |
{ |
| 1129 |
AssertDimension(b, 0); |
| 1130 |
return vector; |
| 1131 |
} |
| 1132 |
|
| 1133 |
|
| 1134 |
|
| 1135 |
template <typename VectorType, |
| 1136 |
std::enable_if_t<IsBlockVector<VectorType>::value, VectorType> * = |
| 1137 |
nullptr> |
| 1138 |
typename VectorType::BlockType & |
| 1139 |
block(VectorType &vector, const unsigned int b) |
| 1140 |
{ |
| 1141 |
return vector.block(b); |
| 1142 |
} |
| 1143 |
|
| 1144 |
|
| 1145 |
|
| 1146 |
template <typename VectorType, |
| 1147 |
std::enable_if_t<IsBlockVector<VectorType>::value, VectorType> * = |
| 1148 |
nullptr> |
| 1149 |
const typename VectorType::BlockType & |
| 1150 |
block(const VectorType &vector, const unsigned int b) |
| 1151 |
{ |
| 1152 |
return vector.block(b); |
| 1153 |
} |
| 1154 |
|
| 1155 |
|
| 1156 |
|
| 1157 |
template <bool delayed_reorthogonalization, |
| 1158 |
typename VectorType, |
| 1159 |
std::enable_if_t<!is_dealii_compatible_vector<VectorType>::value, |
| 1160 |
VectorType> * = nullptr> |
| 1161 |
void |
| 1162 |
Tvmult_add(const unsigned int n, |
| 1163 |
const VectorType &vv, |
| 1164 |
const TmpVectors<VectorType> &orthogonal_vectors, |
| 1165 |
Vector<double> &h, |
| 1166 |
std::vector<const typename VectorType::value_type *> &) |
| 1167 |
{ |
| 1168 |
for (unsigned int i = 0; i < n; ++i) |
| 1169 |
{ |
| 1170 |
h(i) += vv * orthogonal_vectors[i]; |
| 1171 |
if (delayed_reorthogonalization) |
| 1172 |
h(n + i) += orthogonal_vectors[i] * orthogonal_vectors[n - 1]; |
| 1173 |
} |
| 1174 |
if (delayed_reorthogonalization) |
| 1175 |
h(n + n) += vv * vv; |
| 1176 |
} |
| 1177 |
|
| 1178 |
|
| 1179 |
|
| 1180 |
// worker method for deal.II's vector types implemented in .cc file |
| 1181 |
template <bool delayed_reorthogonalization, typename Number> |
| 1182 |
void |
| 1183 |
do_Tvmult_add(const unsigned int n_vectors, |
| 1184 |
const std::size_t locally_owned_size, |
| 1185 |
const Number *current_vector, |
| 1186 |
const std::vector<const Number *> &orthogonal_vectors, |
| 1187 |
Vector<double> &b); |
| 1188 |
|
| 1189 |
|
| 1190 |
|
| 1191 |
template <bool delayed_reorthogonalization, |
| 1192 |
typename VectorType, |
| 1193 |
std::enable_if_t<is_dealii_compatible_vector<VectorType>::value, |
| 1194 |
VectorType> * = nullptr> |
| 1195 |
void |
| 1196 |
Tvmult_add( |
| 1197 |
const unsigned int n, |
| 1198 |
const VectorType &vv, |
| 1199 |
const TmpVectors<VectorType> &orthogonal_vectors, |
| 1200 |
Vector<double> &h, |
| 1201 |
std::vector<const typename VectorType::value_type *> &vector_ptrs) |
| 1202 |
{ |
| 1203 |
for (unsigned int b = 0; b < n_blocks(vv); ++b) |
| 1204 |
{ |
| 1205 |
vector_ptrs.resize(n); |
| 1206 |
for (unsigned int i = 0; i < n; ++i) |
| 1207 |
vector_ptrs[i] = block(orthogonal_vectors[i], b).begin(); |
| 1208 |
|
| 1209 |
do_Tvmult_add<delayed_reorthogonalization>(n, |
| 1210 |
block(vv, b).end() - |
| 1211 |
block(vv, b).begin(), |
| 1212 |
block(vv, b).begin(), |
| 1213 |
vector_ptrs, |
| 1214 |
h); |
| 1215 |
} |
| 1216 |
|
| 1217 |
Utilities::MPI::sum(h, block(vv, 0).get_mpi_communicator(), h); |
| 1218 |
} |
| 1219 |
|
| 1220 |
|
| 1221 |
|
| 1222 |
template <bool delayed_reorthogonalization, |
| 1223 |
typename VectorType, |
| 1224 |
std::enable_if_t<!is_dealii_compatible_vector<VectorType>::value, |
| 1225 |
VectorType> * = nullptr> |
| 1226 |
double |
| 1227 |
subtract_and_norm(const unsigned int n, |
| 1228 |
const TmpVectors<VectorType> &orthogonal_vectors, |
| 1229 |
const Vector<double> &h, |
| 1230 |
VectorType &vv, |
| 1231 |
std::vector<const typename VectorType::value_type *> &) |
| 1232 |
{ |
| 1233 |
Assert(n > 0, ExcInternalError()); |
| 1234 |
|
| 1235 |
VectorType &last_vector = |
| 1236 |
const_cast<VectorType &>(orthogonal_vectors[n - 1]); |
| 1237 |
for (unsigned int i = 0; i < n - 1; ++i) |
| 1238 |
{ |
| 1239 |
if (delayed_reorthogonalization && i + 2 < n) |
| 1240 |
last_vector.add(-h(n + i), orthogonal_vectors[i]); |
| 1241 |
vv.add(-h(i), orthogonal_vectors[i]); |
| 1242 |
} |
| 1243 |
|
| 1244 |
if (delayed_reorthogonalization) |
| 1245 |
{ |
| 1246 |
if (n > 1) |
| 1247 |
last_vector.sadd(1. / h(n + n - 1), |
| 1248 |
-h(n + n - 2) / h(n + n - 1), |
| 1249 |
orthogonal_vectors[n - 2]); |
| 1250 |
|
| 1251 |
// h(n + n) is lucky breakdown |
| 1252 |
const double scaling_factor_vv = h(n + n) > 0.0 ? |
| 1253 |
1. / (h(n + n - 1) * h(n + n)) : |
| 1254 |
1. / (h(n + n - 1) * h(n + n - 1)); |
| 1255 |
vv.sadd(scaling_factor_vv, |
| 1256 |
-h(n - 1) * scaling_factor_vv, |
| 1257 |
last_vector); |
| 1258 |
|
| 1259 |
// the delayed reorthogonalization computes the norm from other |
| 1260 |
// quantities |
| 1261 |
return std::numeric_limits<double>::signaling_NaN(); |
| 1262 |
} |
| 1263 |
else |
| 1264 |
return std::sqrt( |
| 1265 |
vv.add_and_dot(-h(n - 1), orthogonal_vectors[n - 1], vv)); |
| 1266 |
} |
| 1267 |
|
| 1268 |
|
| 1269 |
|
| 1270 |
// worker method for deal.II's vector types implemented in .cc file |
| 1271 |
template <bool delayed_reorthogonalization, typename Number> |
| 1272 |
double |
| 1273 |
do_subtract_and_norm(const unsigned int n_vectors, |
| 1274 |
const std::size_t locally_owned_size, |
| 1275 |
const std::vector<const Number *> &orthogonal_vectors, |
| 1276 |
const Vector<double> &h, |
| 1277 |
Number *current_vector); |
| 1278 |
|
| 1279 |
|
| 1280 |
|
| 1281 |
template <bool delayed_reorthogonalization, |
| 1282 |
typename VectorType, |
| 1283 |
std::enable_if_t<is_dealii_compatible_vector<VectorType>::value, |
| 1284 |
VectorType> * = nullptr> |
| 1285 |
double |
| 1286 |
subtract_and_norm( |
| 1287 |
const unsigned int n, |
| 1288 |
const TmpVectors<VectorType> &orthogonal_vectors, |
| 1289 |
const Vector<double> &h, |
| 1290 |
VectorType &vv, |
| 1291 |
std::vector<const typename VectorType::value_type *> &vector_ptrs) |
| 1292 |
{ |
| 1293 |
double norm_vv_temp = 0.0; |
| 1294 |
|
| 1295 |
for (unsigned int b = 0; b < n_blocks(vv); ++b) |
| 1296 |
{ |
| 1297 |
vector_ptrs.resize(n); |
| 1298 |
for (unsigned int i = 0; i < n; ++i) |
| 1299 |
vector_ptrs[i] = block(orthogonal_vectors[i], b).begin(); |
| 1300 |
|
| 1301 |
norm_vv_temp += do_subtract_and_norm<delayed_reorthogonalization>( |
| 1302 |
n, |
| 1303 |
block(vv, b).end() - block(vv, b).begin(), |
| 1304 |
vector_ptrs, |
| 1305 |
h, |
| 1306 |
block(vv, b).begin()); |
| 1307 |
} |
| 1308 |
|
| 1309 |
return std::sqrt( |
| 1310 |
Utilities::MPI::sum(norm_vv_temp, block(vv, 0).get_mpi_communicator())); |
| 1311 |
} |
| 1312 |
|
| 1313 |
|
| 1314 |
|
| 1315 |
template <typename VectorType, |
| 1316 |
std::enable_if_t<!is_dealii_compatible_vector<VectorType>::value, |
| 1317 |
VectorType> * = nullptr> |
| 1318 |
void |
| 1319 |
add(VectorType &p, |
| 1320 |
const unsigned int n, |
| 1321 |
const Vector<double> &h, |
| 1322 |
const TmpVectors<VectorType> &tmp_vectors, |
| 1323 |
const bool zero_out, |
| 1324 |
std::vector<const typename VectorType::value_type *> &) |
| 1325 |
{ |
| 1326 |
if (zero_out) |
| 1327 |
p.equ(h(0), tmp_vectors[0]); |
| 1328 |
else |
| 1329 |
p.add(h(0), tmp_vectors[0]); |
| 1330 |
|
| 1331 |
for (unsigned int i = 1; i < n; ++i) |
| 1332 |
p.add(h(i), tmp_vectors[i]); |
| 1333 |
} |
| 1334 |
|
| 1335 |
|
| 1336 |
|
| 1337 |
// worker method for deal.II's vector types implemented in .cc file |
| 1338 |
template <typename Number> |
| 1339 |
void |
| 1340 |
do_add(const unsigned int n_vectors, |
| 1341 |
const std::size_t locally_owned_size, |
| 1342 |
const std::vector<const Number *> &tmp_vectors, |
| 1343 |
const Vector<double> &h, |
| 1344 |
const bool zero_out, |
| 1345 |
Number *output); |
| 1346 |
|
| 1347 |
|
| 1348 |
|
| 1349 |
template <typename VectorType, |
| 1350 |
std::enable_if_t<is_dealii_compatible_vector<VectorType>::value, |
| 1351 |
VectorType> * = nullptr> |
| 1352 |
void |
| 1353 |
add(VectorType &p, |
| 1354 |
const unsigned int n, |
| 1355 |
const Vector<double> &h, |
| 1356 |
const TmpVectors<VectorType> &tmp_vectors, |
| 1357 |
const bool zero_out, |
| 1358 |
std::vector<const typename VectorType::value_type *> &vector_ptrs) |
| 1359 |
{ |
| 1360 |
for (unsigned int b = 0; b < n_blocks(p); ++b) |
| 1361 |
{ |
| 1362 |
vector_ptrs.resize(n); |
| 1363 |
for (unsigned int i = 0; i < n; ++i) |
| 1364 |
vector_ptrs[i] = block(tmp_vectors[i], b).begin(); |
| 1365 |
do_add(n, |
| 1366 |
block(p, b).end() - block(p, b).begin(), |
| 1367 |
vector_ptrs, |
| 1368 |
h, |
| 1369 |
zero_out, |
| 1370 |
block(p, b).begin()); |
| 1371 |
} |
| 1372 |
} |
| 1373 |
|
| 1374 |
|
| 1375 |
|
| 1376 |
template <typename Number> |
| 1377 |
inline void |
| 1378 |
ArnoldiProcess<Number>::initialize( |
| 1379 |
const LinearAlgebra::OrthogonalizationStrategy orthogonalization_strategy, |
| 1380 |
const unsigned int basis_size, |
| 1381 |
const bool force_reorthogonalization) |
| 1382 |
{ |
| 1383 |
this->orthogonalization_strategy = orthogonalization_strategy; |
| 1384 |
this->do_reorthogonalization = force_reorthogonalization; |
| 1385 |
|
| 1386 |
hessenberg_matrix.reinit(basis_size + 1, basis_size); |
| 1387 |
triangular_matrix.reinit(basis_size + 1, basis_size, true); |
| 1388 |
|
| 1389 |
// some additional vectors, also used in the orthogonalization |
| 1390 |
projected_rhs.reinit(basis_size + 1, true); |
| 1391 |
givens_rotations.reserve(basis_size); |
| 1392 |
|
| 1393 |
if (orthogonalization_strategy == |
| 1394 |
LinearAlgebra::OrthogonalizationStrategy:: |
| 1395 |
delayed_classical_gram_schmidt) |
| 1396 |
h.reinit(2 * basis_size + 3); |
| 1397 |
else |
| 1398 |
h.reinit(basis_size + 1); |
| 1399 |
} |
| 1400 |
|
| 1401 |
|
| 1402 |
|
| 1403 |
template <typename Number> |
| 1404 |
template <typename VectorType> |
| 1405 |
inline double |
| 1406 |
ArnoldiProcess<Number>::orthonormalize_nth_vector( |
| 1407 |
const unsigned int n, |
| 1408 |
TmpVectors<VectorType> &orthogonal_vectors, |
| 1409 |
const unsigned int accumulated_iterations, |
| 1410 |
const boost::signals2::signal<void(int)> &reorthogonalize_signal) |
| 1411 |
{ |
| 1412 |
AssertIndexRange(n, hessenberg_matrix.m()); |
| 1413 |
AssertIndexRange(n, orthogonal_vectors.size() + 1); |
| 1414 |
|
| 1415 |
VectorType &vv = orthogonal_vectors[n]; |
| 1416 |
|
| 1417 |
double residual_estimate = std::numeric_limits<double>::signaling_NaN(); |
| 1418 |
if (n == 0) |
| 1419 |
{ |
| 1420 |
givens_rotations.clear(); |
| 1421 |
residual_estimate = vv.l2_norm(); |
| 1422 |
if (residual_estimate != 0.) |
| 1423 |
vv /= residual_estimate; |
| 1424 |
projected_rhs(0) = residual_estimate; |
| 1425 |
} |
| 1426 |
else if (orthogonalization_strategy == |
| 1427 |
LinearAlgebra::OrthogonalizationStrategy:: |
| 1428 |
delayed_classical_gram_schmidt) |
| 1429 |
{ |
| 1430 |
// The algorithm implemented in the following few lines is algorithm |
| 1431 |
// 4 of Bielich et al. (2022). |
| 1432 |
|
| 1433 |
// To avoid un-scaled numbers as appearing with the original |
| 1434 |
// algorithm by Bielich et al., we use a preliminary scaling of the |
| 1435 |
// last vector. This will be corrected in the delayed step. |
| 1436 |
const double previous_scaling = n > 0 ? h(n + n - 2) : 1.; |
| 1437 |
|
| 1438 |
// Reset h to zero |
| 1439 |
h.reinit(n + n + 1); |
| 1440 |
|
| 1441 |
// global reduction |
| 1442 |
Tvmult_add<true>(n, vv, orthogonal_vectors, h, vector_ptrs); |
| 1443 |
|
| 1444 |
// delayed correction terms |
| 1445 |
double tmp = 0; |
| 1446 |
for (unsigned int i = 0; i < n - 1; ++i) |
| 1447 |
tmp += h(n + i) * h(n + i); |
| 1448 |
const double alpha_j = h(n + n - 1) > tmp ? |
| 1449 |
std::sqrt(h(n + n - 1) - tmp) : |
| 1450 |
std::sqrt(h(n + n - 1)); |
| 1451 |
h(n + n - 1) = alpha_j; |
| 1452 |
|
| 1453 |
tmp = 0; |
| 1454 |
for (unsigned int i = 0; i < n - 1; ++i) |
| 1455 |
tmp += h(i) * h(n + i); |
| 1456 |
h(n - 1) = (h(n - 1) - tmp) / alpha_j; |
| 1457 |
|
| 1458 |
// representation of H(j-1) |
| 1459 |
if (n > 1) |
| 1460 |
{ |
| 1461 |
for (unsigned int i = 0; i < n - 1; ++i) |
| 1462 |
hessenberg_matrix(i, n - 2) += h(n + i) * previous_scaling; |
| 1463 |
hessenberg_matrix(n - 1, n - 2) = alpha_j * previous_scaling; |
| 1464 |
} |
| 1465 |
for (unsigned int i = 0; i < n; ++i) |
| 1466 |
{ |
| 1467 |
double sum = 0; |
| 1468 |
for (unsigned int j = (i == 0 ? 0 : i - 1); j < n - 1; ++j) |
| 1469 |
sum += hessenberg_matrix(i, j) * h(n + j); |
| 1470 |
hessenberg_matrix(i, n - 1) = (h(i) - sum) / alpha_j; |
| 1471 |
} |
| 1472 |
|
| 1473 |
// compute norm estimate for approximate convergence criterion |
| 1474 |
// (value of norm to be corrected in next iteration) |
| 1475 |
double sum = 0; |
| 1476 |
for (unsigned int i = 0; i < n - 1; ++i) |
| 1477 |
sum += h(i) * h(i); |
| 1478 |
sum += (2. - 1.) * h(n - 1) * h(n - 1); |
| 1479 |
hessenberg_matrix(n, n - 1) = |
| 1480 |
std::sqrt(std::abs(h(n + n) - sum)) / alpha_j; |
| 1481 |
|
| 1482 |
// projection and delayed reorthogonalization. We scale the vector |
| 1483 |
// vv here by the preliminary norm to avoid working with too large |
| 1484 |
// values and correct the actual norm in the Hessenberg matrix in |
| 1485 |
// high precision in the next iteration. |
| 1486 |
h(n + n) = hessenberg_matrix(n, n - 1); |
| 1487 |
subtract_and_norm<true>(n, orthogonal_vectors, h, vv, vector_ptrs); |
| 1488 |
|
| 1489 |
// transform new column of upper Hessenberg matrix into upper |
| 1490 |
// triangular form by computing the respective factor |
| 1491 |
residual_estimate = do_givens_rotation( |
| 1492 |
true, n - 2, triangular_matrix, givens_rotations, projected_rhs); |
| 1493 |
} |
| 1494 |
else |
| 1495 |
{ |
| 1496 |
// need initial norm for detection of re-orthogonalization, see below |
| 1497 |
double norm_vv = 0.0; |
| 1498 |
double norm_vv_start = 0; |
| 1499 |
const bool consider_reorthogonalize = |
| 1500 |
(do_reorthogonalization == false) && (n % 5 == 0); |
| 1501 |
if (consider_reorthogonalize) |
| 1502 |
norm_vv_start = vv.l2_norm(); |
| 1503 |
|
| 1504 |
// Reset h to zero |
| 1505 |
h.reinit(n); |
| 1506 |
|
| 1507 |
// run two loops with index 0: orthogonalize, 1: reorthogonalize |
| 1508 |
for (unsigned int c = 0; c < 2; ++c) |
| 1509 |
{ |
| 1510 |
// Orthogonalization |
| 1511 |
if (orthogonalization_strategy == |
| 1512 |
LinearAlgebra::OrthogonalizationStrategy:: |
| 1513 |
modified_gram_schmidt) |
| 1514 |
{ |
| 1515 |
double htmp = vv * orthogonal_vectors[0]; |
| 1516 |
h(0) += htmp; |
| 1517 |
for (unsigned int i = 1; i < n; ++i) |
| 1518 |
{ |
| 1519 |
htmp = vv.add_and_dot(-htmp, |
| 1520 |
orthogonal_vectors[i - 1], |
| 1521 |
orthogonal_vectors[i]); |
| 1522 |
h(i) += htmp; |
| 1523 |
} |
| 1524 |
|
| 1525 |
norm_vv = std::sqrt( |
| 1526 |
vv.add_and_dot(-htmp, orthogonal_vectors[n - 1], vv)); |
| 1527 |
} |
| 1528 |
else if (orthogonalization_strategy == |
| 1529 |
LinearAlgebra::OrthogonalizationStrategy:: |
| 1530 |
classical_gram_schmidt) |
| 1531 |
{ |
| 1532 |
Tvmult_add<false>(n, vv, orthogonal_vectors, h, vector_ptrs); |
| 1533 |
norm_vv = subtract_and_norm<false>( |
| 1534 |
n, orthogonal_vectors, h, vv, vector_ptrs); |
| 1535 |
} |
| 1536 |
else |
| 1537 |
{ |
| 1538 |
AssertThrow(false, ExcNotImplemented()); |
| 1539 |
} |
| 1540 |
|
| 1541 |
if (c == 1) |
| 1542 |
break; // reorthogonalization already performed -> finished |
| 1543 |
|
| 1544 |
// Re-orthogonalization if loss of orthogonality detected. For the |
| 1545 |
// test, use a strategy discussed in C. T. Kelley, Iterative |
| 1546 |
// Methods for Linear and Nonlinear Equations, SIAM, Philadelphia, |
| 1547 |
// 1995: Compare the norm of vv after orthogonalization with its |
| 1548 |
// norm when starting the orthogonalization. If vv became very |
| 1549 |
// small (here: less than the square root of the machine precision |
| 1550 |
// times 10), it is almost in the span of the previous vectors, |
| 1551 |
// which indicates loss of precision. |
| 1552 |
if (consider_reorthogonalize) |
| 1553 |
{ |
| 1554 |
if (norm_vv > |
| 1555 |
10. * norm_vv_start * |
| 1556 |
std::sqrt(std::numeric_limits< |
| 1557 |
typename VectorType::value_type>::epsilon())) |
| 1558 |
break; |
| 1559 |
|
| 1560 |
else |
| 1561 |
{ |
| 1562 |
do_reorthogonalization = true; |
| 1563 |
if (!reorthogonalize_signal.empty()) |
| 1564 |
reorthogonalize_signal(accumulated_iterations); |
| 1565 |
} |
| 1566 |
} |
| 1567 |
|
| 1568 |
if (do_reorthogonalization == false) |
| 1569 |
break; // no reorthogonalization needed -> finished |
| 1570 |
} |
| 1571 |
|
| 1572 |
for (unsigned int i = 0; i < n; ++i) |
| 1573 |
hessenberg_matrix(i, n - 1) = h(i); |
| 1574 |
hessenberg_matrix(n, n - 1) = norm_vv; |
| 1575 |
|
| 1576 |
// norm_vv is a lucky breakdown, the solver will reach convergence, |
| 1577 |
// but we must not divide by zero here. |
| 1578 |
if (norm_vv != 0) |
| 1579 |
vv /= norm_vv; |
| 1580 |
|
| 1581 |
residual_estimate = do_givens_rotation( |
| 1582 |
false, n - 1, triangular_matrix, givens_rotations, projected_rhs); |
| 1583 |
} |
| 1584 |
|
| 1585 |
return residual_estimate; |
| 1586 |
} |
| 1587 |
|
| 1588 |
|
| 1589 |
|
| 1590 |
template <typename Number> |
| 1591 |
inline double |
| 1592 |
ArnoldiProcess<Number>::do_givens_rotation( |
| 1593 |
const bool delayed_reorthogonalization, |
| 1594 |
const int col, |
| 1595 |
FullMatrix<double> &matrix, |
| 1596 |
std::vector<std::pair<double, double>> &rotations, |
| 1597 |
Vector<double> &rhs) |
| 1598 |
{ |
| 1599 |
// for the delayed orthogonalization, we can only compute the column of |
| 1600 |
// the previous iteration (as there will be correction terms added to the |
| 1601 |
// present column for stability reasons), but we still want to compute |
| 1602 |
// the residual estimate from the accumulated work; we therefore perform |
| 1603 |
// givens rotations on two columns simultaneously |
| 1604 |
if (delayed_reorthogonalization) |
| 1605 |
{ |
| 1606 |
if (col >= 0) |
| 1607 |
{ |
| 1608 |
AssertDimension(rotations.size(), static_cast<std::size_t>(col)); |
| 1609 |
matrix(0, col) = hessenberg_matrix(0, col); |
| 1610 |
} |
| 1611 |
double H_next = hessenberg_matrix(0, col + 1); |
| 1612 |
for (int i = 0; i < col; ++i) |
| 1613 |
{ |
| 1614 |
const double c = rotations[i].first; |
| 1615 |
const double s = rotations[i].second; |
| 1616 |
const double Hi = matrix(i, col); |
| 1617 |
const double Hi1 = hessenberg_matrix(i + 1, col); |
| 1618 |
H_next = -s * H_next + c * hessenberg_matrix(i + 1, col + 1); |
| 1619 |
matrix(i, col) = c * Hi + s * Hi1; |
| 1620 |
matrix(i + 1, col) = -s * Hi + c * Hi1; |
| 1621 |
} |
| 1622 |
|
| 1623 |
if (col >= 0) |
| 1624 |
{ |
| 1625 |
const double H_col1 = hessenberg_matrix(col + 1, col); |
| 1626 |
const double H_col = matrix(col, col); |
| 1627 |
const double r = 1. / std::sqrt(H_col * H_col + H_col1 * H_col1); |
| 1628 |
rotations.emplace_back(H_col * r, H_col1 * r); |
| 1629 |
matrix(col, col) = |
| 1630 |
rotations[col].first * H_col + rotations[col].second * H_col1; |
| 1631 |
|
| 1632 |
rhs(col + 1) = -rotations[col].second * rhs(col); |
| 1633 |
rhs(col) *= rotations[col].first; |
| 1634 |
|
| 1635 |
H_next = |
| 1636 |
-rotations[col].second * H_next + |
| 1637 |
rotations[col].first * hessenberg_matrix(col + 1, col + 1); |
| 1638 |
} |
| 1639 |
|
| 1640 |
const double H_last = hessenberg_matrix(col + 2, col + 1); |
| 1641 |
const double r = 1. / std::sqrt(H_next * H_next + H_last * H_last); |
| 1642 |
return std::abs(H_last * r * rhs(col + 1)); |
| 1643 |
} |
| 1644 |
else |
| 1645 |
{ |
| 1646 |
AssertDimension(rotations.size(), static_cast<std::size_t>(col)); |
| 1647 |
|
| 1648 |
matrix(0, col) = hessenberg_matrix(0, col); |
| 1649 |
for (int i = 0; i < col; ++i) |
| 1650 |
{ |
| 1651 |
const double c = rotations[i].first; |
| 1652 |
const double s = rotations[i].second; |
| 1653 |
const double Hi = matrix(i, col); |
| 1654 |
const double Hi1 = hessenberg_matrix(i + 1, col); |
| 1655 |
matrix(i, col) = c * Hi + s * Hi1; |
| 1656 |
matrix(i + 1, col) = -s * Hi + c * Hi1; |
| 1657 |
} |
| 1658 |
|
| 1659 |
const double Hi = matrix(col, col); |
| 1660 |
const double Hi1 = hessenberg_matrix(col + 1, col); |
| 1661 |
const double r = 1. / std::sqrt(Hi * Hi + Hi1 * Hi1); |
| 1662 |
rotations.emplace_back(Hi * r, Hi1 * r); |
| 1663 |
matrix(col, col) = |
| 1664 |
rotations[col].first * Hi + rotations[col].second * Hi1; |
| 1665 |
|
| 1666 |
rhs(col + 1) = -rotations[col].second * rhs(col); |
| 1667 |
rhs(col) *= rotations[col].first; |
| 1668 |
|
| 1669 |
return std::abs(rhs(col + 1)); |
| 1670 |
} |
| 1671 |
} |
| 1672 |
|
| 1673 |
|
| 1674 |
|
| 1675 |
template <typename Number> |
| 1676 |
inline const Vector<double> & |
| 1677 |
ArnoldiProcess<Number>::solve_projected_system( |
| 1678 |
const bool orthogonalization_finished) |
| 1679 |
{ |
| 1680 |
FullMatrix<double> tmp_triangular_matrix; |
| 1681 |
Vector<double> tmp_rhs; |
| 1682 |
FullMatrix<double> *matrix = &triangular_matrix; |
| 1683 |
Vector<double> *rhs = &projected_rhs; |
| 1684 |
unsigned int n = givens_rotations.size(); |
| 1685 |
|
| 1686 |
// If we solve with the delayed orthogonalization, we still need to |
| 1687 |
// perform the elimination of the last column before we can solve the |
| 1688 |
// projected system. We distinguish two cases, one where the |
| 1689 |
// orthogonalization has finished (i.e., end of inner iteration in |
| 1690 |
// GMRES) and we can safely overwrite the content of the tridiagonal |
| 1691 |
// matrix and right hand side, and the case during the inner iterations, |
| 1692 |
// where we need to create copies of the matrices in the QR |
| 1693 |
// decomposition as well as the right hand side. |
| 1694 |
if (orthogonalization_strategy == |
| 1695 |
LinearAlgebra::OrthogonalizationStrategy:: |
| 1696 |
delayed_classical_gram_schmidt) |
| 1697 |
{ |
| 1698 |
n += 1; |
| 1699 |
if (!orthogonalization_finished) |
| 1700 |
{ |
| 1701 |
tmp_triangular_matrix = triangular_matrix; |
| 1702 |
tmp_rhs = projected_rhs; |
| 1703 |
std::vector<std::pair<double, double>> tmp_givens_rotations( |
| 1704 |
givens_rotations); |
| 1705 |
do_givens_rotation(false, |
| 1706 |
givens_rotations.size(), |
| 1707 |
tmp_triangular_matrix, |
| 1708 |
tmp_givens_rotations, |
| 1709 |
tmp_rhs); |
| 1710 |
matrix = &tmp_triangular_matrix; |
| 1711 |
rhs = &tmp_rhs; |
| 1712 |
} |
| 1713 |
else |
| 1714 |
do_givens_rotation(false, |
| 1715 |
givens_rotations.size(), |
| 1716 |
triangular_matrix, |
| 1717 |
givens_rotations, |
| 1718 |
projected_rhs); |
| 1719 |
} |
| 1720 |
|
| 1721 |
// Now solve the triangular system by backward substitution |
| 1722 |
projected_solution.reinit(n); |
| 1723 |
for (int i = n - 1; i >= 0; --i) |
| 1724 |
{ |
| 1725 |
double s = (*rhs)(i); |
| 1726 |
for (unsigned int j = i + 1; j < n; ++j) |
| 1727 |
s -= projected_solution(j) * (*matrix)(i, j); |
| 1728 |
projected_solution(i) = s / (*matrix)(i, i); |
| 1729 |
AssertIsFinite(projected_solution(i)); |
| 1730 |
} |
| 1731 |
|
| 1732 |
return projected_solution; |
| 1733 |
} |
| 1734 |
|
| 1735 |
|
| 1736 |
|
| 1737 |
template <typename Number> |
| 1738 |
inline const FullMatrix<double> & |
| 1739 |
ArnoldiProcess<Number>::get_hessenberg_matrix() const |
| 1740 |
{ |
| 1741 |
return hessenberg_matrix; |
| 1742 |
} |
| 1743 |
|
| 1744 |
|
| 1745 |
|
| 1746 |
// A comparator for better printing eigenvalues |
| 1747 |
inline bool |
| 1748 |
complex_less_pred(const std::complex<double> &x, |
| 1749 |
const std::complex<double> &y) |
| 1750 |
{ |
| 1751 |
return x.real() < y.real() || |
| 1752 |
(x.real() == y.real() && x.imag() < y.imag()); |
| 1753 |
} |
| 1754 |
} // namespace SolverGMRESImplementation |
| 1755 |
} // namespace internal |
| 1756 |
|
| 1757 |
|
| 1758 |
|
| 1759 |
template <typename VectorType> |
| 1760 |
DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>) |
| 1761 |
inline void SolverGMRES<VectorType>::compute_eigs_and_cond( |
| 1762 |
const FullMatrix<double> &H_orig, |
| 1763 |
const unsigned int n, |
| 1764 |
const boost::signals2::signal<void(const std::vector<std::complex<double>> &)> |
| 1765 |
&eigenvalues_signal, |
| 1766 |
const boost::signals2::signal<void(const FullMatrix<double> &)> |
| 1767 |
&hessenberg_signal, |
| 1768 |
const boost::signals2::signal<void(double)> &cond_signal) |
| 1769 |
{ |
| 1770 |
// Avoid copying the Hessenberg matrix if it isn't needed. |
| 1771 |
if ((!eigenvalues_signal.empty() || !hessenberg_signal.empty() || |
| 1772 |
!cond_signal.empty()) && |
| 1773 |
n > 0) |
| 1774 |
{ |
| 1775 |
LAPACKFullMatrix<double> mat(n, n); |
| 1776 |
for (unsigned int i = 0; i < n; ++i) |
| 1777 |
for (unsigned int j = 0; j < n; ++j) |
| 1778 |
mat(i, j) = H_orig(i, j); |
| 1779 |
hessenberg_signal(H_orig); |
| 1780 |
// Avoid computing eigenvalues if they are not needed. |
| 1781 |
if (!eigenvalues_signal.empty()) |
| 1782 |
{ |
| 1783 |
// Copy mat so that we can compute svd below. Necessary since |
| 1784 |
// compute_eigenvalues will leave mat in state |
| 1785 |
// LAPACKSupport::unusable. |
| 1786 |
LAPACKFullMatrix<double> mat_eig(mat); |
| 1787 |
mat_eig.compute_eigenvalues(); |
| 1788 |
std::vector<std::complex<double>> eigenvalues(n); |
| 1789 |
for (unsigned int i = 0; i < mat_eig.n(); ++i) |
| 1790 |
eigenvalues[i] = mat_eig.eigenvalue(i); |
| 1791 |
// Sort eigenvalues for nicer output. |
| 1792 |
std::sort(eigenvalues.begin(), |
| 1793 |
eigenvalues.end(), |
| 1794 |
internal::SolverGMRESImplementation::complex_less_pred); |
| 1795 |
eigenvalues_signal(eigenvalues); |
| 1796 |
} |
| 1797 |
// Calculate condition number, avoid calculating the svd if a slot |
| 1798 |
// isn't connected. Need at least a 2-by-2 matrix to do the estimate. |
| 1799 |
if (!cond_signal.empty() && (mat.n() > 1)) |
| 1800 |
{ |
| 1801 |
mat.compute_svd(); |
| 1802 |
double condition_number = |
| 1803 |
mat.singular_value(0) / mat.singular_value(mat.n() - 1); |
| 1804 |
cond_signal(condition_number); |
| 1805 |
} |
| 1806 |
} |
| 1807 |
} |
| 1808 |
|
| 1809 |
|
| 1810 |
|
| 1811 |
template <typename VectorType> |
| 1812 |
DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>) |
| 1813 |
template <typename MatrixType, typename PreconditionerType> |
| 1814 |
DEAL_II_CXX20_REQUIRES( |
| 1815 |
(concepts::is_linear_operator_on<MatrixType, VectorType> && |
| 1816 |
concepts::is_linear_operator_on<PreconditionerType, VectorType>)) |
| 1817 |
void SolverGMRES<VectorType>::solve(const MatrixType &A, |
| 1818 |
VectorType &x, |
| 1819 |
const VectorType &b, |
| 1820 |
const PreconditionerType &preconditioner) |
| 1821 |
{ |
| 1822 |
std::unique_ptr<LogStream::Prefix> prefix; |
| 1823 |
if (!additional_data.batched_mode) |
| 1824 |
prefix = std::make_unique<LogStream::Prefix>("GMRES"); |
| 1825 |
|
| 1826 |
// extra call to std::max to placate static analyzers: coverity rightfully |
| 1827 |
// complains that data.max_n_tmp_vectors - 2 may overflow |
| 1828 |
const unsigned int basis_size = |
| 1829 |
(additional_data.max_basis_size > 0 ? |
| 1830 |
additional_data.max_basis_size : |
| 1831 |
std::max(additional_data.max_n_tmp_vectors, 3u) - 2); |
| 1832 |
|
| 1833 |
// Generate an object where basis vectors are stored. |
| 1834 |
internal::SolverGMRESImplementation::TmpVectors<VectorType> basis_vectors( |
| 1835 |
basis_size + 2, this->memory); |
| 1836 |
|
| 1837 |
// number of the present iteration; this number is not reset to zero upon a |
| 1838 |
// restart |
| 1839 |
unsigned int accumulated_iterations = 0; |
| 1840 |
|
| 1841 |
const bool do_eigenvalues = |
| 1842 |
!additional_data.batched_mode && |
| 1843 |
(!condition_number_signal.empty() || |
| 1844 |
!all_condition_numbers_signal.empty() || !eigenvalues_signal.empty() || |
| 1845 |
!all_eigenvalues_signal.empty() || !hessenberg_signal.empty() || |
| 1846 |
!all_hessenberg_signal.empty()); |
| 1847 |
|
| 1848 |
SolverControl::State iteration_state = SolverControl::iterate; |
| 1849 |
double res = std::numeric_limits<double>::lowest(); |
| 1850 |
|
| 1851 |
// switch to determine whether we want a left or a right preconditioner. at |
| 1852 |
// present, left is default, but both ways are implemented |
| 1853 |
const bool left_precondition = !additional_data.right_preconditioning; |
| 1854 |
|
| 1855 |
// Per default the left preconditioned GMRES uses the preconditioned |
| 1856 |
// residual and the right preconditioned GMRES uses the unpreconditioned |
| 1857 |
// residual as stopping criterion. |
| 1858 |
const bool use_default_residual = additional_data.use_default_residual; |
| 1859 |
|
| 1860 |
// define an alias |
| 1861 |
VectorType &p = basis_vectors(basis_size + 1, x); |
| 1862 |
|
| 1863 |
// Following vectors are needed when we are not using the default residuals |
| 1864 |
// as stopping criterion |
| 1865 |
typename VectorMemory<VectorType>::Pointer r; |
| 1866 |
typename VectorMemory<VectorType>::Pointer x_; |
| 1867 |
if (!use_default_residual) |
| 1868 |
{ |
| 1869 |
r = std::move(typename VectorMemory<VectorType>::Pointer(this->memory)); |
| 1870 |
x_ = std::move(typename VectorMemory<VectorType>::Pointer(this->memory)); |
| 1871 |
r->reinit(x); |
| 1872 |
x_->reinit(x); |
| 1873 |
} |
| 1874 |
|
| 1875 |
arnoldi_process.initialize(additional_data.orthogonalization_strategy, |
| 1876 |
basis_size, |
| 1877 |
additional_data.force_re_orthogonalization); |
| 1878 |
|
| 1879 |
/////////////////////////////////////////////////////////////////////////// |
| 1880 |
// outer iteration: loop until we either reach convergence or the maximum |
| 1881 |
// number of iterations is exceeded. each cycle of this loop amounts to one |
| 1882 |
// restart |
| 1883 |
do |
| 1884 |
{ |
| 1885 |
VectorType &v = basis_vectors(0, x); |
| 1886 |
|
| 1887 |
// Compute the preconditioned/unpreconditioned residual for left/right |
| 1888 |
// preconditioning. If 'x' is the zero vector, then we can bypass the |
| 1889 |
// full computation. But 'x' is only likely to be the zero vector if |
| 1890 |
// that's what the user provided as the starting guess, so it's only |
| 1891 |
// worth checking for this in the first iteration. (Calling all_zero() |
| 1892 |
// costs as much in memory transfer and communication as computing the |
| 1893 |
// norm of a vector.) |
| 1894 |
if (left_precondition) |
| 1895 |
{ |
| 1896 |
if (accumulated_iterations == 0 && x.all_zero()) |
| 1897 |
preconditioner.vmult(v, b); |
| 1898 |
else |
| 1899 |
{ |
| 1900 |
A.vmult(p, x); |
| 1901 |
p.sadd(-1., 1., b); |
| 1902 |
preconditioner.vmult(v, p); |
| 1903 |
} |
| 1904 |
} |
| 1905 |
else |
| 1906 |
{ |
| 1907 |
if (accumulated_iterations == 0 && x.all_zero()) |
| 1908 |
v = b; |
| 1909 |
else |
| 1910 |
{ |
| 1911 |
A.vmult(v, x); |
| 1912 |
v.sadd(-1., 1., b); |
| 1913 |
} |
| 1914 |
} |
| 1915 |
|
| 1916 |
const double norm_v = arnoldi_process.orthonormalize_nth_vector( |
| 1917 |
0, basis_vectors, accumulated_iterations, re_orthogonalize_signal); |
| 1918 |
|
| 1919 |
// check the residual here as well since it may be that we got the exact |
| 1920 |
// (or an almost exact) solution vector at the outset. if we wouldn't |
| 1921 |
// check here, the next scaling operation would produce garbage |
| 1922 |
if (use_default_residual) |
| 1923 |
{ |
| 1924 |
res = norm_v; |
| 1925 |
if (additional_data.batched_mode) |
| 1926 |
iteration_state = solver_control.check(accumulated_iterations, res); |
| 1927 |
else |
| 1928 |
iteration_state = |
| 1929 |
this->iteration_status(accumulated_iterations, res, x); |
| 1930 |
|
| 1931 |
if (iteration_state != SolverControl::iterate) |
| 1932 |
break; |
| 1933 |
} |
| 1934 |
else |
| 1935 |
{ |
| 1936 |
deallog << "default_res=" << norm_v << std::endl; |
| 1937 |
|
| 1938 |
if (left_precondition) |
| 1939 |
{ |
| 1940 |
A.vmult(*r, x); |
| 1941 |
r->sadd(-1., 1., b); |
| 1942 |
} |
| 1943 |
else |
| 1944 |
preconditioner.vmult(*r, v); |
| 1945 |
|
| 1946 |
res = r->l2_norm(); |
| 1947 |
if (additional_data.batched_mode) |
| 1948 |
iteration_state = solver_control.check(accumulated_iterations, res); |
| 1949 |
else |
| 1950 |
iteration_state = |
| 1951 |
this->iteration_status(accumulated_iterations, res, x); |
| 1952 |
|
| 1953 |
if (iteration_state != SolverControl::iterate) |
| 1954 |
break; |
| 1955 |
} |
| 1956 |
|
| 1957 |
// inner iteration doing at most as many steps as the size of the |
| 1958 |
// Arnoldi basis |
| 1959 |
unsigned int inner_iteration = 0; |
| 1960 |
for (; (inner_iteration < basis_size && |
| 1961 |
iteration_state == SolverControl::iterate); |
| 1962 |
++inner_iteration) |
| 1963 |
{ |
| 1964 |
++accumulated_iterations; |
| 1965 |
// yet another alias |
| 1966 |
VectorType &vv = basis_vectors(inner_iteration + 1, x); |
| 1967 |
|
| 1968 |
if (left_precondition) |
| 1969 |
{ |
| 1970 |
A.vmult(p, basis_vectors[inner_iteration]); |
| 1971 |
preconditioner.vmult(vv, p); |
| 1972 |
} |
| 1973 |
else |
| 1974 |
{ |
| 1975 |
preconditioner.vmult(p, basis_vectors[inner_iteration]); |
| 1976 |
A.vmult(vv, p); |
| 1977 |
} |
| 1978 |
|
| 1979 |
res = |
| 1980 |
arnoldi_process.orthonormalize_nth_vector(inner_iteration + 1, |
| 1981 |
basis_vectors, |
| 1982 |
accumulated_iterations, |
| 1983 |
re_orthogonalize_signal); |
| 1984 |
|
| 1985 |
if (use_default_residual) |
| 1986 |
{ |
| 1987 |
if (additional_data.batched_mode) |
| 1988 |
iteration_state = |
| 1989 |
solver_control.check(accumulated_iterations, res); |
| 1990 |
else |
| 1991 |
iteration_state = |
| 1992 |
this->iteration_status(accumulated_iterations, res, x); |
| 1993 |
} |
| 1994 |
else |
| 1995 |
{ |
| 1996 |
if (!additional_data.batched_mode) |
| 1997 |
deallog << "default_res=" << res << std::endl; |
| 1998 |
|
| 1999 |
*x_ = x; |
| 2000 |
const Vector<double> &projected_solution = |
| 2001 |
arnoldi_process.solve_projected_system(false); |
| 2002 |
|
| 2003 |
if (left_precondition) |
| 2004 |
for (unsigned int i = 0; i < inner_iteration + 1; ++i) |
| 2005 |
x_->add(projected_solution(i), basis_vectors[i]); |
| 2006 |
else |
| 2007 |
{ |
| 2008 |
p = 0.; |
| 2009 |
for (unsigned int i = 0; i < inner_iteration + 1; ++i) |
| 2010 |
p.add(projected_solution(i), basis_vectors[i]); |
| 2011 |
preconditioner.vmult(*r, p); |
| 2012 |
x_->add(1., *r); |
| 2013 |
}; |
| 2014 |
A.vmult(*r, *x_); |
| 2015 |
r->sadd(-1., 1., b); |
| 2016 |
|
| 2017 |
// Now *r contains the unpreconditioned residual!! |
| 2018 |
if (left_precondition) |
| 2019 |
{ |
| 2020 |
res = r->l2_norm(); |
| 2021 |
iteration_state = |
| 2022 |
this->iteration_status(accumulated_iterations, res, x); |
| 2023 |
} |
| 2024 |
else |
| 2025 |
{ |
| 2026 |
preconditioner.vmult(*x_, *r); |
| 2027 |
res = x_->l2_norm(); |
| 2028 |
|
| 2029 |
if (additional_data.batched_mode) |
| 2030 |
iteration_state = |
| 2031 |
solver_control.check(accumulated_iterations, res); |
| 2032 |
else |
| 2033 |
iteration_state = |
| 2034 |
this->iteration_status(accumulated_iterations, res, x); |
| 2035 |
} |
| 2036 |
} |
| 2037 |
} |
| 2038 |
|
| 2039 |
// end of inner iteration; now update the global solution vector x with |
| 2040 |
// the solution of the projected system (least-squares solution) |
| 2041 |
const Vector<double> &projected_solution = |
| 2042 |
arnoldi_process.solve_projected_system(true); |
| 2043 |
|
| 2044 |
if (do_eigenvalues) |
| 2045 |
compute_eigs_and_cond(arnoldi_process.get_hessenberg_matrix(), |
| 2046 |
inner_iteration, |
| 2047 |
all_eigenvalues_signal, |
| 2048 |
all_hessenberg_signal, |
| 2049 |
condition_number_signal); |
| 2050 |
|
| 2051 |
if (left_precondition) |
| 2052 |
dealii::internal::SolverGMRESImplementation::add( |
| 2053 |
x, |
| 2054 |
inner_iteration, |
| 2055 |
projected_solution, |
| 2056 |
basis_vectors, |
| 2057 |
false, |
| 2058 |
arnoldi_process.vector_ptrs); |
| 2059 |
else |
| 2060 |
{ |
| 2061 |
dealii::internal::SolverGMRESImplementation::add( |
| 2062 |
p, |
| 2063 |
inner_iteration, |
| 2064 |
projected_solution, |
| 2065 |
basis_vectors, |
| 2066 |
true, |
| 2067 |
arnoldi_process.vector_ptrs); |
| 2068 |
preconditioner.vmult(v, p); |
| 2069 |
x.add(1., v); |
| 2070 |
} |
| 2071 |
|
| 2072 |
// in the last round, print the eigenvalues from the last Arnoldi step |
| 2073 |
if (iteration_state != SolverControl::iterate) |
| 2074 |
{ |
| 2075 |
if (do_eigenvalues) |
| 2076 |
compute_eigs_and_cond(arnoldi_process.get_hessenberg_matrix(), |
| 2077 |
inner_iteration, |
| 2078 |
eigenvalues_signal, |
| 2079 |
hessenberg_signal, |
| 2080 |
condition_number_signal); |
| 2081 |
|
| 2082 |
if (!additional_data.batched_mode && !krylov_space_signal.empty()) |
| 2083 |
krylov_space_signal(basis_vectors); |
| 2084 |
|
| 2085 |
// end of outer iteration. restart if no convergence and the number of |
| 2086 |
// iterations is not exceeded |
| 2087 |
} |
| 2088 |
} |
| 2089 |
while (iteration_state == SolverControl::iterate); |
| 2090 |
|
| 2091 |
// in case of failure: throw exception |
| 2092 |
AssertThrow(iteration_state == SolverControl::success, |
| 2093 |
SolverControl::NoConvergence(accumulated_iterations, res)); |
| 2094 |
} |
| 2095 |
|
| 2096 |
|
| 2097 |
|
| 2098 |
template <typename VectorType> |
| 2099 |
DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>) |
| 2100 |
boost::signals2::connection |
| 2101 |
SolverGMRES<VectorType>::connect_condition_number_slot( |
| 2102 |
const std::function<void(double)> &slot, |
| 2103 |
const bool every_iteration) |
| 2104 |
{ |
| 2105 |
if (every_iteration) |
| 2106 |
{ |
| 2107 |
return all_condition_numbers_signal.connect(slot); |
| 2108 |
} |
| 2109 |
else |
| 2110 |
{ |
| 2111 |
return condition_number_signal.connect(slot); |
| 2112 |
} |
| 2113 |
} |
| 2114 |
|
| 2115 |
|
| 2116 |
|
| 2117 |
template <typename VectorType> |
| 2118 |
DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>) |
| 2119 |
boost::signals2::connection SolverGMRES<VectorType>::connect_eigenvalues_slot( |
| 2120 |
const std::function<void(const std::vector<std::complex<double>> &)> &slot, |
| 2121 |
const bool every_iteration) |
| 2122 |
{ |
| 2123 |
if (every_iteration) |
| 2124 |
{ |
| 2125 |
return all_eigenvalues_signal.connect(slot); |
| 2126 |
} |
| 2127 |
else |
| 2128 |
{ |
| 2129 |
return eigenvalues_signal.connect(slot); |
| 2130 |
} |
| 2131 |
} |
| 2132 |
|
| 2133 |
|
| 2134 |
|
| 2135 |
template <typename VectorType> |
| 2136 |
DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>) |
| 2137 |
boost::signals2::connection SolverGMRES<VectorType>::connect_hessenberg_slot( |
| 2138 |
const std::function<void(const FullMatrix<double> &)> &slot, |
| 2139 |
const bool every_iteration) |
| 2140 |
{ |
| 2141 |
if (every_iteration) |
| 2142 |
{ |
| 2143 |
return all_hessenberg_signal.connect(slot); |
| 2144 |
} |
| 2145 |
else |
| 2146 |
{ |
| 2147 |
return hessenberg_signal.connect(slot); |
| 2148 |
} |
| 2149 |
} |
| 2150 |
|
| 2151 |
|
| 2152 |
|
| 2153 |
template <typename VectorType> |
| 2154 |
DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>) |
| 2155 |
boost::signals2::connection SolverGMRES<VectorType>::connect_krylov_space_slot( |
| 2156 |
const std::function<void( |
| 2157 |
const internal::SolverGMRESImplementation::TmpVectors<VectorType> &)> &slot) |
| 2158 |
{ |
| 2159 |
return krylov_space_signal.connect(slot); |
| 2160 |
} |
| 2161 |
|
| 2162 |
|
| 2163 |
|
| 2164 |
template <typename VectorType> |
| 2165 |
DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>) |
| 2166 |
boost::signals2::connection |
| 2167 |
SolverGMRES<VectorType>::connect_re_orthogonalization_slot( |
| 2168 |
const std::function<void(int)> &slot) |
| 2169 |
{ |
| 2170 |
return re_orthogonalize_signal.connect(slot); |
| 2171 |
} |
| 2172 |
|
| 2173 |
|
| 2174 |
|
| 2175 |
template <typename VectorType> |
| 2176 |
DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>) |
| 2177 |
double SolverGMRES<VectorType>::criterion() |
| 2178 |
{ |
| 2179 |
// dummy implementation. this function is not needed for the present |
| 2180 |
// implementation of gmres |
| 2181 |
DEAL_II_ASSERT_UNREACHABLE(); |
| 2182 |
return 0; |
| 2183 |
} |
| 2184 |
|
| 2185 |
|
| 2186 |
|
| 2187 |
//----------------------------------------------------------------------// |
| 2188 |
|
| 2189 |
|
| 2190 |
|
| 2191 |
template <typename VectorType> |
| 2192 |
DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>) |
| 2193 |
SolverMPGMRES<VectorType>::SolverMPGMRES(SolverControl &cn, |
| 2194 |
VectorMemory<VectorType> &mem, |
| 2195 |
const AdditionalData &data) |
| 2196 |
: SolverBase<VectorType>(cn, mem) |
| 2197 |
, additional_data(data) |
| 2198 |
{} |
| 2199 |
|
| 2200 |
|
| 2201 |
|
| 2202 |
template <typename VectorType> |
| 2203 |
DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>) |
| 2204 |
SolverMPGMRES<VectorType>::SolverMPGMRES(SolverControl &cn, |
| 2205 |
const AdditionalData &data) |
| 2206 |
: SolverBase<VectorType>(cn) |
| 2207 |
, additional_data(data) |
| 2208 |
{} |
| 2209 |
|
| 2210 |
|
| 2211 |
|
| 2212 |
template <typename VectorType> |
| 2213 |
DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>) |
| 2214 |
template <typename MatrixType, typename... PreconditionerTypes> |
| 2215 |
DEAL_II_CXX20_REQUIRES( |
| 2216 |
(concepts::is_linear_operator_on<MatrixType, VectorType> && |
| 2217 |
(concepts::is_linear_operator_on<PreconditionerTypes, VectorType> && ...))) |
| 2218 |
void SolverMPGMRES<VectorType>::solve( |
| 2219 |
const MatrixType &A, |
| 2220 |
VectorType &x, |
| 2221 |
const VectorType &b, |
| 2222 |
const PreconditionerTypes &...preconditioners) |
| 2223 |
{ |
| 2224 |
LogStream::Prefix prefix("MPGMRES"); |
| 2225 |
|
| 2226 |
if (additional_data.use_truncated_mpgmres_strategy) |
| 2227 |
SolverMPGMRES<VectorType>::solve_internal( |
| 2228 |
A, x, b, IndexingStrategy::truncated_mpgmres, preconditioners...); |
| 2229 |
else |
| 2230 |
SolverMPGMRES<VectorType>::solve_internal( |
| 2231 |
A, x, b, IndexingStrategy::full_mpgmres, preconditioners...); |
| 2232 |
} |
| 2233 |
|
| 2234 |
|
| 2235 |
|
| 2236 |
template <typename VectorType> |
| 2237 |
DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>) |
| 2238 |
template <typename MatrixType, typename... PreconditionerTypes> |
| 2239 |
void SolverMPGMRES<VectorType>::solve_internal( |
| 2240 |
const MatrixType &A, |
| 2241 |
VectorType &x, |
| 2242 |
const VectorType &b, |
| 2243 |
const IndexingStrategy &indexing_strategy, |
| 2244 |
const PreconditionerTypes &...preconditioners) |
| 2245 |
{ |
| 2246 |
constexpr std::size_t n_preconditioners = sizeof...(PreconditionerTypes); |
| 2247 |
|
| 2248 |
// A lambda for applying the nth preconditioner to a vector src storing |
| 2249 |
// the result in dst: |
| 2250 |
|
| 2251 |
const auto apply_nth_preconditioner = [&](unsigned int n, |
| 2252 |
auto &dst, |
| 2253 |
const auto &src) { |
| 2254 |
// We cycle through all preconditioners and call the nth one: |
| 2255 |
std::size_t i = 0; |
| 2256 |
|
| 2257 |
[[maybe_unused]] bool preconditioner_called = false; |
| 2258 |
|
| 2259 |
const auto call_matching_preconditioner = [&](const auto &preconditioner) { |
| 2260 |
if (i++ == n) |
| 2261 |
{ |
| 2262 |
Assert(!preconditioner_called, dealii::ExcInternalError()); |
| 2263 |
preconditioner_called = true; |
| 2264 |
preconditioner.vmult(dst, src); |
| 2265 |
} |
| 2266 |
}; |
| 2267 |
|
| 2268 |
// https://en.cppreference.com/w/cpp/language/fold |
| 2269 |
(call_matching_preconditioner(preconditioners), ...); |
| 2270 |
Assert(preconditioner_called, dealii::ExcInternalError()); |
| 2271 |
}; |
| 2272 |
|
| 2273 |
std::size_t current_index = 0; |
| 2274 |
|
| 2275 |
// A lambda that cycles through all preconditioners in sequence while |
| 2276 |
// applying exactly one preconditioner with each function invocation to |
| 2277 |
// the vector src and storing the result in dst: |
| 2278 |
|
| 2279 |
const auto preconditioner_vmult = [&](auto &dst, const auto &src) { |
| 2280 |
// We have no preconditioner that we could apply |
| 2281 |
if (n_preconditioners == 0) |
| 2282 |
dst = src; |
| 2283 |
else |
| 2284 |
{ |
| 2285 |
apply_nth_preconditioner(current_index, dst, src); |
| 2286 |
current_index = (current_index + 1) % n_preconditioners; |
| 2287 |
} |
| 2288 |
}; |
| 2289 |
|
| 2290 |
// Return the correct index for constructing the next vector in the |
| 2291 |
// Krylov space sequence according to the chosen indexing strategy |
| 2292 |
|
| 2293 |
const auto previous_vector_index = |
| 2294 |
[n_preconditioners, indexing_strategy](unsigned int i) -> unsigned int { |
| 2295 |
// In the special case of no preconditioners we simply fall back to the |
| 2296 |
// FGMRES indexing strategy. |
| 2297 |
if (n_preconditioners == 0) |
| 2298 |
{ |
| 2299 |
return i; |
| 2300 |
} |
| 2301 |
|
| 2302 |
switch (indexing_strategy) |
| 2303 |
{ |
| 2304 |
case IndexingStrategy::fgmres: |
| 2305 |
// 0, 1, 2, 3, ... |
| 2306 |
return i; |
| 2307 |
case IndexingStrategy::full_mpgmres: |
| 2308 |
// 0, 0, ..., 1, 1, ..., 2, 2, ..., 3, 3, ... |
| 2309 |
return i / n_preconditioners; |
| 2310 |
case IndexingStrategy::truncated_mpgmres: |
| 2311 |
// 0, 0, ..., 1, 2, 3, ... |
| 2312 |
return (1 + i >= n_preconditioners) ? (1 + i - n_preconditioners) : 0; |
| 2313 |
default: |
| 2314 |
DEAL_II_ASSERT_UNREACHABLE(); |
| 2315 |
return 0; |
| 2316 |
} |
| 2317 |
}; |
| 2318 |
|
| 2319 |
SolverControl::State iteration_state = SolverControl::iterate; |
| 2320 |
|
| 2321 |
const unsigned int basis_size = additional_data.max_basis_size; |
| 2322 |
|
| 2323 |
// Generate an object where basis vectors are stored. |
| 2324 |
typename internal::SolverGMRESImplementation::TmpVectors<VectorType> v( |
| 2325 |
basis_size + 1, this->memory); |
| 2326 |
typename internal::SolverGMRESImplementation::TmpVectors<VectorType> z( |
| 2327 |
basis_size, this->memory); |
| 2328 |
|
| 2329 |
// number of the present iteration; this number is not reset to zero upon a |
| 2330 |
// restart |
| 2331 |
unsigned int accumulated_iterations = 0; |
| 2332 |
|
| 2333 |
// matrix used for the orthogonalization process later |
| 2334 |
arnoldi_process.initialize(additional_data.orthogonalization_strategy, |
| 2335 |
basis_size, |
| 2336 |
false); |
| 2337 |
|
| 2338 |
// Iteration starts here |
| 2339 |
double res = std::numeric_limits<double>::lowest(); |
| 2340 |
|
| 2341 |
do |
| 2342 |
{ |
| 2343 |
// Compute the residual. If 'x' is the zero vector, then we can bypass |
| 2344 |
// the full computation. But 'x' is only likely to be the zero vector if |
| 2345 |
// that's what the user provided as the starting guess, so it's only |
| 2346 |
// worth checking for this in the first iteration. (Calling all_zero() |
| 2347 |
// costs as much in memory transfer and communication as computing the |
| 2348 |
// norm of a vector.) |
| 2349 |
if (accumulated_iterations == 0 && x.all_zero()) |
| 2350 |
v(0, x) = b; |
| 2351 |
else |
| 2352 |
{ |
| 2353 |
A.vmult(v(0, x), x); |
| 2354 |
v[0].sadd(-1., 1., b); |
| 2355 |
} |
| 2356 |
|
| 2357 |
res = arnoldi_process.orthonormalize_nth_vector(0, v); |
| 2358 |
iteration_state = this->iteration_status(accumulated_iterations, res, x); |
| 2359 |
if (iteration_state == SolverControl::success) |
| 2360 |
break; |
| 2361 |
|
| 2362 |
unsigned int inner_iteration = 0; |
| 2363 |
for (; (inner_iteration < basis_size && |
| 2364 |
iteration_state == SolverControl::iterate); |
| 2365 |
++inner_iteration) |
| 2366 |
{ |
| 2367 |
preconditioner_vmult(z(inner_iteration, x), |
| 2368 |
v[previous_vector_index(inner_iteration)]); |
| 2369 |
A.vmult(v(inner_iteration + 1, x), z[inner_iteration]); |
| 2370 |
|
| 2371 |
res = |
| 2372 |
arnoldi_process.orthonormalize_nth_vector(inner_iteration + 1, v); |
| 2373 |
|
| 2374 |
// check convergence. note that the vector 'x' we pass to the |
| 2375 |
// criterion is not the final solution we compute if we |
| 2376 |
// decide to jump out of the iteration (we update 'x' again |
| 2377 |
// right after the current loop) |
| 2378 |
iteration_state = |
| 2379 |
this->iteration_status(++accumulated_iterations, res, x); |
| 2380 |
} |
| 2381 |
|
| 2382 |
// Solve triangular system with projected quantities and update solution |
| 2383 |
// vector |
| 2384 |
const Vector<double> &projected_solution = |
| 2385 |
arnoldi_process.solve_projected_system(true); |
| 2386 |
dealii::internal::SolverGMRESImplementation::add( |
| 2387 |
x, |
| 2388 |
inner_iteration, |
| 2389 |
projected_solution, |
| 2390 |
z, |
| 2391 |
false, |
| 2392 |
arnoldi_process.vector_ptrs); |
| 2393 |
} |
| 2394 |
while (iteration_state == SolverControl::iterate); |
| 2395 |
|
| 2396 |
// in case of failure: throw exception |
| 2397 |
if (iteration_state != SolverControl::success) |
| 2398 |
AssertThrow(false, |
| 2399 |
SolverControl::NoConvergence(accumulated_iterations, res)); |
| 2400 |
} |
| 2401 |
|
| 2402 |
|
| 2403 |
|
| 2404 |
//----------------------------------------------------------------------// |
| 2405 |
|
| 2406 |
|
| 2407 |
|
| 2408 |
template <typename VectorType> |
| 2409 |
DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>) |
| 2410 |
SolverFGMRES<VectorType>::SolverFGMRES(SolverControl &cn, |
| 2411 |
VectorMemory<VectorType> &mem, |
| 2412 |
const AdditionalData &data) |
| 2413 |
: SolverMPGMRES<VectorType>( |
| 2414 |
cn, |
| 2415 |
mem, |
| 2416 |
typename SolverMPGMRES<VectorType>::AdditionalData{ |
| 2417 |
data.max_basis_size, |
| 2418 |
data.orthogonalization_strategy, |
| 2419 |
true}) |
| 2420 |
{} |
| 2421 |
|
| 2422 |
|
| 2423 |
|
| 2424 |
template <typename VectorType> |
| 2425 |
DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>) |
| 2426 |
SolverFGMRES<VectorType>::SolverFGMRES(SolverControl &cn, |
| 2427 |
const AdditionalData &data) |
| 2428 |
: SolverMPGMRES<VectorType>( |
| 2429 |
cn, |
| 2430 |
typename SolverMPGMRES<VectorType>::AdditionalData{ |
| 2431 |
data.max_basis_size, |
| 2432 |
data.orthogonalization_strategy, |
| 2433 |
true}) |
| 2434 |
{} |
| 2435 |
|
| 2436 |
|
| 2437 |
|
| 2438 |
template <typename VectorType> |
| 2439 |
DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>) |
| 2440 |
template <typename MatrixType, typename... PreconditionerTypes> |
| 2441 |
DEAL_II_CXX20_REQUIRES( |
| 2442 |
(concepts::is_linear_operator_on<MatrixType, VectorType> && |
| 2443 |
(concepts::is_linear_operator_on<PreconditionerTypes, VectorType> && ...))) |
| 2444 |
void SolverFGMRES<VectorType>::solve( |
| 2445 |
const MatrixType &A, |
| 2446 |
VectorType &x, |
| 2447 |
const VectorType &b, |
| 2448 |
const PreconditionerTypes &...preconditioners) |
| 2449 |
{ |
| 2450 |
LogStream::Prefix prefix("FGMRES"); |
| 2451 |
SolverMPGMRES<VectorType>::solve_internal( |
| 2452 |
A, x, b, SolverFGMRES::IndexingStrategy::fgmres, preconditioners...); |
| 2453 |
} |
| 2454 |
|
| 2455 |
|
| 2456 |
#endif // DOXYGEN |
| 2457 |
|
| 2458 |
DEAL_II_NAMESPACE_CLOSE |
| 2459 |
|
| 2460 |
#endif |