| 1 |
// SPDX-FileCopyrightText: Copyright © DUNE Project contributors, see file LICENSE.md in module root |
| 2 |
// SPDX-License-Identifier: LicenseRef-GPL-2.0-only-with-DUNE-exception |
| 3 |
// -*- tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- |
| 4 |
// vi: set et ts=4 sw=2 sts=2: |
| 5 |
#ifndef DUNE_ISTL_DILU_HH |
| 6 |
#define DUNE_ISTL_DILU_HH |
| 7 |
|
| 8 |
#include <cmath> |
| 9 |
#include <complex> |
| 10 |
#include <map> |
| 11 |
#include <vector> |
| 12 |
#include <sstream> |
| 13 |
|
| 14 |
#include <dune/common/fmatrix.hh> |
| 15 |
#include <dune/common/scalarvectorview.hh> |
| 16 |
#include <dune/common/scalarmatrixview.hh> |
| 17 |
|
| 18 |
#include "istlexception.hh" |
| 19 |
|
| 20 |
/** \file |
| 21 |
* \brief The diagonal incomplete LU factorization kernels |
| 22 |
*/ |
| 23 |
|
| 24 |
namespace Dune |
| 25 |
{ |
| 26 |
|
| 27 |
/** @addtogroup ISTL_Kernel |
| 28 |
@{ |
| 29 |
*/ |
| 30 |
|
| 31 |
namespace DILU |
| 32 |
{ |
| 33 |
|
| 34 |
/*! compute DILU decomposition of A |
| 35 |
|
| 36 |
The preconditioner matrix M has the property |
| 37 |
|
| 38 |
diag(A) = diag(M) = diag((D + L_A) D^{-1} (D + U_A)) = diag(D + L_A D^{-1} U_A) |
| 39 |
|
| 40 |
such that the diagonal matrix D can be constructed: |
| 41 |
|
| 42 |
D_11 = A_11 |
| 43 |
D_22 = A22 - L_A_{21} D_{11}^{-1} U_A_{12} |
| 44 |
and etc |
| 45 |
|
| 46 |
we store the inverse of D to be used when applying the preconditioner. |
| 47 |
|
| 48 |
For more details, see: R. Barrett et al., "Templates for the Solution of Linear Systems: |
| 49 |
Building Blocks for Iterative Methods", 1994. Available from: https://www.netlib.org/templates/templates.pdf |
| 50 |
*/ |
| 51 |
template <class M> |
| 52 |
void blockDILUDecomposition(M &A, std::vector<typename M::block_type> &Dinv_) |
| 53 |
{ |
| 54 |
auto endi = A.end(); |
| 55 |
for (auto row = A.begin(); row != endi; ++row) |
| 56 |
{ |
| 57 |
const auto row_i = row.index(); |
| 58 |
const auto col = row->find(row_i); |
| 59 |
// initialise Dinv[i] = A[i, i] |
| 60 |
Dinv_[row_i] = *col; |
| 61 |
} |
| 62 |
|
| 63 |
for (auto row = A.begin(); row != endi; ++row) |
| 64 |
{ |
| 65 |
const auto row_i = row.index(); |
| 66 |
for (auto a_ij = row->begin(); a_ij.index() < row_i; ++a_ij) |
| 67 |
{ |
| 68 |
const auto col_j = a_ij.index(); |
| 69 |
const auto a_ji = A[col_j].find(row_i); |
| 70 |
// if A[i, j] != 0 and A[j, i] != 0 |
| 71 |
if (a_ji != A[col_j].end()) |
| 72 |
{ |
| 73 |
// Dinv[i] -= A[i, j] * d[j] * A[j, i] |
| 74 |
Dinv_[row_i] -= (*a_ij) * Dinv_[col_j] * (*a_ji); |
| 75 |
} |
| 76 |
} |
| 77 |
|
| 78 |
// store the inverse |
| 79 |
try |
| 80 |
{ |
| 81 |
Impl::asMatrix(Dinv_[row_i]).invert(); // compute inverse of diagonal block |
| 82 |
} |
| 83 |
catch (Dune::FMatrixError &e) |
| 84 |
{ |
| 85 |
std::ostringstream sstream; |
| 86 |
sstream << THROWSPEC(MatrixBlockError) |
| 87 |
<< "DILU failed to invert matrix block D[" << row_i << "]" << e.what(); |
| 88 |
MatrixBlockError ex; |
| 89 |
ex.message(sstream.str()); |
| 90 |
ex.r = row_i; |
| 91 |
throw ex; |
| 92 |
} |
| 93 |
} |
| 94 |
} |
| 95 |
|
| 96 |
/*! DILU backsolve |
| 97 |
|
| 98 |
M = (D + L_A) D^-1 (D + U_A) (a LU decomposition of M) |
| 99 |
where L_A and U_A are the strictly lower and upper parts of A. |
| 100 |
|
| 101 |
Working with residual d = b - Ax and update v = x_{n+1} - x_n |
| 102 |
solving the product M^-1(d) using upper and lower triangular solve: |
| 103 |
|
| 104 |
v = M^{-1} d = (D + U_A)^{-1} D (D + L_A)^{-1} d |
| 105 |
|
| 106 |
define y = (D + L_A)^{-1} d |
| 107 |
|
| 108 |
lower triangular solve: (D + L_A) y = d |
| 109 |
upper triangular solve: (D + U_A) v = D y |
| 110 |
*/ |
| 111 |
template <class M, class X, class Y> |
| 112 |
void blockDILUBacksolve(const M &A, const std::vector<typename M::block_type> Dinv_, X &v, const Y &d) |
| 113 |
{ |
| 114 |
using dblock = typename Y::block_type; |
| 115 |
using vblock = typename X::block_type; |
| 116 |
|
| 117 |
// lower triangular solve: (D + L_A) y = d |
| 118 |
auto endi = A.end(); |
| 119 |
for (auto row = A.begin(); row != endi; ++row) |
| 120 |
{ |
| 121 |
const auto row_i = row.index(); |
| 122 |
dblock rhsValue(d[row_i]); |
| 123 |
auto &&rhs = Impl::asVector(rhsValue); |
| 124 |
for (auto a_ij = (*row).begin(); a_ij.index() < row_i; ++a_ij) |
| 125 |
{ |
| 126 |
// if A[i][j] != 0 |
| 127 |
// rhs -= A[i][j]* y[j], where v_j stores y_j |
| 128 |
const auto col_j = a_ij.index(); |
| 129 |
Impl::asMatrix(*a_ij).mmv(v[col_j], rhs); |
| 130 |
} |
| 131 |
// y_i = Dinv_i * rhs |
| 132 |
// storing y_i in v_i |
| 133 |
auto &&vi = Impl::asVector(v[row_i]); |
| 134 |
Impl::asMatrix(Dinv_[row_i]).mv(rhs, vi); // (D + L_A)_ii = D_i |
| 135 |
} |
| 136 |
|
| 137 |
// upper triangular solve: (D + U_A) v = Dy |
| 138 |
auto rendi = A.beforeBegin(); |
| 139 |
for (auto row = A.beforeEnd(); row != rendi; --row) |
| 140 |
{ |
| 141 |
const auto row_i = row.index(); |
| 142 |
// rhs = 0 |
| 143 |
vblock rhs(0.0); |
| 144 |
for (auto a_ij = (*row).beforeEnd(); a_ij.index() > row_i; --a_ij) |
| 145 |
{ |
| 146 |
// if A[i][j] != 0 |
| 147 |
// rhs += A[i][j]*v[j] |
| 148 |
const auto col_j = a_ij.index(); |
| 149 |
Impl::asMatrix(*a_ij).umv(v[col_j], rhs); |
| 150 |
} |
| 151 |
// calculate update v = M^-1*d |
| 152 |
// v_i = y_i - Dinv_i*rhs |
| 153 |
// before update v_i is y_i |
| 154 |
auto &&vi = Impl::asVector(v[row_i]); |
| 155 |
Impl::asMatrix(Dinv_[row_i]).mmv(rhs, vi); |
| 156 |
} |
| 157 |
} |
| 158 |
} // end namespace DILU |
| 159 |
|
| 160 |
/** @} end documentation */ |
| 161 |
|
| 162 |
} // end namespace |
| 163 |
|
| 164 |
#endif |