Debian Codegraph @

include/deal.II/matrix_free/matrix_free.templates.h

raw
1 // ------------------------------------------------------------------------
2 //
3 // SPDX-License-Identifier: LGPL-2.1-or-later
4 // Copyright (C) 2012 - 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_matrix_free_templates_h
16 #define dealii_matrix_free_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/mpi.h>
23 #include <deal.II/base/mpi_consensus_algorithms.h>
24 #include <deal.II/base/multithread_info.h>
25 #include <deal.II/base/polynomials_piecewise.h>
26 #include <deal.II/base/quadrature_lib.h>
27 #include <deal.II/base/tensor_product_polynomials.h>
28
29 #include <deal.II/distributed/tria.h>
30
31 #include <deal.II/dofs/dof_accessor.h>
32
33 #include <deal.II/fe/fe_dgp.h>
34 #include <deal.II/fe/fe_dgq.h>
35 #include <deal.II/fe/fe_poly.h>
36 #include <deal.II/fe/fe_q_dg0.h>
37
38 #include <deal.II/hp/q_collection.h>
39
40 #include <deal.II/lac/dynamic_sparsity_pattern.h>
41
42 #include <deal.II/matrix_free/constraint_info.h>
43 #include <deal.II/matrix_free/face_info.h>
44 #include <deal.II/matrix_free/face_setup_internal.h>
45 #include <deal.II/matrix_free/hanging_nodes_internal.h>
46 #include <deal.II/matrix_free/matrix_free.h>
47
48 #ifdef DEAL_II_WITH_TBB
49 # include <deal.II/base/parallel.h>
50
51 # include <tbb/concurrent_unordered_map.h>
52 #endif
53
54 #include <fstream>
55
56 //
57 // TBB with oneAPI API has deprecated and removed the
58 // <code>tbb::tasks</code> backend. With this it is no longer possible to
59 // compile the following code that builds a directed acyclic graph (DAG) of
60 // (thread parallel) tasks without a major porting effort. It turned out
61 // that such a dynamic handling of dependencies and structures is not as
62 // competitive as initially assumed. Consequently, this part of the matrix
63 // free infrastructure has seen less attention than the rest over the last
64 // years and is (presumably) not used that often.
65 //
66 // In case of detected oneAPI backend we simply disable threading in the
67 // matrix free backend for now.
68 //
69 // Matthias Maier, Martin Kronbichler, 2021
70 //
71
72 DEAL_II_NAMESPACE_OPEN
73
74
75
76 // --------------------- MatrixFree -----------------------------------
77
78 template <int dim, typename Number, typename VectorizedArrayType>
79 MatrixFree<dim, Number, VectorizedArrayType>::MatrixFree()
80 : EnableObserverPointer()
81 , indices_are_initialized(false)
82 , mapping_is_initialized(false)
83 , mg_level(numbers::invalid_unsigned_int)
84 , first_hp_dof_handler_index(0)
85 {}
86
87
88
89 template <int dim, typename Number, typename VectorizedArrayType>
90 MatrixFree<dim, Number, VectorizedArrayType>::MatrixFree(
91 const MatrixFree<dim, Number, VectorizedArrayType> &other)
92 : EnableObserverPointer()
93 {
94 copy_from(other);
95 }
96
97
98
99 template <int dim, typename Number, typename VectorizedArrayType>
100 std::pair<unsigned int, unsigned int>
101 MatrixFree<dim, Number, VectorizedArrayType>::create_cell_subrange_hp_by_index(
102 const std::pair<unsigned int, unsigned int> &range,
103 const unsigned int fe_index,
104 const unsigned int dof_handler_index) const
105 {
106 if (dof_info[dof_handler_index].max_fe_index == 0)
107 return range;
108
109 AssertIndexRange(fe_index, dof_info[dof_handler_index].max_fe_index);
110 const std::vector<unsigned int> &fe_indices =
111 dof_info[dof_handler_index].cell_active_fe_index;
112
113 if (fe_indices.empty() == true ||
114 dof_handlers[dof_handler_index]->get_fe_collection().size() == 1)
115 return range;
116 else
117 {
118 // the range over which we are searching must be ordered, otherwise we
119 // got a range that spans over too many cells
120 if constexpr (running_in_debug_mode())
121 {
122 for (unsigned int i = range.first + 1; i < range.second; ++i)
123 Assert(
124 fe_indices[i] >= fe_indices[i - 1],
125 ExcMessage(
126 "Cell range must be over sorted range of FE indices in hp-case!"));
127 AssertIndexRange(range.first, fe_indices.size() + 1);
128 AssertIndexRange(range.second, fe_indices.size() + 1);
129 }
130 std::pair<unsigned int, unsigned int> return_range;
131 return_range.first = std::lower_bound(fe_indices.begin() + range.first,
132 fe_indices.begin() + range.second,
133 fe_index) -
134 fe_indices.begin();
135 return_range.second =
136 std::lower_bound(fe_indices.begin() + return_range.first,
137 fe_indices.begin() + range.second,
138 fe_index + 1) -
139 fe_indices.begin();
140 Assert(return_range.first >= range.first &&
141 return_range.second <= range.second,
142 ExcInternalError());
143 return return_range;
144 }
145 }
146
147
148
149 namespace internal
150 {
151 class FaceRangeComparator
152 {
153 public:
154 FaceRangeComparator(const std::vector<unsigned int> &fe_indices,
155 const bool include,
156 const bool only_face_type)
157 : fe_indices(fe_indices)
158 , include(include)
159 , only_face_type(only_face_type)
160 {}
161
162 template <int vectorization_width>
163 bool
164 operator()(const internal::MatrixFreeFunctions::FaceToCellTopology<
165 vectorization_width> &face,
166 const std::array<unsigned int, 2> &fe_index)
167 {
168 const unsigned int face_type = face.face_type;
169
170 if (only_face_type)
171 return include ? (face_type <= fe_index[0]) : (face_type < fe_index[0]);
172
173 const std::array<unsigned int, 2> fe_index_face = {
174 {face_type, fe_indices[face.cells_interior[0] / vectorization_width]}};
175
176 return include ? (fe_index_face <= fe_index) : (fe_index_face < fe_index);
177 }
178
179 template <int vectorization_width>
180 bool
181 operator()(const internal::MatrixFreeFunctions::FaceToCellTopology<
182 vectorization_width> &face,
183 const std::array<unsigned int, 3> &fe_index)
184 {
185 const unsigned int face_type = face.face_type;
186
187 if (only_face_type)
188 return include ? (face_type <= fe_index[0]) : (face_type < fe_index[0]);
189
190 const std::array<unsigned int, 3> fe_index_face = {
191 {face_type,
192 fe_indices[face.cells_interior[0] / vectorization_width],
193 fe_indices[face.cells_exterior[0] / vectorization_width]}};
194
195 return include ? (fe_index_face <= fe_index) : (fe_index_face < fe_index);
196 }
197
198 private:
199 const std::vector<unsigned int> &fe_indices;
200 const bool include;
201 const bool only_face_type;
202 };
203 } // namespace internal
204
205
206
207 template <int dim, typename Number, typename VectorizedArrayType>
208 void
209 MatrixFree<dim, Number, VectorizedArrayType>::renumber_dofs(
210 std::vector<types::global_dof_index> &renumbering,
211 const unsigned int dof_handler_index)
212 {
213 AssertIndexRange(dof_handler_index, dof_info.size());
214 dof_info[dof_handler_index].compute_dof_renumbering(renumbering);
215 }
216
217
218
219 template <int dim, typename Number, typename VectorizedArrayType>
220 const DoFHandler<dim> &
221 MatrixFree<dim, Number, VectorizedArrayType>::get_dof_handler(
222 const unsigned int dof_handler_index) const
223 {
224 AssertIndexRange(dof_handler_index, n_components());
225
226 return *(dof_handlers[dof_handler_index]);
227 }
228
229
230
231 template <int dim, typename Number, typename VectorizedArrayType>
232 const AffineConstraints<Number> &
233 MatrixFree<dim, Number, VectorizedArrayType>::get_affine_constraints(
234 const unsigned int dof_handler_index) const
235 {
236 AssertIndexRange(dof_handler_index, n_components());
237
238 AssertThrow(affine_constraints[dof_handler_index] != nullptr,
239 ExcMessage(
240 "AffineConstraints are only accessible if its Number type "
241 "matches with Number type of MatrixFree!"));
242
243 return *(affine_constraints[dof_handler_index]);
244 }
245
246
247
248 template <int dim, typename Number, typename VectorizedArrayType>
249 typename DoFHandler<dim>::cell_iterator
250 MatrixFree<dim, Number, VectorizedArrayType>::get_cell_iterator(
251 const unsigned int cell_batch_index,
252 const unsigned int lane_index,
253 const unsigned int dof_handler_index) const
254 {
255 AssertIndexRange(dof_handler_index, dof_handlers.size());
256 AssertIndexRange(cell_batch_index, task_info.cell_partition_data.back());
257 AssertIndexRange(lane_index,
258 n_active_entries_per_cell_batch(cell_batch_index));
259
260 std::pair<unsigned int, unsigned int> index =
261 cell_level_index[cell_batch_index * VectorizedArrayType::size() +
262 lane_index];
263 return typename DoFHandler<dim>::cell_iterator(
264 &dof_handlers[dof_handler_index]->get_triangulation(),
265 index.first,
266 index.second,
267 &*dof_handlers[dof_handler_index]);
268 }
269
270
271
272 template <int dim, typename Number, typename VectorizedArrayType>
273 std::pair<int, int>
274 MatrixFree<dim, Number, VectorizedArrayType>::get_cell_level_and_index(
275 const unsigned int cell_batch_index,
276 const unsigned int lane_index) const
277 {
278 AssertIndexRange(cell_batch_index, task_info.cell_partition_data.back());
279 AssertIndexRange(lane_index,
280 n_active_entries_per_cell_batch(cell_batch_index));
281
282 std::pair<int, int> level_index_pair =
283 cell_level_index[cell_batch_index * VectorizedArrayType::size() +
284 lane_index];
285 return level_index_pair;
286 }
287
288
289
290 template <int dim, typename Number, typename VectorizedArrayType>
291 unsigned int
292 MatrixFree<dim, Number, VectorizedArrayType>::get_matrix_free_cell_index(
293 const typename Triangulation<dim>::cell_iterator &cell) const
294 {
295 return mf_cell_indices[(this->get_mg_level() ==
296 numbers::invalid_unsigned_int) ?
297 cell->active_cell_index() :
298 cell->index()];
299 }
300
301
302
303 template <int dim, typename Number, typename VectorizedArrayType>
304 std::pair<typename DoFHandler<dim>::cell_iterator, unsigned int>
305 MatrixFree<dim, Number, VectorizedArrayType>::get_face_iterator(
306 const unsigned int face_batch_index,
307 const unsigned int lane_index,
308 const bool interior,
309 const unsigned int fe_component) const
310 {
311 AssertIndexRange(fe_component, dof_handlers.size());
312
313 AssertIndexRange(lane_index,
314 n_active_entries_per_face_batch(face_batch_index));
315
316 const internal::MatrixFreeFunctions::FaceToCellTopology<
317 VectorizedArrayType::size()>
318 face2cell_info = get_face_info(face_batch_index);
319
320 const unsigned int cell_index = interior ?
321 face2cell_info.cells_interior[lane_index] :
322 face2cell_info.cells_exterior[lane_index];
323
324 Assert(cell_index != numbers::invalid_unsigned_int,
325 ExcMessage(
326 "Invalid cell index for requested face. Exterior cells cannot be"
327 " accessed on boundaries."));
328
329 std::pair<unsigned int, unsigned int> index = cell_level_index[cell_index];
330
331 return {typename DoFHandler<dim>::cell_iterator(
332 &dof_handlers[fe_component]->get_triangulation(),
333 index.first,
334 index.second,
335 &*dof_handlers[fe_component]),
336 interior ? face2cell_info.interior_face_no :
337 face2cell_info.exterior_face_no};
338 }
339
340
341
342 template <int dim, typename Number, typename VectorizedArrayType>
343 void
344 MatrixFree<dim, Number, VectorizedArrayType>::copy_from(
345 const MatrixFree<dim, Number, VectorizedArrayType> &v)
346 {
347 clear();
348 dof_handlers = v.dof_handlers;
349 dof_info = v.dof_info;
350 constraint_pool_data = v.constraint_pool_data;
351 constraint_pool_row_index = v.constraint_pool_row_index;
352 mapping_info = v.mapping_info;
353 shape_info = v.shape_info;
354 cell_level_index = v.cell_level_index;
355 cell_level_index_end_local = v.cell_level_index_end_local;
356 task_info = v.task_info;
357 face_info = v.face_info;
358 indices_are_initialized = v.indices_are_initialized;
359 mapping_is_initialized = v.mapping_is_initialized;
360 mg_level = v.mg_level;
361 first_hp_dof_handler_index = v.first_hp_dof_handler_index;
362 }
363
364
365
366 namespace internal
367 {
368 template <typename Number, typename Number2>
369 void
370 store_affine_constraints(
371 const dealii::AffineConstraints<Number2> *,
372 ObserverPointer<const dealii::AffineConstraints<Number>>
373 &stored_constraints)
374 {
375 stored_constraints = nullptr;
376 }
377
378 template <typename Number>
379 void
380 store_affine_constraints(
381 const dealii::AffineConstraints<Number> *affine_constraints,
382 ObserverPointer<const dealii::AffineConstraints<Number>>
383 &stored_constraints)
384 {
385 stored_constraints = affine_constraints;
386 }
387 } // namespace internal
388
389
390
391 template <int dim, typename Number, typename VectorizedArrayType>
392 template <typename number2, int q_dim>
393 void
394 MatrixFree<dim, Number, VectorizedArrayType>::internal_reinit(
395 const std::shared_ptr<hp::MappingCollection<dim>> &mapping,
396 const std::vector<const DoFHandler<dim, dim> *> &dof_handler,
397 const std::vector<const AffineConstraints<number2> *> &constraints,
398 const std::vector<IndexSet> &locally_owned_dofs,
399 const std::vector<hp::QCollection<q_dim>> &quad,
400 const typename MatrixFree<dim, Number, VectorizedArrayType>::AdditionalData
401 &additional_data)
402 {
403 // Store the level of the mesh to be worked on.
404 this->mg_level = additional_data.mg_level;
405
406 // Reads out the FE information and stores the shape function values,
407 // gradients and Hessians for quadrature points.
408 {
409 unsigned int n_components = 0;
410 for (unsigned int no = 0; no < dof_handler.size(); ++no)
411 n_components += dof_handler[no]->get_fe(0).n_base_elements();
412 const unsigned int n_quad = quad.size();
413 unsigned int n_fe_in_collection = 0;
414 for (unsigned int no = 0; no < dof_handler.size(); ++no)
415 n_fe_in_collection =
416 std::max(n_fe_in_collection,
417 dof_handler[no]->get_fe_collection().size());
418 unsigned int n_quad_in_collection = 0;
419 for (unsigned int q = 0; q < n_quad; ++q)
420 n_quad_in_collection = std::max(n_quad_in_collection, quad[q].size());
421 shape_info.reinit(TableIndices<4>(
422 n_components, n_quad, n_fe_in_collection, n_quad_in_collection));
423 for (unsigned int no = 0, c = 0; no < dof_handler.size(); ++no)
424 for (unsigned int b = 0; b < dof_handler[no]->get_fe(0).n_base_elements();
425 ++b, ++c)
426 for (unsigned int fe_no = 0;
427 fe_no < dof_handler[no]->get_fe_collection().size();
428 ++fe_no)
429 for (unsigned int nq = 0; nq < n_quad; ++nq)
430 for (unsigned int q_no = 0; q_no < quad[nq].size(); ++q_no)
431 shape_info(c, nq, fe_no, q_no)
432 .reinit(quad[nq][q_no], dof_handler[no]->get_fe(fe_no), b);
433 }
434
435 // Vector of DoFHandler indices of those that are in hp-mode
436 const std::vector<unsigned int> hp_dof_handler_index =
437 std::invoke([&dof_handler]() {
438 std::vector<unsigned int> hp_dof_handler_index;
439 hp_dof_handler_index.reserve(dof_handler.size());
440 for (unsigned int i = 0; i < dof_handler.size(); ++i)
441 {
442 if (dof_handler[i]->has_hp_capabilities())
443 hp_dof_handler_index.emplace_back(i);
444 }
445 return hp_dof_handler_index;
446 });
447 if (hp_dof_handler_index.size() > 0)
448 first_hp_dof_handler_index = hp_dof_handler_index[0];
449
450 // Store pointers to AffineConstraints objects if Number type matches
451 affine_constraints.resize(constraints.size());
452 for (unsigned int no = 0; no < constraints.size(); ++no)
453 internal::store_affine_constraints(constraints[no], affine_constraints[no]);
454
455 if (additional_data.initialize_indices == true)
456 {
457 clear();
458 Assert(dof_handler.size() > 0, ExcMessage("No DoFHandler is given."));
459 AssertDimension(dof_handler.size(), constraints.size());
460 AssertDimension(dof_handler.size(), locally_owned_dofs.size());
461
462 task_info.allow_ghosted_vectors_in_loops =
463 additional_data.allow_ghosted_vectors_in_loops;
464
465 task_info.communicator = dof_handler[0]->get_mpi_communicator();
466 task_info.communicator_sm = additional_data.communicator_sm;
467 task_info.my_pid =
468 Utilities::MPI::this_mpi_process(task_info.communicator);
469 task_info.n_procs =
470 Utilities::MPI::n_mpi_processes(task_info.communicator);
471
472 if constexpr (running_in_debug_mode())
473 {
474 for (const auto &constraint : constraints)
475 Assert(
476 constraint->is_closed(task_info.communicator),
477 ExcMessage(
478 "You have provided a non-empty AffineConstraints object that has not "
479 "been closed. Please call AffineConstraints::close() before "
480 "calling MatrixFree::reinit()!"));
481 }
482
483 initialize_dof_handlers(dof_handler, additional_data);
484 for (unsigned int no = 0; no < dof_handler.size(); ++no)
485 {
486 dof_info[no].store_plain_indices =
487 additional_data.store_plain_indices;
488 dof_info[no].global_base_element_offset =
489 no > 0 ? dof_info[no - 1].global_base_element_offset +
490 dof_handler[no - 1]->get_fe(0).n_base_elements() :
491 0;
492 }
493
494 // initialize the basic multithreading information that needs to be
495 // passed to the DoFInfo structure
496 #if defined(DEAL_II_WITH_TBB) && !defined(DEAL_II_TBB_WITH_ONEAPI)
497 if (additional_data.tasks_parallel_scheme != AdditionalData::none &&
498 MultithreadInfo::n_threads() > 1)
499 {
500 task_info.scheme =
501 internal::MatrixFreeFunctions::TaskInfo::TasksParallelScheme(
502 static_cast<int>(additional_data.tasks_parallel_scheme));
503 task_info.block_size = additional_data.tasks_block_size;
504 }
505 else
506 #endif
507 task_info.scheme = internal::MatrixFreeFunctions::TaskInfo::none;
508
509 // set dof_indices together with constraint_indicator and
510 // constraint_pool_data. It also reorders the way cells are gone through
511 // (to separate cells with overlap to other processors from others
512 // without).
513 initialize_indices(constraints, locally_owned_dofs, additional_data);
514 }
515
516 // initialize bare structures
517 else if (dof_info.size() != dof_handler.size())
518 {
519 initialize_dof_handlers(dof_handler, additional_data);
520 std::vector<unsigned int> dummy;
521 std::vector<unsigned char> dummy2;
522 task_info.vectorization_length = VectorizedArrayType::size();
523 task_info.n_active_cells = cell_level_index.size();
524 task_info.create_blocks_serial(
525 dummy, 1, false, dummy, false, dummy, dummy, dummy2);
526
527 // NOLINTNEXTLINE(modernize-loop-convert)
528 for (unsigned int i = 0; i < dof_info.size(); ++i)
529 {
530 Assert(dof_handler[i]->get_fe_collection().size() == 1,
531 ExcNotImplemented());
532 dof_info[i].n_base_elements =
533 dof_handler[i]->get_fe(0).n_base_elements();
534 dof_info[i].n_components.resize(dof_info[i].n_base_elements);
535 dof_info[i].start_components.resize(dof_info[i].n_base_elements + 1);
536 for (unsigned int c = 0; c < dof_info[i].n_base_elements; ++c)
537 {
538 dof_info[i].n_components[c] =
539 dof_handler[i]->get_fe(0).element_multiplicity(c);
540 for (unsigned int l = 0; l < dof_info[i].n_components[c]; ++l)
541 dof_info[i].component_to_base_index.push_back(c);
542 dof_info[i].start_components[c + 1] =
543 dof_info[i].start_components[c] + dof_info[i].n_components[c];
544 }
545 dof_info[i].dofs_per_cell.push_back(
546 dof_handler[i]->get_fe(0).n_dofs_per_cell());
547
548 const unsigned int n_regular_cells = cell_level_index.size();
549 // if indices are not initialized, the cell_level_index might not be
550 // divisible by the vectorization length. But it must be for
551 // mapping_info...
552 while (cell_level_index.size() % VectorizedArrayType::size() != 0)
553 cell_level_index.push_back(cell_level_index.back());
554
555 // adjust lengths for vectorization
556 dof_info[i]
557 .n_vectorization_lanes_filled
558 [internal::MatrixFreeFunctions::DoFInfo::dof_access_cell]
559 .resize(cell_level_index.size() / VectorizedArrayType::size(),
560 VectorizedArrayType::size());
561 if (n_regular_cells < cell_level_index.size())
562 dof_info[i].n_vectorization_lanes_filled
563 [internal::MatrixFreeFunctions::DoFInfo::dof_access_cell]
564 [n_regular_cells / VectorizedArrayType::size()] =
565 n_regular_cells % VectorizedArrayType::size();
566 }
567 }
568
569 // subdivide cell, face and boundary face partitioner data, s.t., all
570 // ranges have the same active FE indices
571 if (task_info.scheme != internal::MatrixFreeFunctions::TaskInfo::
572 TasksParallelScheme::partition_color)
573 {
574 // ... for cells
575 {
576 auto &ptr = task_info.cell_partition_data_hp_ptr;
577 auto &data = task_info.cell_partition_data_hp;
578
579 ptr = {0};
580 data = {};
581 data.reserve(2 * task_info.cell_partition_data.size());
582
583 for (unsigned int i = 0; i < task_info.cell_partition_data.size() - 1;
584 ++i)
585 {
586 if (task_info.cell_partition_data[i + 1] >
587 task_info.cell_partition_data[i])
588 {
589 std::pair<unsigned int, unsigned int> range{
590 task_info.cell_partition_data[i],
591 task_info.cell_partition_data[i + 1]};
592
593 if (range.second > range.first)
594 for (unsigned int i = 0; i < this->n_active_fe_indices(); ++i)
595 {
596 const auto cell_subrange =
597 this->create_cell_subrange_hp_by_index(
598 range, i, first_hp_dof_handler_index);
599
600 if (cell_subrange.second <= cell_subrange.first)
601 continue;
602
603 data.push_back(cell_subrange.first);
604 data.push_back(cell_subrange.second);
605 }
606 }
607
608 ptr.push_back(data.size() / 2);
609 }
610 }
611
612 // ... for inner faces
613 if (task_info.face_partition_data.empty() == false)
614 {
615 auto &ptr = task_info.face_partition_data_hp_ptr;
616 auto &data = task_info.face_partition_data_hp;
617
618 ptr = {0};
619 data = {};
620 data.reserve(2 * task_info.face_partition_data.size());
621
622 const auto create_inner_face_subrange_hp_by_index =
623 [&](const std::pair<unsigned int, unsigned int> &range,
624 const unsigned int face_type,
625 const unsigned int fe_index_interior,
626 const unsigned int fe_index_exterior,
627 const unsigned int dof_handler_index)
628 -> std::pair<unsigned int, unsigned int> {
629 const unsigned int n_face_types =
630 std::max<unsigned int>(dim - 1, 1);
631
632 if ((dof_info[dof_handler_index].max_fe_index == 0 ||
633 dof_handlers[dof_handler_index]->get_fe_collection().size() ==
634 1) &&
635 n_face_types == 1)
636 return range;
637
638 AssertIndexRange(fe_index_interior,
639 dof_info[dof_handler_index].max_fe_index);
640 AssertIndexRange(fe_index_exterior,
641 dof_info[dof_handler_index].max_fe_index);
642 const std::vector<unsigned int> &fe_indices =
643 dof_info[dof_handler_index].cell_active_fe_index;
644 if (fe_indices.empty() == true && n_face_types == 1)
645 return range;
646 else
647 {
648 const bool only_face_type =
649 dof_info[dof_handler_index].max_fe_index == 0 ||
650 dof_handlers[dof_handler_index]->get_fe_collection().size() ==
651 1 ||
652 fe_indices.empty() == true;
653
654 std::pair<unsigned int, unsigned int> return_range;
655 return_range.first =
656 std::lower_bound(
657 face_info.faces.begin() + range.first,
658 face_info.faces.begin() + range.second,
659 std::array<unsigned int, 3>{
660 {face_type, fe_index_interior, fe_index_exterior}},
661 internal::FaceRangeComparator(fe_indices,
662 false,
663 only_face_type)) -
664 face_info.faces.begin();
665 return_range.second =
666 std::lower_bound(
667 face_info.faces.begin() + return_range.first,
668 face_info.faces.begin() + range.second,
669 std::array<unsigned int, 3>{
670 {face_type, fe_index_interior, fe_index_exterior}},
671 internal::FaceRangeComparator(fe_indices,
672 true,
673 only_face_type)) -
674 face_info.faces.begin();
675 Assert(return_range.first >= range.first &&
676 return_range.second <= range.second,
677 ExcInternalError());
678 return return_range;
679 }
680 };
681
682 for (unsigned int i = 0; i < task_info.face_partition_data.size() - 1;
683 ++i)
684 {
685 if (task_info.face_partition_data[i + 1] >
686 task_info.face_partition_data[i])
687 {
688 std::pair<unsigned int, unsigned int> range{
689 task_info.face_partition_data[i],
690 task_info.face_partition_data[i + 1]};
691
692 if (range.second > range.first)
693 for (unsigned int t = 0;
694 t < std::max<unsigned int>(dim - 1, 1);
695 ++t)
696 for (unsigned int i = 0; i < this->n_active_fe_indices();
697 ++i)
698 for (unsigned int j = 0;
699 j < this->n_active_fe_indices();
700 ++j)
701 {
702 const auto subrange =
703 create_inner_face_subrange_hp_by_index(
704 range, t, i, j, first_hp_dof_handler_index);
705
706 if (subrange.second <= subrange.first)
707 continue;
708
709 data.push_back(subrange.first);
710 data.push_back(subrange.second);
711 }
712 }
713
714 ptr.push_back(data.size() / 2);
715 }
716 }
717
718 // ... for boundary faces
719 if (task_info.boundary_partition_data.empty() == false)
720 {
721 auto &ptr = task_info.boundary_partition_data_hp_ptr;
722 auto &data = task_info.boundary_partition_data_hp;
723
724 ptr = {0};
725 data = {};
726 data.reserve(2 * task_info.boundary_partition_data.size());
727
728 const auto create_boundary_face_subrange_hp_by_index =
729 [&](const std::pair<unsigned int, unsigned int> &range,
730 const unsigned int face_type,
731 const unsigned int fe_index,
732 const unsigned int dof_handler_index)
733 -> std::pair<unsigned int, unsigned int> {
734 const unsigned int n_face_types =
735 std::max<unsigned int>(dim - 1, 1);
736
737 if ((dof_info[dof_handler_index].max_fe_index == 0 ||
738 dof_handlers[dof_handler_index]->get_fe_collection().size() ==
739 1) &&
740 n_face_types == 1)
741 return range;
742
743 AssertIndexRange(fe_index,
744 dof_info[dof_handler_index].max_fe_index);
745 const std::vector<unsigned int> &fe_indices =
746 dof_info[dof_handler_index].cell_active_fe_index;
747 if (fe_indices.empty() == true && n_face_types == 1)
748 return range;
749 else
750 {
751 const bool only_face_type =
752 dof_info[dof_handler_index].max_fe_index == 0 ||
753 dof_handlers[dof_handler_index]->get_fe_collection().size() ==
754 1 ||
755 fe_indices.empty() == true;
756
757 std::pair<unsigned int, unsigned int> return_range;
758 return_range.first =
759 std::lower_bound(face_info.faces.begin() + range.first,
760 face_info.faces.begin() + range.second,
761 std::array<unsigned int, 2>{
762 {face_type, fe_index}},
763 internal::FaceRangeComparator(
764 fe_indices, false, only_face_type)) -
765 face_info.faces.begin();
766 return_range.second =
767 std::lower_bound(face_info.faces.begin() + return_range.first,
768 face_info.faces.begin() + range.second,
769 std::array<unsigned int, 2>{
770 {face_type, fe_index}},
771 internal::FaceRangeComparator(
772 fe_indices, true, only_face_type)) -
773 face_info.faces.begin();
774 Assert(return_range.first >= range.first &&
775 return_range.second <= range.second,
776 ExcInternalError());
777 return return_range;
778 }
779 };
780
781 for (unsigned int i = 0;
782 i < task_info.boundary_partition_data.size() - 1;
783 ++i)
784 {
785 if (task_info.boundary_partition_data[i + 1] >
786 task_info.boundary_partition_data[i])
787 {
788 std::pair<unsigned int, unsigned int> range{
789 task_info.boundary_partition_data[i],
790 task_info.boundary_partition_data[i + 1]};
791
792 if (range.second > range.first)
793 for (unsigned int t = 0;
794 t < std::max<unsigned int>(dim - 1, 1);
795 ++t)
796 for (unsigned int i = 0; i < this->n_active_fe_indices();
797 ++i)
798 {
799 const auto cell_subrange =
800 create_boundary_face_subrange_hp_by_index(
801 range, t, i, first_hp_dof_handler_index);
802
803 if (cell_subrange.second <= cell_subrange.first)
804 continue;
805
806 data.push_back(cell_subrange.first);
807 data.push_back(cell_subrange.second);
808 }
809 }
810
811 ptr.push_back(data.size() / 2);
812 }
813 }
814 }
815
816 // Evaluates transformations from unit to real cell, Jacobian determinants,
817 // quadrature points in real space, based on the ordering of the cells
818 // determined in @p extract_local_to_global_indices.
819 if (additional_data.initialize_mapping == true)
820 {
821 // check if active FE indices of all hp-DoFHandlers are the same.
822 for (unsigned int i = 1; i < hp_dof_handler_index.size(); ++i)
823 {
824 Assert(dof_info[hp_dof_handler_index[0]].cell_active_fe_index ==
825 dof_info[hp_dof_handler_index[i]].cell_active_fe_index,
826 ExcNotImplemented());
827 }
828
829 // Will the piola transform be used? If so we need to update
830 // the Jacobian gradients in case of update_gradients on general cells.
831 bool piola_transform = false;
832 for (unsigned int no = 0, c = 0; no < dof_handler.size(); ++no)
833 for (unsigned int b = 0;
834 b < dof_handler[no]->get_fe(0).n_base_elements();
835 ++b, ++c)
836 for (unsigned int fe_no = 0;
837 fe_no < dof_handler[no]->get_fe_collection().size();
838 ++fe_no)
839 for (unsigned int nq = 0; nq < quad.size(); ++nq)
840 for (unsigned int q_no = 0; q_no < quad[nq].size(); ++q_no)
841 if (shape_info(c, nq, fe_no, q_no).element_type ==
842 internal::MatrixFreeFunctions::ElementType::
843 tensor_raviart_thomas)
844 piola_transform = true;
845
846 mapping_info.initialize(
847 dof_handler[0]->get_triangulation(),
848 cell_level_index,
849 face_info,
850 hp_dof_handler_index.size() > 0 ?
851 dof_info[hp_dof_handler_index[0]].cell_active_fe_index :
852 std::vector<unsigned int>(),
853 mapping,
854 quad,
855 additional_data.mapping_update_flags,
856 additional_data.mapping_update_flags_boundary_faces,
857 additional_data.mapping_update_flags_inner_faces,
858 additional_data.mapping_update_flags_faces_by_cells,
859 piola_transform);
860
861 mapping_is_initialized = true;
862 }
863
864 // set up map: deal.II index -> MatrixFree index
865 {
866 const auto &tria = dof_handler[0]->get_triangulation();
867 const auto mg_level = this->get_mg_level();
868
869 mf_cell_indices.resize((mg_level == numbers::invalid_unsigned_int) ?
870 tria.n_active_cells() :
871 (mg_level < tria.n_levels() ?
872 tria.n_raw_cells(mg_level) :
873 0),
874 numbers::invalid_unsigned_int);
875
876 for (unsigned int cell = 0;
877 cell < n_cell_batches() + n_ghost_cell_batches();
878 ++cell)
879 for (unsigned int v = 0; v < n_active_entries_per_cell_batch(cell); ++v)
880 {
881 const auto tria_cell = get_cell_iterator(cell, v);
882 mf_cell_indices[(mg_level == numbers::invalid_unsigned_int) ?
883 tria_cell->active_cell_index() :
884 tria_cell->index()] =
885 cell * VectorizedArrayType::size() + v;
886 }
887 }
888 }
889
890
891
892 template <int dim, typename Number, typename VectorizedArrayType>
893 void
894 MatrixFree<dim, Number, VectorizedArrayType>::update_mapping(
895 const Mapping<dim> &mapping)
896 {
897 update_mapping(std::make_shared<hp::MappingCollection<dim>>(mapping));
898 }
899
900
901
902 template <int dim, typename Number, typename VectorizedArrayType>
903 void
904 MatrixFree<dim, Number, VectorizedArrayType>::update_mapping(
905 const std::shared_ptr<hp::MappingCollection<dim>> &mapping)
906 {
907 AssertDimension(shape_info.size(1), mapping_info.cell_data.size());
908 mapping_info.update_mapping(
909 dof_handlers[0]->get_triangulation(),
910 cell_level_index,
911 face_info,
912 dof_info[first_hp_dof_handler_index].cell_active_fe_index,
913 mapping);
914 }
915
916
917
918 template <int dim, typename Number, typename VectorizedArrayType>
919 template <int spacedim>
920 bool
921 MatrixFree<dim, Number, VectorizedArrayType>::is_supported(
922 const FiniteElement<dim, spacedim> &fe)
923 {
924 return internal::MatrixFreeFunctions::ShapeInfo<double>::is_supported(fe);
925 }
926
927
928
929 namespace internal
930 {
931 namespace MatrixFreeFunctions
932 {
933 // steps through all children and adds the active cells recursively
934 template <typename InIterator>
935 void
936 resolve_cell(
937 const InIterator &cell,
938 std::vector<std::pair<unsigned int, unsigned int>> &cell_its,
939 std::vector<std::pair<unsigned int, unsigned int>> &ghost_cell_its)
940 {
941 if (cell->has_children())
942 for (unsigned int child = 0; child < cell->n_children(); ++child)
943 resolve_cell(cell->child(child), cell_its, ghost_cell_its);
944 else if (cell->is_locally_owned())
945 {
946 Assert(cell->is_active(), ExcInternalError());
947 cell_its.emplace_back(cell->level(), cell->index());
948 }
949 else if (cell->is_ghost())
950 {
951 Assert(cell->is_active(), ExcInternalError());
952 ghost_cell_its.emplace_back(cell->level(), cell->index());
953 }
954 }
955 } // namespace MatrixFreeFunctions
956 } // namespace internal
957
958
959
960 template <int dim, typename Number, typename VectorizedArrayType>
961 void
962 MatrixFree<dim, Number, VectorizedArrayType>::initialize_dof_handlers(
963 const std::vector<const DoFHandler<dim, dim> *> &dof_handler_in,
964 const AdditionalData &additional_data)
965 {
966 cell_level_index.clear();
967 auto ghosted_cell_index = cell_level_index;
968 dof_handlers.resize(dof_handler_in.size());
969 for (unsigned int no = 0; no < dof_handler_in.size(); ++no)
970 dof_handlers[no] = dof_handler_in[no];
971
972 dof_info.resize(dof_handlers.size());
973 for (unsigned int no = 0; no < dof_handlers.size(); ++no)
974 dof_info[no].vectorization_length = VectorizedArrayType::size();
975
976 const Triangulation<dim> &tria = dof_handlers[0]->get_triangulation();
977 const unsigned int level = additional_data.mg_level;
978 if (level == numbers::invalid_unsigned_int)
979 {
980 cell_level_index.reserve(tria.n_active_cells());
981
982 // Go through cells on zeroth level and then successively step down into
983 // children. This gives a z-ordering of the cells, which is beneficial
984 // when setting up neighboring relations between cells for thread
985 // parallelization
986 for (const auto &cell : tria.cell_iterators_on_level(0))
987 internal::MatrixFreeFunctions::resolve_cell(cell,
988 cell_level_index,
989 ghosted_cell_index);
990
991 Assert(task_info.n_procs > 1 ||
992 cell_level_index.size() == tria.n_active_cells(),
993 ExcInternalError());
994 }
995 else
996 {
997 AssertIndexRange(level, tria.n_global_levels());
998 if (level < tria.n_levels())
999 {
1000 cell_level_index.reserve(tria.n_cells(level));
1001 for (const auto &cell : tria.cell_iterators_on_level(level))
1002 if (cell->is_locally_owned_on_level())
1003 cell_level_index.emplace_back(cell->level(), cell->index());
1004 else if (additional_data.store_ghost_cells == true &&
1005 cell->is_ghost_on_level())
1006 ghosted_cell_index.emplace_back(cell->level(), cell->index());
1007 }
1008 }
1009
1010 // All these are cells local to this processor. Therefore, set
1011 // cell_level_index_end_local to the size of cell_level_index.
1012 cell_level_index_end_local = cell_level_index.size();
1013
1014 // If ghost cells are stored, add them to the end of the cell_level_index
1015 if (additional_data.store_ghost_cells == true)
1016 cell_level_index.insert(cell_level_index.end(),
1017 ghosted_cell_index.begin(),
1018 ghosted_cell_index.end());
1019 }
1020
1021
1022
1023 namespace internal
1024 {
1025 #if defined(DEAL_II_WITH_TBB) && !defined(DEAL_II_TBB_WITH_ONEAPI)
1026
1027 # ifdef DEAL_II_TBB_WITH_ONEAPI
1028 struct unsigned_int_pair_hash
1029 {
1030 std::size_t
1031 operator()(const std::pair<unsigned int, unsigned int> &pair) const
1032 {
1033 return std::hash<unsigned int>()(pair.first) ^
1034 std::hash<unsigned int>()(pair.second);
1035 }
1036 };
1037 # endif
1038
1039 inline void
1040 fill_index_subrange(
1041 const unsigned int begin,
1042 const unsigned int end,
1043 const std::vector<std::pair<unsigned int, unsigned int>> &cell_level_index,
1044 tbb::concurrent_unordered_map<std::pair<unsigned int, unsigned int>,
1045 unsigned int
1046 # ifdef DEAL_II_TBB_WITH_ONEAPI
1047 ,
1048 unsigned_int_pair_hash
1049 # endif
1050 > &map)
1051 {
1052 if (cell_level_index.empty())
1053 return;
1054 unsigned int cell = begin;
1055 if (cell == 0)
1056 map.insert(std::make_pair(cell_level_index[cell++], 0U));
1057 for (; cell < end; ++cell)
1058 if (cell_level_index[cell] != cell_level_index[cell - 1])
1059 map.insert(std::make_pair(cell_level_index[cell], cell));
1060 }
1061
1062 template <int dim>
1063 inline void
1064 fill_connectivity_subrange(
1065 const unsigned int begin,
1066 const unsigned int end,
1067 const dealii::Triangulation<dim> &tria,
1068 const std::vector<std::pair<unsigned int, unsigned int>> &cell_level_index,
1069 const tbb::concurrent_unordered_map<std::pair<unsigned int, unsigned int>,
1070 unsigned int
1071 # ifdef DEAL_II_TBB_WITH_ONEAPI
1072 ,
1073 unsigned_int_pair_hash
1074 # endif
1075 > &map,
1076 DynamicSparsityPattern &connectivity_direct)
1077 {
1078 const unsigned int locally_owned_size = connectivity_direct.n_rows();
1079 std::vector<types::global_dof_index> new_indices;
1080 for (unsigned int cell = begin; cell < end; ++cell)
1081 {
1082 new_indices.clear();
1083 typename dealii::Triangulation<dim>::cell_iterator dcell(
1084 &tria, cell_level_index[cell].first, cell_level_index[cell].second);
1085 for (auto f : dcell->face_indices())
1086 {
1087 // Only inner faces couple different cells
1088 if (dcell->at_boundary(f) == false &&
1089 dcell->neighbor_or_periodic_neighbor(f)->level_subdomain_id() ==
1090 dcell->level_subdomain_id())
1091 {
1092 std::pair<unsigned int, unsigned int> level_index(
1093 dcell->neighbor_or_periodic_neighbor(f)->level(),
1094 dcell->neighbor_or_periodic_neighbor(f)->index());
1095 auto it = map.find(level_index);
1096 if (it != map.end())
1097 {
1098 const unsigned int neighbor_cell = it->second;
1099 if (neighbor_cell != cell &&
1100 neighbor_cell < locally_owned_size)
1101 new_indices.push_back(neighbor_cell);
1102 }
1103 }
1104 }
1105 std::sort(new_indices.begin(), new_indices.end());
1106 connectivity_direct.add_entries(cell,
1107 new_indices.begin(),
1108 std::unique(new_indices.begin(),
1109 new_indices.end()),
1110 true);
1111 }
1112 }
1113
1114 inline void
1115 fill_connectivity_indirect_subrange(
1116 const unsigned int begin,
1117 const unsigned int end,
1118 const DynamicSparsityPattern &connectivity_direct,
1119 DynamicSparsityPattern &connectivity)
1120 {
1121 std::vector<types::global_dof_index> new_indices;
1122 for (unsigned int block = begin; block < end; ++block)
1123 {
1124 new_indices.clear();
1125 for (DynamicSparsityPattern::iterator it =
1126 connectivity_direct.begin(block);
1127 it != connectivity_direct.end(block);
1128 ++it)
1129 {
1130 new_indices.push_back(it->column());
1131 for (DynamicSparsityPattern::iterator it_neigh =
1132 connectivity_direct.begin(it->column());
1133 it_neigh != connectivity_direct.end(it->column());
1134 ++it_neigh)
1135 if (it_neigh->column() != block)
1136 new_indices.push_back(it_neigh->column());
1137 }
1138 std::sort(new_indices.begin(), new_indices.end());
1139 connectivity.add_entries(block,
1140 new_indices.begin(),
1141 std::unique(new_indices.begin(),
1142 new_indices.end()),
1143 true);
1144 }
1145 }
1146
1147 #endif
1148
1149 template <int dim, typename number>
1150 std::vector<bool>
1151 compute_dof_info(
1152 const std::vector<const dealii::AffineConstraints<number> *> &constraint,
1153 const std::vector<IndexSet> &locally_owned_dofs,
1154 const std::vector<ObserverPointer<const DoFHandler<dim>>> &dof_handlers,
1155 const Table<2, MatrixFreeFunctions::ShapeInfo<double>> &shape_infos,
1156 const unsigned int cell_level_index_end_local,
1157 const unsigned int mg_level,
1158 const bool hold_all_faces_to_owned_cells,
1159 const std::vector<unsigned int> &cell_vectorization_category,
1160 const bool cell_vectorization_categories_strict,
1161 const bool do_face_integrals,
1162 const bool build_inner_faces,
1163 const bool overlap_communication_computation,
1164 MatrixFreeFunctions::TaskInfo &task_info,
1165 std::vector<std::pair<unsigned int, unsigned int>> &cell_level_index,
1166 std::vector<MatrixFreeFunctions::DoFInfo> &dof_info,
1167 MatrixFreeFunctions::FaceSetup<dim> &face_setup,
1168 MatrixFreeFunctions::ConstraintValues<double> &constraint_values,
1169 const bool use_vector_data_exchanger_full)
1170 {
1171 if (do_face_integrals)
1172 face_setup.initialize(dof_handlers[0]->get_triangulation(),
1173 mg_level,
1174 hold_all_faces_to_owned_cells,
1175 build_inner_faces,
1176 cell_level_index);
1177
1178 const unsigned int n_dof_handlers = dof_handlers.size();
1179 const unsigned int n_active_cells = cell_level_index.size();
1180
1181 const Triangulation<dim> &tria = dof_handlers[0]->get_triangulation();
1182
1183 AssertDimension(n_dof_handlers, locally_owned_dofs.size());
1184 AssertDimension(n_dof_handlers, constraint.size());
1185
1186 std::vector<types::global_dof_index> local_dof_indices_resolved;
1187 std::vector<types::global_dof_index> local_dof_indices;
1188 std::vector<std::vector<std::vector<unsigned int>>> lexicographic(
1189 n_dof_handlers);
1190
1191 std::vector<bool> is_fe_dg(n_dof_handlers, false);
1192
1193 bool cell_categorization_enabled = !cell_vectorization_category.empty();
1194
1195 bool use_fast_hanging_node_algorithm = true;
1196
1197 if (use_fast_hanging_node_algorithm)
1198 {
1199 const auto &reference_cells = tria.get_reference_cells();
1200 use_fast_hanging_node_algorithm =
1201 std::all_of(reference_cells.begin(),
1202 reference_cells.end(),
1203 [](const auto &r) {
1204 return r.is_hyper_cube() || r.is_simplex();
1205 });
1206 }
1207
1208 if (use_fast_hanging_node_algorithm)
1209 for (unsigned int no = 0; no < n_dof_handlers; ++no)
1210 {
1211 const dealii::hp::FECollection<dim> &fes =
1212 dof_handlers[no]->get_fe_collection();
1213
1214 use_fast_hanging_node_algorithm &=
1215 std::all_of(fes.begin(), fes.end(), [&fes](const auto &fe) {
1216 return fes[0].compare_for_domination(fe) ==
1217 FiniteElementDomination::Domination::
1218 either_element_can_dominate;
1219 });
1220 }
1221
1222 for (unsigned int no = 0; no < n_dof_handlers; ++no)
1223 {
1224 const dealii::hp::FECollection<dim> &fes =
1225 dof_handlers[no]->get_fe_collection();
1226
1227 if (fes.size() > 1)
1228 {
1229 Assert(cell_vectorization_category.empty(), ExcNotImplemented());
1230 dof_info[no].cell_active_fe_index.resize(
1231 n_active_cells, numbers::invalid_unsigned_int);
1232 }
1233 else if (cell_categorization_enabled == true)
1234 dof_info[no].cell_active_fe_index.resize(
1235 n_active_cells, numbers::invalid_unsigned_int);
1236
1237 is_fe_dg[no] = fes[0].n_dofs_per_vertex() == 0;
1238
1239 lexicographic[no].resize(fes.size());
1240
1241 dof_info[no].fe_index_conversion.resize(fes.size());
1242 dof_info[no].max_fe_index = fes.size();
1243
1244 dof_info[no].component_dof_indices_offset.clear();
1245 dof_info[no].component_dof_indices_offset.resize(fes.size());
1246 for (unsigned int fe_index = 0; fe_index < fes.size(); ++fe_index)
1247 {
1248 const FiniteElement<dim> &fe = fes[fe_index];
1249 // cache number of finite elements and dofs_per_cell
1250 dof_info[no].dofs_per_cell.push_back(fe.n_dofs_per_cell());
1251 dof_info[no].dofs_per_face.push_back(fe.n_dofs_per_face(
1252 0)); // we assume that all faces have the same number of dofs
1253 dof_info[no].n_base_elements = fe.n_base_elements();
1254 dof_info[no].n_components.resize(dof_info[no].n_base_elements);
1255 dof_info[no].start_components.resize(dof_info[no].n_base_elements +
1256 1);
1257 dof_info[no].component_to_base_index.clear();
1258 dof_info[no].component_dof_indices_offset[fe_index].push_back(0);
1259 dof_info[no].fe_index_conversion[fe_index].clear();
1260 for (unsigned int c = 0; c < dof_info[no].n_base_elements; ++c)
1261 {
1262 dof_info[no].n_components[c] =
1263 fe.element_multiplicity(c) *
1264 fe.base_element(c).n_components();
1265 for (unsigned int l = 0; l < dof_info[no].n_components[c]; ++l)
1266 {
1267 dof_info[no].component_to_base_index.push_back(c);
1268 dof_info[no]
1269 .component_dof_indices_offset[fe_index]
1270 .push_back(
1271 dof_info[no]
1272 .component_dof_indices_offset[fe_index]
1273 .back() +
1274 shape_infos(dof_info[no].global_base_element_offset + c,
1275 fe_index)
1276 .dofs_per_component_on_cell);
1277 dof_info[no].fe_index_conversion[fe_index].push_back(
1278 fe.base_element(c).degree);
1279 }
1280 dof_info[no].start_components[c + 1] =
1281 dof_info[no].start_components[c] +
1282 dof_info[no].n_components[c];
1283 const auto &lex =
1284 shape_infos(dof_info[no].global_base_element_offset + c,
1285 fe_index)
1286 .lexicographic_numbering;
1287 lexicographic[no][fe_index].insert(
1288 lexicographic[no][fe_index].end(), lex.begin(), lex.end());
1289 }
1290
1291 AssertDimension(lexicographic[no][fe_index].size(),
1292 dof_info[no].dofs_per_cell[fe_index]);
1293 AssertDimension(
1294 dof_info[no].component_dof_indices_offset[fe_index].size() - 1,
1295 dof_info[no].start_components.back());
1296 AssertDimension(
1297 dof_info[no].component_dof_indices_offset[fe_index].back(),
1298 dof_info[no].dofs_per_cell[fe_index]);
1299 }
1300
1301 // set locally owned range for each component
1302 Assert(locally_owned_dofs[no].is_contiguous(), ExcNotImplemented());
1303 dof_info[no].vector_partitioner =
1304 std::make_shared<Utilities::MPI::Partitioner>(locally_owned_dofs[no],
1305 task_info.communicator);
1306
1307 if (use_vector_data_exchanger_full == false)
1308 dof_info[no].vector_exchanger =
1309 std::make_shared<internal::MatrixFreeFunctions::VectorDataExchange::
1310 PartitionerWrapper>(
1311 dof_info[no].vector_partitioner);
1312 else
1313 dof_info[no].vector_exchanger = std::make_shared<
1314 internal::MatrixFreeFunctions::VectorDataExchange::Full>(
1315 dof_info[no].vector_partitioner, task_info.communicator_sm);
1316
1317 // initialize the arrays for indices
1318 const unsigned int n_components_total =
1319 dof_info[no].start_components.back();
1320 dof_info[no].row_starts.resize(n_active_cells * n_components_total + 1);
1321 dof_info[no].row_starts[0].first = 0;
1322 dof_info[no].row_starts[0].second = 0;
1323 dof_info[no].dof_indices.reserve(
1324 (n_active_cells * dof_info[no].dofs_per_cell[0] * 3) / 2);
1325
1326 // cache the constrained indices for use in matrix-vector products and
1327 // the like
1328 for (const auto &line : constraint[no]->get_lines())
1329 if (dof_info[no].vector_partitioner->in_local_range(line.index))
1330 dof_info[no].constrained_dofs.push_back(
1331 dof_info[no].vector_partitioner->global_to_local(line.index));
1332 }
1333
1334 // extract all the global indices associated with the computation, and form
1335 // the ghost indices
1336 std::vector<unsigned int> subdomain_boundary_cells;
1337 std::unique_ptr<dealii::internal::MatrixFreeFunctions::HangingNodes<dim>>
1338 hanging_nodes;
1339
1340 if (dim > 1 && mg_level == numbers::invalid_unsigned_int)
1341 {
1342 hanging_nodes = std::make_unique<
1343 dealii::internal::MatrixFreeFunctions::HangingNodes<dim>>(tria);
1344 for (unsigned int no = 0; no < n_dof_handlers; ++no)
1345 {
1346 dof_info[no].hanging_node_constraint_masks.resize(n_active_cells);
1347
1348 dof_info[no].hanging_node_constraint_masks_comp =
1349 hanging_nodes->compute_supported_components(
1350 dof_handlers[no]->get_fe_collection());
1351
1352 if ([](const auto &supported_components) {
1353 return std::none_of(supported_components.begin(),
1354 supported_components.end(),
1355 [](const auto &a) {
1356 return *std::max_element(a.begin(),
1357 a.end());
1358 });
1359 }(dof_info[no].hanging_node_constraint_masks_comp))
1360 dof_info[no].hanging_node_constraint_masks_comp = {};
1361 }
1362 }
1363
1364 for (unsigned int counter = 0; counter < n_active_cells; ++counter)
1365 {
1366 bool cell_at_subdomain_boundary =
1367 (face_setup.at_processor_boundary.size() > counter &&
1368 face_setup.at_processor_boundary[counter]) ||
1369 (overlap_communication_computation == false && task_info.n_procs > 1);
1370
1371 for (unsigned int no = 0; no < n_dof_handlers; ++no)
1372 {
1373 const DoFHandler<dim> &dofh = *dof_handlers[no];
1374 bool cell_has_hanging_node_constraints = false;
1375
1376 // read indices from active cells
1377 if (mg_level == numbers::invalid_unsigned_int)
1378 {
1379 typename DoFHandler<dim>::active_cell_iterator cell_it(
1380 &tria,
1381 cell_level_index[counter].first,
1382 cell_level_index[counter].second,
1383 &dofh);
1384 const unsigned int fe_index =
1385 dofh.get_fe_collection().size() > 1 ?
1386 cell_it->active_fe_index() :
1387 0;
1388 const unsigned int dofs_per_cell =
1389 dof_info[no].dofs_per_cell[fe_index];
1390 if (dofh.get_fe_collection().size() > 1)
1391 dof_info[no].cell_active_fe_index[counter] = fe_index;
1392 else if (cell_categorization_enabled)
1393 {
1394 AssertIndexRange(cell_it->active_cell_index(),
1395 cell_vectorization_category.size());
1396 dof_info[no].cell_active_fe_index[counter] =
1397 cell_vectorization_category[cell_it->active_cell_index()];
1398 }
1399
1400 local_dof_indices_resolved.resize(dofs_per_cell);
1401 cell_it->get_dof_indices(local_dof_indices_resolved);
1402
1403 local_dof_indices.resize(dofs_per_cell);
1404 for (unsigned int i = 0; i < dofs_per_cell; ++i)
1405 local_dof_indices[i] =
1406 local_dof_indices_resolved[lexicographic[no][fe_index][i]];
1407
1408 if (dim > 1 && use_fast_hanging_node_algorithm)
1409 {
1410 local_dof_indices_resolved = local_dof_indices;
1411
1412 cell_has_hanging_node_constraints =
1413 dof_info[no].process_hanging_node_constraints(
1414 *hanging_nodes,
1415 lexicographic[no],
1416 counter,
1417 cell_it,
1418 local_dof_indices_resolved);
1419 }
1420 }
1421 // we are requested to use a multigrid level
1422 else
1423 {
1424 AssertIndexRange(mg_level, tria.n_levels());
1425 typename DoFHandler<dim>::cell_iterator cell_it(
1426 &tria,
1427 cell_level_index[counter].first,
1428 cell_level_index[counter].second,
1429 &dofh);
1430 const unsigned int dofs_per_cell =
1431 dof_info[no].dofs_per_cell[0];
1432 local_dof_indices_resolved.resize(dofs_per_cell);
1433 cell_it->get_mg_dof_indices(local_dof_indices_resolved);
1434
1435 if (cell_categorization_enabled)
1436 {
1437 AssertIndexRange(cell_it->index(),
1438 cell_vectorization_category.size());
1439 dof_info[no].cell_active_fe_index[counter] =
1440 cell_vectorization_category[cell_level_index[counter]
1441 .second];
1442 }
1443
1444 local_dof_indices.resize(dofs_per_cell);
1445 for (unsigned int i = 0; i < dofs_per_cell; ++i)
1446 local_dof_indices[i] =
1447 local_dof_indices_resolved[lexicographic[no][0][i]];
1448 }
1449
1450 dof_info[no].read_dof_indices(cell_has_hanging_node_constraints ?
1451 local_dof_indices_resolved :
1452 local_dof_indices,
1453 local_dof_indices,
1454 cell_has_hanging_node_constraints,
1455 *constraint[no],
1456 counter,
1457 constraint_values,
1458 cell_at_subdomain_boundary);
1459 }
1460
1461 // if we found dofs on some FE component that belong to other
1462 // processors, the cell is added to the boundary cells.
1463 if (cell_at_subdomain_boundary == true &&
1464 counter < cell_level_index_end_local)
1465 subdomain_boundary_cells.push_back(counter);
1466 }
1467
1468 // clear hanging_node_constraint_masks if there are no hanging nodes
1469 if (dim > 1 && mg_level == numbers::invalid_unsigned_int)
1470 for (unsigned int no = 0; no < n_dof_handlers; ++no)
1471 {
1472 auto &vec = dof_info[no].hanging_node_constraint_masks;
1473 if (std::all_of(vec.begin(), vec.end(), [](const auto i) {
1474 return i == internal::MatrixFreeFunctions::
1475 unconstrained_compressed_constraint_kind;
1476 }))
1477 vec.clear();
1478 }
1479
1480 task_info.n_active_cells = cell_level_index_end_local;
1481 task_info.n_ghost_cells = n_active_cells - cell_level_index_end_local;
1482
1483 // Finalize the creation of the ghost indices
1484 {
1485 std::vector<unsigned int> cells_with_ghosts(subdomain_boundary_cells);
1486 for (unsigned int c = cell_level_index_end_local; c < n_active_cells; ++c)
1487 cells_with_ghosts.push_back(c);
1488 for (unsigned int no = 0; no < n_dof_handlers; ++no)
1489 {
1490 if (do_face_integrals && mg_level != numbers::invalid_unsigned_int)
1491 {
1492 // in case of adaptivity, go through the cells on the next finer
1493 // level and check whether we need to get read access to some of
1494 // those entries for the mg flux matrices
1495 std::vector<types::global_dof_index> dof_indices;
1496 if (mg_level + 1 < tria.n_global_levels())
1497 for (const auto &cell :
1498 dof_handlers[no]->cell_iterators_on_level(mg_level + 1))
1499 if (cell->level_subdomain_id() == task_info.my_pid)
1500 for (const unsigned int f : cell->face_indices())
1501 if ((cell->at_boundary(f) == false ||
1502 cell->has_periodic_neighbor(f) == true) &&
1503 cell->level() >
1504 cell->neighbor_or_periodic_neighbor(f)->level() &&
1505 cell->neighbor_or_periodic_neighbor(f)
1506 ->level_subdomain_id() != task_info.my_pid)
1507 {
1508 dof_indices.resize(
1509 cell->neighbor_or_periodic_neighbor(f)
1510 ->get_fe()
1511 .n_dofs_per_cell());
1512 cell->neighbor_or_periodic_neighbor(f)
1513 ->get_mg_dof_indices(dof_indices);
1514 for (const auto dof_index : dof_indices)
1515 dof_info[no].ghost_dofs.push_back(dof_index);
1516 }
1517 }
1518 dof_info[no].assign_ghosts(cells_with_ghosts,
1519 task_info.communicator_sm,
1520 use_vector_data_exchanger_full);
1521 }
1522 }
1523
1524 const auto [hp_functionality_enabled, first_hp_dof_handler_index] =
1525 std::invoke([&dof_handlers]() -> std::pair<bool, unsigned int> {
1526 bool hp_functionality_enabled = false;
1527 unsigned int first_hp_dof_handler_index = 0;
1528 for (unsigned int i = 0; i < dof_handlers.size(); ++i)
1529 {
1530 if (dof_handlers[i]->has_hp_capabilities())
1531 {
1532 hp_functionality_enabled = true;
1533 first_hp_dof_handler_index = i;
1534 break;
1535 }
1536 }
1537 return {hp_functionality_enabled, first_hp_dof_handler_index};
1538 });
1539
1540 const unsigned int n_lanes = task_info.vectorization_length;
1541 std::vector<unsigned int> renumbering;
1542 std::vector<unsigned char> irregular_cells;
1543
1544 Assert(
1545 task_info.scheme == internal::MatrixFreeFunctions::TaskInfo::none ||
1546 cell_vectorization_category.empty(),
1547 ExcMessage(
1548 "You explicitly requested re-categorization of cells; however, this "
1549 "feature is not available if threading is enabled. Please disable "
1550 "threading in MatrixFree by setting "
1551 "MatrixFree::Additional_data.tasks_parallel_scheme = MatrixFree<dim, double>::AdditionalData::none."));
1552
1553 if (task_info.scheme == internal::MatrixFreeFunctions::TaskInfo::none)
1554 {
1555 const bool strict_categories =
1556 cell_vectorization_categories_strict || hp_functionality_enabled;
1557 unsigned int max_dofs_per_cell = 0;
1558 for (const auto &info : dof_info)
1559 for (const auto &dofs : info.dofs_per_cell)
1560 max_dofs_per_cell = std::max(max_dofs_per_cell, dofs);
1561
1562 // Detect cells with the same parent to make sure they get scheduled
1563 // together in the loop, which increases data locality.
1564 std::vector<unsigned int> parent_relation(
1565 task_info.n_active_cells + task_info.n_ghost_cells,
1566 numbers::invalid_unsigned_int);
1567
1568 constexpr unsigned int max_children_per_cell =
1569 GeometryInfo<dim>::max_children_per_cell;
1570 const unsigned int n_levels =
1571 mg_level == numbers::invalid_unsigned_int ? tria.n_levels() - 1 :
1572 mg_level;
1573 std::vector<std::vector<
1574 std::pair<unsigned int,
1575 std::array<unsigned int, max_children_per_cell>>>>
1576 cell_parents(n_levels);
1577
1578 // Set up data structures, making sure that the current process has
1579 // cells on that level in the case of MG
1580 for (unsigned int level = 0; level < n_levels; ++level)
1581 if (tria.n_levels() > level)
1582 cell_parents[level].resize(tria.n_raw_cells(level));
1583
1584 for (unsigned int c = 0; c < cell_level_index_end_local; ++c)
1585 if (cell_level_index[c].first > 0)
1586 {
1587 typename Triangulation<dim>::cell_iterator cell(
1588 &tria, cell_level_index[c].first, cell_level_index[c].second);
1589 Assert(cell->level() > 0, ExcInternalError());
1590 const auto parent = cell->parent();
1591 auto &entry = cell_parents[parent->level()][parent->index()];
1592 entry.second[entry.first++] = c;
1593 }
1594 unsigned int position = 0;
1595 for (const auto &cells_on_level : cell_parents)
1596 for (const auto &it : cells_on_level)
1597 if (it.first == GeometryInfo<dim>::max_children_per_cell)
1598 {
1599 for (auto i : it.second)
1600 parent_relation[i] = position;
1601 ++position;
1602 }
1603 task_info.create_blocks_serial(
1604 subdomain_boundary_cells,
1605 max_dofs_per_cell,
1606 hp_functionality_enabled,
1607 dof_info[first_hp_dof_handler_index].cell_active_fe_index,
1608 strict_categories,
1609 parent_relation,
1610 renumbering,
1611 irregular_cells);
1612 }
1613 else
1614 {
1615 task_info.make_boundary_cells_divisible(subdomain_boundary_cells);
1616
1617 // For strategy with blocking before partitioning: reorganize the
1618 // indices in order to overlap communication in MPI with computations:
1619 // Place all cells with ghost indices into one chunk. Also reorder cells
1620 // so that we can parallelize by threads
1621 task_info.initial_setup_blocks_tasks(subdomain_boundary_cells,
1622 renumbering,
1623 irregular_cells);
1624 const internal::MatrixFreeFunctions::DoFInfo &dof_info_hp =
1625 dof_info[first_hp_dof_handler_index];
1626 task_info.guess_block_size(dof_info_hp.dofs_per_cell[0]);
1627
1628 unsigned int n_cell_batches_before =
1629 *(task_info.cell_partition_data.end() - 2);
1630 unsigned int n_ghost_slots =
1631 *(task_info.cell_partition_data.end() - 1) - n_cell_batches_before;
1632
1633 unsigned int start_nonboundary = numbers::invalid_unsigned_int;
1634 if (task_info.scheme ==
1635 internal::MatrixFreeFunctions::TaskInfo::partition_color ||
1636 task_info.scheme == internal::MatrixFreeFunctions::TaskInfo::color)
1637 {
1638 // set up partitions. if we just use coloring without partitions, do
1639 // nothing here, assume all cells to belong to the zero partition
1640 // (that we otherwise use for MPI boundary cells)
1641 if (task_info.scheme ==
1642 internal::MatrixFreeFunctions::TaskInfo::color)
1643 {
1644 start_nonboundary =
1645 task_info.n_procs > 1 ?
1646 std::min(((task_info.cell_partition_data[2] -
1647 task_info.cell_partition_data[1] +
1648 task_info.block_size - 1) /
1649 task_info.block_size) *
1650 task_info.block_size,
1651 task_info.cell_partition_data[3]) :
1652 0;
1653 }
1654 else
1655 {
1656 if (task_info.n_procs > 1)
1657 {
1658 task_info.cell_partition_data[1] = 0;
1659 task_info.cell_partition_data[2] =
1660 task_info.cell_partition_data[3];
1661 }
1662 start_nonboundary = task_info.cell_partition_data.back();
1663 }
1664
1665 if (hp_functionality_enabled)
1666 {
1667 irregular_cells.resize(0);
1668 irregular_cells.resize(task_info.cell_partition_data.back() +
1669 2 * dof_info_hp.max_fe_index);
1670 std::vector<std::vector<unsigned int>> renumbering_fe_index;
1671 renumbering_fe_index.resize(dof_info_hp.max_fe_index);
1672 unsigned int counter;
1673 n_cell_batches_before = 0;
1674 for (counter = 0;
1675 counter < std::min(start_nonboundary * n_lanes,
1676 task_info.n_active_cells);
1677 counter++)
1678 {
1679 AssertIndexRange(counter, renumbering.size());
1680 AssertIndexRange(renumbering[counter],
1681 dof_info_hp.cell_active_fe_index.size());
1682 renumbering_fe_index
1683 [dof_info_hp.cell_active_fe_index[renumbering[counter]]]
1684 .push_back(renumbering[counter]);
1685 }
1686 counter = 0;
1687 for (unsigned int j = 0; j < dof_info_hp.max_fe_index; ++j)
1688 {
1689 for (const auto jj : renumbering_fe_index[j])
1690 renumbering[counter++] = jj;
1691 irregular_cells[renumbering_fe_index[j].size() / n_lanes +
1692 n_cell_batches_before] =
1693 renumbering_fe_index[j].size() % n_lanes;
1694 n_cell_batches_before +=
1695 (renumbering_fe_index[j].size() + n_lanes - 1) / n_lanes;
1696 renumbering_fe_index[j].resize(0);
1697 }
1698
1699 for (counter = start_nonboundary * n_lanes;
1700 counter < task_info.n_active_cells;
1701 counter++)
1702 {
1703 renumbering_fe_index
1704 [dof_info_hp.cell_active_fe_index.empty() ?
1705 0 :
1706 dof_info_hp.cell_active_fe_index[renumbering[counter]]]
1707 .push_back(renumbering[counter]);
1708 }
1709 counter = start_nonboundary * n_lanes;
1710 for (unsigned int j = 0; j < dof_info_hp.max_fe_index; ++j)
1711 {
1712 for (const auto jj : renumbering_fe_index[j])
1713 renumbering[counter++] = jj;
1714 irregular_cells[renumbering_fe_index[j].size() / n_lanes +
1715 n_cell_batches_before] =
1716 renumbering_fe_index[j].size() % n_lanes;
1717 n_cell_batches_before +=
1718 (renumbering_fe_index[j].size() + n_lanes - 1) / n_lanes;
1719 }
1720 AssertIndexRange(n_cell_batches_before,
1721 task_info.cell_partition_data.back() +
1722 2 * dof_info_hp.max_fe_index + 1);
1723 irregular_cells.resize(n_cell_batches_before + n_ghost_slots);
1724 *(task_info.cell_partition_data.end() - 2) =
1725 n_cell_batches_before;
1726 *(task_info.cell_partition_data.end() - 1) =
1727 n_cell_batches_before + n_ghost_slots;
1728 }
1729 }
1730
1731 task_info.n_blocks = (*(task_info.cell_partition_data.end() - 2) +
1732 task_info.block_size - 1) /
1733 task_info.block_size;
1734
1735 DynamicSparsityPattern connectivity;
1736 connectivity.reinit(task_info.n_active_cells, task_info.n_active_cells);
1737 if (do_face_integrals)
1738 {
1739 #if defined(DEAL_II_WITH_TBB) && !defined(DEAL_II_TBB_WITH_ONEAPI)
1740 // step 1: build map between the index in the matrix-free context
1741 // and the one in the triangulation
1742 tbb::concurrent_unordered_map<std::pair<unsigned int, unsigned int>,
1743 unsigned int
1744 # ifdef DEAL_II_TBB_WITH_ONEAPI
1745 ,
1746 unsigned_int_pair_hash
1747 # endif
1748 >
1749 map;
1750 dealii::parallel::apply_to_subranges(
1751 0,
1752 cell_level_index.size(),
1753 [&cell_level_index, &map](const unsigned int begin,
1754 const unsigned int end) {
1755 fill_index_subrange(begin, end, cell_level_index, map);
1756 },
1757 50);
1758
1759 // step 2: Make a list for all blocks with other blocks that write
1760 // to the cell (due to the faces that are associated to it)
1761 DynamicSparsityPattern connectivity_direct(connectivity.n_rows(),
1762 connectivity.n_cols());
1763 dealii::parallel::apply_to_subranges(
1764 0,
1765 task_info.n_active_cells,
1766 [&cell_level_index, &tria, &map, &connectivity_direct](
1767 const unsigned int begin, const unsigned int end) {
1768 fill_connectivity_subrange<dim>(
1769 begin, end, tria, cell_level_index, map, connectivity_direct);
1770 },
1771 20);
1772 connectivity_direct.symmetrize();
1773
1774 // step 3: Include also interaction between neighbors one layer away
1775 // because faces might be assigned to cells differently
1776 dealii::parallel::apply_to_subranges(
1777 0,
1778 task_info.n_active_cells,
1779 [&connectivity_direct, &connectivity](const unsigned int begin,
1780 const unsigned int end) {
1781 fill_connectivity_indirect_subrange(begin,
1782 end,
1783 connectivity_direct,
1784 connectivity);
1785 },
1786 20);
1787 #endif
1788 }
1789 if (task_info.n_active_cells > 0)
1790 dof_info_hp.make_connectivity_graph(task_info,
1791 renumbering,
1792 connectivity);
1793
1794 task_info.make_thread_graph(dof_info_hp.cell_active_fe_index,
1795 connectivity,
1796 renumbering,
1797 irregular_cells,
1798 hp_functionality_enabled);
1799
1800 Assert(irregular_cells.size() >= task_info.cell_partition_data.back(),
1801 ExcInternalError());
1802
1803 irregular_cells.resize(task_info.cell_partition_data.back() +
1804 n_ghost_slots);
1805 if (n_ghost_slots > 0)
1806 {
1807 for (unsigned int i = task_info.cell_partition_data.back();
1808 i < task_info.cell_partition_data.back() + n_ghost_slots - 1;
1809 ++i)
1810 irregular_cells[i] = 0;
1811 irregular_cells.back() = task_info.n_ghost_cells % n_lanes;
1812 }
1813
1814 if constexpr (running_in_debug_mode())
1815 {
1816 {
1817 unsigned int n_cells = 0;
1818 for (unsigned int i = 0; i < task_info.cell_partition_data.back();
1819 ++i)
1820 n_cells +=
1821 irregular_cells[i] > 0 ? irregular_cells[i] : n_lanes;
1822 AssertDimension(n_cells, task_info.n_active_cells);
1823 n_cells = 0;
1824 for (unsigned int i = task_info.cell_partition_data.back();
1825 i < n_ghost_slots + task_info.cell_partition_data.back();
1826 ++i)
1827 n_cells +=
1828 irregular_cells[i] > 0 ? irregular_cells[i] : n_lanes;
1829 AssertDimension(n_cells, task_info.n_ghost_cells);
1830 }
1831 }
1832
1833 task_info.cell_partition_data.push_back(
1834 task_info.cell_partition_data.back() + n_ghost_slots);
1835 }
1836
1837 // Finally perform the renumbering. We also want to group several cells
1838 // together to a batch of cells for SIMD (vectorized) execution (where the
1839 // arithmetic operations of several cells will then be done
1840 // simultaneously).
1841 if constexpr (running_in_debug_mode())
1842 {
1843 {
1844 AssertDimension(renumbering.size(),
1845 task_info.n_active_cells + task_info.n_ghost_cells);
1846 std::vector<unsigned int> sorted_renumbering(renumbering);
1847 std::sort(sorted_renumbering.begin(), sorted_renumbering.end());
1848 for (unsigned int i = 0; i < sorted_renumbering.size(); ++i)
1849 Assert(sorted_renumbering[i] == i, ExcInternalError());
1850 }
1851 }
1852 {
1853 std::vector<std::pair<unsigned int, unsigned int>> cell_level_index_old;
1854 cell_level_index.swap(cell_level_index_old);
1855 cell_level_index.reserve(task_info.cell_partition_data.back() * n_lanes);
1856 unsigned int position_cell = 0;
1857 for (unsigned int i = 0; i < task_info.cell_partition_data.back(); ++i)
1858 {
1859 unsigned int n_comp =
1860 (irregular_cells[i] > 0) ? irregular_cells[i] : n_lanes;
1861 for (unsigned int j = 0; j < n_comp; ++j)
1862 cell_level_index.push_back(
1863 cell_level_index_old[renumbering[position_cell + j]]);
1864
1865 // generate a cell and level index also when we have not filled up
1866 // vectorization_length cells. This is needed for MappingInfo when the
1867 // transformation data is initialized. We just set the value to the
1868 // last valid cell in that case.
1869 for (unsigned int j = n_comp; j < n_lanes; ++j)
1870 cell_level_index.push_back(
1871 cell_level_index_old[renumbering[position_cell + n_comp - 1]]);
1872 position_cell += n_comp;
1873 }
1874 AssertDimension(position_cell,
1875 task_info.n_active_cells + task_info.n_ghost_cells);
1876 AssertDimension(cell_level_index.size(),
1877 task_info.cell_partition_data.back() * n_lanes);
1878 }
1879
1880 std::vector<unsigned int> constraint_pool_row_index;
1881 constraint_pool_row_index.resize(1, 0);
1882 for (const auto &it : constraint_values.constraints)
1883 constraint_pool_row_index.push_back(constraint_pool_row_index.back() +
1884 it.first.size());
1885
1886 for (unsigned int no = 0; no < n_dof_handlers; ++no)
1887 dof_info[no].reorder_cells(task_info,
1888 renumbering,
1889 constraint_pool_row_index,
1890 irregular_cells);
1891
1892 return is_fe_dg;
1893 }
1894 } // namespace internal
1895
1896
1897
1898 template <int dim, typename Number, typename VectorizedArrayType>
1899 template <typename number2>
1900 void
1901 MatrixFree<dim, Number, VectorizedArrayType>::initialize_indices(
1902 const std::vector<const AffineConstraints<number2> *> &constraint,
1903 const std::vector<IndexSet> &locally_owned_dofs,
1904 const AdditionalData &additional_data)
1905 {
1906 // insert possible ghost cells and construct face topology
1907 const bool do_face_integrals =
1908 (additional_data.mapping_update_flags_inner_faces |
1909 additional_data.mapping_update_flags_boundary_faces) != update_default;
1910 internal::MatrixFreeFunctions::FaceSetup<dim> face_setup;
1911
1912 // create a vector with the dummy information about dofs in ShapeInfo
1913 // without the template of VectorizedArrayType
1914 Table<2, internal::MatrixFreeFunctions::ShapeInfo<double>> shape_info_dummy(
1915 shape_info.size(0), shape_info.size(2));
1916 {
1917 Quadrature<dim> quad(QGauss<dim>(1));
1918 Quadrature<dim> quad_simplex(QGaussSimplex<dim>(1));
1919 for (unsigned int no = 0, c = 0; no < dof_handlers.size(); ++no)
1920 for (unsigned int b = 0;
1921 b < dof_handlers[no]->get_fe(0).n_base_elements();
1922 ++b, ++c)
1923 for (unsigned int fe_no = 0;
1924 fe_no < dof_handlers[no]->get_fe_collection().size();
1925 ++fe_no)
1926 shape_info_dummy(c, fe_no).reinit(
1927 dof_handlers[no]->get_fe(fe_no).reference_cell() ==
1928 ReferenceCells::get_hypercube<dim>() ?
1929 quad :
1930 quad_simplex,
1931 dof_handlers[no]->get_fe(fe_no),
1932 b);
1933 }
1934
1935 bool overlap_communication_computation =
1936 additional_data.overlap_communication_computation;
1937
1938 if (overlap_communication_computation)
1939 {
1940 for (unsigned int no = 0; no < dof_handlers.size(); ++no)
1941 for (unsigned int fe_no = 0;
1942 fe_no < dof_handlers[no]->get_fe_collection().size();
1943 ++fe_no)
1944 if ((additional_data.mapping_update_flags_inner_faces !=
1945 update_default) &&
1946 (dof_handlers[no]->get_fe(fe_no).n_dofs_per_cell() == 0))
1947 // disable overlapping of communication and computation if
1948 // FE_Nothing is used and face integrals are performed
1949 // see #14342 and #14553.
1950 overlap_communication_computation = false;
1951 }
1952
1953 const unsigned int n_lanes = VectorizedArrayType::size();
1954 task_info.vectorization_length = n_lanes;
1955 internal::MatrixFreeFunctions::ConstraintValues<double> constraint_values;
1956 const std::vector<bool> is_fe_dg = internal::compute_dof_info(
1957 constraint,
1958 locally_owned_dofs,
1959 dof_handlers,
1960 shape_info_dummy,
1961 cell_level_index_end_local,
1962 additional_data.mg_level,
1963 additional_data.hold_all_faces_to_owned_cells,
1964 additional_data.cell_vectorization_category,
1965 additional_data.cell_vectorization_categories_strict,
1966 do_face_integrals,
1967 additional_data.mapping_update_flags_inner_faces != update_default,
1968 overlap_communication_computation,
1969 task_info,
1970 cell_level_index,
1971 dof_info,
1972 face_setup,
1973 constraint_values,
1974 additional_data.communicator_sm != MPI_COMM_SELF);
1975
1976 // set constraint pool from the std::map and reorder the indices
1977 std::vector<const std::vector<double> *> constraints(
1978 constraint_values.constraints.size());
1979 unsigned int length = 0;
1980 for (const auto &it : constraint_values.constraints)
1981 {
1982 AssertIndexRange(it.second, constraints.size());
1983 constraints[it.second] = &it.first;
1984 length += it.first.size();
1985 }
1986 constraint_pool_data.clear();
1987 constraint_pool_data.reserve(length);
1988 constraint_pool_row_index.reserve(constraint_values.constraints.size() + 1);
1989 constraint_pool_row_index.resize(1, 0);
1990 for (const auto &constraint : constraints)
1991 {
1992 Assert(constraint != nullptr, ExcInternalError());
1993 constraint_pool_data.insert(constraint_pool_data.end(),
1994 constraint->begin(),
1995 constraint->end());
1996 constraint_pool_row_index.push_back(constraint_pool_data.size());
1997 }
1998
1999 AssertDimension(constraint_pool_data.size(), length);
2000
2001 // Finally resort the faces and collect several faces for vectorization
2002 if ((additional_data.mapping_update_flags_inner_faces |
2003 additional_data.mapping_update_flags_boundary_faces) != update_default)
2004 {
2005 face_setup.generate_faces(dof_handlers[0]->get_triangulation(),
2006 cell_level_index,
2007 task_info);
2008 if (additional_data.mapping_update_flags_inner_faces != update_default)
2009 Assert(face_setup.refinement_edge_faces.empty(),
2010 ExcNotImplemented("Setting up data structures on MG levels with "
2011 "hanging nodes is currently not supported."));
2012 face_info.faces.clear();
2013
2014 std::vector<bool> hard_vectorization_boundary(
2015 task_info.face_partition_data.size(), false);
2016 if (task_info.scheme == internal::MatrixFreeFunctions::TaskInfo::none)
2017 {
2018 // In case we do an MPI data exchange, we must make sure to first
2019 // complete all face integrals with results in the ghost range
2020 if (task_info.partition_row_index[2] <
2021 task_info.face_partition_data.size())
2022 hard_vectorization_boundary[task_info.partition_row_index[2]] =
2023 true;
2024 }
2025 else
2026 {
2027 // If we do threading, we need to strictly adhere to each partition,
2028 // as we can't schedule work on conflicting face batches
2029 std::fill(hard_vectorization_boundary.begin(),
2030 hard_vectorization_boundary.end(),
2031 true);
2032 }
2033
2034 const internal::MatrixFreeFunctions::DoFInfo &dof_info_hp =
2035 dof_info[first_hp_dof_handler_index];
2036
2037 if (additional_data.mapping_update_flags_inner_faces != update_default)
2038 internal::MatrixFreeFunctions::collect_faces_vectorization(
2039 face_setup.inner_faces,
2040 hard_vectorization_boundary,
2041 task_info.face_partition_data,
2042 face_info.faces,
2043 dof_info_hp.cell_active_fe_index);
2044
2045 // on boundary faces, we must also respect the vectorization boundary of
2046 // the inner faces because we might have dependencies on ghosts of
2047 // remote vector entries for continuous elements
2048 internal::MatrixFreeFunctions::collect_faces_vectorization(
2049 face_setup.boundary_faces,
2050 hard_vectorization_boundary,
2051 task_info.boundary_partition_data,
2052 face_info.faces,
2053 dof_info_hp.cell_active_fe_index);
2054
2055 // for the other ghosted faces, there are no scheduling restrictions
2056 hard_vectorization_boundary.clear();
2057 hard_vectorization_boundary.resize(
2058 task_info.ghost_face_partition_data.size(), false);
2059 internal::MatrixFreeFunctions::collect_faces_vectorization(
2060 face_setup.inner_ghost_faces,
2061 hard_vectorization_boundary,
2062 task_info.ghost_face_partition_data,
2063 face_info.faces,
2064 dof_info_hp.cell_active_fe_index);
2065 hard_vectorization_boundary.clear();
2066 hard_vectorization_boundary.resize(
2067 task_info.refinement_edge_face_partition_data.size(), false);
2068 internal::MatrixFreeFunctions::collect_faces_vectorization(
2069 face_setup.refinement_edge_faces,
2070 hard_vectorization_boundary,
2071 task_info.refinement_edge_face_partition_data,
2072 face_info.faces,
2073 dof_info_hp.cell_active_fe_index);
2074
2075 cell_level_index.resize(
2076 cell_level_index.size() +
2077 VectorizedArrayType::size() *
2078 (task_info.refinement_edge_face_partition_data[1] -
2079 task_info.refinement_edge_face_partition_data[0]));
2080
2081 for (auto &di : dof_info)
2082 di.compute_face_index_compression(
2083 face_info.faces, additional_data.hold_all_faces_to_owned_cells);
2084
2085 // build the inverse map back from the faces array to
2086 // cell_and_face_to_plain_faces
2087 face_info.cell_and_face_to_plain_faces.reinit(
2088 TableIndices<3>(task_info.cell_partition_data.back(),
2089 GeometryInfo<dim>::faces_per_cell,
2090 VectorizedArrayType::size()),
2091 true);
2092 face_info.cell_and_face_to_plain_faces.fill(
2093 numbers::invalid_unsigned_int);
2094 face_info.cell_and_face_boundary_id.reinit(
2095 TableIndices<3>(task_info.cell_partition_data.back(),
2096 ReferenceCells::max_n_faces<dim>(),
2097 VectorizedArrayType::size()),
2098 true);
2099 face_info.cell_and_face_boundary_id.fill(numbers::invalid_boundary_id);
2100
2101 for (unsigned int f = 0; f < task_info.ghost_face_partition_data.back();
2102 ++f)
2103 for (unsigned int v = 0; v < VectorizedArrayType::size() &&
2104 face_info.faces[f].cells_interior[v] !=
2105 numbers::invalid_unsigned_int;
2106 ++v)
2107 {
2108 TableIndices<3> index(face_info.faces[f].cells_interior[v] /
2109 VectorizedArrayType::size(),
2110 face_info.faces[f].interior_face_no,
2111 face_info.faces[f].cells_interior[v] %
2112 VectorizedArrayType::size());
2113
2114 // Assert(cell_and_face_to_plain_faces(index) ==
2115 // numbers::invalid_unsigned_int,
2116 // ExcInternalError("Should only visit each face once"));
2117 face_info.cell_and_face_to_plain_faces(index) =
2118 f * VectorizedArrayType::size() + v;
2119 if (face_info.faces[f].cells_exterior[v] !=
2120 numbers::invalid_unsigned_int)
2121 {
2122 TableIndices<3> index(face_info.faces[f].cells_exterior[v] /
2123 VectorizedArrayType::size(),
2124 face_info.faces[f].exterior_face_no,
2125 face_info.faces[f].cells_exterior[v] %
2126 VectorizedArrayType::size());
2127 // Assert(cell_and_face_to_plain_faces(index) ==
2128 // numbers::invalid_unsigned_int,
2129 // ExcInternalError("Should only visit each face once"));
2130 face_info.cell_and_face_to_plain_faces(index) =
2131 f * VectorizedArrayType::size() + v;
2132 }
2133 else
2134 face_info.cell_and_face_boundary_id(index) =
2135 types::boundary_id(face_info.faces[f].exterior_face_no);
2136 }
2137
2138 // compute tighter index sets for various sets of face integrals
2139 unsigned int count = 0;
2140 for (auto &di : dof_info)
2141 di.compute_tight_partitioners(
2142 shape_info_dummy,
2143 *(task_info.cell_partition_data.end() - 2) *
2144 VectorizedArrayType::size(),
2145 VectorizedArrayType::size(),
2146 face_setup.inner_faces,
2147 face_setup.inner_ghost_faces,
2148 is_fe_dg[count++] && additional_data.hold_all_faces_to_owned_cells,
2149 task_info.communicator_sm,
2150 task_info.communicator_sm != MPI_COMM_SELF);
2151 }
2152
2153 for (auto &di : dof_info)
2154 di.compute_vector_zero_access_pattern(task_info, face_info.faces);
2155
2156 #ifdef DEAL_II_WITH_MPI
2157 {
2158 // non-buffering mode is only supported if the indices of all cells are
2159 // contiguous for all dof_info objects.
2160 bool is_non_buffering_sm_supported = true;
2161 for (const auto &di : dof_info)
2162 {
2163 is_non_buffering_sm_supported &= di.dofs_per_cell.size() == 1;
2164 for (const auto &v : di.index_storage_variants[2])
2165 is_non_buffering_sm_supported &=
2166 (v == internal::MatrixFreeFunctions::DoFInfo::IndexStorageVariants::
2167 contiguous);
2168 }
2169
2170 is_non_buffering_sm_supported =
2171 Utilities::MPI::min(static_cast<unsigned int>(
2172 is_non_buffering_sm_supported),
2173 task_info.communicator);
2174
2175 const MPI_Comm communicator_sm = this->task_info.communicator_sm;
2176
2177 if (is_non_buffering_sm_supported)
2178 {
2179 // gather the ranks of the shared-memory domain
2180 const auto sm_procs = Utilities::MPI::mpi_processes_within_communicator(
2181 task_info.communicator, communicator_sm);
2182
2183 // get my rank within the shared-memory domain
2184 const unsigned int my_sm_pid = std::distance(
2185 sm_procs.begin(),
2186 std::find(sm_procs.begin(), sm_procs.end(), task_info.my_pid));
2187
2188 // process any dof_info
2189 const auto di_index = 0;
2190 const auto &di = dof_info[di_index];
2191
2192 std::array<std::vector<std::pair<unsigned int, unsigned int>>, 3>
2193 cell_indices_contiguous_sm;
2194
2195 // collect for each cell: sm rank + offset
2196 cell_indices_contiguous_sm[2] = [&]() {
2197 // result
2198 std::vector<std::pair<unsigned int, unsigned int>> cells(
2199 di.dof_indices_contiguous[2].size(),
2200 {numbers::invalid_unsigned_int, numbers::invalid_unsigned_int});
2201
2202 // locally-owned cells
2203 std::vector<std::pair<unsigned int, types::global_cell_index>>
2204 cells_locally_owned;
2205 cells_locally_owned.reserve(n_cell_batches() * n_lanes);
2206
2207 // shared-ghost cells (categorized according to sm-rank)
2208 std::vector<
2209 std::vector<std::pair<unsigned int, types::global_cell_index>>>
2210 cells_shared_ghosts(sm_procs.size());
2211
2212 for (unsigned int cell = 0;
2213 cell < n_cell_batches() + n_ghost_cell_batches();
2214 ++cell)
2215 for (unsigned int v = 0;
2216 v < this->n_active_entries_per_cell_batch(cell);
2217 ++v)
2218 {
2219 const unsigned int index = cell * n_lanes + v;
2220
2221 const auto cell_iterator = get_cell_iterator(cell, v, di_index);
2222
2223 // determine global cell index
2224 const unsigned int local_cell_index =
2225 di.dof_indices_contiguous[2][index] /
2226 this->get_dofs_per_cell(di_index);
2227
2228 const types::global_cell_index global_cell_index =
2229 (additional_data.mg_level == numbers::invalid_unsigned_int) ?
2230 cell_iterator->global_active_cell_index() :
2231 cell_iterator->global_level_cell_index();
2232
2233 // determine sm rank
2234 unsigned int sm_rank = my_sm_pid;
2235
2236 if (cell < n_cell_batches())
2237 {
2238 // locally-owned cell
2239 cells_locally_owned.emplace_back(local_cell_index,
2240 global_cell_index);
2241 }
2242 else
2243 {
2244 // ghost cell
2245 const auto ptr =
2246 std::find(sm_procs.begin(),
2247 sm_procs.end(),
2248 additional_data.mg_level ==
2249 numbers::invalid_unsigned_int ?
2250 cell_iterator->subdomain_id() :
2251 cell_iterator->level_subdomain_id());
2252
2253 if (ptr != sm_procs.end())
2254 {
2255 // shared ghost cell:
2256 sm_rank = std::distance(sm_procs.begin(), ptr);
2257 cells_shared_ghosts[sm_rank].emplace_back(
2258 index, global_cell_index);
2259 }
2260 else
2261 {
2262 // remote ghost cell: nothing to do since the values are
2263 // communicated (i.e. locally available)
2264 }
2265 }
2266
2267 // write back result
2268 cells[cell * n_lanes + v] = {sm_rank, local_cell_index};
2269 }
2270
2271 std::sort(cells_locally_owned.begin(),
2272 cells_locally_owned.end(),
2273 [](const auto &a, const auto &b) {
2274 return a.second < b.second;
2275 });
2276
2277 // get offsets of shared cells
2278 std::vector<unsigned int> targets;
2279 for (unsigned int i = 0; i < cells_shared_ghosts.size(); ++i)
2280 if (cells_shared_ghosts[i].size() > 0)
2281 targets.push_back(i);
2282
2283 // Then set up the callbacks the consensus algorithm needs:
2284 const auto create_request = [&](const auto other_rank) {
2285 auto &source = cells_shared_ghosts[other_rank];
2286 std::sort(source.begin(),
2287 source.end(),
2288 [](const auto &a, const auto &b) {
2289 return a.second < b.second;
2290 });
2291
2292 std::vector<dealii::types::global_dof_index> send_buffer;
2293 send_buffer.reserve(source.size());
2294 for (const auto &i : source)
2295 send_buffer.push_back(i.second);
2296
2297 return send_buffer;
2298 };
2299
2300 const auto answer_request = [&](const auto, const auto &request) {
2301 std::vector<unsigned int> answer;
2302 answer.reserve(request.size());
2303
2304 unsigned int j = 0;
2305
2306 for (unsigned int i = 0; i < request.size(); ++i)
2307 {
2308 for (; j < cells_locally_owned.size(); ++j)
2309 if (cells_locally_owned[j].second == request[i])
2310 {
2311 answer.push_back(cells_locally_owned[j].first);
2312 break;
2313 }
2314 }
2315
2316 AssertDimension(answer.size(), request.size());
2317 return answer;
2318 };
2319
2320 const auto process_answer = [&](const auto other_rank,
2321 const auto &answer) {
2322 Assert(answer.size() == cells_shared_ghosts[other_rank].size(),
2323 ExcInternalError());
2324 for (unsigned int i = 0; i < answer.size(); ++i)
2325 {
2326 cells[cells_shared_ghosts[other_rank][i].first] = {other_rank,
2327 answer[i]};
2328 }
2329 };
2330
2331 Utilities::MPI::ConsensusAlgorithms::Selector<
2332 std::vector<dealii::types::global_dof_index>,
2333 std::vector<unsigned int>>()
2334 .run(targets,
2335 create_request,
2336 answer_request,
2337 process_answer,
2338 communicator_sm);
2339
2340 return cells;
2341 }();
2342
2343 // process faces (0: interior; 1: exterior)
2344 for (unsigned int i = 0; i < 2; ++i)
2345 {
2346 cell_indices_contiguous_sm[i].assign(
2347 di.dof_indices_contiguous[i].size(),
2348 {numbers::invalid_unsigned_int, numbers::invalid_unsigned_int});
2349
2350 for (unsigned int face_index = 0;
2351 face_index < cell_indices_contiguous_sm[i].size();
2352 ++face_index)
2353 {
2354 const unsigned int cell_index =
2355 (i == 0) ? get_face_info(face_index / n_lanes)
2356 .cells_interior[face_index % n_lanes] :
2357 get_face_info(face_index / n_lanes)
2358 .cells_exterior[face_index % n_lanes];
2359
2360 if (cell_index == numbers::invalid_unsigned_int)
2361 continue;
2362
2363 cell_indices_contiguous_sm[i][face_index] =
2364 cell_indices_contiguous_sm[2][cell_index];
2365 }
2366 }
2367
2368 for (auto &di : dof_info)
2369 di.compute_shared_memory_contiguous_indices(
2370 cell_indices_contiguous_sm);
2371 }
2372 }
2373 #endif
2374
2375 indices_are_initialized = true;
2376 }
2377
2378
2379
2380 template <int dim, typename Number, typename VectorizedArrayType>
2381 void
2382 MatrixFree<dim, Number, VectorizedArrayType>::clear()
2383 {
2384 dof_info.clear();
2385 mapping_info.clear();
2386 cell_level_index.clear();
2387 task_info.clear();
2388 dof_handlers.clear();
2389 face_info.clear();
2390 indices_are_initialized = false;
2391 mapping_is_initialized = false;
2392 }
2393
2394
2395
2396 template <int dim, typename Number, typename VectorizedArrayType>
2397 std::size_t
2398 MatrixFree<dim, Number, VectorizedArrayType>::memory_consumption() const
2399 {
2400 std::size_t memory = MemoryConsumption::memory_consumption(dof_info);
2401 memory += MemoryConsumption::memory_consumption(cell_level_index);
2402 memory += MemoryConsumption::memory_consumption(face_info);
2403 memory += MemoryConsumption::memory_consumption(shape_info);
2404 memory += MemoryConsumption::memory_consumption(constraint_pool_data);
2405 memory += MemoryConsumption::memory_consumption(constraint_pool_row_index);
2406 memory += MemoryConsumption::memory_consumption(task_info);
2407 memory += sizeof(*this);
2408 memory += mapping_info.memory_consumption();
2409 return memory;
2410 }
2411
2412
2413
2414 template <int dim, typename Number, typename VectorizedArrayType>
2415 template <typename StreamType>
2416 void
2417 MatrixFree<dim, Number, VectorizedArrayType>::print_memory_consumption(
2418 StreamType &out) const
2419 {
2420 out << " Memory matrix-free data total: --> ";
2421 task_info.print_memory_statistics(out, memory_consumption());
2422 out << " Memory cell index: ";
2423 task_info.print_memory_statistics(
2424 out, MemoryConsumption::memory_consumption(cell_level_index));
2425 if (Utilities::MPI::sum(face_info.faces.size(), task_info.communicator) > 0)
2426 {
2427 out << " Memory face indicators: ";
2428 task_info.print_memory_statistics(
2429 out, MemoryConsumption::memory_consumption(face_info.faces));
2430 }
2431 for (unsigned int j = 0; j < dof_info.size(); ++j)
2432 {
2433 out << " Memory DoFInfo component " << j << std::endl;
2434 dof_info[j].print_memory_consumption(out, task_info);
2435 }
2436
2437 out << " Memory mapping info" << std::endl;
2438 mapping_info.print_memory_consumption(out, task_info);
2439
2440 out << " Memory unit cell shape data: ";
2441 task_info.print_memory_statistics(
2442 out, MemoryConsumption::memory_consumption(shape_info));
2443 if (task_info.scheme != internal::MatrixFreeFunctions::TaskInfo::none)
2444 {
2445 out << " Memory task partitioning info: ";
2446 task_info.print_memory_statistics(
2447 out, MemoryConsumption::memory_consumption(task_info));
2448 }
2449 }
2450
2451
2452
2453 template <int dim, typename Number, typename VectorizedArrayType>
2454 void
2455 MatrixFree<dim, Number, VectorizedArrayType>::print(std::ostream &out) const
2456 {
2457 // print indices local to global
2458 for (unsigned int no = 0; no < dof_info.size(); ++no)
2459 {
2460 out << "\n-- Index data for component " << no << " --" << std::endl;
2461 dof_info[no].print(constraint_pool_data, constraint_pool_row_index, out);
2462 out << std::endl;
2463 }
2464 }
2465
2466
2467
2468 DEAL_II_NAMESPACE_CLOSE
2469
2470 #endif