| 1 |
// ------------------------------------------------------------------------ |
| 2 |
// |
| 3 |
// SPDX-License-Identifier: LGPL-2.1-or-later |
| 4 |
// Copyright (C) 2019 - 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_idr_h |
| 16 |
#define dealii_solver_idr_h |
| 17 |
|
| 18 |
|
| 19 |
#include <deal.II/base/config.h> |
| 20 |
|
| 21 |
#include <deal.II/base/enable_observer_pointer.h> |
| 22 |
#include <deal.II/base/logstream.h> |
| 23 |
#include <deal.II/base/signaling_nan.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/solver.h> |
| 29 |
#include <deal.II/lac/solver_control.h> |
| 30 |
|
| 31 |
#include <cmath> |
| 32 |
#include <random> |
| 33 |
|
| 34 |
DEAL_II_NAMESPACE_OPEN |
| 35 |
|
| 36 |
/** |
| 37 |
* @addtogroup Solvers |
| 38 |
* @{ |
| 39 |
*/ |
| 40 |
|
| 41 |
namespace internal |
| 42 |
{ |
| 43 |
/** |
| 44 |
* A namespace for a helper class to the IDR(s) solver. |
| 45 |
*/ |
| 46 |
namespace SolverIDRImplementation |
| 47 |
{ |
| 48 |
/** |
| 49 |
* Class to hold temporary vectors whose size depends on |
| 50 |
* the solver parameter s. |
| 51 |
*/ |
| 52 |
template <typename VectorType> |
| 53 |
class TmpVectors |
| 54 |
{ |
| 55 |
public: |
| 56 |
/** |
| 57 |
* Constructor. Prepares an array of @p VectorType of length @p s_param. |
| 58 |
*/ |
| 59 |
TmpVectors(const unsigned int s_param, VectorMemory<VectorType> &vmem); |
| 60 |
|
| 61 |
/** |
| 62 |
* Destructor. Delete all allocated vectors. |
| 63 |
*/ |
| 64 |
~TmpVectors() = default; |
| 65 |
|
| 66 |
/** |
| 67 |
* Get vector number @p i. If this vector was unused before, an error |
| 68 |
* occurs. |
| 69 |
*/ |
| 70 |
VectorType & |
| 71 |
operator[](const unsigned int i) const; |
| 72 |
|
| 73 |
/** |
| 74 |
* Get vector number @p i. Allocate it if necessary. |
| 75 |
* |
| 76 |
* If a vector must be allocated, @p temp is used to reinit it to the |
| 77 |
* proper dimensions. |
| 78 |
*/ |
| 79 |
VectorType & |
| 80 |
operator()(const unsigned int i, const VectorType &temp); |
| 81 |
|
| 82 |
private: |
| 83 |
/** |
| 84 |
* Pool where vectors are obtained from. |
| 85 |
*/ |
| 86 |
VectorMemory<VectorType> &mem; |
| 87 |
|
| 88 |
/** |
| 89 |
* Field for storing the vectors. |
| 90 |
*/ |
| 91 |
std::vector<typename VectorMemory<VectorType>::Pointer> data; |
| 92 |
}; |
| 93 |
} // namespace SolverIDRImplementation |
| 94 |
} // namespace internal |
| 95 |
|
| 96 |
/** |
| 97 |
* This class implements the IDR(s) method used for solving nonsymmetric, |
| 98 |
* indefinite linear systems, developed in <a |
| 99 |
* href="https://epubs.siam.org/doi/abs/10.1137/070685804"> |
| 100 |
* IDR(s): A Family of Simple and Fast Algorithms for Solving Large |
| 101 |
* Nonsymmetric Systems of Linear Equations by Martin B. van Gijzen and Peter |
| 102 |
* Sonneveld </a>. The implementation here is the preconditioned version from <a |
| 103 |
* href="https://dl.acm.org/citation.cfm?id=2049667"> |
| 104 |
* Algorithm 913: An Elegant IDR(s) Variant that Efficiently Exploits |
| 105 |
* Biorthogonality Properties |
| 106 |
* by Martin B. van Gijzen and Peter Sonneveld</a>. The local structure |
| 107 |
* @p AdditionalData takes the value for the parameter s which can be any |
| 108 |
* integer greater than or equal to 1. For <code>s=1</code>, this method has |
| 109 |
* similar convergence to BiCGStab. |
| 110 |
* |
| 111 |
* @note Each iteration of IDR(s) requires <code>s+1</code> preconditioning steps |
| 112 |
* and matrix-vector products. In this implementation the residual is updated |
| 113 |
* and convergence is checked after each of these inner steps inside the outer |
| 114 |
* iteration. If the user enables the history data, the residual at each of |
| 115 |
* these steps is stored and therefore there will be multiple values per |
| 116 |
* iteration. |
| 117 |
*/ |
| 118 |
template <typename VectorType = Vector<double>> |
| 119 |
DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>) |
| 120 |
class SolverIDR : public SolverBase<VectorType> |
| 121 |
{ |
| 122 |
public: |
| 123 |
/** |
| 124 |
* Structure for storing additional data needed by the solver. |
| 125 |
*/ |
| 126 |
struct AdditionalData |
| 127 |
{ |
| 128 |
/** |
| 129 |
* Constructor. By default, an IDR(2) method is used. |
| 130 |
*/ |
| 131 |
explicit AdditionalData(const unsigned int s = 2) |
| 132 |
: s(s) |
| 133 |
{} |
| 134 |
|
| 135 |
const unsigned int s; |
| 136 |
}; |
| 137 |
|
| 138 |
/** |
| 139 |
* Constructor. |
| 140 |
*/ |
| 141 |
SolverIDR(SolverControl &cn, |
| 142 |
VectorMemory<VectorType> &mem, |
| 143 |
const AdditionalData &data = AdditionalData()); |
| 144 |
|
| 145 |
/** |
| 146 |
* Constructor. Use an object of type GrowingVectorMemory as a default to |
| 147 |
* allocate memory. |
| 148 |
*/ |
| 149 |
explicit SolverIDR(SolverControl &cn, |
| 150 |
const AdditionalData &data = AdditionalData()); |
| 151 |
|
| 152 |
/** |
| 153 |
* Virtual destructor. |
| 154 |
*/ |
| 155 |
virtual ~SolverIDR() override = default; |
| 156 |
|
| 157 |
/** |
| 158 |
* Solve the linear system <code>Ax=b</code> for x. |
| 159 |
*/ |
| 160 |
template <typename MatrixType, typename PreconditionerType> |
| 161 |
DEAL_II_CXX20_REQUIRES( |
| 162 |
(concepts::is_linear_operator_on<MatrixType, VectorType> && |
| 163 |
concepts::is_linear_operator_on<PreconditionerType, VectorType>)) |
| 164 |
void solve(const MatrixType &A, |
| 165 |
VectorType &x, |
| 166 |
const VectorType &b, |
| 167 |
const PreconditionerType &preconditioner); |
| 168 |
|
| 169 |
protected: |
| 170 |
/** |
| 171 |
* Interface for derived class. This function gets the current iteration |
| 172 |
* vector, the residual and the update vector in each step. It can be used |
| 173 |
* for graphical output of the convergence history. |
| 174 |
*/ |
| 175 |
virtual void |
| 176 |
print_vectors(const unsigned int step, |
| 177 |
const VectorType &x, |
| 178 |
const VectorType &r, |
| 179 |
const VectorType &d) const; |
| 180 |
|
| 181 |
private: |
| 182 |
/** |
| 183 |
* Additional solver parameters. |
| 184 |
*/ |
| 185 |
AdditionalData additional_data; |
| 186 |
}; |
| 187 |
|
| 188 |
/** @} */ |
| 189 |
/*------------------------- Implementation ----------------------------*/ |
| 190 |
|
| 191 |
#ifndef DOXYGEN |
| 192 |
|
| 193 |
|
| 194 |
namespace internal |
| 195 |
{ |
| 196 |
namespace SolverIDRImplementation |
| 197 |
{ |
| 198 |
template <typename VectorType> |
| 199 |
inline TmpVectors<VectorType>::TmpVectors(const unsigned int s_param, |
| 200 |
VectorMemory<VectorType> &vmem) |
| 201 |
: mem(vmem) |
| 202 |
, data(s_param) |
| 203 |
{} |
| 204 |
|
| 205 |
|
| 206 |
|
| 207 |
template <typename VectorType> |
| 208 |
inline VectorType & |
| 209 |
TmpVectors<VectorType>::operator[](const unsigned int i) const |
| 210 |
{ |
| 211 |
AssertIndexRange(i, data.size()); |
| 212 |
|
| 213 |
Assert(data[i] != nullptr, ExcNotInitialized()); |
| 214 |
return *data[i]; |
| 215 |
} |
| 216 |
|
| 217 |
|
| 218 |
|
| 219 |
template <typename VectorType> |
| 220 |
inline VectorType & |
| 221 |
TmpVectors<VectorType>::operator()(const unsigned int i, |
| 222 |
const VectorType &temp) |
| 223 |
{ |
| 224 |
AssertIndexRange(i, data.size()); |
| 225 |
if (data[i] == nullptr) |
| 226 |
{ |
| 227 |
data[i] = std::move(typename VectorMemory<VectorType>::Pointer(mem)); |
| 228 |
data[i]->reinit(temp, true); |
| 229 |
} |
| 230 |
return *data[i]; |
| 231 |
} |
| 232 |
|
| 233 |
|
| 234 |
|
| 235 |
template <typename VectorType, |
| 236 |
std::enable_if_t<!IsBlockVector<VectorType>::value, VectorType> |
| 237 |
* = nullptr> |
| 238 |
unsigned int |
| 239 |
n_blocks(const VectorType &) |
| 240 |
{ |
| 241 |
return 1; |
| 242 |
} |
| 243 |
|
| 244 |
|
| 245 |
|
| 246 |
template <typename VectorType, |
| 247 |
std::enable_if_t<IsBlockVector<VectorType>::value, VectorType> * = |
| 248 |
nullptr> |
| 249 |
unsigned int |
| 250 |
n_blocks(const VectorType &vector) |
| 251 |
{ |
| 252 |
return vector.n_blocks(); |
| 253 |
} |
| 254 |
|
| 255 |
|
| 256 |
|
| 257 |
template <typename VectorType, |
| 258 |
std::enable_if_t<!IsBlockVector<VectorType>::value, VectorType> |
| 259 |
* = nullptr> |
| 260 |
VectorType & |
| 261 |
block(VectorType &vector, const unsigned int b) |
| 262 |
{ |
| 263 |
AssertDimension(b, 0); |
| 264 |
return vector; |
| 265 |
} |
| 266 |
|
| 267 |
|
| 268 |
|
| 269 |
template <typename VectorType, |
| 270 |
std::enable_if_t<IsBlockVector<VectorType>::value, VectorType> * = |
| 271 |
nullptr> |
| 272 |
typename VectorType::BlockType & |
| 273 |
block(VectorType &vector, const unsigned int b) |
| 274 |
{ |
| 275 |
return vector.block(b); |
| 276 |
} |
| 277 |
|
| 278 |
} // namespace SolverIDRImplementation |
| 279 |
} // namespace internal |
| 280 |
|
| 281 |
|
| 282 |
|
| 283 |
template <typename VectorType> |
| 284 |
DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>) |
| 285 |
SolverIDR<VectorType>::SolverIDR(SolverControl &cn, |
| 286 |
VectorMemory<VectorType> &mem, |
| 287 |
const AdditionalData &data) |
| 288 |
: SolverBase<VectorType>(cn, mem) |
| 289 |
, additional_data(data) |
| 290 |
{} |
| 291 |
|
| 292 |
|
| 293 |
|
| 294 |
template <typename VectorType> |
| 295 |
DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>) |
| 296 |
SolverIDR<VectorType>::SolverIDR(SolverControl &cn, const AdditionalData &data) |
| 297 |
: SolverBase<VectorType>(cn) |
| 298 |
, additional_data(data) |
| 299 |
{} |
| 300 |
|
| 301 |
|
| 302 |
|
| 303 |
template <typename VectorType> |
| 304 |
DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>) |
| 305 |
void SolverIDR<VectorType>::print_vectors(const unsigned int, |
| 306 |
const VectorType &, |
| 307 |
const VectorType &, |
| 308 |
const VectorType &) const |
| 309 |
{} |
| 310 |
|
| 311 |
|
| 312 |
|
| 313 |
template <typename VectorType> |
| 314 |
DEAL_II_CXX20_REQUIRES(concepts::is_vector_space_vector<VectorType>) |
| 315 |
template <typename MatrixType, typename PreconditionerType> |
| 316 |
DEAL_II_CXX20_REQUIRES( |
| 317 |
(concepts::is_linear_operator_on<MatrixType, VectorType> && |
| 318 |
concepts::is_linear_operator_on<PreconditionerType, VectorType>)) |
| 319 |
void SolverIDR<VectorType>::solve(const MatrixType &A, |
| 320 |
VectorType &x, |
| 321 |
const VectorType &b, |
| 322 |
const PreconditionerType &preconditioner) |
| 323 |
{ |
| 324 |
LogStream::Prefix prefix("IDR(s)"); |
| 325 |
|
| 326 |
SolverControl::State iteration_state = SolverControl::iterate; |
| 327 |
unsigned int step = 0; |
| 328 |
|
| 329 |
const unsigned int s = additional_data.s; |
| 330 |
|
| 331 |
// Define temporary vectors which do not do not depend on s |
| 332 |
typename VectorMemory<VectorType>::Pointer r_pointer(this->memory); |
| 333 |
typename VectorMemory<VectorType>::Pointer v_pointer(this->memory); |
| 334 |
typename VectorMemory<VectorType>::Pointer uhat_pointer(this->memory); |
| 335 |
|
| 336 |
VectorType &r = *r_pointer; |
| 337 |
VectorType &v = *v_pointer; |
| 338 |
VectorType &uhat = *uhat_pointer; |
| 339 |
|
| 340 |
r.reinit(x, true); |
| 341 |
v.reinit(x, true); |
| 342 |
uhat.reinit(x, true); |
| 343 |
|
| 344 |
// Initial residual |
| 345 |
A.vmult(r, x); |
| 346 |
r.sadd(-1.0, 1.0, b); |
| 347 |
|
| 348 |
using value_type = typename VectorType::value_type; |
| 349 |
using real_type = typename numbers::NumberTraits<value_type>::real_type; |
| 350 |
|
| 351 |
// Check for convergent initial guess |
| 352 |
real_type res = r.l2_norm(); |
| 353 |
iteration_state = this->iteration_status(step, res, x); |
| 354 |
if (iteration_state == SolverControl::success) |
| 355 |
return; |
| 356 |
|
| 357 |
// Initialize sets of vectors/matrices whose size dependent on s |
| 358 |
internal::SolverIDRImplementation::TmpVectors<VectorType> G(s, this->memory); |
| 359 |
internal::SolverIDRImplementation::TmpVectors<VectorType> U(s, this->memory); |
| 360 |
internal::SolverIDRImplementation::TmpVectors<VectorType> Q(s, this->memory); |
| 361 |
FullMatrix<value_type> M(s, s); |
| 362 |
|
| 363 |
// Random number generator for vector entries of |
| 364 |
// Q (normal distribution, mean=0 sigma=1) |
| 365 |
std::mt19937 rng; |
| 366 |
std::normal_distribution<> normal_distribution(0.0, 1.0); |
| 367 |
for (unsigned int i = 0; i < s; ++i) |
| 368 |
{ |
| 369 |
// Initialize vectors |
| 370 |
G(i, x); |
| 371 |
U(i, x); |
| 372 |
|
| 373 |
// Compute random set of s orthonormalized vectors Q |
| 374 |
// Note: the first vector is chosen to be the initial |
| 375 |
// residual to match BiCGStab (as is done in comparisons |
| 376 |
// with BiCGStab in the papers listed in the documentation |
| 377 |
// of this function) |
| 378 |
VectorType &tmp_q = Q(i, x); |
| 379 |
if (i != 0) |
| 380 |
{ |
| 381 |
for (unsigned int b = 0; |
| 382 |
b < internal::SolverIDRImplementation::n_blocks(tmp_q); |
| 383 |
++b) |
| 384 |
for (auto indx : internal::SolverIDRImplementation::block(tmp_q, b) |
| 385 |
.locally_owned_elements()) |
| 386 |
internal::SolverIDRImplementation::block(tmp_q, b)(indx) = |
| 387 |
normal_distribution(rng); |
| 388 |
tmp_q.compress(VectorOperation::insert); |
| 389 |
} |
| 390 |
else |
| 391 |
tmp_q = r; |
| 392 |
|
| 393 |
for (unsigned int j = 0; j < i; ++j) |
| 394 |
{ |
| 395 |
v = Q[j]; |
| 396 |
v *= (v * tmp_q) / (tmp_q * tmp_q); |
| 397 |
tmp_q.add(-1.0, v); |
| 398 |
} |
| 399 |
|
| 400 |
if (i != 0) |
| 401 |
tmp_q *= 1.0 / tmp_q.l2_norm(); |
| 402 |
|
| 403 |
M(i, i) = 1.; |
| 404 |
} |
| 405 |
|
| 406 |
value_type omega = 1.; |
| 407 |
|
| 408 |
bool early_exit = false; |
| 409 |
|
| 410 |
// Outer iteration |
| 411 |
while (iteration_state == SolverControl::iterate) |
| 412 |
{ |
| 413 |
++step; |
| 414 |
|
| 415 |
// Compute phi |
| 416 |
Vector<value_type> phi(s); |
| 417 |
for (unsigned int i = 0; i < s; ++i) |
| 418 |
phi(i) = Q[i] * r; |
| 419 |
|
| 420 |
// Inner iteration over s |
| 421 |
for (unsigned int k = 0; k < s; ++k) |
| 422 |
{ |
| 423 |
// Solve M(k:s)*gamma = phi(k:s) |
| 424 |
Vector<value_type> gamma(s - k); |
| 425 |
{ |
| 426 |
Vector<value_type> phik(s - k); |
| 427 |
FullMatrix<value_type> Mk(s - k, s - k); |
| 428 |
std::vector<unsigned int> indices; |
| 429 |
unsigned int j = 0; |
| 430 |
for (unsigned int i = k; i < s; ++i, ++j) |
| 431 |
{ |
| 432 |
indices.push_back(i); |
| 433 |
phik(j) = phi(i); |
| 434 |
} |
| 435 |
Mk.extract_submatrix_from(M, indices, indices); |
| 436 |
|
| 437 |
FullMatrix<value_type> Mk_inv(s - k, s - k); |
| 438 |
Mk_inv.invert(Mk); |
| 439 |
Mk_inv.vmult(gamma, phik); |
| 440 |
} |
| 441 |
|
| 442 |
v = r; |
| 443 |
|
| 444 |
if (step > 1) |
| 445 |
{ |
| 446 |
for (unsigned int i = k, j = 0; i < s; ++i, ++j) |
| 447 |
v.add(-gamma(j), G[i]); |
| 448 |
} |
| 449 |
|
| 450 |
preconditioner.vmult(uhat, v); |
| 451 |
|
| 452 |
if (step > 1) |
| 453 |
{ |
| 454 |
uhat.sadd(omega, gamma(0), U[k]); |
| 455 |
for (unsigned int i = k + 1, j = 1; i < s; ++i, ++j) |
| 456 |
uhat.add(gamma(j), U[i]); |
| 457 |
} |
| 458 |
else |
| 459 |
uhat *= omega; |
| 460 |
|
| 461 |
A.vmult(G[k], uhat); |
| 462 |
|
| 463 |
// Update G and U |
| 464 |
// Orthogonalize G[k] to Q0,..,Q_{k-1} and update uhat |
| 465 |
if (k > 0) |
| 466 |
{ |
| 467 |
value_type alpha = Q[0] * G[k] / M(0, 0); |
| 468 |
for (unsigned int i = 1; i < k; ++i) |
| 469 |
{ |
| 470 |
const value_type alpha_old = alpha; |
| 471 |
alpha = G[k].add_and_dot(-alpha, G[i - 1], Q[i]) / M(i, i); |
| 472 |
|
| 473 |
// update uhat every other iteration to reduce vector access |
| 474 |
if (i % 2 == 1) |
| 475 |
uhat.add(-alpha_old, U[i - 1], -alpha, U[i]); |
| 476 |
} |
| 477 |
M(k, k) = G[k].add_and_dot(-alpha, G[k - 1], Q[k]); |
| 478 |
if (k % 2 == 1) |
| 479 |
uhat.add(-alpha, U[k - 1]); |
| 480 |
} |
| 481 |
else |
| 482 |
M(k, k) = G[k] * Q[k]; |
| 483 |
|
| 484 |
U[k].swap(uhat); |
| 485 |
|
| 486 |
// Update kth column of M |
| 487 |
for (unsigned int i = k + 1; i < s; ++i) |
| 488 |
M(i, k) = Q[i] * G[k]; |
| 489 |
|
| 490 |
// Orthogonalize r to Q0,...,Qk, update x |
| 491 |
{ |
| 492 |
const value_type beta = phi(k) / M(k, k); |
| 493 |
r.add(-beta, G[k]); |
| 494 |
x.add(beta, U[k]); |
| 495 |
|
| 496 |
print_vectors(step, x, r, U[k]); |
| 497 |
|
| 498 |
// Check for early convergence. If so, store |
| 499 |
// information in early_exit so that outer iteration |
| 500 |
// is broken before recomputing the residual |
| 501 |
res = r.l2_norm(); |
| 502 |
iteration_state = this->iteration_status(step, res, x); |
| 503 |
if (iteration_state != SolverControl::iterate) |
| 504 |
{ |
| 505 |
early_exit = true; |
| 506 |
break; |
| 507 |
} |
| 508 |
|
| 509 |
// Update phi |
| 510 |
if (k + 1 < s) |
| 511 |
{ |
| 512 |
for (unsigned int i = 0; i < k + 1; ++i) |
| 513 |
phi(i) = 0.0; |
| 514 |
for (unsigned int i = k + 1; i < s; ++i) |
| 515 |
phi(i) -= beta * M(i, k); |
| 516 |
} |
| 517 |
} |
| 518 |
} |
| 519 |
if (early_exit == true) |
| 520 |
break; |
| 521 |
|
| 522 |
// Update r and x |
| 523 |
preconditioner.vmult(uhat, r); |
| 524 |
A.vmult(v, uhat); |
| 525 |
|
| 526 |
omega = (v * r) / (v * v); |
| 527 |
|
| 528 |
res = std::sqrt(r.add_and_dot(-1.0 * omega, v, r)); |
| 529 |
x.add(omega, uhat); |
| 530 |
|
| 531 |
print_vectors(step, x, r, uhat); |
| 532 |
|
| 533 |
// Check for convergence |
| 534 |
iteration_state = this->iteration_status(step, res, x); |
| 535 |
if (iteration_state != SolverControl::iterate) |
| 536 |
break; |
| 537 |
} |
| 538 |
|
| 539 |
if (iteration_state != SolverControl::success) |
| 540 |
AssertThrow(false, SolverControl::NoConvergence(step, res)); |
| 541 |
} |
| 542 |
|
| 543 |
|
| 544 |
#endif // DOXYGEN |
| 545 |
|
| 546 |
DEAL_II_NAMESPACE_CLOSE |
| 547 |
|
| 548 |
#endif |