Debian Codegraph @

include/deal.II/lac/sparse_ilu.templates.h

raw
1 // ------------------------------------------------------------------------
2 //
3 // SPDX-License-Identifier: LGPL-2.1-or-later
4 // Copyright (C) 1999 - 2023 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_sparse_ilu_templates_h
16 #define dealii_sparse_ilu_templates_h
17
18
19
20 #include <deal.II/base/config.h>
21
22 #include <deal.II/lac/sparse_ilu.h>
23 #include <deal.II/lac/vector.h>
24
25 #include <algorithm>
26 #include <cmath>
27
28
29 DEAL_II_NAMESPACE_OPEN
30
31
32 template <typename number>
33 template <typename somenumber>
34 void
35 SparseILU<number>::initialize(const SparseMatrix<somenumber> &matrix,
36 const AdditionalData &data)
37 {
38 SparseLUDecomposition<number>::initialize(matrix, data);
39
40 Assert(matrix.m() == matrix.n(), ExcNotQuadratic());
41 Assert(this->m() == this->n(), ExcNotQuadratic());
42 Assert(matrix.m() == this->m(), ExcDimensionMismatch(matrix.m(), this->m()));
43
44 Assert(data.strengthen_diagonal >= 0,
45 ExcInvalidStrengthening(data.strengthen_diagonal));
46
47 this->strengthen_diagonal = data.strengthen_diagonal;
48 this->prebuild_lower_bound();
49 this->copy_from(matrix);
50
51 if (data.strengthen_diagonal > 0)
52 this->strengthen_diagonal_impl();
53
54 // in the following, we implement algorithm 10.4 in the book by Saad by
55 // translating in essence the algorithm given at the end of section 10.3.2,
56 // using the names of variables used there
57 const SparsityPattern &sparsity = this->get_sparsity_pattern();
58 const std::size_t *const ia = sparsity.rowstart.get();
59 const size_type *const ja = sparsity.colnums.get();
60
61 number *luval = this->SparseMatrix<number>::val.get();
62
63 const size_type N = this->m();
64 size_type jrow = 0;
65
66 std::vector<size_type> iw(N, numbers::invalid_size_type);
67
68 for (size_type k = 0; k < N; ++k)
69 {
70 const size_type j1 = ia[k], j2 = ia[k + 1] - 1;
71
72 for (size_type j = j1; j <= j2; ++j)
73 iw[ja[j]] = j;
74
75 // the algorithm in the book works on the elements of row k left of the
76 // diagonal. however, since we store the diagonal element at the first
77 // position, start at the element after the diagonal and run as long as
78 // we don't walk into the right half
79 size_type j = j1 + 1;
80
81 // pathological case: the current row of the matrix has only the
82 // diagonal entry. then we have nothing to do.
83 if (j > j2)
84 goto label_200;
85
86 label_150:
87
88 jrow = ja[j];
89 if (jrow >= k)
90 goto label_200;
91
92 // actual computations:
93 {
94 number t1 = luval[j] * luval[ia[jrow]];
95 luval[j] = t1;
96
97 // jj runs from just right of the diagonal to the end of the row
98 size_type jj = ia[jrow] + 1;
99 while (ja[jj] < jrow)
100 ++jj;
101 for (; jj < ia[jrow + 1]; ++jj)
102 {
103 const size_type jw = iw[ja[jj]];
104 if (jw != numbers::invalid_size_type)
105 luval[jw] -= t1 * luval[jj];
106 }
107
108 ++j;
109 if (j <= j2)
110 goto label_150;
111 }
112
113 label_200:
114
115 // in the book there is an assertion that we have hit the diagonal
116 // element, i.e. that jrow==k. however, we store the diagonal element at
117 // the front, so jrow must actually be larger than k or j is already in
118 // the next row
119 Assert((jrow > k) || (j == ia[k + 1]), ExcInternalError());
120
121 // now we have to deal with the diagonal element. in the book it is
122 // located at position 'j', but here we use the convention of storing
123 // the diagonal element first, so instead of j we use uptr[k]=ia[k]
124 Assert(luval[ia[k]] != 0, ExcZeroPivot(k));
125
126 luval[ia[k]] = 1. / luval[ia[k]];
127
128 for (size_type j = j1; j <= j2; ++j)
129 iw[ja[j]] = numbers::invalid_size_type;
130 }
131 }
132
133
134
135 template <typename number>
136 template <typename somenumber>
137 void
138 SparseILU<number>::vmult(Vector<somenumber> &dst,
139 const Vector<somenumber> &src) const
140 {
141 Assert(dst.size() == src.size(),
142 ExcDimensionMismatch(dst.size(), src.size()));
143 Assert(dst.size() == this->m(), ExcDimensionMismatch(dst.size(), this->m()));
144
145 const size_type N = dst.size();
146 const std::size_t *const rowstart_indices =
147 this->get_sparsity_pattern().rowstart.get();
148 const size_type *const column_numbers =
149 this->get_sparsity_pattern().colnums.get();
150
151 // solve LUx=b in two steps:
152 // first Ly = b, then
153 // Ux = y
154 //
155 // first a forward solve. since
156 // the diagonal values of L are
157 // one, there holds
158 // y_i = b_i
159 // - sum_{j=0}^{i-1} L_{ij}y_j
160 // we split the y_i = b_i off and
161 // perform it at the outset of the
162 // loop
163 dst = src;
164 for (size_type row = 0; row < N; ++row)
165 {
166 // get start of this row. skip the
167 // diagonal element
168 const size_type *const rowstart =
169 &column_numbers[rowstart_indices[row] + 1];
170 // find the position where the part
171 // right of the diagonal starts
172 const size_type *const first_after_diagonal =
173 this->prebuilt_lower_bound[row];
174
175 somenumber dst_row = dst(row);
176 const number *luval =
177 this->SparseMatrix<number>::val.get() + (rowstart - column_numbers);
178 for (const size_type *col = rowstart; col != first_after_diagonal;
179 ++col, ++luval)
180 dst_row -= *luval * dst(*col);
181 dst(row) = dst_row;
182 }
183
184 // now the backward solve. same
185 // procedure, but we need not set
186 // dst before, since this is already
187 // done.
188 //
189 // note that we need to scale now,
190 // since the diagonal is not equal to
191 // one now
192 for (int row = N - 1; row >= 0; --row)
193 {
194 // get end of this row
195 const size_type *const rowend =
196 &column_numbers[rowstart_indices[row + 1]];
197 // find the position where the part
198 // right of the diagonal starts
199 const size_type *const first_after_diagonal =
200 this->prebuilt_lower_bound[row];
201
202 somenumber dst_row = dst(row);
203 const number *luval = this->SparseMatrix<number>::val.get() +
204 (first_after_diagonal - column_numbers);
205 for (const size_type *col = first_after_diagonal; col != rowend;
206 ++col, ++luval)
207 dst_row -= *luval * dst(*col);
208
209 // scale by the diagonal element.
210 // note that the diagonal element
211 // was stored inverted
212 dst(row) = dst_row * this->diag_element(row);
213 }
214 }
215
216
217 template <typename number>
218 template <typename somenumber>
219 void
220 SparseILU<number>::Tvmult(Vector<somenumber> &dst,
221 const Vector<somenumber> &src) const
222 {
223 Assert(dst.size() == src.size(),
224 ExcDimensionMismatch(dst.size(), src.size()));
225 Assert(dst.size() == this->m(), ExcDimensionMismatch(dst.size(), this->m()));
226
227 const size_type N = dst.size();
228 const std::size_t *const rowstart_indices =
229 this->get_sparsity_pattern().rowstart.get();
230 const size_type *const column_numbers =
231 this->get_sparsity_pattern().colnums.get();
232
233 // solve (LU)'x=b in two steps:
234 // first U'y = b, then
235 // L'x = y
236 //
237 // first a forward solve. Due to the
238 // fact that the transpose of U'
239 // is not easily accessible, a
240 // temporary vector is required.
241 Vector<somenumber> tmp(N);
242
243 dst = src;
244 for (size_type row = 0; row < N; ++row)
245 {
246 dst(row) -= tmp(row);
247 // scale by the diagonal element.
248 // note that the diagonal element
249 // was stored inverted
250 dst(row) *= this->diag_element(row);
251
252 // get end of this row
253 const size_type *const rowend =
254 &column_numbers[rowstart_indices[row + 1]];
255 // find the position where the part
256 // right of the diagonal starts
257 const size_type *const first_after_diagonal =
258 this->prebuilt_lower_bound[row];
259
260 const somenumber dst_row = dst(row);
261 const number *luval = this->SparseMatrix<number>::val.get() +
262 (first_after_diagonal - column_numbers);
263 for (const size_type *col = first_after_diagonal; col != rowend;
264 ++col, ++luval)
265 tmp(*col) += *luval * dst_row;
266 }
267
268 // now the backward solve. same
269 // procedure, but we need not set
270 // dst before, since this is already
271 // done.
272 //
273 // note that we no scaling is required
274 // now, since the diagonal is one
275 // now
276 tmp = 0;
277 for (int row = N - 1; row >= 0; --row)
278 {
279 dst(row) -= tmp(row);
280
281 // get start of this row. skip the
282 // diagonal element
283 const size_type *const rowstart =
284 &column_numbers[rowstart_indices[row] + 1];
285 // find the position where the part
286 // right of the diagonal starts
287 const size_type *const first_after_diagonal =
288 this->prebuilt_lower_bound[row];
289
290 const somenumber dst_row = dst(row);
291 const number *luval =
292 this->SparseMatrix<number>::val.get() + (rowstart - column_numbers);
293 for (const size_type *col = rowstart; col != first_after_diagonal;
294 ++col, ++luval)
295 tmp(*col) += *luval * dst_row;
296 }
297 }
298
299
300 template <typename number>
301 std::size_t
302 SparseILU<number>::memory_consumption() const
303 {
304 return SparseLUDecomposition<number>::memory_consumption();
305 }
306
307 DEAL_II_NAMESPACE_CLOSE
308
309 #endif