| 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_precondition_block_h |
| 16 |
#define dealii_precondition_block_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/exceptions.h> |
| 23 |
#include <deal.II/base/observer_pointer.h> |
| 24 |
|
| 25 |
#include <deal.II/lac/precondition_block_base.h> |
| 26 |
|
| 27 |
#include <vector> |
| 28 |
|
| 29 |
DEAL_II_NAMESPACE_OPEN |
| 30 |
|
| 31 |
/** |
| 32 |
* @addtogroup Preconditioners |
| 33 |
* @{ |
| 34 |
*/ |
| 35 |
|
| 36 |
|
| 37 |
/** |
| 38 |
* Base class for actual block preconditioners. This class assumes the |
| 39 |
* <tt>MatrixType</tt> consisting of invertible blocks of @p blocksize on the |
| 40 |
* diagonal and provides the inversion of the diagonal blocks of the matrix. |
| 41 |
* It is not necessary for this class that the matrix be block diagonal; |
| 42 |
* rather, it applies to matrices of arbitrary structure with the minimal |
| 43 |
* property of having invertible blocks on the diagonal. The matrix must |
| 44 |
* have access to individual matrix entries. |
| 45 |
* |
| 46 |
* The block matrix structure used by this class is given, e.g., for the DG |
| 47 |
* method for the transport equation. For a downstream numbering the matrices |
| 48 |
* even have got a block lower left matrix structure, i.e. the matrices are |
| 49 |
* empty above the diagonal blocks. |
| 50 |
* |
| 51 |
* @note This class is intended to be used for matrices whose structure is |
| 52 |
* given by local contributions from disjoint cells, such as for DG methods. |
| 53 |
* It is not intended for problems where the block structure results from |
| 54 |
* different physical variables such as in the Stokes equations considered in |
| 55 |
* step-22. |
| 56 |
* |
| 57 |
* For all matrices that are empty above and below the diagonal blocks (i.e. |
| 58 |
* for all block diagonal matrices) the @p BlockJacobi preconditioner is a |
| 59 |
* direct solver. For all matrices that are empty only above the diagonal |
| 60 |
* blocks (e.g. the matrices one gets by the DG method with downstream |
| 61 |
* numbering) @p BlockSOR is a direct solver. |
| 62 |
* |
| 63 |
* This first implementation of the @p PreconditionBlock assumes the matrix |
| 64 |
* has blocks each of the same block size. Varying block sizes within the |
| 65 |
* matrix must still be implemented if needed. |
| 66 |
* |
| 67 |
* The first template parameter denotes the type of number representation in |
| 68 |
* the sparse matrix, the second denotes the type of number representation in |
| 69 |
* which the inverted diagonal block matrices are stored within this class by |
| 70 |
* <tt>invert_diagblocks()</tt>. If you don't want to use the block inversion |
| 71 |
* as an exact solver, but rather as a preconditioner, you may probably want |
| 72 |
* to store the inverted blocks with less accuracy than the original matrix; |
| 73 |
* for example, <tt>number==double, inverse_type=float</tt> might be a viable |
| 74 |
* choice. |
| 75 |
* |
| 76 |
* @see |
| 77 |
* @ref GlossBlockLA "Block (linear algebra)" |
| 78 |
*/ |
| 79 |
template <typename MatrixType, |
| 80 |
typename inverse_type = typename MatrixType::value_type> |
| 81 |
class PreconditionBlock : public virtual EnableObserverPointer, |
| 82 |
protected PreconditionBlockBase<inverse_type> |
| 83 |
{ |
| 84 |
private: |
| 85 |
/** |
| 86 |
* Define number type of matrix. |
| 87 |
*/ |
| 88 |
using number = typename MatrixType::value_type; |
| 89 |
|
| 90 |
/** |
| 91 |
* Value type for inverse matrices. |
| 92 |
*/ |
| 93 |
using value_type = inverse_type; |
| 94 |
|
| 95 |
public: |
| 96 |
/** |
| 97 |
* Declare type for container size. |
| 98 |
*/ |
| 99 |
using size_type = types::global_dof_index; |
| 100 |
|
| 101 |
/** |
| 102 |
* Parameters for block preconditioners. |
| 103 |
*/ |
| 104 |
class AdditionalData |
| 105 |
{ |
| 106 |
public: |
| 107 |
/** |
| 108 |
* Constructor. Block size must be given since there is no reasonable |
| 109 |
* default parameter. |
| 110 |
*/ |
| 111 |
AdditionalData(const size_type block_size, |
| 112 |
const double relaxation = 1., |
| 113 |
const bool invert_diagonal = true, |
| 114 |
const bool same_diagonal = false); |
| 115 |
|
| 116 |
/** |
| 117 |
* Relaxation parameter. |
| 118 |
*/ |
| 119 |
double relaxation; |
| 120 |
|
| 121 |
/** |
| 122 |
* Block size. |
| 123 |
*/ |
| 124 |
size_type block_size; |
| 125 |
|
| 126 |
/** |
| 127 |
* Invert diagonal during initialization. |
| 128 |
*/ |
| 129 |
bool invert_diagonal; |
| 130 |
|
| 131 |
/** |
| 132 |
* Assume all diagonal blocks are equal to save memory. |
| 133 |
*/ |
| 134 |
bool same_diagonal; |
| 135 |
/** |
| 136 |
* Choose the inversion method for the blocks. |
| 137 |
*/ |
| 138 |
typename PreconditionBlockBase<inverse_type>::Inversion inversion; |
| 139 |
|
| 140 |
/** |
| 141 |
* The if #inversion is SVD, the threshold below which a singular value |
| 142 |
* will be considered zero and thus not inverted. This parameter is used |
| 143 |
* in the call to LAPACKFullMatrix::compute_inverse_svd(). |
| 144 |
*/ |
| 145 |
double threshold; |
| 146 |
}; |
| 147 |
|
| 148 |
|
| 149 |
/** |
| 150 |
* Constructor. |
| 151 |
*/ |
| 152 |
PreconditionBlock(bool store_diagonals = false); |
| 153 |
|
| 154 |
/** |
| 155 |
* Destructor. |
| 156 |
*/ |
| 157 |
~PreconditionBlock() override = default; |
| 158 |
|
| 159 |
/** |
| 160 |
* Initialize matrix and block size. We store the matrix and the block size |
| 161 |
* in the preconditioner object. In a second step, the inverses of the |
| 162 |
* diagonal blocks may be computed. |
| 163 |
* |
| 164 |
* Additionally, a relaxation parameter for derived classes may be provided. |
| 165 |
*/ |
| 166 |
void |
| 167 |
initialize(const MatrixType &A, const AdditionalData parameters); |
| 168 |
|
| 169 |
protected: |
| 170 |
/** |
| 171 |
* Initialize matrix and block size for permuted preconditioning. |
| 172 |
* Additionally to the parameters of the other initialize() function, we |
| 173 |
* hand over two index vectors with the permutation and its inverse. For the |
| 174 |
* meaning of these vectors see PreconditionBlockSOR. |
| 175 |
* |
| 176 |
* In a second step, the inverses of the diagonal blocks may be computed. |
| 177 |
* Make sure you use invert_permuted_diagblocks() to yield consistent data. |
| 178 |
* |
| 179 |
* Additionally, a relaxation parameter for derived classes may be provided. |
| 180 |
*/ |
| 181 |
void |
| 182 |
initialize(const MatrixType &A, |
| 183 |
const std::vector<size_type> &permutation, |
| 184 |
const std::vector<size_type> &inverse_permutation, |
| 185 |
const AdditionalData parameters); |
| 186 |
|
| 187 |
/** |
| 188 |
* Set either the permutation of rows or the permutation of blocks, |
| 189 |
* depending on the size of the vector. |
| 190 |
* |
| 191 |
* If the size of the permutation vectors is equal to the dimension of the |
| 192 |
* linear system, it is assumed that rows are permuted individually. In this |
| 193 |
* case, set_permutation() must be called before initialize(), since the |
| 194 |
* diagonal blocks are built from the permuted entries of the matrix. |
| 195 |
* |
| 196 |
* If the size of the permutation vector is not equal to the dimension of |
| 197 |
* the system, the diagonal blocks are computed from the unpermuted entries. |
| 198 |
* Instead, the relaxation methods step() and Tstep() are executed applying |
| 199 |
* the blocks in the order given by the permutation vector. They will throw |
| 200 |
* an exception if length of this vector is not equal to the number of |
| 201 |
* blocks. |
| 202 |
* |
| 203 |
* @note Permutation of blocks can only be applied to the relaxation |
| 204 |
* operators step() and Tstep(), not to the preconditioning operators |
| 205 |
* vmult() and Tvmult(). |
| 206 |
* |
| 207 |
* @note It is safe to call set_permutation() before initialize(), while the |
| 208 |
* other order is only admissible for block permutation. |
| 209 |
*/ |
| 210 |
void |
| 211 |
set_permutation(const std::vector<size_type> &permutation, |
| 212 |
const std::vector<size_type> &inverse_permutation); |
| 213 |
|
| 214 |
/** |
| 215 |
* Replacement of invert_diagblocks() for permuted preconditioning. |
| 216 |
*/ |
| 217 |
void |
| 218 |
invert_permuted_diagblocks(); |
| 219 |
|
| 220 |
public: |
| 221 |
/** |
| 222 |
* Deletes the inverse diagonal block matrices if existent, sets the |
| 223 |
* blocksize to 0, hence leaves the class in the state that it had directly |
| 224 |
* after calling the constructor. |
| 225 |
*/ |
| 226 |
void |
| 227 |
clear(); |
| 228 |
|
| 229 |
/** |
| 230 |
* Check whether the object is empty. |
| 231 |
*/ |
| 232 |
bool |
| 233 |
empty() const; |
| 234 |
|
| 235 |
/** |
| 236 |
* Read-only access to entries. This function is only possible if the |
| 237 |
* inverse diagonal blocks are stored. |
| 238 |
*/ |
| 239 |
value_type |
| 240 |
el(size_type i, size_type j) const; |
| 241 |
|
| 242 |
/** |
| 243 |
* Stores the inverse of the diagonal blocks in @p inverse. This costs some |
| 244 |
* additional memory - for DG methods about 1/3 (for double inverses) or 1/6 |
| 245 |
* (for float inverses) of that used for the matrix - but it makes the |
| 246 |
* preconditioning much faster. |
| 247 |
* |
| 248 |
* It is not allowed to call this function twice (will produce an error) |
| 249 |
* before a call of <tt>clear(...)</tt> because at the second time there |
| 250 |
* already exist the inverse matrices. |
| 251 |
* |
| 252 |
* After this function is called, the lock on the matrix given through the |
| 253 |
* @p use_matrix function is released, i.e. you may overwrite of delete it. |
| 254 |
* You may want to do this in case you use this matrix to precondition |
| 255 |
* another matrix. |
| 256 |
*/ |
| 257 |
void |
| 258 |
invert_diagblocks(); |
| 259 |
|
| 260 |
/** |
| 261 |
* Perform one block relaxation step in forward numbering. |
| 262 |
* |
| 263 |
* Depending on the arguments @p dst and @p pref, this performs an SOR step |
| 264 |
* (both reference the same vector) of a Jacobi step (both different |
| 265 |
* vectors). For the Jacobi step, the calling function must copy @p dst to |
| 266 |
* @p pref after this. |
| 267 |
* |
| 268 |
* @note If a permutation is set, it is automatically honored by this |
| 269 |
* function. |
| 270 |
*/ |
| 271 |
template <typename number2> |
| 272 |
void |
| 273 |
forward_step(Vector<number2> &dst, |
| 274 |
const Vector<number2> &prev, |
| 275 |
const Vector<number2> &src, |
| 276 |
const bool transpose_diagonal) const; |
| 277 |
|
| 278 |
/** |
| 279 |
* Perform one block relaxation step in backward numbering. |
| 280 |
* |
| 281 |
* Depending on the arguments @p dst and @p pref, this performs an SOR step |
| 282 |
* (both reference the same vector) of a Jacobi step (both different |
| 283 |
* vectors). For the Jacobi step, the calling function must copy @p dst to |
| 284 |
* @p pref after this. |
| 285 |
* |
| 286 |
* @note If a permutation is set, it is automatically honored by this |
| 287 |
* function. |
| 288 |
*/ |
| 289 |
template <typename number2> |
| 290 |
void |
| 291 |
backward_step(Vector<number2> &dst, |
| 292 |
const Vector<number2> &prev, |
| 293 |
const Vector<number2> &src, |
| 294 |
const bool transpose_diagonal) const; |
| 295 |
|
| 296 |
|
| 297 |
/** |
| 298 |
* Return the size of the blocks. |
| 299 |
*/ |
| 300 |
size_type |
| 301 |
block_size() const; |
| 302 |
|
| 303 |
/** |
| 304 |
* Determine an estimate for the memory consumption (in bytes) of this |
| 305 |
* object. |
| 306 |
*/ |
| 307 |
std::size_t |
| 308 |
memory_consumption() const; |
| 309 |
|
| 310 |
/** |
| 311 |
* @addtogroup Exceptions |
| 312 |
* @{ |
| 313 |
*/ |
| 314 |
|
| 315 |
/** |
| 316 |
* For non-overlapping block preconditioners, the block size must divide the |
| 317 |
* matrix size. If not, this exception gets thrown. |
| 318 |
*/ |
| 319 |
DeclException2(ExcWrongBlockSize, |
| 320 |
int, |
| 321 |
int, |
| 322 |
<< "The blocksize " << arg1 << " and the size of the matrix " |
| 323 |
<< arg2 << " do not match."); |
| 324 |
|
| 325 |
/** |
| 326 |
* Exception |
| 327 |
*/ |
| 328 |
DeclException0(ExcInverseMatricesAlreadyExist); |
| 329 |
|
| 330 |
/** @} */ |
| 331 |
|
| 332 |
protected: |
| 333 |
/** |
| 334 |
* Size of the blocks. Each diagonal block is assumed to be of the same |
| 335 |
* size. |
| 336 |
*/ |
| 337 |
size_type blocksize; |
| 338 |
|
| 339 |
/** |
| 340 |
* Pointer to the matrix. Make sure that the matrix exists as long as this |
| 341 |
* class needs it, i.e. until calling @p invert_diagblocks, or (if the |
| 342 |
* inverse matrices should not be stored) until the last call of the |
| 343 |
* preconditoining @p vmult function of the derived classes. |
| 344 |
*/ |
| 345 |
ObserverPointer<const MatrixType, PreconditionBlock<MatrixType, inverse_type>> |
| 346 |
A; |
| 347 |
/** |
| 348 |
* Relaxation parameter to be used by derived classes. |
| 349 |
*/ |
| 350 |
double relaxation; |
| 351 |
|
| 352 |
/** |
| 353 |
* The permutation vector |
| 354 |
*/ |
| 355 |
std::vector<size_type> permutation; |
| 356 |
|
| 357 |
/** |
| 358 |
* The inverse permutation vector |
| 359 |
*/ |
| 360 |
std::vector<size_type> inverse_permutation; |
| 361 |
}; |
| 362 |
|
| 363 |
|
| 364 |
|
| 365 |
/** |
| 366 |
* Block Jacobi preconditioning. See PreconditionBlock for requirements on the |
| 367 |
* matrix. This class satisfies the |
| 368 |
* @ref ConceptRelaxationType "relaxation concept". |
| 369 |
* |
| 370 |
* @note Instantiations for this template are provided for <tt>@<float@> and |
| 371 |
* @<double@></tt>; others can be generated in application programs (see the |
| 372 |
* section on |
| 373 |
* @ref Instantiations |
| 374 |
* in the manual). |
| 375 |
*/ |
| 376 |
template <typename MatrixType, |
| 377 |
typename inverse_type = typename MatrixType::value_type> |
| 378 |
class PreconditionBlockJacobi |
| 379 |
: public virtual EnableObserverPointer, |
| 380 |
private PreconditionBlock<MatrixType, inverse_type> |
| 381 |
{ |
| 382 |
private: |
| 383 |
/** |
| 384 |
* Define number type of matrix. |
| 385 |
*/ |
| 386 |
using number = typename MatrixType::value_type; |
| 387 |
|
| 388 |
public: |
| 389 |
/** |
| 390 |
* Declare type for container size. |
| 391 |
*/ |
| 392 |
using size_type = types::global_dof_index; |
| 393 |
|
| 394 |
/** |
| 395 |
* Standard-conforming iterator. |
| 396 |
*/ |
| 397 |
class const_iterator |
| 398 |
{ |
| 399 |
private: |
| 400 |
/** |
| 401 |
* Accessor class for iterators |
| 402 |
*/ |
| 403 |
class Accessor |
| 404 |
{ |
| 405 |
public: |
| 406 |
/** |
| 407 |
* Constructor. Since we use accessors only for read access, a const |
| 408 |
* matrix pointer is sufficient. |
| 409 |
*/ |
| 410 |
Accessor(const PreconditionBlockJacobi<MatrixType, inverse_type> *matrix, |
| 411 |
const size_type row); |
| 412 |
|
| 413 |
/** |
| 414 |
* Row number of the element represented by this object. |
| 415 |
*/ |
| 416 |
size_type |
| 417 |
row() const; |
| 418 |
|
| 419 |
/** |
| 420 |
* Column number of the element represented by this object. |
| 421 |
*/ |
| 422 |
size_type |
| 423 |
column() const; |
| 424 |
|
| 425 |
/** |
| 426 |
* Value of this matrix entry. |
| 427 |
*/ |
| 428 |
inverse_type |
| 429 |
value() const; |
| 430 |
|
| 431 |
protected: |
| 432 |
/** |
| 433 |
* The matrix accessed. |
| 434 |
*/ |
| 435 |
const PreconditionBlockJacobi<MatrixType, inverse_type> *matrix; |
| 436 |
|
| 437 |
/** |
| 438 |
* Save block size here for further reference. |
| 439 |
*/ |
| 440 |
size_type bs; |
| 441 |
|
| 442 |
/** |
| 443 |
* Current block number. |
| 444 |
*/ |
| 445 |
size_type a_block; |
| 446 |
|
| 447 |
/** |
| 448 |
* Iterator inside block. |
| 449 |
*/ |
| 450 |
typename FullMatrix<inverse_type>::const_iterator b_iterator; |
| 451 |
|
| 452 |
/** |
| 453 |
* End of current block. |
| 454 |
*/ |
| 455 |
typename FullMatrix<inverse_type>::const_iterator b_end; |
| 456 |
|
| 457 |
// Make enclosing class a friend. |
| 458 |
friend class const_iterator; |
| 459 |
}; |
| 460 |
|
| 461 |
public: |
| 462 |
/** |
| 463 |
* Constructor. |
| 464 |
*/ |
| 465 |
const_iterator( |
| 466 |
const PreconditionBlockJacobi<MatrixType, inverse_type> *matrix, |
| 467 |
const size_type row); |
| 468 |
|
| 469 |
/** |
| 470 |
* Prefix increment. |
| 471 |
*/ |
| 472 |
const_iterator & |
| 473 |
operator++(); |
| 474 |
|
| 475 |
/** |
| 476 |
* Dereferencing operator. |
| 477 |
*/ |
| 478 |
const Accessor & |
| 479 |
operator*() const; |
| 480 |
|
| 481 |
/** |
| 482 |
* Dereferencing operator. |
| 483 |
*/ |
| 484 |
const Accessor * |
| 485 |
operator->() const; |
| 486 |
|
| 487 |
/** |
| 488 |
* Comparison. True, if both iterators point to the same matrix position. |
| 489 |
*/ |
| 490 |
bool |
| 491 |
operator==(const const_iterator &) const; |
| 492 |
/** |
| 493 |
* Inverse of <tt>==</tt>. |
| 494 |
*/ |
| 495 |
bool |
| 496 |
operator!=(const const_iterator &) const; |
| 497 |
|
| 498 |
/** |
| 499 |
* Comparison operator. Result is true if either the first row number is |
| 500 |
* smaller or if the row numbers are equal and the first index is smaller. |
| 501 |
*/ |
| 502 |
bool |
| 503 |
operator<(const const_iterator &) const; |
| 504 |
|
| 505 |
private: |
| 506 |
/** |
| 507 |
* Store an object of the accessor class. |
| 508 |
*/ |
| 509 |
Accessor accessor; |
| 510 |
}; |
| 511 |
|
| 512 |
/** |
| 513 |
* import functions from private base class |
| 514 |
*/ |
| 515 |
using typename PreconditionBlock<MatrixType, inverse_type>::AdditionalData; |
| 516 |
using PreconditionBlock<MatrixType, inverse_type>::initialize; |
| 517 |
using PreconditionBlock<MatrixType, inverse_type>::clear; |
| 518 |
using PreconditionBlock<MatrixType, inverse_type>::empty; |
| 519 |
using PreconditionBlock<MatrixType, inverse_type>::el; |
| 520 |
using PreconditionBlock<MatrixType, inverse_type>::invert_diagblocks; |
| 521 |
using PreconditionBlock<MatrixType, inverse_type>::block_size; |
| 522 |
using PreconditionBlockBase<inverse_type>::size; |
| 523 |
using PreconditionBlockBase<inverse_type>::inverse; |
| 524 |
using PreconditionBlockBase<inverse_type>::inverse_householder; |
| 525 |
using PreconditionBlockBase<inverse_type>::inverse_svd; |
| 526 |
using PreconditionBlockBase<inverse_type>::log_statistics; |
| 527 |
using PreconditionBlock<MatrixType, inverse_type>::set_permutation; |
| 528 |
|
| 529 |
/** |
| 530 |
* Execute block Jacobi preconditioning. |
| 531 |
* |
| 532 |
* This function will automatically use the inverse matrices if they exist, |
| 533 |
* if not then BlockJacobi will need much time inverting the diagonal block |
| 534 |
* matrices in each preconditioning step. |
| 535 |
*/ |
| 536 |
template <typename number2> |
| 537 |
void |
| 538 |
vmult(Vector<number2> &, const Vector<number2> &) const; |
| 539 |
|
| 540 |
/** |
| 541 |
* Same as @p vmult, since Jacobi is symmetric. |
| 542 |
*/ |
| 543 |
template <typename number2> |
| 544 |
void |
| 545 |
Tvmult(Vector<number2> &, const Vector<number2> &) const; |
| 546 |
/** |
| 547 |
* Execute block Jacobi preconditioning, adding to @p dst. |
| 548 |
* |
| 549 |
* This function will automatically use the inverse matrices if they exist, |
| 550 |
* if not then BlockJacobi will need much time inverting the diagonal block |
| 551 |
* matrices in each preconditioning step. |
| 552 |
*/ |
| 553 |
template <typename number2> |
| 554 |
void |
| 555 |
vmult_add(Vector<number2> &, const Vector<number2> &) const; |
| 556 |
|
| 557 |
/** |
| 558 |
* Same as @p vmult_add, since Jacobi is symmetric. |
| 559 |
*/ |
| 560 |
template <typename number2> |
| 561 |
void |
| 562 |
Tvmult_add(Vector<number2> &, const Vector<number2> &) const; |
| 563 |
|
| 564 |
/** |
| 565 |
* Perform one step of the Jacobi iteration. |
| 566 |
*/ |
| 567 |
template <typename number2> |
| 568 |
void |
| 569 |
step(Vector<number2> &dst, const Vector<number2> &rhs) const; |
| 570 |
|
| 571 |
/** |
| 572 |
* Perform one step of the Jacobi iteration. |
| 573 |
*/ |
| 574 |
template <typename number2> |
| 575 |
void |
| 576 |
Tstep(Vector<number2> &dst, const Vector<number2> &rhs) const; |
| 577 |
|
| 578 |
/** |
| 579 |
* Iterator starting at the first entry. |
| 580 |
*/ |
| 581 |
const_iterator |
| 582 |
begin() const; |
| 583 |
|
| 584 |
/** |
| 585 |
* Final iterator. |
| 586 |
*/ |
| 587 |
const_iterator |
| 588 |
end() const; |
| 589 |
|
| 590 |
/** |
| 591 |
* Iterator starting at the first entry of row @p r. |
| 592 |
*/ |
| 593 |
const_iterator |
| 594 |
begin(const size_type r) const; |
| 595 |
|
| 596 |
/** |
| 597 |
* Final iterator of row @p r. |
| 598 |
*/ |
| 599 |
const_iterator |
| 600 |
end(const size_type r) const; |
| 601 |
|
| 602 |
|
| 603 |
private: |
| 604 |
/** |
| 605 |
* Actual implementation of the preconditioner. |
| 606 |
* |
| 607 |
* Depending on @p adding, the result of preconditioning is added to the |
| 608 |
* destination vector. |
| 609 |
*/ |
| 610 |
template <typename number2> |
| 611 |
void |
| 612 |
do_vmult(Vector<number2> &, const Vector<number2> &, bool adding) const; |
| 613 |
|
| 614 |
friend class Accessor; |
| 615 |
friend class const_iterator; |
| 616 |
}; |
| 617 |
|
| 618 |
|
| 619 |
|
| 620 |
/** |
| 621 |
* Block SOR preconditioning. This class satisfies the |
| 622 |
* @ref ConceptRelaxationType "relaxation concept". |
| 623 |
* |
| 624 |
* The functions @p vmult and @p Tvmult execute a (transposed) block-SOR step, |
| 625 |
* based on the blocks in PreconditionBlock. The elements outside the diagonal |
| 626 |
* blocks may be distributed arbitrarily. |
| 627 |
* |
| 628 |
* See PreconditionBlock for requirements on the matrix. The blocks used in |
| 629 |
* this class must be contiguous and non-overlapping. An overlapping Schwarz |
| 630 |
* relaxation method can be found in RelaxationBlockSOR; that class does not |
| 631 |
* offer preconditioning, though. |
| 632 |
* |
| 633 |
* <h3>Permutations</h3> |
| 634 |
* |
| 635 |
* Optionally, the entries of the source vector can be treated in the order of |
| 636 |
* the indices in the permutation vector set by #set_permutation (or the |
| 637 |
* opposite order for Tvmult()). The inverse permutation is used for storing |
| 638 |
* elements back into this vector. This functionality is automatically enabled |
| 639 |
* after a call to set_permutation() with vectors of nonzero size. |
| 640 |
* |
| 641 |
* @note The diagonal blocks, like the matrix, are not permuted! Therefore, |
| 642 |
* the permutation vector can only swap whole blocks. It may not change the |
| 643 |
* order inside blocks or swap single indices between blocks. |
| 644 |
* |
| 645 |
* <h3>Instantiations</h3> |
| 646 |
* |
| 647 |
* @note Instantiations for this template are provided for <tt>@<float@> and |
| 648 |
* @<double@></tt>; others can be generated in application programs (see the |
| 649 |
* section on |
| 650 |
* @ref Instantiations |
| 651 |
* in the manual). |
| 652 |
*/ |
| 653 |
template <typename MatrixType, |
| 654 |
typename inverse_type = typename MatrixType::value_type> |
| 655 |
class PreconditionBlockSOR |
| 656 |
: public virtual EnableObserverPointer, |
| 657 |
protected PreconditionBlock<MatrixType, inverse_type> |
| 658 |
{ |
| 659 |
public: |
| 660 |
/** |
| 661 |
* Declare type for container size. |
| 662 |
*/ |
| 663 |
using size_type = types::global_dof_index; |
| 664 |
|
| 665 |
/** |
| 666 |
* Default constructor. |
| 667 |
*/ |
| 668 |
PreconditionBlockSOR(); |
| 669 |
|
| 670 |
/** |
| 671 |
* Define number type of matrix. |
| 672 |
*/ |
| 673 |
using number = typename MatrixType::value_type; |
| 674 |
|
| 675 |
/** |
| 676 |
* import types and functions from protected base class. |
| 677 |
*/ |
| 678 |
using typename PreconditionBlock<MatrixType, inverse_type>::AdditionalData; |
| 679 |
using PreconditionBlock<MatrixType, inverse_type>::initialize; |
| 680 |
using PreconditionBlock<MatrixType, inverse_type>::clear; |
| 681 |
using PreconditionBlockBase<inverse_type>::size; |
| 682 |
using PreconditionBlockBase<inverse_type>::inverse; |
| 683 |
using PreconditionBlockBase<inverse_type>::inverse_householder; |
| 684 |
using PreconditionBlockBase<inverse_type>::inverse_svd; |
| 685 |
using PreconditionBlock<MatrixType, inverse_type>::invert_diagblocks; |
| 686 |
using PreconditionBlock<MatrixType, inverse_type>::set_permutation; |
| 687 |
using PreconditionBlockBase<inverse_type>::log_statistics; |
| 688 |
|
| 689 |
/** |
| 690 |
* Execute block SOR preconditioning. |
| 691 |
* |
| 692 |
* This function will automatically use the inverse matrices if they exist, |
| 693 |
* if not then BlockSOR will waste much time inverting the diagonal block |
| 694 |
* matrices in each preconditioning step. |
| 695 |
* |
| 696 |
* For matrices which are empty above the diagonal blocks BlockSOR is a |
| 697 |
* direct solver. |
| 698 |
*/ |
| 699 |
template <typename number2> |
| 700 |
void |
| 701 |
vmult(Vector<number2> &, const Vector<number2> &) const; |
| 702 |
|
| 703 |
/** |
| 704 |
* Execute block SOR preconditioning. |
| 705 |
* |
| 706 |
* Warning: this function performs normal @p vmult without adding. |
| 707 |
* |
| 708 |
* @see vmult |
| 709 |
*/ |
| 710 |
template <typename number2> |
| 711 |
void |
| 712 |
vmult_add(Vector<number2> &, const Vector<number2> &) const; |
| 713 |
|
| 714 |
/** |
| 715 |
* Backward application of vmult(). |
| 716 |
* |
| 717 |
* In the current implementation, this is not the transpose of vmult(). It |
| 718 |
* is a transposed Gauss-Seidel algorithm applied to the whole matrix, but |
| 719 |
* the diagonal blocks being inverted are not transposed. Therefore, it is |
| 720 |
* the transposed, if the diagonal blocks are symmetric. |
| 721 |
*/ |
| 722 |
template <typename number2> |
| 723 |
void |
| 724 |
Tvmult(Vector<number2> &, const Vector<number2> &) const; |
| 725 |
|
| 726 |
/** |
| 727 |
* Execute backward block SOR preconditioning. |
| 728 |
* |
| 729 |
* Warning: this function performs normal @p vmult without adding. |
| 730 |
* |
| 731 |
* @see vmult |
| 732 |
*/ |
| 733 |
template <typename number2> |
| 734 |
void |
| 735 |
Tvmult_add(Vector<number2> &, const Vector<number2> &) const; |
| 736 |
|
| 737 |
/** |
| 738 |
* Perform one step of the SOR iteration. |
| 739 |
*/ |
| 740 |
template <typename number2> |
| 741 |
void |
| 742 |
step(Vector<number2> &dst, const Vector<number2> &rhs) const; |
| 743 |
|
| 744 |
/** |
| 745 |
* Perform one step of the transposed SOR iteration. |
| 746 |
*/ |
| 747 |
template <typename number2> |
| 748 |
void |
| 749 |
Tstep(Vector<number2> &dst, const Vector<number2> &rhs) const; |
| 750 |
|
| 751 |
protected: |
| 752 |
/** |
| 753 |
* Constructor to be used by PreconditionBlockSSOR. |
| 754 |
*/ |
| 755 |
PreconditionBlockSOR(bool store); |
| 756 |
|
| 757 |
/** |
| 758 |
* Implementation of the forward substitution loop called by vmult() and |
| 759 |
* vmult_add(). |
| 760 |
* |
| 761 |
* If a #permutation is set by set_permutation(), it will automatically be |
| 762 |
* honored by this function. |
| 763 |
* |
| 764 |
* The parameter @p adding does not have any function, yet. |
| 765 |
*/ |
| 766 |
template <typename number2> |
| 767 |
void |
| 768 |
forward(Vector<number2> &, |
| 769 |
const Vector<number2> &, |
| 770 |
const bool transpose_diagonal, |
| 771 |
const bool adding) const; |
| 772 |
|
| 773 |
/** |
| 774 |
* Implementation of the backward substitution loop called by Tvmult() and |
| 775 |
* Tvmult_add(). |
| 776 |
* |
| 777 |
* If a #permutation is set by set_permutation(), it will automatically be |
| 778 |
* honored by this function. |
| 779 |
* |
| 780 |
* The parameter @p adding does not have any function, yet. |
| 781 |
*/ |
| 782 |
template <typename number2> |
| 783 |
void |
| 784 |
backward(Vector<number2> &, |
| 785 |
const Vector<number2> &, |
| 786 |
const bool transpose_diagonal, |
| 787 |
const bool adding) const; |
| 788 |
}; |
| 789 |
|
| 790 |
|
| 791 |
/** |
| 792 |
* Block SSOR preconditioning. This class satisfies the |
| 793 |
* @ref ConceptRelaxationType "relaxation concept". |
| 794 |
* |
| 795 |
* The functions @p vmult and @p Tvmult execute a block-SSOR step, based on |
| 796 |
* the implementation in PreconditionBlockSOR. This class requires storage of |
| 797 |
* the diagonal blocks and their inverses. |
| 798 |
* |
| 799 |
* See PreconditionBlock for requirements on the matrix. The blocks used in |
| 800 |
* this class must be contiguous and non-overlapping. An overlapping Schwarz |
| 801 |
* relaxation method can be found in RelaxationBlockSSOR; that class does not |
| 802 |
* offer preconditioning, though. |
| 803 |
* |
| 804 |
* @note Instantiations for this template are provided for <tt>@<float@> and |
| 805 |
* @<double@></tt>; others can be generated in application programs (see the |
| 806 |
* section on |
| 807 |
* @ref Instantiations |
| 808 |
* in the manual). |
| 809 |
*/ |
| 810 |
template <typename MatrixType, |
| 811 |
typename inverse_type = typename MatrixType::value_type> |
| 812 |
class PreconditionBlockSSOR |
| 813 |
: public virtual EnableObserverPointer, |
| 814 |
private PreconditionBlockSOR<MatrixType, inverse_type> |
| 815 |
{ |
| 816 |
public: |
| 817 |
/** |
| 818 |
* Declare type for container size. |
| 819 |
*/ |
| 820 |
using size_type = types::global_dof_index; |
| 821 |
|
| 822 |
/** |
| 823 |
* Define number type of matrix. |
| 824 |
*/ |
| 825 |
using number = typename MatrixType::value_type; |
| 826 |
|
| 827 |
/** |
| 828 |
* Constructor. |
| 829 |
*/ |
| 830 |
PreconditionBlockSSOR(); |
| 831 |
|
| 832 |
// Keep AdditionalData accessible |
| 833 |
using typename PreconditionBlockSOR<MatrixType, inverse_type>::AdditionalData; |
| 834 |
|
| 835 |
// The following are the |
| 836 |
// functions of the base classes |
| 837 |
// which we want to keep |
| 838 |
// accessible. |
| 839 |
/** |
| 840 |
* Make initialization function publicly available. |
| 841 |
*/ |
| 842 |
using PreconditionBlockSOR<MatrixType, inverse_type>::initialize; |
| 843 |
using PreconditionBlockSOR<MatrixType, inverse_type>::clear; |
| 844 |
using PreconditionBlockBase<inverse_type>::size; |
| 845 |
using PreconditionBlockBase<inverse_type>::inverse; |
| 846 |
using PreconditionBlockBase<inverse_type>::inverse_householder; |
| 847 |
using PreconditionBlockBase<inverse_type>::inverse_svd; |
| 848 |
using PreconditionBlockBase<inverse_type>::log_statistics; |
| 849 |
using PreconditionBlockSOR<MatrixType, inverse_type>::set_permutation; |
| 850 |
using PreconditionBlockSOR<MatrixType, inverse_type>::empty; |
| 851 |
using PreconditionBlockSOR<MatrixType, inverse_type>::el; |
| 852 |
using PreconditionBlockSOR<MatrixType, inverse_type>::invert_diagblocks; |
| 853 |
|
| 854 |
/** |
| 855 |
* Execute block SSOR preconditioning. |
| 856 |
* |
| 857 |
* This function will automatically use the inverse matrices if they exist, |
| 858 |
* if not then BlockSOR will waste much time inverting the diagonal block |
| 859 |
* matrices in each preconditioning step. |
| 860 |
*/ |
| 861 |
template <typename number2> |
| 862 |
void |
| 863 |
vmult(Vector<number2> &, const Vector<number2> &) const; |
| 864 |
|
| 865 |
/** |
| 866 |
* Same as vmult() |
| 867 |
*/ |
| 868 |
template <typename number2> |
| 869 |
void |
| 870 |
Tvmult(Vector<number2> &, const Vector<number2> &) const; |
| 871 |
|
| 872 |
/** |
| 873 |
* Perform one step of the SOR iteration. |
| 874 |
*/ |
| 875 |
template <typename number2> |
| 876 |
void |
| 877 |
step(Vector<number2> &dst, const Vector<number2> &rhs) const; |
| 878 |
|
| 879 |
/** |
| 880 |
* Perform one step of the transposed SOR iteration. |
| 881 |
*/ |
| 882 |
template <typename number2> |
| 883 |
void |
| 884 |
Tstep(Vector<number2> &dst, const Vector<number2> &rhs) const; |
| 885 |
}; |
| 886 |
|
| 887 |
/** @} */ |
| 888 |
//--------------------------------------------------------------------------- |
| 889 |
|
| 890 |
#ifndef DOXYGEN |
| 891 |
|
| 892 |
template <typename MatrixType, typename inverse_type> |
| 893 |
inline bool |
| 894 |
PreconditionBlock<MatrixType, inverse_type>::empty() const |
| 895 |
{ |
| 896 |
if (A == nullptr) |
| 897 |
return true; |
| 898 |
return A->empty(); |
| 899 |
} |
| 900 |
|
| 901 |
|
| 902 |
template <typename MatrixType, typename inverse_type> |
| 903 |
inline inverse_type |
| 904 |
PreconditionBlock<MatrixType, inverse_type>::el(size_type i, size_type j) const |
| 905 |
{ |
| 906 |
const size_type bs = blocksize; |
| 907 |
const unsigned int nb = i / bs; |
| 908 |
|
| 909 |
const FullMatrix<inverse_type> &B = this->inverse(nb); |
| 910 |
|
| 911 |
const size_type ib = i % bs; |
| 912 |
const size_type jb = j % bs; |
| 913 |
|
| 914 |
if (jb + nb * bs != j) |
| 915 |
{ |
| 916 |
return 0.; |
| 917 |
} |
| 918 |
|
| 919 |
return B(ib, jb); |
| 920 |
} |
| 921 |
|
| 922 |
//--------------------------------------------------------------------------- |
| 923 |
|
| 924 |
template <typename MatrixType, typename inverse_type> |
| 925 |
inline PreconditionBlockJacobi<MatrixType, inverse_type>::const_iterator:: |
| 926 |
Accessor::Accessor( |
| 927 |
const PreconditionBlockJacobi<MatrixType, inverse_type> *matrix, |
| 928 |
const size_type row) |
| 929 |
: matrix(matrix) |
| 930 |
, bs(matrix->block_size()) |
| 931 |
, a_block(row / bs) |
| 932 |
, b_iterator(&matrix->inverse(0), 0, 0) |
| 933 |
, b_end(&matrix->inverse(0), 0, 0) |
| 934 |
{ |
| 935 |
// This is the end accessor, which |
| 936 |
// does not have a valid block. |
| 937 |
if (a_block == matrix->size()) |
| 938 |
return; |
| 939 |
|
| 940 |
const size_type r = row % bs; |
| 941 |
|
| 942 |
b_iterator = matrix->inverse(a_block).begin(r); |
| 943 |
b_end = matrix->inverse(a_block).end(); |
| 944 |
|
| 945 |
AssertIndexRange(a_block, matrix->size()); |
| 946 |
} |
| 947 |
|
| 948 |
|
| 949 |
template <typename MatrixType, typename inverse_type> |
| 950 |
inline typename PreconditionBlockJacobi<MatrixType, inverse_type>::size_type |
| 951 |
PreconditionBlockJacobi<MatrixType, |
| 952 |
inverse_type>::const_iterator::Accessor::row() const |
| 953 |
{ |
| 954 |
Assert(a_block < matrix->size(), ExcIteratorPastEnd()); |
| 955 |
|
| 956 |
return bs * a_block + b_iterator->row(); |
| 957 |
} |
| 958 |
|
| 959 |
|
| 960 |
template <typename MatrixType, typename inverse_type> |
| 961 |
inline typename PreconditionBlockJacobi<MatrixType, inverse_type>::size_type |
| 962 |
PreconditionBlockJacobi<MatrixType, |
| 963 |
inverse_type>::const_iterator::Accessor::column() const |
| 964 |
{ |
| 965 |
Assert(a_block < matrix->size(), ExcIteratorPastEnd()); |
| 966 |
|
| 967 |
return bs * a_block + b_iterator->column(); |
| 968 |
} |
| 969 |
|
| 970 |
|
| 971 |
template <typename MatrixType, typename inverse_type> |
| 972 |
inline inverse_type |
| 973 |
PreconditionBlockJacobi<MatrixType, |
| 974 |
inverse_type>::const_iterator::Accessor::value() const |
| 975 |
{ |
| 976 |
Assert(a_block < matrix->size(), ExcIteratorPastEnd()); |
| 977 |
|
| 978 |
return b_iterator->value(); |
| 979 |
} |
| 980 |
|
| 981 |
|
| 982 |
template <typename MatrixType, typename inverse_type> |
| 983 |
inline PreconditionBlockJacobi<MatrixType, inverse_type>::const_iterator:: |
| 984 |
const_iterator( |
| 985 |
const PreconditionBlockJacobi<MatrixType, inverse_type> *matrix, |
| 986 |
const size_type row) |
| 987 |
: accessor(matrix, row) |
| 988 |
{} |
| 989 |
|
| 990 |
|
| 991 |
template <typename MatrixType, typename inverse_type> |
| 992 |
inline typename PreconditionBlockJacobi<MatrixType, |
| 993 |
inverse_type>::const_iterator & |
| 994 |
PreconditionBlockJacobi<MatrixType, inverse_type>::const_iterator::operator++() |
| 995 |
{ |
| 996 |
Assert(*this != accessor.matrix->end(), ExcIteratorPastEnd()); |
| 997 |
|
| 998 |
++accessor.b_iterator; |
| 999 |
if (accessor.b_iterator == accessor.b_end) |
| 1000 |
{ |
| 1001 |
++accessor.a_block; |
| 1002 |
|
| 1003 |
if (accessor.a_block < accessor.matrix->size()) |
| 1004 |
{ |
| 1005 |
accessor.b_iterator = |
| 1006 |
accessor.matrix->inverse(accessor.a_block).begin(); |
| 1007 |
accessor.b_end = accessor.matrix->inverse(accessor.a_block).end(); |
| 1008 |
} |
| 1009 |
} |
| 1010 |
return *this; |
| 1011 |
} |
| 1012 |
|
| 1013 |
|
| 1014 |
template <typename MatrixType, typename inverse_type> |
| 1015 |
inline const typename PreconditionBlockJacobi<MatrixType, inverse_type>:: |
| 1016 |
const_iterator::Accessor & |
| 1017 |
PreconditionBlockJacobi<MatrixType, inverse_type>::const_iterator::operator*() |
| 1018 |
const |
| 1019 |
{ |
| 1020 |
return accessor; |
| 1021 |
} |
| 1022 |
|
| 1023 |
|
| 1024 |
template <typename MatrixType, typename inverse_type> |
| 1025 |
inline const typename PreconditionBlockJacobi<MatrixType, inverse_type>:: |
| 1026 |
const_iterator::Accessor * |
| 1027 |
PreconditionBlockJacobi<MatrixType, |
| 1028 |
inverse_type>::const_iterator::operator->() const |
| 1029 |
{ |
| 1030 |
return &accessor; |
| 1031 |
} |
| 1032 |
|
| 1033 |
|
| 1034 |
template <typename MatrixType, typename inverse_type> |
| 1035 |
inline bool |
| 1036 |
PreconditionBlockJacobi<MatrixType, inverse_type>::const_iterator::operator==( |
| 1037 |
const const_iterator &other) const |
| 1038 |
{ |
| 1039 |
if (accessor.a_block == accessor.matrix->size() && |
| 1040 |
accessor.a_block == other.accessor.a_block) |
| 1041 |
return true; |
| 1042 |
|
| 1043 |
if (accessor.a_block != other.accessor.a_block) |
| 1044 |
return false; |
| 1045 |
|
| 1046 |
return (accessor.row() == other.accessor.row() && |
| 1047 |
accessor.column() == other.accessor.column()); |
| 1048 |
} |
| 1049 |
|
| 1050 |
|
| 1051 |
template <typename MatrixType, typename inverse_type> |
| 1052 |
inline bool |
| 1053 |
PreconditionBlockJacobi<MatrixType, inverse_type>::const_iterator::operator!=( |
| 1054 |
const const_iterator &other) const |
| 1055 |
{ |
| 1056 |
return !(*this == other); |
| 1057 |
} |
| 1058 |
|
| 1059 |
|
| 1060 |
template <typename MatrixType, typename inverse_type> |
| 1061 |
inline bool |
| 1062 |
PreconditionBlockJacobi<MatrixType, inverse_type>::const_iterator::operator<( |
| 1063 |
const const_iterator &other) const |
| 1064 |
{ |
| 1065 |
return (accessor.row() < other.accessor.row() || |
| 1066 |
(accessor.row() == other.accessor.row() && |
| 1067 |
accessor.column() < other.accessor.column())); |
| 1068 |
} |
| 1069 |
|
| 1070 |
|
| 1071 |
template <typename MatrixType, typename inverse_type> |
| 1072 |
inline |
| 1073 |
typename PreconditionBlockJacobi<MatrixType, inverse_type>::const_iterator |
| 1074 |
PreconditionBlockJacobi<MatrixType, inverse_type>::begin() const |
| 1075 |
{ |
| 1076 |
return const_iterator(this, 0); |
| 1077 |
} |
| 1078 |
|
| 1079 |
|
| 1080 |
template <typename MatrixType, typename inverse_type> |
| 1081 |
inline |
| 1082 |
typename PreconditionBlockJacobi<MatrixType, inverse_type>::const_iterator |
| 1083 |
PreconditionBlockJacobi<MatrixType, inverse_type>::end() const |
| 1084 |
{ |
| 1085 |
return const_iterator(this, this->size() * this->block_size()); |
| 1086 |
} |
| 1087 |
|
| 1088 |
|
| 1089 |
template <typename MatrixType, typename inverse_type> |
| 1090 |
inline |
| 1091 |
typename PreconditionBlockJacobi<MatrixType, inverse_type>::const_iterator |
| 1092 |
PreconditionBlockJacobi<MatrixType, inverse_type>::begin( |
| 1093 |
const size_type r) const |
| 1094 |
{ |
| 1095 |
AssertIndexRange(r, this->A->m()); |
| 1096 |
return const_iterator(this, r); |
| 1097 |
} |
| 1098 |
|
| 1099 |
|
| 1100 |
|
| 1101 |
template <typename MatrixType, typename inverse_type> |
| 1102 |
inline |
| 1103 |
typename PreconditionBlockJacobi<MatrixType, inverse_type>::const_iterator |
| 1104 |
PreconditionBlockJacobi<MatrixType, inverse_type>::end( |
| 1105 |
const size_type r) const |
| 1106 |
{ |
| 1107 |
AssertIndexRange(r, this->A->m()); |
| 1108 |
return const_iterator(this, r + 1); |
| 1109 |
} |
| 1110 |
|
| 1111 |
#endif // DOXYGEN |
| 1112 |
|
| 1113 |
DEAL_II_NAMESPACE_CLOSE |
| 1114 |
|
| 1115 |
#endif |