Debian Codegraph @

include/deal.II/lac/sparse_matrix_tools.h

raw
1 // ------------------------------------------------------------------------
2 //
3 // SPDX-License-Identifier: LGPL-2.1-or-later
4 // Copyright (C) 2022 - 2025 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_matrix_tools_h
16 #define dealii_sparse_matrix_tools_h
17
18 #include <deal.II/base/config.h>
19
20 #include <deal.II/base/mpi_consensus_algorithms.h>
21
22 #include <deal.II/dofs/dof_handler.h>
23
24 #include <deal.II/lac/dynamic_sparsity_pattern.h>
25
26 DEAL_II_NAMESPACE_OPEN
27
28 /**
29 * A namespace to process sparse matrices.
30 */
31 namespace SparseMatrixTools
32 {
33 /**
34 * Given a sparse matrix (@p system_matrix, @p sparsity_pattern),
35 * construct a new sparse matrix (@p system_matrix_out, @p sparsity_pattern_out)
36 * by restriction
37 * @f[
38 * A_i = R_i A R_i^T,
39 * @f]
40 * where the Boolean matrix $R_i$ is defined by the entries of @p requested_is.
41 *
42 * The function can be called by multiple processes with different sets
43 * of indices, allowing to assign each process a different $A_i$.
44 *
45 * Such a function is useful to implement Schwarz methods, where
46 * operations of type
47 * @f[
48 * u^{n} = u^{n-1} + \sum_{i} R_i^T A_i^{-1} R_i (f - A u^{n-1})
49 * @f]
50 * are performed to iteratively solve a system of type $Au=f$.
51 *
52 * @warning This is a collective call that needs to be executed by all
53 * processes in the communicator of @p sparse_matrix_in.
54 */
55 template <typename SparseMatrixType,
56 typename SparsityPatternType,
57 typename SparseMatrixType2,
58 typename SparsityPatternType2>
59 void
60 restrict_to_serial_sparse_matrix(const SparseMatrixType &sparse_matrix_in,
61 const SparsityPatternType &sparsity_pattern,
62 const IndexSet &requested_is,
63 SparseMatrixType2 &system_matrix_out,
64 SparsityPatternType2 &sparsity_pattern_out);
65
66 /**
67 * Similar to the above function, but taking two index sets
68 * (@p index_set_0, @p index_set_1), allowing to block the matrix. This
69 * is particularly useful, when dealing with vectors of type
70 * parallel::distributed::Vector, where the vector is blocked according
71 * to locally owned and ghost indices. As a consequence, the most
72 * typical usecase will be to pass in the set of locally owned DoFs and set
73 * of active or locally relevant DoFs.
74 *
75 * @warning This is a collective call that needs to be executed by all
76 * processes in the communicator of @p sparse_matrix_in.
77 */
78 template <typename SparseMatrixType,
79 typename SparsityPatternType,
80 typename SparseMatrixType2,
81 typename SparsityPatternType2>
82 void
83 restrict_to_serial_sparse_matrix(const SparseMatrixType &sparse_matrix_in,
84 const SparsityPatternType &sparsity_pattern,
85 const IndexSet &index_set_0,
86 const IndexSet &index_set_1,
87 SparseMatrixType2 &system_matrix_out,
88 SparsityPatternType2 &sparsity_pattern_out);
89
90 /**
91 * A restriction operation similar to the above one. However, the operation
92 * is performed for each locally owned active cell individually and index sets
93 * are given by their DoFs. The correct entries in the resulting vector can
94 * accessed by CellAccessor::active_cell_index().
95 *
96 * @note In a certain sense, this is the reversion of the cell loop during
97 * matrix assembly. However, doing this on a distributed matrix is not
98 * trivial, since 1) rows might be owned by different processes and 2) degrees
99 * of freedom might be constrained, resulting in "missing" entries in the
100 * matrix.
101 *
102 * @warning This is a collective call that needs to be executed by all
103 * processes in the communicator of @p sparse_matrix_in.
104 */
105 template <int dim,
106 int spacedim,
107 typename SparseMatrixType,
108 typename SparsityPatternType,
109 typename Number>
110 void
111 restrict_to_cells(const SparseMatrixType &system_matrix,
112 const SparsityPatternType &sparsity_pattern,
113 const DoFHandler<dim, spacedim> &dof_handler,
114 std::vector<FullMatrix<Number>> &blocks);
115
116 /**
117 * A restriction operation similar to the above one. However, the indices
118 * of the blocks can be chosen arbitrarily. If the indices of cells are
119 * given, the output is the same as of the above function. However, one
120 * can also provide, e.g., indices that are also part of a halo around
121 * a cell to implement element-block based overlapping Schwarz methods.
122 *
123 * If no indices are provided for a block, the resulting matrix of this
124 * block is empty.
125 *
126 * @warning This is a collective call that needs to be executed by all
127 * processes in the communicator of @p sparse_matrix_in.
128 */
129 template <typename SparseMatrixType,
130 typename SparsityPatternType,
131 typename Number>
132 void
133 restrict_to_full_matrices(
134 const SparseMatrixType &sparse_matrix_in,
135 const SparsityPatternType &sparsity_pattern,
136 const std::vector<std::vector<types::global_dof_index>> &indices,
137 std::vector<FullMatrix<Number>> &blocks);
138
139
140 #ifndef DOXYGEN
141 /*---------------------- Inline functions ---------------------------------*/
142
143 namespace internal
144 {
145 template <typename T>
146 using get_mpi_communicator_t =
147 decltype(std::declval<const T>().get_mpi_communicator());
148
149 template <typename T>
150 constexpr bool has_get_mpi_communicator =
151 dealii::internal::is_supported_operation<get_mpi_communicator_t, T>;
152
153 template <typename T>
154 using local_size_t = decltype(std::declval<const T>().local_size());
155
156 template <typename T>
157 constexpr bool has_local_size =
158 dealii::internal::is_supported_operation<local_size_t, T>;
159
160 template <typename SparseMatrixType,
161 std::enable_if_t<has_get_mpi_communicator<SparseMatrixType>,
162 SparseMatrixType> * = nullptr>
163 MPI_Comm
164 get_mpi_communicator(const SparseMatrixType &sparse_matrix)
165 {
166 return sparse_matrix.get_mpi_communicator();
167 }
168
169 template <typename SparseMatrixType,
170 std::enable_if_t<!has_get_mpi_communicator<SparseMatrixType>,
171 SparseMatrixType> * = nullptr>
172 MPI_Comm
173 get_mpi_communicator(const SparseMatrixType & /*sparse_matrix*/)
174 {
175 return MPI_COMM_SELF;
176 }
177
178 template <typename SparseMatrixType,
179 std::enable_if_t<has_local_size<SparseMatrixType>,
180 SparseMatrixType> * = nullptr>
181 unsigned int
182 get_local_size(const SparseMatrixType &sparse_matrix)
183 {
184 return sparse_matrix.local_size();
185 }
186
187 template <typename SparseMatrixType,
188 std::enable_if_t<!has_local_size<SparseMatrixType>,
189 SparseMatrixType> * = nullptr>
190 unsigned int
191 get_local_size(const SparseMatrixType &sparse_matrix)
192 {
193 AssertDimension(sparse_matrix.m(), sparse_matrix.n());
194
195 return sparse_matrix.m();
196 }
197
198 // Helper function to extract for a distributed sparse matrix rows
199 // potentially not owned by the current process.
200 template <typename Number,
201 typename SparseMatrixType,
202 typename SparsityPatternType>
203 std::vector<std::vector<std::pair<types::global_dof_index, Number>>>
204 extract_remote_rows(const SparseMatrixType &system_matrix,
205 const SparsityPatternType &sparsity_pattern,
206 const IndexSet &locally_active_dofs,
207 const MPI_Comm comm)
208 {
209 std::vector<unsigned int> dummy(locally_active_dofs.n_elements());
210
211 const auto local_size = get_local_size(system_matrix);
212 const auto [prefix_sum, total_sum] =
213 Utilities::MPI::partial_and_total_sum(local_size, comm);
214 IndexSet locally_owned_dofs(total_sum);
215 locally_owned_dofs.add_range(prefix_sum, prefix_sum + local_size);
216
217 using T1 = std::vector<
218 std::pair<types::global_dof_index,
219 std::vector<std::pair<types::global_dof_index, Number>>>>;
220
221 std::map<unsigned int, IndexSet> requesters;
222 std::tie(std::ignore, requesters) =
223 Utilities::MPI::compute_index_owner_and_requesters(locally_owned_dofs,
224 locally_active_dofs,
225 comm);
226
227 std::vector<std::vector<std::pair<types::global_dof_index, Number>>>
228 locally_relevant_matrix_entries(locally_active_dofs.n_elements());
229
230
231 std::vector<unsigned int> ranks;
232 ranks.reserve(requesters.size());
233
234 for (const auto &i : requesters)
235 ranks.push_back(i.first);
236
237 std::vector<std::vector<unsigned int>> row_to_procs(
238 locally_owned_dofs.n_elements());
239
240 for (const auto &requester : requesters)
241 for (const auto &index : requester.second)
242 row_to_procs[locally_owned_dofs.index_within_set(index)].push_back(
243 requester.first);
244
245 std::map<unsigned int, T1> data;
246
247 std::pair<types::global_dof_index,
248 std::vector<std::pair<types::global_dof_index, Number>>>
249 buffer;
250
251 for (unsigned int i = 0; i < row_to_procs.size(); ++i)
252 {
253 if (row_to_procs[i].empty())
254 continue;
255
256 const auto row = locally_owned_dofs.nth_index_in_set(i);
257 auto entry = system_matrix.begin(row);
258
259 const unsigned int row_length = sparsity_pattern.row_length(row);
260
261 buffer.first = row;
262 buffer.second.resize(row_length);
263
264 for (unsigned int j = 0; j < row_length; ++j, ++entry)
265 buffer.second[j] = {entry->column(), entry->value()};
266
267 for (const auto &proc : row_to_procs[i])
268 data[proc].emplace_back(buffer);
269 }
270
271 dealii::Utilities::MPI::ConsensusAlgorithms::selector<T1>(
272 ranks,
273 [&](const unsigned int other_rank) { return data[other_rank]; },
274 [&](const unsigned int &, const T1 &buffer_recv) {
275 for (const auto &i : buffer_recv)
276 {
277 auto &dst =
278 locally_relevant_matrix_entries[locally_active_dofs
279 .index_within_set(i.first)];
280 dst = i.second;
281 std::sort(dst.begin(),
282 dst.end(),
283 [](const auto &a, const auto &b) {
284 return a.first < b.first;
285 });
286 }
287 },
288 comm);
289
290 return locally_relevant_matrix_entries;
291 }
292 } // namespace internal
293
294
295
296 template <typename SparseMatrixType,
297 typename SparsityPatternType,
298 typename SparseMatrixType2,
299 typename SparsityPatternType2>
300 void
301 restrict_to_serial_sparse_matrix(const SparseMatrixType &system_matrix,
302 const SparsityPatternType &sparsity_pattern,
303 const IndexSet &index_set_0,
304 const IndexSet &index_set_1,
305 SparseMatrixType2 &system_matrix_out,
306 SparsityPatternType2 &sparsity_pattern_out)
307 {
308 Assert(index_set_1.size() == 0 || index_set_0.size() == index_set_1.size(),
309 ExcInternalError());
310
311 auto index_set_1_cleared = index_set_1;
312 if (index_set_1.size() != 0)
313 index_set_1_cleared.subtract_set(index_set_0);
314
315 const auto index_within_set = [&index_set_0,
316 &index_set_1_cleared](const auto n) {
317 if (index_set_0.is_element(n))
318 return index_set_0.index_within_set(n);
319 else
320 return index_set_0.n_elements() +
321 index_set_1_cleared.index_within_set(n);
322 };
323
324 // 1) collect needed rows
325 auto index_set_union = index_set_0;
326
327 if (index_set_1.size() != 0)
328 index_set_union.add_indices(index_set_1_cleared);
329
330 // TODO: actually only communicate remote rows as in the case of
331 // SparseMatrixTools::restrict_to_cells()
332 const auto locally_relevant_matrix_entries =
333 internal::extract_remote_rows<typename SparseMatrixType2::value_type>(
334 system_matrix,
335 sparsity_pattern,
336 index_set_union,
337 internal::get_mpi_communicator(system_matrix));
338
339
340 // 2) create sparsity pattern
341 const unsigned int n_rows = index_set_union.n_elements();
342 const unsigned int n_cols = index_set_union.n_elements();
343 const unsigned int entries_per_row =
344 locally_relevant_matrix_entries.empty() ?
345 0 :
346 std::max_element(locally_relevant_matrix_entries.begin(),
347 locally_relevant_matrix_entries.end(),
348 [](const auto &a, const auto &b) {
349 return a.size() < b.size();
350 })
351 ->size();
352
353 sparsity_pattern_out.reinit(n_rows, n_cols, entries_per_row);
354
355 std::vector<types::global_dof_index> temp_indices;
356 std::vector<typename SparseMatrixType2::value_type> temp_values;
357
358 for (unsigned int row = 0; row < index_set_union.n_elements(); ++row)
359 {
360 const auto &global_row_entries = locally_relevant_matrix_entries[row];
361
362 temp_indices.clear();
363 temp_indices.reserve(global_row_entries.size());
364
365 for (const auto &global_row_entry : global_row_entries)
366 {
367 const auto global_index = std::get<0>(global_row_entry);
368
369 if (index_set_union.is_element(global_index))
370 temp_indices.push_back(index_within_set(global_index));
371 }
372
373 sparsity_pattern_out.add_entries(
374 index_within_set(index_set_union.nth_index_in_set(row)),
375 temp_indices.begin(),
376 temp_indices.end());
377 }
378
379 sparsity_pattern_out.compress();
380
381 // 3) setup matrix
382 system_matrix_out.reinit(sparsity_pattern_out);
383
384 // 4) fill entries
385 for (unsigned int row = 0; row < index_set_union.n_elements(); ++row)
386 {
387 const auto &global_row_entries = locally_relevant_matrix_entries[row];
388
389 temp_indices.clear();
390 temp_values.clear();
391
392 temp_indices.reserve(global_row_entries.size());
393 temp_values.reserve(global_row_entries.size());
394
395 for (const auto &global_row_entry : global_row_entries)
396 {
397 const auto global_index = std::get<0>(global_row_entry);
398
399 if (index_set_union.is_element(global_index))
400 {
401 temp_indices.push_back(index_within_set(global_index));
402 temp_values.push_back(std::get<1>(global_row_entry));
403 }
404 }
405
406 system_matrix_out.add(index_within_set(
407 index_set_union.nth_index_in_set(row)),
408 temp_indices,
409 temp_values);
410 }
411
412 system_matrix_out.compress(VectorOperation::add);
413 }
414
415
416
417 template <typename SparseMatrixType,
418 typename SparsityPatternType,
419 typename SparseMatrixType2,
420 typename SparsityPatternType2>
421 void
422 restrict_to_serial_sparse_matrix(const SparseMatrixType &system_matrix,
423 const SparsityPatternType &sparsity_pattern,
424 const IndexSet &requested_is,
425 SparseMatrixType2 &system_matrix_out,
426 SparsityPatternType2 &sparsity_pattern_out)
427 {
428 restrict_to_serial_sparse_matrix(system_matrix,
429 sparsity_pattern,
430 requested_is,
431 IndexSet(), // simply pass empty index set
432 system_matrix_out,
433 sparsity_pattern_out);
434 }
435
436
437
438 template <typename SparseMatrixType,
439 typename SparsityPatternType,
440 typename Number>
441 void
442 restrict_to_full_matrices(
443 const SparseMatrixType &system_matrix,
444 const SparsityPatternType &sparsity_pattern,
445 const std::vector<std::vector<types::global_dof_index>> &indices,
446 std::vector<FullMatrix<Number>> &blocks)
447 {
448 // 0) determine which rows are locally owned and which ones are remote
449 const auto local_size = internal::get_local_size(system_matrix);
450 const auto prefix_sum = Utilities::MPI::partial_and_total_sum(
451 local_size, internal::get_mpi_communicator(system_matrix));
452 IndexSet locally_owned_dofs(std::get<1>(prefix_sum));
453 locally_owned_dofs.add_range(std::get<0>(prefix_sum),
454 std::get<0>(prefix_sum) + local_size);
455
456 std::vector<dealii::types::global_dof_index> ghost_indices_vector;
457
458 for (const auto &i : indices)
459 ghost_indices_vector.insert(ghost_indices_vector.end(),
460 i.begin(),
461 i.end());
462
463 std::sort(ghost_indices_vector.begin(), ghost_indices_vector.end());
464
465 IndexSet locally_active_dofs(std::get<1>(prefix_sum));
466 locally_active_dofs.add_indices(ghost_indices_vector.begin(),
467 ghost_indices_vector.end());
468
469 locally_active_dofs.subtract_set(locally_owned_dofs);
470
471 // 1) collect remote rows of sparse matrix
472 const auto locally_relevant_matrix_entries =
473 internal::extract_remote_rows<Number>(system_matrix,
474 sparsity_pattern,
475 locally_active_dofs,
476 internal::get_mpi_communicator(
477 system_matrix));
478
479
480 // 2) loop over all cells and "revert" assembly
481 blocks.clear();
482 blocks.resize(indices.size());
483
484 for (unsigned int c = 0; c < indices.size(); ++c)
485 {
486 if (indices[c].empty())
487 continue;
488
489 const auto &local_dof_indices = indices[c];
490 auto &cell_matrix = blocks[c];
491
492 // allocate memory
493 const unsigned int dofs_per_cell = indices[c].size();
494
495 cell_matrix = FullMatrix<Number>(dofs_per_cell, dofs_per_cell);
496
497 // loop over all entries of the restricted element matrix and
498 // do different things if rows are locally owned or not and
499 // if column entries of that row exist or not
500 for (unsigned int i = 0; i < dofs_per_cell; ++i)
501 for (unsigned int j = 0; j < dofs_per_cell; ++j)
502 {
503 if (locally_owned_dofs.is_element(
504 local_dof_indices[i])) // row is local
505 {
506 if constexpr (std::is_same_v<SparseMatrixType,
507 dealii::SparseMatrix<Number>>)
508 {
509 const types::global_dof_index ind =
510 system_matrix.get_sparsity_pattern()(
511 local_dof_indices[i], local_dof_indices[j]);
512
513 // If SparsityPattern::operator()` found the entry, then
514 // we can access the corresponding value without a
515 // second search in the sparse matrix, otherwise the
516 // matrix entry at that index is zero because it does
517 // not exist in the sparsity pattern
518 if (ind != SparsityPattern::invalid_entry)
519 {
520 const SparseMatrixIterators::Accessor<Number, true>
521 accessor(&system_matrix, ind);
522 cell_matrix(i, j) = accessor.value();
523 }
524 else
525 cell_matrix(i, j) = 0.0;
526 }
527 else
528 cell_matrix(i, j) =
529 sparsity_pattern.exists(local_dof_indices[i],
530 local_dof_indices[j]) ?
531 system_matrix(local_dof_indices[i],
532 local_dof_indices[j]) :
533 0.0;
534 }
535 else // row is ghost
536 {
537 Assert(locally_active_dofs.is_element(local_dof_indices[i]),
538 ExcInternalError());
539
540 const auto &row_entries =
541 locally_relevant_matrix_entries[locally_active_dofs
542 .index_within_set(
543 local_dof_indices[i])];
544
545 const auto ptr =
546 std::lower_bound(row_entries.begin(),
547 row_entries.end(),
548 std::pair<types::global_dof_index, Number>{
549 local_dof_indices[j], /*dummy*/ 0.0},
550 [](const auto a, const auto b) {
551 return a.first < b.first;
552 });
553
554 if (ptr != row_entries.end() &&
555 local_dof_indices[j] == ptr->first)
556 cell_matrix(i, j) = ptr->second;
557 else
558 cell_matrix(i, j) = 0.0;
559 }
560 }
561 }
562 }
563
564
565
566 template <int dim,
567 int spacedim,
568 typename SparseMatrixType,
569 typename SparsityPatternType,
570 typename Number>
571 void
572 restrict_to_cells(const SparseMatrixType &system_matrix,
573 const SparsityPatternType &sparsity_pattern,
574 const DoFHandler<dim, spacedim> &dof_handler,
575 std::vector<FullMatrix<Number>> &blocks)
576 {
577 std::vector<std::vector<types::global_dof_index>> all_dof_indices;
578 all_dof_indices.resize(dof_handler.get_triangulation().n_active_cells());
579
580 for (const auto &cell : dof_handler.active_cell_iterators())
581 {
582 if (cell->is_locally_owned() == false)
583 continue;
584
585 auto &local_dof_indices = all_dof_indices[cell->active_cell_index()];
586 local_dof_indices.resize(cell->get_fe().n_dofs_per_cell());
587 cell->get_dof_indices(local_dof_indices);
588 }
589
590 restrict_to_full_matrices(system_matrix,
591 sparsity_pattern,
592 all_dof_indices,
593 blocks);
594 }
595 #endif
596
597 } // namespace SparseMatrixTools
598
599 DEAL_II_NAMESPACE_CLOSE
600
601 #endif