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