Debian Codegraph @

dune/istl/dilu.hh

raw
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