Debian Codegraph @

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

raw
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_sparse_vanka_templates_h
16 #define dealii_sparse_vanka_templates_h
17
18
19 #include <deal.II/base/config.h>
20
21 #include <deal.II/base/memory_consumption.h>
22 #include <deal.II/base/thread_management.h>
23
24 #include <deal.II/lac/full_matrix.h>
25 #include <deal.II/lac/sparse_matrix.h>
26 #include <deal.II/lac/sparse_vanka.h>
27 #include <deal.II/lac/vector.h>
28
29 #include <algorithm>
30 #include <map>
31
32 DEAL_II_NAMESPACE_OPEN
33
34 template <typename number>
35 SparseVanka<number>::SparseVanka()
36 : matrix()
37 , selected()
38 , inverses()
39 , _m(0)
40 , _n(0)
41 {}
42
43 template <typename number>
44 SparseVanka<number>::SparseVanka(const SparseMatrix<number> &M,
45 const std::vector<bool> &selected_dofs)
46 : matrix(&M, typeid(*this).name())
47 , selected(&selected_dofs)
48 , inverses(M.m(), nullptr)
49 , _m(M.m())
50 , _n(M.n())
51 {
52 Assert(M.m() == M.n(), ExcNotQuadratic());
53 Assert(M.m() == selected->size(),
54 ExcDimensionMismatch(M.m(), selected->size()));
55
56 compute_inverses();
57 }
58
59
60 template <typename number>
61 SparseVanka<number>::~SparseVanka()
62 {
63 typename std::vector<
64 ObserverPointer<FullMatrix<float>, SparseVanka<number>>>::iterator i;
65 for (i = inverses.begin(); i != inverses.end(); ++i)
66 {
67 FullMatrix<float> *p = *i;
68 *i = nullptr;
69 if (p != nullptr)
70 delete p;
71 }
72 }
73
74
75 template <typename number>
76 void
77 SparseVanka<number>::initialize(const SparseMatrix<number> &M,
78 const AdditionalData &additional_data)
79 {
80 matrix = &M;
81 selected = &(additional_data.selected);
82 inverses.resize(M.m());
83 _m = M.m();
84 _n = M.n();
85
86 Assert(M.m() == M.n(), ExcNotQuadratic());
87 Assert(M.m() == selected->size(),
88 ExcDimensionMismatch(M.m(), selected->size()));
89
90 compute_inverses();
91 }
92
93 template <typename number>
94 void
95 SparseVanka<number>::compute_inverses()
96 {
97 Assert(matrix != nullptr, ExcNotInitialized());
98 Assert(selected != nullptr, ExcNotInitialized());
99
100 const size_type n_inverses =
101 std::count(selected->begin(), selected->end(), true);
102 // somewhat arbitrarily set up an equal number of tasks as we have threads
103 const std::size_t n_tasks = MultithreadInfo::n_threads();
104 const size_type n_inverses_per_task =
105 std::max(static_cast<size_type>(n_inverses / n_tasks),
106 static_cast<size_type>(1U));
107
108 // set up start and end index
109 // for each of the
110 // tasks. note that we have
111 // to work somewhat to get this
112 // appropriate, since the
113 // indices for which inverses
114 // have to be computed may not
115 // be evenly distributed in the
116 // vector. as an extreme
117 // example consider numbering
118 // of DoFs by component, then
119 // all indices for which we
120 // have to do work will be
121 // consecutive, with other
122 // consecutive regions where we
123 // do not have to do something
124 std::vector<std::pair<size_type, unsigned int>> blocking(n_tasks);
125
126 unsigned int c = 0;
127 unsigned int task_n = 0;
128 blocking[0].first = 0;
129
130 for (size_type i = 0; (i < matrix->m()) && (task_n + 1 < n_tasks); ++i)
131 {
132 if ((*selected)[i] == true)
133 ++c;
134 if (c == n_inverses_per_task)
135 {
136 blocking[task_n].second = i;
137 blocking[task_n + 1].first = i;
138 ++task_n;
139
140 c = 0;
141 }
142 }
143 blocking[n_tasks - 1].second = matrix->m();
144
145 // Now spawn the tasks
146 Threads::TaskGroup<> tasks;
147 for (unsigned int i = 0; i < n_tasks; ++i)
148 tasks += Threads::new_task([&, i]() {
149 this->compute_inverses(blocking[i].first, blocking[i].second);
150 });
151 tasks.join_all();
152 }
153
154
155 template <typename number>
156 void
157 SparseVanka<number>::compute_inverses(const size_type begin,
158 const size_type end)
159 {
160 // set-up the vector that will be used
161 // by the functions which we call
162 // below.
163 std::vector<size_type> local_indices;
164
165 // traverse all rows of the matrix
166 // which are selected
167 for (size_type row = begin; row < end; ++row)
168 if ((*selected)[row] == true)
169 compute_inverse(row, local_indices);
170 }
171
172
173
174 template <typename number>
175 void
176 SparseVanka<number>::compute_inverse(const size_type row,
177 std::vector<size_type> &local_indices)
178 {
179 Assert(matrix != nullptr, ExcNotInitialized());
180 Assert(selected != nullptr, ExcNotInitialized());
181
182 // first define an alias to the sparsity
183 // pattern of the matrix, since this
184 // will be used quite often
185 const SparsityPattern &structure = matrix->get_sparsity_pattern();
186
187 const size_type row_length = structure.row_length(row);
188
189 inverses[row] = new FullMatrix<float>(row_length, row_length);
190
191 // collect the dofs that couple
192 // with @p row
193 local_indices.resize(row_length);
194 for (size_type i = 0; i < row_length; ++i)
195 local_indices[i] = structure.column_number(row, i);
196
197 // Build local matrix
198 inverses[row]->extract_submatrix_from(*matrix, local_indices, local_indices);
199
200 // Compute inverse
201 inverses[row]->gauss_jordan();
202 }
203
204
205 template <typename number>
206 template <typename number2>
207 void
208 SparseVanka<number>::vmult(Vector<number2> &dst,
209 const Vector<number2> &src) const
210 {
211 Assert(matrix != nullptr, ExcNotInitialized());
212 Assert(selected != nullptr, ExcNotInitialized());
213
214 // first set output vector to zero
215 dst = 0;
216 // then pass on to the function
217 // that actually does the work
218 apply_preconditioner(dst, src, false);
219 }
220
221 template <typename number>
222 template <typename number2>
223 void
224 SparseVanka<number>::Tvmult(Vector<number2> &dst,
225 const Vector<number2> &src) const
226 {
227 Assert(matrix != nullptr, ExcNotInitialized());
228 Assert(selected != nullptr, ExcNotInitialized());
229
230 // first set output vector to zero
231 dst = 0;
232 // then pass on to the function
233 // that actually does the work
234 apply_preconditioner(dst, src, true);
235 }
236
237
238 template <typename number>
239 void
240 SparseVanka<number>::clear()
241 { // Clear the inverses vector and deallocate memory
242 inverses.clear();
243
244 // Reset the matrix pointer
245 matrix = nullptr;
246
247 // Reset the selected pointer
248 selected = nullptr;
249
250 // Reset the sizes
251 _m = 0;
252 _n = 0;
253 }
254
255 template <typename number>
256 template <typename number2>
257 void
258 SparseVanka<number>::apply_preconditioner(
259 Vector<number2> &dst,
260 const Vector<number2> &src,
261 const bool transpose,
262 const std::vector<bool> *const dof_mask) const
263 {
264 Assert(dst.size() == src.size(),
265 ExcDimensionMismatch(dst.size(), src.size()));
266 Assert(dst.size() == matrix->m(),
267 ExcDimensionMismatch(dst.size(), src.size()));
268
269 // first define an alias to the sparsity
270 // pattern of the matrix, since this
271 // will be used quite often
272 const SparsityPattern &structure = matrix->get_sparsity_pattern();
273
274
275 // store whether we shall work on
276 // the whole matrix, or only on
277 // blocks. this variable is used to
278 // optimize access to vectors a
279 // little bit.
280 const bool range_is_restricted = (dof_mask != nullptr);
281
282 // space to be used for local
283 // systems. allocate as much memory
284 // as is the maximum. this
285 // eliminates the need to
286 // re-allocate memory inside the
287 // loop.
288 FullMatrix<float> local_matrix(structure.max_entries_per_row(),
289 structure.max_entries_per_row());
290 Vector<float> b(structure.max_entries_per_row());
291 Vector<float> x(structure.max_entries_per_row());
292
293 std::map<size_type, size_type> local_index;
294
295 // traverse all rows of the matrix
296 // which are selected
297 const size_type n = matrix->m();
298 for (size_type row = 0; row < n; ++row)
299 if (((*selected)[row] == true) &&
300 ((range_is_restricted == false) || ((*dof_mask)[row] == true)))
301 {
302 const size_type row_length = structure.row_length(row);
303
304 b.reinit(row_length);
305 x.reinit(row_length);
306 // mapping between:
307 // 1 column number of all
308 // entries in this row, and
309 // 2 the position within this
310 // row (as stored in the
311 // SparsityPattern object
312 //
313 // since we do not explicitly
314 // consider nonsymmetric sparsity
315 // patterns, the first element
316 // of each entry simply denotes
317 // all degrees of freedom that
318 // couple with @p row.
319 local_index.clear();
320 for (size_type i = 0; i < row_length; ++i)
321 local_index.insert(
322 std::pair<size_type, size_type>(structure.column_number(row, i),
323 i));
324
325 // Build local matrix and rhs
326 for (std::map<size_type, size_type>::const_iterator is =
327 local_index.begin();
328 is != local_index.end();
329 ++is)
330 {
331 // irow loops over all DoFs that
332 // couple with the present DoF
333 const size_type irow = is->first;
334 // index of DoF irow in the matrix
335 // row corresponding to DoF @p row.
336 // runs between 0 and row_length
337 const size_type i = is->second;
338
339 // copy rhs
340 b(i) = src(irow);
341
342 // for all the DoFs that irow
343 // couples with
344 // number of DoFs coupling to
345 // irow (including irow itself)
346 for (typename SparseMatrix<number>::const_iterator p =
347 matrix->begin(irow);
348 p != matrix->end(irow);
349 ++p)
350 {
351 // find out whether this DoF
352 // (that couples with @p irow,
353 // which itself couples with
354 // @p row) also couples with
355 // @p row.
356 const std::map<size_type, size_type>::const_iterator js =
357 local_index.find(p->column());
358 // if not, then still use
359 // this dof to modify the rhs
360 //
361 // note that if so, we already
362 // have copied the entry above
363 if (js == local_index.end())
364 {
365 if (!range_is_restricted ||
366 ((*dof_mask)[p->column()] == true))
367 b(i) -= p->value() * dst(p->column());
368 }
369 }
370 }
371
372 // apply preconditioner
373 if (transpose)
374 inverses[row]->Tvmult(x, b);
375 else
376 inverses[row]->vmult(x, b);
377
378 // Distribute new values
379 for (std::map<size_type, size_type>::const_iterator is =
380 local_index.begin();
381 is != local_index.end();
382 ++is)
383 {
384 const size_type irow = is->first;
385 const size_type i = is->second;
386
387 if (!range_is_restricted || ((*dof_mask)[irow] == true))
388 dst(irow) = x(i);
389 // do nothing if not in
390 // the range
391 }
392 }
393 }
394
395
396
397 template <typename number>
398 std::size_t
399 SparseVanka<number>::memory_consumption() const
400 {
401 std::size_t mem =
402 (sizeof(*this) + MemoryConsumption::memory_consumption(*selected));
403 for (size_type i = 0; i < inverses.size(); ++i)
404 mem += MemoryConsumption::memory_consumption(*inverses[i]);
405
406 return mem;
407 }
408
409
410
411 template <typename number>
412 SparseVanka<number>::AdditionalData::AdditionalData(
413 const std::vector<bool> &selected)
414 : selected(selected)
415 {}
416
417
418 //---------------------------------------------------------------------------
419
420
421 template <typename number>
422 SparseBlockVanka<number>::SparseBlockVanka(
423 const SparseMatrix<number> &M,
424 const std::vector<bool> &selected,
425 const unsigned int n_blocks,
426 const BlockingStrategy blocking_strategy)
427 : SparseVanka<number>(M, selected)
428 , n_blocks(n_blocks)
429 , dof_masks(n_blocks, std::vector<bool>(M.m(), false))
430 {
431 compute_dof_masks(M, selected, blocking_strategy);
432 }
433
434
435 template <typename number>
436 void
437 SparseBlockVanka<number>::compute_dof_masks(
438 const SparseMatrix<number> &M,
439 const std::vector<bool> &selected,
440 const BlockingStrategy blocking_strategy)
441 {
442 Assert(n_blocks > 0, ExcInternalError());
443
444 const size_type n_inverses =
445 std::count(selected.begin(), selected.end(), true);
446
447 const size_type n_inverses_per_block =
448 std::max(n_inverses / n_blocks, static_cast<size_type>(1U));
449
450 // precompute the splitting points
451 std::vector<std::pair<size_type, size_type>> intervals(n_blocks);
452
453 // set up start and end index for
454 // each of the blocks. note that
455 // we have to work somewhat to get
456 // this appropriate, since the
457 // indices for which inverses have
458 // to be computed may not be evenly
459 // distributed in the vector. as an
460 // extreme example consider
461 // numbering of DoFs by component,
462 // then all indices for which we
463 // have to do work will be
464 // consecutive, with other
465 // consecutive regions where we do
466 // not have to do something
467 {
468 unsigned int c = 0;
469 unsigned int block = 0;
470 intervals[0].first = 0;
471
472 for (size_type i = 0; (i < M.m()) && (block + 1 < n_blocks); ++i)
473 {
474 if (selected[i] == true)
475 ++c;
476 if (c == n_inverses_per_block)
477 {
478 intervals[block].second = i;
479 intervals[block + 1].first = i;
480 ++block;
481
482 c = 0;
483 }
484 }
485 intervals[n_blocks - 1].second = M.m();
486 }
487
488 // now transfer the knowledge on
489 // the splitting points into the
490 // vector<bool>s that the base
491 // class wants to see. the way how
492 // we do this depends on the
493 // requested blocking strategy
494 switch (blocking_strategy)
495 {
496 case index_intervals:
497 {
498 for (unsigned int block = 0; block < n_blocks; ++block)
499 std::fill_n(dof_masks[block].begin() + intervals[block].first,
500 intervals[block].second - intervals[block].first,
501 true);
502 break;
503 }
504
505 case adaptive:
506 {
507 // the splitting points for
508 // the DoF have been computed
509 // above already, but we will
510 // only use them to split the
511 // Lagrange dofs into
512 // blocks. splitting the
513 // remaining dofs will be
514 // done now.
515
516 // first count how often the
517 // Lagrange dofs of each
518 // block access the different
519 // dofs
520 Table<2, size_type> access_count(n_blocks, M.m());
521
522 // set-up the map that will
523 // be used to store the
524 // indices each Lagrange dof
525 // accesses
526 const SparsityPattern &structure = M.get_sparsity_pattern();
527
528 for (size_type row = 0; row < M.m(); ++row)
529 if (selected[row] == true)
530 {
531 // first find out to
532 // which block the
533 // present row belongs
534 unsigned int block_number = 0;
535 while (row >= intervals[block_number].second)
536 ++block_number;
537 Assert(block_number < n_blocks, ExcInternalError());
538
539 // now traverse the
540 // matrix structure to
541 // find out to which
542 // dofs number the
543 // present index wants
544 // to write
545 const size_type row_length = structure.row_length(row);
546 for (size_type i = 0; i < row_length; ++i)
547 ++access_count[block_number][structure.column_number(row, i)];
548 }
549
550 // now we know that block @p i
551 // wants to write to DoF @p j
552 // as often as
553 // <tt>access_count[i][j]</tt>
554 // times. Let @p j be allotted
555 // to the block which
556 // accesses it most often.
557 //
558 // if it is a Lagrange dof,
559 // the of course we leave it
560 // to the block we put it
561 // into in the first place
562 for (size_type row = 0; row < M.m(); ++row)
563 if (selected[row] == true)
564 {
565 unsigned int block_number = 0;
566 while (row >= intervals[block_number].second)
567 ++block_number;
568
569 dof_masks[block_number][row] = true;
570 }
571 else
572 {
573 // find out which block
574 // accesses this dof
575 // the most often
576 size_type max_accesses = 0;
577 unsigned int max_access_block = 0;
578 for (unsigned int block = 0; block < n_blocks; ++block)
579 if (access_count[block][row] > max_accesses)
580 {
581 max_accesses = access_count[block][row];
582 max_access_block = block;
583 }
584 dof_masks[max_access_block][row] = true;
585 }
586
587 break;
588 }
589
590 default:
591 DEAL_II_ASSERT_UNREACHABLE();
592 }
593 }
594
595
596
597 template <typename number>
598 template <typename number2>
599 void
600 SparseBlockVanka<number>::vmult(Vector<number2> &dst,
601 const Vector<number2> &src) const
602 {
603 dst = 0;
604
605 Threads::TaskGroup<> tasks;
606 for (unsigned int block = 0; block < n_blocks; ++block)
607 tasks += Threads::new_task([&, block] {
608 this->apply_preconditioner(dst, src, false, &dof_masks[block]);
609 });
610 tasks.join_all();
611 }
612
613 template <typename number>
614 template <typename number2>
615 void
616 SparseBlockVanka<number>::Tvmult(Vector<number2> &dst,
617 const Vector<number2> &src) const
618 {
619 dst = 0;
620
621 Threads::TaskGroup<> tasks;
622 for (unsigned int block = 0; block < n_blocks; ++block)
623 tasks += Threads::new_task([&, block] {
624 this->apply_preconditioner(dst, src, true, &dof_masks[block]);
625 });
626 tasks.join_all();
627 }
628
629
630
631 template <typename number>
632 std::size_t
633 SparseBlockVanka<number>::memory_consumption() const
634 {
635 return SparseVanka<number>::memory_consumption() +
636 MemoryConsumption::memory_consumption(dof_masks);
637 }
638
639
640
641 DEAL_II_NAMESPACE_CLOSE
642
643 #endif