Debian Codegraph @

dune/istl/test/dilutest.cc

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
6 /** \file \brief Tests the DILU preconditioner.
7 */
8
9 #include <dune/common/fvector.hh>
10 #include <dune/common/fmatrix.hh>
11 #include <dune/common/test/testsuite.hh>
12
13 #include <dune/istl/bcrsmatrix.hh>
14 #include <dune/istl/operators.hh>
15 #include <dune/istl/preconditioners.hh>
16 #include <dune/istl/solvers.hh>
17
18
19
20 void seqDILUApplyIsCorrect1()
21 {
22 /*
23 Tests that applying the dilu preconditioner matches the expected result
24 for a 2x2 matrix, with block size 2x2.
25 A x = b
26 | | 3 1| | 1 0| | | |1| | | |2| |
27 | | 2 1| | 0 1| | | |2| | | |1| |
28 | | x | | = | |
29 | | 0 0| |-1 0| | | |1| | | |3| |
30 | | 0 0| | 0 -1| | | |1| | | |4| |
31 */
32
33
34 const int N = 2;
35 const int bz = 2;
36 const int nonZeroes = 3;
37 using Matrix = Dune::BCRSMatrix<Dune::FieldMatrix<double, bz, bz>>;
38 using Vector = Dune::BlockVector<Dune::FieldVector<double, bz>>;
39
40 using ft = typename Vector::field_type;
41 const ft myEps((ft)1e-6);
42 Dune::TestSuite t;
43
44 Matrix A(N, N, nonZeroes, Matrix::row_wise);
45 for (auto row = A.createbegin(); row != A.createend(); ++row) {
46 row.insert(row.index());
47 if (row.index() == 0) {
48 row.insert(row.index() + 1);
49 }
50 }
51
52 A[0][0][0][0]=3.0;
53 A[0][0][0][1]=1.0;
54 A[0][0][1][0]=2.0;
55 A[0][0][1][1]=1.0;
56
57 A[0][1][0][0]=1.0;
58 A[0][1][1][1]=1.0;
59
60 A[1][1][0][0]=-1.0;
61 A[1][1][1][1]=-1.0;
62
63
64 Vector x(2);
65 x[0][0] = 1.0;
66 x[0][1] = 2.0;
67 x[1][0] = 1.0;
68 x[1][1] = 1.0;
69
70 Vector b(2);
71 b[0][0] = 2.0;
72 b[0][1] = 1.0;
73 b[1][0] = 3.0;
74 b[1][1] = 4.0;
75
76
77 auto D_00 = A[0][0];
78 auto D_00_inv = D_00;
79 D_00_inv.invert();
80 // D_11 = A_11 - L_10 D_0_inv U_01 = A_11
81 auto D_11 = A[1][1];
82 auto D_11_inv = D_11;
83 D_11_inv.invert();
84
85 // define: z = M^-1(b - Ax)
86 // where: M = (D + L_A) A^-1 (D + U_A)
87 // lower triangular solve: (D + L) y = b - Ax
88 // y_0 = D_00_inv*[b_0 - (A_00*x_0 + A_01*x_1)]
89 Vector y(2);
90
91 auto rhs = b[0];
92 A[0][0].mmv(x[0], rhs);
93 A[0][1].mmv(x[1], rhs);
94 D_00_inv.mv(rhs, y[0]);
95
96 // y_1 = D_11_inv*(b_1 - (A_10*x_0 + A_11*x_1) - A_10*y_0) = D_11_inv*(b_1 - A_11*x_1)
97 rhs = b[1];
98 A[1][1].mmv(x[1], rhs);
99 D_11_inv.mv(rhs, y[1]);
100
101
102 // upper triangular solve: (D + U) z = Dy
103 // z_1 = y_1
104 Vector z(2);
105 z[1] = y[1];
106
107 // z_0 = y_0 - D_00_inv*A_01*z_1
108 z[0] = y[0];
109 auto temp = D_00_inv*A[0][1];
110 temp.mmv(z[1], z[0]);
111
112 // z is now the update x_k+1 - x_k
113
114 Dune::SeqDILU<Matrix,Vector,Vector> seqDILU(A, 1);
115 Vector v(2);
116 Vector d(b);
117 A.mmv(x, d);
118 seqDILU.apply(v, d);
119
120 // compare calculated update z from equations to update v from DILU preconditioner
121 for (int i = 0; i < 2; ++i) {
122 for (int j = 0; j < 2; ++j) {
123 t.check(std::abs(v[i][j] - z[i][j]) <= myEps)
124 << " Error in SeqDILUApplyIsCorrect1, v[" << i <<"][" << j << "]=" << v[i][j] << " != z[" << i <<"][" << j << "]=" << z[i][j];
125 }
126 }
127 }
128
129
130 void seqDILUApplyIsCorrect2()
131 {
132 /*
133 Tests that applying the DILU preconditioner matches the expected result
134 for a 3x3 matrix, with block size 3x3.
135
136 A x = b
137 | | 3 1 2| | 0 0 0| | 0 0 0| | | |1| | | |2| |
138 | | 2 3 1| | 0 0 0| | 0 0 0| | | |2| | | |1| |
139 | | 2 1 0| | 0 0 0| | 0 0 0| | | |3| | | |2| |
140 | | | | | |
141 | | 0 0 0| | 1 0 1| | 1 0 2| | | |1| | | |2| |
142 | | 0 0 0| | 4 1 0| | 0 1 1| | x | |3| | = | |3| |
143 | | 0 0 0| | 3 1 3| | 0 1 3| | | |2| | | |2| |
144 | | | | | |
145 | | 0 0 0| | 1 0 2| | 1 3 2| | | |1| | | |0| |
146 | | 0 0 0| | 0 1 4| | 2 1 3| | | |0| | | |2| |
147 | | 0 0 0| | 5 1 1| | 3 1 2| | | |2| | | |1| |
148 */
149
150 const int N = 3;
151 const int bz = 3;
152 const int nonZeroes = 5;
153 using Matrix = Dune::BCRSMatrix<Dune::FieldMatrix<double, bz, bz>>;
154 using Vector = Dune::BlockVector<Dune::FieldVector<double, bz>>;
155
156 using ft = typename Vector::field_type;
157 const ft myEps((ft)1e-6);
158 Dune::TestSuite t;
159
160 Matrix A(N, N, nonZeroes, Matrix::row_wise);
161 for (auto row = A.createbegin(); row != A.createend(); ++row) {
162 if (row.index() == 0) {
163 row.insert(row.index());
164 }
165 else if (row.index() == 1) {
166 row.insert(row.index());
167 row.insert(row.index() + 1);
168 }
169 else if (row.index() == 2) {
170 row.insert(row.index() - 1);
171 row.insert(row.index());
172 }
173 }
174
175 A[0][0][0][0]=3.0; A[1][1][0][0]=1.0; A[1][2][0][0]=1.0;
176 A[0][0][0][1]=1.0; A[1][1][0][1]=0.0; A[1][2][0][1]=0.0;
177 A[0][0][0][2]=2.0; A[1][1][0][2]=1.0; A[1][2][0][2]=2.0;
178 A[0][0][1][0]=2.0; A[1][1][1][0]=4.0; A[1][2][1][0]=0.0;
179 A[0][0][1][1]=3.0; A[1][1][1][1]=1.0; A[1][2][1][1]=1.0;
180 A[0][0][1][2]=1.0; A[1][1][1][2]=0.0; A[1][2][1][2]=1.0;
181 A[0][0][2][0]=2.0; A[1][1][2][0]=3.0; A[1][2][2][0]=0.0;
182 A[0][0][2][1]=1.0; A[1][1][2][1]=1.0; A[1][2][2][1]=1.0;
183 A[0][0][2][2]=0.0; A[1][1][2][2]=3.0; A[1][2][2][2]=3.0;
184
185 A[2][1][0][0]=1.0; A[2][2][0][0]=1.0;
186 A[2][1][0][1]=0.0; A[2][2][0][1]=3.0;
187 A[2][1][0][2]=2.0; A[2][2][0][2]=2.0;
188 A[2][1][1][0]=0.0; A[2][2][1][0]=2.0;
189 A[2][1][1][1]=1.0; A[2][2][1][1]=1.0;
190 A[2][1][1][2]=4.0; A[2][2][1][2]=3.0;
191 A[2][1][2][0]=5.0; A[2][2][2][0]=3.0;
192 A[2][1][2][1]=1.0; A[2][2][2][1]=1.0;
193 A[2][1][2][2]=1.0; A[2][2][2][2]=2.0;
194
195 Vector x(3);
196 x[0][0] = 1.0; x[1][0] = 1.0; x[2][0] = 1.0;
197 x[0][1] = 2.0; x[1][1] = 3.0; x[2][1] = 0.0;
198 x[0][2] = 3.0; x[1][2] = 2.0; x[2][2] = 2.0;
199
200 Vector b(3);
201 b[0][0] = 2.0; b[1][0] = 2.0; b[2][0] = 0.0;
202 b[0][1] = 1.0; b[1][1] = 3.0; b[2][1] = 2.0;
203 b[0][2] = 2.0; b[1][2] = 2.0; b[2][2] = 1.0;
204
205
206 // D_00 = A_00
207 auto D_00 = A[0][0];
208 auto D_00_inv = D_00;
209 D_00_inv.invert();
210 // D_11 = A_11 - L_10 D_00_inv U_01
211 // = A_11
212 auto D_11 = A[1][1];
213 auto D_11_inv = D_11;
214 D_11_inv.invert();
215 // D_22 = A_22 - A_20 D_00_inv A_02 - A_21 D_11_inv A_12
216 // = A_22 - A_21 D_11_inv A_12
217 auto D_22 = A[2][2] - A[2][1]*D_11_inv*A[1][2];
218 auto D_22_inv = D_22;
219 D_22_inv.invert();
220
221 // define: z = M^-1(b - Ax)
222 // where: M = (D + L_A) A^-1 (D + U_A)
223 // lower triangular solve: (D + L) y = b - Ax
224
225 Vector y(3);
226 // y_0 = D_00_inv*[b_0 - (A_00*x_0 + A_01*x_1)]
227 // = D_00_inv*[b_0 - A_00*x_0]
228 auto rhs = b[0];
229 A[0][0].mmv(x[0], rhs);
230 D_00_inv.mv(rhs, y[0]);
231
232 // y_1 = D_11_inv*(b_1 - (A_10*x_0 + A_11*x_1 + A_12*x_2) - A_10*y_0)
233 // = D_11_inv*(b_1 - A_11*x_1)
234 rhs = b[1];
235 A[1][1].mmv(x[1], rhs);
236 A[1][2].mmv(x[2], rhs);
237 D_11_inv.mv(rhs, y[1]);
238
239 // y_2 = D_22_inv*(b_2 - (A_20*x_0 + A_21*x_1 + A_22*x_2) - (A_20*y_0 + A_21*y_1))
240 // = D_22_inv*(b_2 - (A_21*x_1 + A_22*x_2) - (A_21*y_1))
241 rhs = b[2];
242 A[2][1].mmv(x[1], rhs);
243 A[2][2].mmv(x[2], rhs);
244 A[2][1].mmv(y[1], rhs);
245 D_22_inv.mv(rhs, y[2]);
246
247
248 // upper triangular solve: (D + U) z = Dy
249 Vector z(3);
250 // z_2 = y_2
251 z[2] = y[2];
252
253 // z_1 = y_1 - D_11_inv*A_12*z_2
254 z[1] = y[1];
255 auto temp = D_11_inv*A[1][2];
256 temp.mmv(z[2], z[1]);
257
258 // z_0 = y_0 - D_00_inv(A_01*z_1 + A_02*z_2)
259 // z_0 = y_0
260 z[0] = y[0];
261
262 // z is now the update x_k+1 - x_k
263
264 Dune::SeqDILU<Matrix,Vector,Vector> seqDILU(A, 1);
265 Vector v(3);
266 Vector d(b);
267 A.mmv(x, d);
268 seqDILU.apply(v, d);
269
270 for (int i = 0; i < 3; ++i) {
271 for (int j = 0; j < 3; ++j) {
272 t.check(std::abs(v[i][j] - z[i][j]) <= myEps)
273 << " Error in SeqDILUApplyIsCorrect2, v[" << i <<"][" << j << "]=" << v[i][j] << " != z[" << i <<"][" << j << "]=" << z[i][j];
274 }
275 }
276 }
277
278
279 void seqDILUApplyIsEqualToSeqILUApply()
280 {
281 /*
282 Tests that applying the DILU preconditioner is equivalent to applying an ILU preconditioner
283 for a block diagonal matrix.
284
285 A x = b
286 | | 3 1| | 0 0| | | |1| | | |2| |
287 | | 2 1| | 0 0| | | |2| | | |1| |
288 | | x | | = | |
289 | | 0 0| |-1 0| | | |1| | | |3| |
290 | | 0 0| | 0 -1| | | |1| | | |4| |
291 */
292
293 const int N = 2;
294 const int bz = 2;
295 const int nonZeroes = 2;
296 using Matrix = Dune::BCRSMatrix<Dune::FieldMatrix<double, bz, bz>>;
297 using Vector = Dune::BlockVector<Dune::FieldVector<double, bz>>;
298
299 using ft = typename Vector::field_type;
300 const ft myEps((ft)1e-6);
301 Dune::TestSuite t;
302
303 Matrix A(N, N, nonZeroes, Matrix::row_wise);
304 for (auto row = A.createbegin(); row != A.createend(); ++row) {
305 row.insert(row.index());
306 }
307
308 A[0][0][0][0]=3.0;
309 A[0][0][0][1]=1.0;
310 A[0][0][1][0]=2.0;
311 A[0][0][1][1]=1.0;
312
313 A[1][1][0][0]=-1.0;
314 A[1][1][1][1]=-1.0;
315
316 Vector x(2);
317 x[0][0] = 1.0;
318 x[0][1] = 2.0;
319 x[1][0] = 1.0;
320 x[1][1] = 1.0;
321
322 Vector b(2);
323 b[0][0] = 2.0;
324 b[0][1] = 1.0;
325 b[1][0] = 3.0;
326 b[1][1] = 4.0;
327
328 Dune::SeqDILU<Matrix,Vector,Vector> seqDILU(A, 1);
329 Vector v_DILU(2);
330 Vector d_DILU(b);
331 A.mmv(x, d_DILU);
332 seqDILU.apply(v_DILU, d_DILU);
333
334 Dune::SeqILU<Matrix,Vector,Vector> seqILU(A, 1);
335 Vector v_ILU(2);
336 Vector d_ILU(b);
337 A.mmv(x, d_ILU);
338 seqDILU.apply(v_ILU, d_ILU);
339
340 for (int i = 0; i < 2; ++i) {
341 for (int j = 0; j < 2; ++j) {
342 t.check(std::abs(v_DILU[i][j] - v_ILU[i][j]) <= myEps)
343 << " Error in SeqDILUApplyIsEqualToSeqILUApply, v_DILU[" << i <<"][" << j << "]=" << v_DILU[i][j] << " != v_ILU[" << i <<"][" << j << "]=" << v_ILU[i][j];
344 }
345 }
346 }
347
348
349
350
351
352
353 int main() try
354 {
355 seqDILUApplyIsCorrect1();
356 seqDILUApplyIsCorrect2();
357 seqDILUApplyIsEqualToSeqILUApply();
358
359 return 0;
360 }
361 catch (std::exception& e) {
362 std::cerr << e.what() << std::endl;
363 return 1;
364 }