Debian Codegraph @

include/deal.II/fe/fe_tools_extrapolate.templates.h

raw
1 // ------------------------------------------------------------------------
2 //
3 // SPDX-License-Identifier: LGPL-2.1-or-later
4 // Copyright (C) 2013 - 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_fe_tools_extrapolate_templates_H
16 #define dealii_fe_tools_extrapolate_templates_H
17
18
19 #include <deal.II/base/config.h>
20
21 #include <deal.II/base/mpi_consensus_algorithms.h>
22 #include <deal.II/base/types.h>
23
24 #include <deal.II/distributed/p4est_wrappers.h>
25 #include <deal.II/distributed/tria.h>
26
27 #include <deal.II/dofs/dof_handler.h>
28 #include <deal.II/dofs/dof_tools.h>
29
30 #include <deal.II/fe/fe_tools.h>
31 #include <deal.II/fe/fe_tools_interpolate.templates.h>
32
33 #include <deal.II/grid/tria.h>
34
35 #include <deal.II/lac/affine_constraints.h>
36 #include <deal.II/lac/block_vector.h>
37 #include <deal.II/lac/block_vector_base.h>
38 #include <deal.II/lac/la_parallel_block_vector.h>
39 #include <deal.II/lac/la_parallel_vector.h>
40 #include <deal.II/lac/petsc_block_vector.h>
41 #include <deal.II/lac/petsc_vector.h>
42 #include <deal.II/lac/trilinos_parallel_block_vector.h>
43 #include <deal.II/lac/trilinos_tpetra_block_vector.h>
44 #include <deal.II/lac/trilinos_tpetra_vector.h>
45 #include <deal.II/lac/trilinos_vector.h>
46
47 #include <queue>
48
49 DEAL_II_NAMESPACE_OPEN
50
51 namespace FETools
52 {
53 namespace internal
54 {
55 #ifndef DEAL_II_WITH_P4EST
56 // Dummy implementation in case p4est is not available.
57 template <int dim, int spacedim, class OutVector>
58 class ExtrapolateImplementation
59 {
60 public:
61 ExtrapolateImplementation()
62 {
63 DEAL_II_NOT_IMPLEMENTED();
64 };
65
66 template <class InVector>
67 void
68 extrapolate_parallel(const InVector & /*u2_relevant*/,
69 const DoFHandler<dim, spacedim> & /*dof2*/,
70 OutVector & /*u2*/)
71 {
72 DEAL_II_NOT_IMPLEMENTED();
73 }
74 };
75
76 #else
77
78 /**
79 * Implementation of the FETools::extrapolate() function
80 * on parallel distributed grids.
81 */
82 template <int dim, int spacedim, class OutVector>
83 class ExtrapolateImplementation
84 {
85 public:
86 ExtrapolateImplementation();
87
88 template <class InVector>
89 void
90 extrapolate_parallel(const InVector &u2_relevant,
91 const DoFHandler<dim, spacedim> &dof2,
92 OutVector &u2);
93
94 private:
95 /**
96 * A shortcut for the type of the OutVector.
97 */
98 using value_type = typename OutVector::value_type;
99
100 /**
101 * A structure holding all data to set dofs recursively on cells of
102 * arbitrary level.
103 */
104 struct WorkPackage
105 {
106 const typename dealii::internal::p4est::types<dim>::forest forest;
107 const typename dealii::internal::p4est::types<dim>::tree tree;
108 const typename dealii::internal::p4est::types<dim>::locidx tree_index;
109 const typename DoFHandler<dim, spacedim>::cell_iterator dealii_cell;
110 const typename dealii::internal::p4est::types<dim>::quadrant p4est_cell;
111 };
112
113
114 /**
115 * A structure holding all data of cells needed from other processes
116 * for the extrapolate algorithm.
117 */
118 struct CellData
119 {
120 /**
121 * Default constructor.
122 */
123 CellData();
124
125 /**
126 * Constructor setting the `dof_values` member to the right size.
127 */
128 CellData(const unsigned int dofs_per_cell);
129
130 /**
131 * Comparison operator.
132 */
133 bool
134 operator<(const CellData &rhs) const;
135
136 /**
137 * Pack or unpack the data of this object into a buffer.
138 */
139 template <class Archive>
140 void
141 serialize(Archive &ar, const unsigned int);
142
143 /**
144 * The values of degrees of freedom associated with the current cell.
145 */
146 Vector<value_type> dof_values;
147
148 /**
149 * The tree within the forest (i.e., the coarse cell) and which of its
150 * descendents we are currently working on.
151 */
152 unsigned int tree_index;
153 typename dealii::internal::p4est::types<dim>::quadrant quadrant;
154
155 types::subdomain_id receiver;
156 };
157
158 // Problem: The function extrapolates a polynomial
159 // function from a finer mesh of size $h$ to a polynmial
160 // function of higher degree but on a coarser mesh of
161 // size $2h$. Therefore the mesh has to consist of patches
162 // of four (2d) or eight (3d) cells and the function requires
163 // that the mesh is refined globally at least once.
164 // The algorithm starts on the coarsest level of the grid,
165 // loops over all cells and if a cell has at least one active child,
166 // dof values are set via
167 // cell->get_interpolated_dof_values(u_input, dof_values)
168 // cell->set_dof_values_by_interpolation(dof_values, u_output)
169 // both *_interpolation_* functions traverse recursively
170 // over all children down to the active cells
171 // and get/set dof values by interpolation.
172 //
173 // On distributed parallel grids the problem arises, that
174 // if a cell has at least one active child, there is no guarantee
175 // that all children of this cell belong to this process.
176 // There might be children which are owned by other processes
177 // and the algorithm needs to find and has to get the
178 // dof values from these processes and so on.
179 //
180 // Algorithm:
181 // 1) Loop over all coarse cells
182 // From each coarse cell traverse down the tree
183 // of refined cells and search for active children
184 // If there is an active child, check, if all
185 // other children down to the finest level are part
186 // of this process, if not, add the cell to the list
187 // of needs.
188 // 2) Send the list of needs to other processes
189 // Each process has a list of needs and after
190 // the loop over all coarse cells (all trees)
191 // is finished, this list can be send to other processes.
192 // 3) Compute the needs required by other processes
193 // While computing the values required from other
194 // processes there can arise new needs and they are
195 // stored in a list again.
196 // 4) Send the computed values and the list of new needs around
197 //
198 // This procedure has to be repeated until no process needs any
199 // new need and all needs are computed, but there are at most the
200 // "number of grid levels" rounds of sending/receiving cell data.
201 //
202 // Then each process has all data needed for extrapolation.
203
204 // driver function sending/receiving all values from
205 // different processes
206 template <class InVector>
207 void
208 compute_all_non_local_data(const DoFHandler<dim, spacedim> &dof2,
209 const InVector &u);
210
211 // traverse recursively over
212 // the cells of this tree and
213 // interpolate over patches which
214 // are part of this process
215 template <class InVector>
216 void
217 interpolate_recursively(
218 const typename dealii::internal::p4est::types<dim>::forest &forest,
219 const typename dealii::internal::p4est::types<dim>::tree &tree,
220 const typename dealii::internal::p4est::types<dim>::locidx &tree_index,
221 const typename DoFHandler<dim, spacedim>::cell_iterator &dealii_cell,
222 const typename dealii::internal::p4est::types<dim>::quadrant
223 &p4est_cell,
224 const InVector &u1,
225 OutVector &u2);
226
227 // get dof values for this
228 // cell by interpolation
229 // if a child is reached which
230 // is not part of this process
231 // a new need is created
232 template <class InVector>
233 void
234 get_interpolated_dof_values(
235 const typename dealii::internal::p4est::types<dim>::forest &forest,
236 const typename dealii::internal::p4est::types<dim>::tree &tree,
237 const typename dealii::internal::p4est::types<dim>::locidx &tree_index,
238 const typename DoFHandler<dim, spacedim>::cell_iterator &dealii_cell,
239 const typename dealii::internal::p4est::types<dim>::quadrant
240 &p4est_cell,
241 const InVector &u,
242 Vector<value_type> &interpolated_values,
243 std::vector<CellData> &new_needs);
244
245 // set dof values for this
246 // cell by interpolation
247 void
248 set_dof_values_by_interpolation(
249 const typename DoFHandler<dim, spacedim>::cell_iterator &dealii_cell,
250 const typename dealii::internal::p4est::types<dim>::quadrant
251 &p4est_cell,
252 const Vector<value_type> &interpolated_values,
253 OutVector &u);
254
255 // compute all cell_data
256 // needed from other processes
257 // to interpolate the part of
258 // this process
259 void
260 compute_needs(const DoFHandler<dim, spacedim> &dof2,
261 std::vector<CellData> &new_needs);
262
263 // traverse over the tree
264 // and look for patches this
265 // process has to work on
266 void
267 traverse_tree_recursively(
268 const typename dealii::internal::p4est::types<dim>::forest &forest,
269 const typename dealii::internal::p4est::types<dim>::tree &tree,
270 const typename dealii::internal::p4est::types<dim>::locidx &tree_index,
271 const typename DoFHandler<dim, spacedim>::cell_iterator &dealii_cell,
272 const typename dealii::internal::p4est::types<dim>::quadrant
273 &p4est_cell,
274 std::vector<CellData> &new_needs);
275
276 // traverse recursively
277 // over a patch and look
278 // for cells needed from
279 // other processes for interpolation
280 void
281 traverse_patch_recursively(
282 const typename dealii::internal::p4est::types<dim>::forest &forest,
283 const typename dealii::internal::p4est::types<dim>::tree &tree,
284 const typename dealii::internal::p4est::types<dim>::locidx &tree_index,
285 const typename DoFHandler<dim, spacedim>::cell_iterator &dealii_cell,
286 const typename dealii::internal::p4est::types<dim>::quadrant
287 &p4est_cell,
288 std::vector<CellData> &new_needs);
289
290 // compute dof values of all
291 // cells collected in cells_to_compute
292 // computed cells are deleted
293 // from cells_to_compute and
294 // stored in computed_cells
295 // during computation there can
296 // be new cells needed from
297 // other processes, these cells
298 // are stored in new_needs
299 template <class InVector>
300 void
301 compute_cells(const DoFHandler<dim, spacedim> &dof2,
302 const InVector &u,
303 std::vector<CellData> &cells_to_compute,
304 std::vector<CellData> &computed_cells,
305 std::vector<CellData> &new_needs);
306
307 // traverse over the tree
308 // and compute cells
309 template <class InVector>
310 void
311 compute_cells_in_tree_recursively(
312 const typename dealii::internal::p4est::types<dim>::forest &forest,
313 const typename dealii::internal::p4est::types<dim>::tree &tree,
314 const typename dealii::internal::p4est::types<dim>::locidx &tree_index,
315 const typename DoFHandler<dim, spacedim>::cell_iterator &dealii_cell,
316 const typename dealii::internal::p4est::types<dim>::quadrant
317 &p4est_cell,
318 const InVector &u,
319 std::vector<CellData> &cells_to_compute,
320 std::vector<CellData> &computed_cells,
321 std::vector<CellData> &new_needs);
322
323 // send all cell_data in the vector
324 // cells_to_send to their receivers
325 // and receives a vector of cell_data
326 void
327 exchange_data_on_cells(const std::vector<CellData> &cells_to_send,
328 std::vector<CellData> &received_cells) const;
329
330 // add new cell_data to
331 // the ordered list new_needs
332 // uses cell_data_insert
333 static void
334 add_new_need(
335 const typename dealii::internal::p4est::types<dim>::forest &forest,
336 const typename dealii::internal::p4est::types<dim>::locidx &tree_index,
337 const typename DoFHandler<dim, spacedim>::cell_iterator &dealii_cell,
338 const typename dealii::internal::p4est::types<dim>::quadrant
339 &p4est_cell,
340 std::vector<CellData> &new_needs);
341
342 // binary search in cells_list
343 // assume that cells_list
344 // is ordered
345 static int
346 cell_data_search(const CellData &cell_data,
347 const std::vector<CellData> &cells_list);
348
349 // insert cell_data into a sorted
350 // vector cells_list at the correct
351 // position if cell_data
352 // not exists already in cells_list
353 static void
354 cell_data_insert(const CellData &cell_data,
355 std::vector<CellData> &cells_list);
356
357 MPI_Comm communicator;
358
359 // a vector of all cells this process has
360 // computed or received data
361 std::vector<CellData> available_cells;
362
363 // When OutVector is a distributed vector from LinearAlgebra::distributed,
364 // stores the dofs indices of refined locally owned (resp., ghost) cells
365 // that have a coarser neighboring ghost (resp., locally owned) cell,
366 // along with the max cell level associated with each of these dofs. Else,
367 // simply stores the indices of dofs on more refined ghosted cells along
368 // with the maximum level
369 std::map<types::global_dof_index, int> dofs_at_refined_ghost_interface;
370
371
372 // counts the send/receive round we are in
373 unsigned int round;
374 };
375
376
377
378 template <class OutVector>
379 class ExtrapolateImplementation<1, 1, OutVector>
380 {
381 public:
382 ExtrapolateImplementation()
383 {
384 AssertThrow(false, ExcNotImplemented());
385 }
386
387 template <class InVector>
388 void
389 extrapolate_parallel(const InVector & /*u2_relevant*/,
390 const DoFHandler<1, 1> & /*dof2*/,
391 OutVector & /*u2*/)
392 {}
393 };
394
395 template <class OutVector>
396 class ExtrapolateImplementation<1, 2, OutVector>
397 {
398 public:
399 ExtrapolateImplementation()
400 {
401 AssertThrow(false, ExcNotImplemented());
402 }
403
404 template <class InVector>
405 void
406 extrapolate_parallel(const InVector & /*u2_relevant*/,
407 const DoFHandler<1, 2> & /*dof2*/,
408 OutVector & /*u2*/)
409 {}
410 };
411
412 template <class OutVector>
413 class ExtrapolateImplementation<1, 3, OutVector>
414 {
415 public:
416 ExtrapolateImplementation()
417 {
418 AssertThrow(false, ExcNotImplemented());
419 }
420
421 template <class InVector>
422 void
423 extrapolate_parallel(const InVector & /*u2_relevant*/,
424 const DoFHandler<1, 3> & /*dof2*/,
425 OutVector & /*u2*/)
426 {}
427 };
428
429
430
431 template <int dim, int spacedim, class OutVector>
432 ExtrapolateImplementation<dim, spacedim, OutVector>::
433 ExtrapolateImplementation()
434 : round(0)
435 {}
436
437
438
439 template <int dim, int spacedim, class OutVector>
440 ExtrapolateImplementation<dim, spacedim, OutVector>::CellData::CellData()
441 : tree_index(0)
442 , receiver(0)
443 {}
444
445
446
447 template <int dim, int spacedim, class OutVector>
448 ExtrapolateImplementation<dim, spacedim, OutVector>::CellData::CellData(
449 const unsigned int dofs_per_cell)
450 : dof_values(dofs_per_cell)
451 , tree_index(0)
452 , receiver(0)
453 {}
454
455
456
457 template <int dim, int spacedim, class OutVector>
458 bool
459 ExtrapolateImplementation<dim, spacedim, OutVector>::CellData::operator<(
460 const CellData &rhs) const
461 {
462 if (dealii::internal::p4est::functions<dim>::quadrant_compare(
463 &quadrant, &rhs.quadrant) < 0)
464 return true;
465
466 return false;
467 }
468
469
470
471 template <int dim, int spacedim, class OutVector>
472 template <class Archive>
473 void
474 ExtrapolateImplementation<dim, spacedim, OutVector>::CellData::serialize(
475 Archive &ar,
476 const unsigned int)
477 {
478 // Serialize those data types for which there are overloads:
479 ar &dof_values &tree_index;
480
481 // Then also serialize the 'quadrant' variable for which there
482 // isn't an overload. Do so by simply copying the individual
483 // bytes
484 ar &boost::serialization::make_array(reinterpret_cast<char *>(&quadrant),
485 sizeof(quadrant));
486 }
487
488
489
490 template <int dim, int spacedim, class OutVector>
491 template <class InVector>
492 void
493 ExtrapolateImplementation<dim, spacedim, OutVector>::
494 interpolate_recursively(
495 const typename dealii::internal::p4est::types<dim>::forest &forest,
496 const typename dealii::internal::p4est::types<dim>::tree &tree,
497 const typename dealii::internal::p4est::types<dim>::locidx &tree_index,
498 const typename DoFHandler<dim, spacedim>::cell_iterator &dealii_cell,
499 const typename dealii::internal::p4est::types<dim>::quadrant
500 &p4est_cell,
501 const InVector &u1,
502 OutVector &u2)
503 {
504 // check if this cell exists in the local p4est
505 int idx = sc_array_bsearch(
506 const_cast<sc_array_t *>(&tree.quadrants),
507 &p4est_cell,
508 dealii::internal::p4est::functions<dim>::quadrant_compare);
509
510 // if neither this cell nor one of it's children belongs to us, don't do
511 // anything
512 if (idx == -1 &&
513 (dealii::internal::p4est::functions<dim>::quadrant_overlaps_tree(
514 const_cast<typename dealii::internal::p4est::types<dim>::tree *>(
515 &tree),
516 &p4est_cell) == false))
517 return;
518
519 bool p4est_has_children = (idx == -1);
520
521 bool locally_owned_children = false;
522 if (p4est_has_children)
523 {
524 Assert(dealii_cell->has_children(), ExcInternalError());
525
526 // check if at least one child is locally owned on our process
527 for (unsigned int child_n = 0; child_n < dealii_cell->n_children();
528 ++child_n)
529 if (dealii_cell->child(child_n)->is_active())
530 if (dealii_cell->child(child_n)->is_locally_owned())
531 {
532 locally_owned_children = true;
533 break;
534 }
535 }
536
537 if (locally_owned_children)
538 {
539 const FiniteElement<dim, spacedim> &fe =
540 dealii_cell->get_dof_handler().get_fe();
541 const unsigned int dofs_per_cell = fe.n_dofs_per_cell();
542
543 Vector<typename OutVector::value_type> interpolated_values(
544 dofs_per_cell);
545
546 std::vector<CellData> new_needs;
547 get_interpolated_dof_values(forest,
548 tree,
549 tree_index,
550 dealii_cell,
551 p4est_cell,
552 u1,
553 interpolated_values,
554 new_needs);
555
556 // at this point of
557 // the procedure no new
558 // needs should come up
559 Assert(new_needs.empty(), ExcInternalError());
560
561 set_dof_values_by_interpolation(dealii_cell,
562 p4est_cell,
563 interpolated_values,
564 u2);
565 }
566 }
567
568
569
570 template <int dim, int spacedim, class OutVector>
571 template <class InVector>
572 void
573 ExtrapolateImplementation<dim, spacedim, OutVector>::
574 get_interpolated_dof_values(
575 const typename dealii::internal::p4est::types<dim>::forest &forest,
576 const typename dealii::internal::p4est::types<dim>::tree &tree,
577 const typename dealii::internal::p4est::types<dim>::locidx &tree_index,
578 const typename DoFHandler<dim, spacedim>::cell_iterator &dealii_cell,
579 const typename dealii::internal::p4est::types<dim>::quadrant
580 &p4est_cell,
581 const InVector &u,
582 Vector<value_type> &interpolated_values,
583 std::vector<CellData> &new_needs)
584 {
585 if (dealii_cell->is_active())
586 {
587 if (dealii_cell->is_locally_owned())
588 {
589 // if this is one of our cells,
590 // get dof values from input vector
591 dealii_cell->get_dof_values(u, interpolated_values);
592 }
593 else
594 {
595 add_new_need(
596 forest, tree_index, dealii_cell, p4est_cell, new_needs);
597 }
598 }
599 else
600 {
601 const FiniteElement<dim, spacedim> &fe =
602 dealii_cell->get_dof_handler().get_fe();
603 const unsigned int dofs_per_cell = fe.n_dofs_per_cell();
604
605 Assert(interpolated_values.size() == dofs_per_cell,
606 ExcDimensionMismatch(interpolated_values.size(),
607 dofs_per_cell));
608 Assert(u.size() == dealii_cell->get_dof_handler().n_dofs(),
609 ExcDimensionMismatch(u.size(),
610 dealii_cell->get_dof_handler().n_dofs()));
611
612 Vector<value_type> tmp1(dofs_per_cell);
613 Vector<value_type> tmp2(dofs_per_cell);
614
615 interpolated_values = 0;
616 std::vector<bool> restriction_is_additive(dofs_per_cell);
617 for (unsigned int i = 0; i < dofs_per_cell; ++i)
618 restriction_is_additive[i] = fe.restriction_is_additive(i);
619
620 typename dealii::internal::p4est::types<dim>::quadrant
621 p4est_child[GeometryInfo<dim>::max_children_per_cell];
622
623 dealii::internal::p4est::init_quadrant_children<dim>(p4est_cell,
624 p4est_child);
625
626 bool found_child = true;
627 for (unsigned int c = 0; c < GeometryInfo<dim>::max_children_per_cell;
628 ++c)
629 {
630 if (dealii::internal::p4est::functions<dim>::
631 quadrant_overlaps_tree(
632 const_cast<
633 typename dealii::internal::p4est::types<dim>::tree *>(
634 &tree),
635 &p4est_child[c]) == false)
636 {
637 // this is a cell this process needs
638 // data from another process
639
640 // check if this cell is
641 // available from other
642 // computed patches
643 CellData cell_data;
644 cell_data.quadrant = p4est_child[c];
645 int pos = cell_data_search(cell_data, available_cells);
646
647 if (pos == -1)
648 {
649 // data is not available
650 // create a new need
651 found_child = false;
652
653 add_new_need(forest,
654 tree_index,
655 dealii_cell->child(c),
656 p4est_child[c],
657 new_needs);
658 }
659 else
660 {
661 Assert(available_cells[pos].dof_values.size() ==
662 dofs_per_cell,
663 ExcDimensionMismatch(
664 available_cells[pos].dof_values.size(),
665 dofs_per_cell));
666
667 tmp1 = available_cells[pos].dof_values;
668 }
669 }
670 else
671 {
672 // get the values from the present child, if necessary by
673 // interpolation either from its own children or
674 // by interpolating from the finite element on an active
675 // child to the finite element space requested here
676 get_interpolated_dof_values(forest,
677 tree,
678 tree_index,
679 dealii_cell->child(c),
680 p4est_child[c],
681 u,
682 tmp1,
683 new_needs);
684 }
685
686 if (found_child)
687 {
688 // interpolate these to the parent cell
689 fe.get_restriction_matrix(c, dealii_cell->refinement_case())
690 .vmult(tmp2, tmp1);
691
692 // and add up or set them in the output vector
693 for (unsigned int i = 0; i < dofs_per_cell; ++i)
694 if (tmp2(i) != value_type())
695 {
696 if (restriction_is_additive[i])
697 interpolated_values(i) += tmp2(i);
698 else
699 interpolated_values(i) = tmp2(i);
700 }
701 }
702 }
703
704 if (found_child == false)
705 interpolated_values = 0;
706 }
707 }
708
709 template <typename T>
710 inline constexpr bool is_la_vector = false;
711
712 template <typename Number, typename MemorySpace>
713 inline constexpr bool
714 is_la_vector<LinearAlgebra::distributed::Vector<Number, MemorySpace>> =
715 true;
716
717 template <typename Number, typename MemorySpace>
718 inline constexpr bool is_la_vector<
719 LinearAlgebra::distributed::BlockVector<Number, MemorySpace>> = true;
720
721 template <int dim, int spacedim, class OutVector>
722 void
723 ExtrapolateImplementation<dim, spacedim, OutVector>::
724 set_dof_values_by_interpolation(
725 const typename DoFHandler<dim, spacedim>::cell_iterator &dealii_cell,
726 const typename dealii::internal::p4est::types<dim>::quadrant
727 &p4est_cell,
728 const Vector<value_type> &local_values,
729 OutVector &u)
730 {
731 const FiniteElement<dim, spacedim> &fe =
732 dealii_cell->get_dof_handler().get_fe();
733 const unsigned int dofs_per_cell = fe.n_dofs_per_cell();
734
735 if (dealii_cell->is_active())
736 {
737 if (dealii_cell->is_locally_owned())
738 {
739 std::vector<types::global_dof_index> indices(dofs_per_cell);
740 dealii_cell->get_dof_indices(indices);
741 for (unsigned int j = 0; j < dofs_per_cell; ++j)
742 {
743 // In serial runs, the DoFs values from refined patches always
744 // overwrite the values that may be set by parent patches if
745 // the triangulation is adaptively refined. For this to also
746 // happen in a distributed simulation, only set the dof value
747 // if there are no more refined ghosted neighbor setting this
748 // dof. A final compression operation at the end will
749 // synchronize the correct refined values on all processors.
750 const bool on_refined_neighbor =
751 (dofs_at_refined_ghost_interface.find(indices[j]) !=
752 dofs_at_refined_ghost_interface.end());
753 if (!(on_refined_neighbor &&
754 dofs_at_refined_ghost_interface[indices[j]] >
755 dealii_cell->level()))
756 ::dealii::internal::ElementAccess<OutVector>::set(
757 local_values(j), indices[j], u);
758 }
759 }
760 }
761 else
762 {
763 Assert(local_values.size() == dofs_per_cell,
764 ExcDimensionMismatch(local_values.size(), dofs_per_cell));
765 Assert(u.size() == dealii_cell->get_dof_handler().n_dofs(),
766 ExcDimensionMismatch(u.size(),
767 dealii_cell->get_dof_handler().n_dofs()));
768
769 Vector<value_type> tmp(dofs_per_cell);
770
771 typename dealii::internal::p4est::types<dim>::quadrant
772 p4est_child[GeometryInfo<dim>::max_children_per_cell];
773
774 dealii::internal::p4est::init_quadrant_children<dim>(p4est_cell,
775 p4est_child);
776
777 for (unsigned int c = 0; c < GeometryInfo<dim>::max_children_per_cell;
778 ++c)
779 {
780 if (tmp.size() > 0)
781 fe.get_prolongation_matrix(c, dealii_cell->refinement_case())
782 .vmult(tmp, local_values);
783
784 set_dof_values_by_interpolation(dealii_cell->child(c),
785 p4est_child[c],
786 tmp,
787 u);
788 }
789 }
790 }
791
792
793
794 template <int dim, int spacedim, class OutVector>
795 void
796 ExtrapolateImplementation<dim, spacedim, OutVector>::compute_needs(
797 const DoFHandler<dim, spacedim> &dof2,
798 std::vector<CellData> &new_needs)
799 {
800 const parallel::distributed::Triangulation<dim, spacedim> *tr =
801 (dynamic_cast<const parallel::distributed::Triangulation<dim, spacedim>
802 *>(&dof2.get_triangulation()));
803
804 Assert(tr != nullptr, ExcInternalError());
805
806 for (const auto &cell : dof2.cell_iterators_on_level(0))
807 {
808 if (dealii::internal::p4est::tree_exists_locally<dim>(
809 tr->parallel_forest,
810 tr->coarse_cell_to_p4est_tree_permutation[cell->index()]) ==
811 false)
812 continue;
813
814 typename dealii::internal::p4est::types<dim>::quadrant
815 p4est_coarse_cell;
816 const unsigned int tree_index =
817 tr->coarse_cell_to_p4est_tree_permutation[cell->index()];
818 typename dealii::internal::p4est::types<dim>::tree *tree =
819 tr->init_tree(cell->index());
820
821 dealii::internal::p4est::init_coarse_quadrant<dim>(p4est_coarse_cell);
822
823 // make sure that each cell on the
824 // coarsest level is at least once
825 // refined, otherwise, these cells
826 // can't be treated and would
827 // generate a bogus result
828 {
829 int idx = sc_array_bsearch(
830 const_cast<sc_array_t *>(&tree->quadrants),
831 &p4est_coarse_cell,
832 dealii::internal::p4est::functions<dim>::quadrant_compare);
833
834 AssertThrow(idx == -1, ExcGridNotRefinedAtLeastOnce());
835 }
836
837 traverse_tree_recursively(*tr->parallel_forest,
838 *tree,
839 tree_index,
840 cell,
841 p4est_coarse_cell,
842 new_needs);
843 }
844 }
845
846
847
848 template <int dim, int spacedim, class OutVector>
849 void
850 ExtrapolateImplementation<dim, spacedim, OutVector>::
851 traverse_tree_recursively(
852 const typename dealii::internal::p4est::types<dim>::forest &forest,
853 const typename dealii::internal::p4est::types<dim>::tree &tree,
854 const typename dealii::internal::p4est::types<dim>::locidx &tree_index,
855 const typename DoFHandler<dim, spacedim>::cell_iterator &dealii_cell,
856 const typename dealii::internal::p4est::types<dim>::quadrant
857 &p4est_cell,
858 std::vector<CellData> &new_needs)
859 {
860 // check if this cell exists in the local p4est
861 int idx = sc_array_bsearch(
862 const_cast<sc_array_t *>(&tree.quadrants),
863 &p4est_cell,
864 dealii::internal::p4est::functions<dim>::quadrant_compare);
865
866 // if neither this cell nor one of it's children belongs to us, don't do
867 // anything
868 if (idx == -1 &&
869 (dealii::internal::p4est::functions<dim>::quadrant_overlaps_tree(
870 const_cast<typename dealii::internal::p4est::types<dim>::tree *>(
871 &tree),
872 &p4est_cell) == false))
873 return;
874
875 bool p4est_has_children = (idx == -1);
876
877 // this cell is part of a patch
878 // this process has to interpolate on
879 // if there is at least one locally
880 // owned child
881 bool locally_owned_children = false;
882 if (p4est_has_children)
883 {
884 Assert(dealii_cell->has_children(), ExcInternalError());
885
886 for (unsigned int child_n = 0; child_n < dealii_cell->n_children();
887 ++child_n)
888 if (dealii_cell->child(child_n)->is_active())
889 if (dealii_cell->child(child_n)->is_locally_owned())
890 {
891 locally_owned_children = true;
892 break;
893 }
894 }
895
896 // traverse the patch recursively
897 // to find cells needed from
898 // other processes
899 if (locally_owned_children)
900 {
901 traverse_patch_recursively(
902 forest, tree, tree_index, dealii_cell, p4est_cell, new_needs);
903 }
904
905 // traverse recursively over this tree
906 if (p4est_has_children)
907 {
908 typename dealii::internal::p4est::types<dim>::quadrant
909 p4est_child[GeometryInfo<dim>::max_children_per_cell];
910
911 dealii::internal::p4est::init_quadrant_children<dim>(p4est_cell,
912 p4est_child);
913
914 for (unsigned int c = 0; c < GeometryInfo<dim>::max_children_per_cell;
915 ++c)
916 {
917 traverse_tree_recursively(forest,
918 tree,
919 tree_index,
920 dealii_cell->child(c),
921 p4est_child[c],
922 new_needs);
923 }
924 }
925 }
926
927
928
929 template <int dim, int spacedim, class OutVector>
930 void
931 ExtrapolateImplementation<dim, spacedim, OutVector>::
932 traverse_patch_recursively(
933 const typename dealii::internal::p4est::types<dim>::forest &forest,
934 const typename dealii::internal::p4est::types<dim>::tree &tree,
935 const typename dealii::internal::p4est::types<dim>::locidx &tree_index,
936 const typename DoFHandler<dim, spacedim>::cell_iterator &dealii_cell,
937 const typename dealii::internal::p4est::types<dim>::quadrant
938 &p4est_cell,
939 std::vector<CellData> &new_needs)
940 {
941 if (dealii_cell->has_children())
942 {
943 Assert(dealii_cell->has_children(), ExcInternalError());
944
945 typename dealii::internal::p4est::types<dim>::quadrant
946 p4est_child[GeometryInfo<dim>::max_children_per_cell];
947
948 dealii::internal::p4est::init_quadrant_children<dim>(p4est_cell,
949 p4est_child);
950
951 for (unsigned int c = 0; c < GeometryInfo<dim>::max_children_per_cell;
952 ++c)
953 {
954 // check if this child
955 // is locally available
956 // in the p4est
957 if (dealii::internal::p4est::functions<dim>::
958 quadrant_overlaps_tree(
959 const_cast<
960 typename dealii::internal::p4est::types<dim>::tree *>(
961 &tree),
962 &p4est_child[c]) == false)
963 {
964 // this is a cell for which this process
965 // needs data from another process
966 // so add the cell to the list
967 add_new_need(forest,
968 tree_index,
969 dealii_cell->child(c),
970 p4est_child[c],
971 new_needs);
972 }
973 else
974 {
975 // at least some part of
976 // the tree rooted in this
977 // child is locally available
978 traverse_patch_recursively(forest,
979 tree,
980 tree_index,
981 dealii_cell->child(c),
982 p4est_child[c],
983 new_needs);
984 }
985 }
986 }
987 }
988
989
990
991 template <int dim, int spacedim, class OutVector>
992 template <class InVector>
993 void
994 ExtrapolateImplementation<dim, spacedim, OutVector>::compute_cells(
995 const DoFHandler<dim, spacedim> &dof2,
996 const InVector &u,
997 std::vector<CellData> &cells_to_compute,
998 std::vector<CellData> &computed_cells,
999 std::vector<CellData> &new_needs)
1000 {
1001 const parallel::distributed::Triangulation<dim, spacedim> *tr =
1002 (dynamic_cast<const parallel::distributed::Triangulation<dim, spacedim>
1003 *>(&dof2.get_triangulation()));
1004
1005 Assert(tr != nullptr, ExcInternalError());
1006
1007 // collect in a set all trees this
1008 // process has to compute cells on
1009 std::set<unsigned int> trees;
1010 for (const auto &c : cells_to_compute)
1011 trees.insert(c.tree_index);
1012
1013 for (const auto &cell : dof2.cell_iterators_on_level(0))
1014 {
1015 // check if this is a tree this process has to
1016 // work on and that this tree is in the p4est
1017 const unsigned int tree_index =
1018 tr->coarse_cell_to_p4est_tree_permutation[cell->index()];
1019
1020 if ((trees.find(tree_index) == trees.end()) ||
1021 (dealii::internal::p4est::tree_exists_locally<dim>(
1022 tr->parallel_forest, tree_index) == false))
1023 continue;
1024
1025 typename dealii::internal::p4est::types<dim>::quadrant
1026 p4est_coarse_cell;
1027 typename dealii::internal::p4est::types<dim>::tree *tree =
1028 tr->init_tree(cell->index());
1029
1030 dealii::internal::p4est::init_coarse_quadrant<dim>(p4est_coarse_cell);
1031
1032 compute_cells_in_tree_recursively(*tr->parallel_forest,
1033 *tree,
1034 tree_index,
1035 cell,
1036 p4est_coarse_cell,
1037 u,
1038 cells_to_compute,
1039 computed_cells,
1040 new_needs);
1041 }
1042 }
1043
1044
1045
1046 template <int dim, int spacedim, class OutVector>
1047 template <class InVector>
1048 void
1049 ExtrapolateImplementation<dim, spacedim, OutVector>::
1050 compute_cells_in_tree_recursively(
1051 const typename dealii::internal::p4est::types<dim>::forest &forest,
1052 const typename dealii::internal::p4est::types<dim>::tree &tree,
1053 const typename dealii::internal::p4est::types<dim>::locidx &tree_index,
1054 const typename DoFHandler<dim, spacedim>::cell_iterator &dealii_cell,
1055 const typename dealii::internal::p4est::types<dim>::quadrant
1056 &p4est_cell,
1057 const InVector &u,
1058 std::vector<CellData> &cells_to_compute,
1059 std::vector<CellData> &computed_cells,
1060 std::vector<CellData> &new_needs)
1061 {
1062 if (cells_to_compute.empty())
1063 return;
1064
1065 // check if this cell exists in the local p4est
1066 int idx = sc_array_bsearch(
1067 const_cast<sc_array_t *>(&tree.quadrants),
1068 &p4est_cell,
1069 dealii::internal::p4est::functions<dim>::quadrant_compare);
1070
1071 // if neither this cell nor one of it's children belongs to us, don't do
1072 // anything
1073 if (idx == -1 &&
1074 (dealii::internal::p4est::functions<dim>::quadrant_overlaps_tree(
1075 const_cast<typename dealii::internal::p4est::types<dim>::tree *>(
1076 &tree),
1077 &p4est_cell) == false))
1078 return;
1079
1080 bool p4est_has_children = (idx == -1);
1081
1082 // check if this quadrant is in the list
1083 CellData cell_data;
1084 cell_data.quadrant = p4est_cell;
1085 int pos = cell_data_search(cell_data, cells_to_compute);
1086 if (pos != -1)
1087 {
1088 std::vector<CellData> tmp;
1089 // compute dof values
1090 get_interpolated_dof_values(forest,
1091 tree,
1092 tree_index,
1093 dealii_cell,
1094 p4est_cell,
1095 u,
1096 cells_to_compute[pos].dof_values,
1097 tmp);
1098 // there is no new cell_data
1099 // this process needs for computing this cell,
1100 // store cell_data in the list of
1101 // computed cells and erase this cell
1102 // from the list of cells to compute
1103 if (tmp.empty())
1104 {
1105 cell_data_insert(cells_to_compute[pos], computed_cells);
1106 cells_to_compute.erase(cells_to_compute.begin() + pos);
1107 }
1108 else
1109 {
1110 for (unsigned int i = 0; i < tmp.size(); ++i)
1111 cell_data_insert(tmp[i], new_needs);
1112 }
1113 }
1114
1115 // search recursively over this tree
1116 if (p4est_has_children)
1117 {
1118 typename dealii::internal::p4est::types<dim>::quadrant
1119 p4est_child[GeometryInfo<dim>::max_children_per_cell];
1120
1121 dealii::internal::p4est::init_quadrant_children<dim>(p4est_cell,
1122 p4est_child);
1123
1124 for (unsigned int c = 0; c < GeometryInfo<dim>::max_children_per_cell;
1125 ++c)
1126 {
1127 compute_cells_in_tree_recursively(forest,
1128 tree,
1129 tree_index,
1130 dealii_cell->child(c),
1131 p4est_child[c],
1132 u,
1133 cells_to_compute,
1134 computed_cells,
1135 new_needs);
1136 }
1137 }
1138 }
1139
1140
1141
1142 template <int dim, int spacedim, class OutVector>
1143 void
1144 ExtrapolateImplementation<dim, spacedim, OutVector>::exchange_data_on_cells(
1145 const std::vector<CellData> &cells_to_send,
1146 std::vector<CellData> &received_cells) const
1147 {
1148 // First figure out where we need to send stuff. Some of the cells
1149 // in the input argument to this function might be destined for
1150 // the same process, so we have to only look at the unique set of
1151 // destinations:
1152 std::set<types::subdomain_id> destinations;
1153 for (const auto &cell : cells_to_send)
1154 destinations.insert(cell.receiver);
1155
1156 // Then set up the send/receive operation. This is best done through
1157 // the 'consensus algorithm' setup that is used for point-to-point
1158 // communication of information in cases where we do not know up
1159 // front which processes (and from how many processes) we have to
1160 // expect information from.
1161 const auto create_request =
1162 [&cells_to_send](
1163 const types::subdomain_id other_rank) -> std::vector<CellData> {
1164 std::vector<CellData> cells_for_this_destination;
1165 for (const auto &cell : cells_to_send)
1166 if (cell.receiver == other_rank)
1167 cells_for_this_destination.emplace_back(cell);
1168
1169 return cells_for_this_destination;
1170 };
1171
1172 const auto process_request =
1173 [&received_cells](const unsigned int other_rank,
1174 const std::vector<CellData> &request) {
1175 // We got a message from 'other_rank', so let us decode the
1176 // message in the same way as we have assembled it above.
1177 // Note that the cells just received do not contain
1178 // information where they came from, and we have to add that
1179 // ourselves for later use.
1180 for (CellData cell_data : request)
1181 {
1182 cell_data.receiver = other_rank;
1183 received_cells.emplace_back(std::move(cell_data));
1184 }
1185 };
1186
1187 Utilities::MPI::ConsensusAlgorithms::selector<std::vector<CellData>>(
1188 std::vector<types::subdomain_id>(destinations.begin(),
1189 destinations.end()),
1190 create_request,
1191 process_request,
1192 communicator);
1193 }
1194
1195
1196
1197 template <int dim, int spacedim, class OutVector>
1198 void
1199 ExtrapolateImplementation<dim, spacedim, OutVector>::add_new_need(
1200 const typename dealii::internal::p4est::types<dim>::forest &forest,
1201 const typename dealii::internal::p4est::types<dim>::locidx &tree_index,
1202 const typename DoFHandler<dim, spacedim>::cell_iterator &dealii_cell,
1203 const typename dealii::internal::p4est::types<dim>::quadrant &p4est_cell,
1204 std::vector<CellData> &new_needs)
1205 {
1206 const FiniteElement<dim, spacedim> &fe =
1207 dealii_cell->get_dof_handler().get_fe();
1208 const unsigned int dofs_per_cell = fe.n_dofs_per_cell();
1209
1210 CellData cell_data(dofs_per_cell);
1211 cell_data.quadrant = p4est_cell;
1212 cell_data.tree_index = tree_index;
1213 cell_data.receiver =
1214 dealii::internal::p4est::functions<dim>::comm_find_owner(
1215 const_cast<typename dealii::internal::p4est::types<dim>::forest *>(
1216 &forest),
1217 tree_index,
1218 &p4est_cell,
1219 dealii_cell->level_subdomain_id());
1220
1221 cell_data_insert(cell_data, new_needs);
1222 }
1223
1224
1225
1226 template <int dim, int spacedim, class OutVector>
1227 int
1228 ExtrapolateImplementation<dim, spacedim, OutVector>::cell_data_search(
1229 const CellData &cell_data,
1230 const std::vector<CellData> &cells_list)
1231 {
1232 typename std::vector<CellData>::const_iterator bound =
1233 std::lower_bound(cells_list.begin(), cells_list.end(), cell_data);
1234
1235 if ((bound != cells_list.end()) && !(cell_data < *bound))
1236 return static_cast<int>(bound - cells_list.begin());
1237
1238 return -1;
1239 }
1240
1241
1242
1243 template <int dim, int spacedim, class OutVector>
1244 void
1245 ExtrapolateImplementation<dim, spacedim, OutVector>::cell_data_insert(
1246 const CellData &cell_data,
1247 std::vector<CellData> &cells_list)
1248 {
1249 // Find the place to insert the cell:
1250 typename std::vector<CellData>::iterator bound =
1251 std::lower_bound(cells_list.begin(), cells_list.end(), cell_data);
1252
1253 // There are three possibilities: The cell needs to be inserted
1254 // at the end, the cell needs to be inserted just before the place
1255 // std::lower_bound found, or the cell already exists in the list
1256 // and no longer needs to be inserted. In that last case,
1257 // cell_data==*bound.
1258 if ((bound == cells_list.end()) || (cell_data < *bound))
1259 cells_list.insert(bound, 1, cell_data);
1260 }
1261
1262
1263
1264 template <int dim, int spacedim, class OutVector>
1265 template <class InVector>
1266 void
1267 ExtrapolateImplementation<dim, spacedim, OutVector>::
1268 compute_all_non_local_data(const DoFHandler<dim, spacedim> &dof2,
1269 const InVector &u)
1270 {
1271 std::vector<CellData> cells_we_need, cells_to_compute, received_cells,
1272 received_needs, new_needs, computed_cells, cells_to_send;
1273
1274 // Compute all the cells needed from other processes.
1275 compute_needs(dof2, cells_we_need);
1276
1277 // Send the cells needed to their owners and receive
1278 // a list of cells other processes need from us.
1279 exchange_data_on_cells(cells_we_need, received_needs);
1280
1281 // The list of received needs can contain some cells more than once
1282 // because different processes may need data from the same cell.
1283 // To compute data only once, generate a vector with unique entries
1284 // and distribute the computed data afterwards back to a vector with
1285 // correct receivers.
1286 // Computing cell_data can cause a need for data from some new cells.
1287 // If a cell is computed, send it back to their senders, maybe receive
1288 // new needs and compute again, do not wait that all cells are computed
1289 // or all needs are collected.
1290 // Otherwise we can run into a deadlock if a cell needed from another
1291 // process itself needs some data from us.
1292 unsigned int ready = 0;
1293 do
1294 {
1295 for (const auto &need : received_needs)
1296 cell_data_insert(need, cells_to_compute);
1297
1298 compute_cells(dof2, u, cells_to_compute, computed_cells, new_needs);
1299
1300 // if there are no cells to compute and no new needs, stop
1301 ready =
1302 Utilities::MPI::sum(new_needs.size() + cells_to_compute.size(),
1303 communicator);
1304
1305 for (const auto &comp : computed_cells)
1306 {
1307 // store computed cells...
1308 cell_data_insert(comp, available_cells);
1309
1310 // ...and generate a vector of computed cells with correct
1311 // receivers, then delete this received need from the list
1312 typename std::vector<CellData>::iterator recv =
1313 received_needs.begin();
1314 while (recv != received_needs.end())
1315 {
1316 if (dealii::internal::p4est::quadrant_is_equal<dim>(
1317 recv->quadrant, comp.quadrant))
1318 {
1319 recv->dof_values = comp.dof_values;
1320 cells_to_send.push_back(*recv);
1321 received_needs.erase(recv);
1322 recv = received_needs.begin();
1323 }
1324 else
1325 ++recv;
1326 }
1327 }
1328
1329 exchange_data_on_cells(cells_to_send, received_cells);
1330
1331 // store received cell_data
1332 for (const auto &recv : received_cells)
1333 {
1334 cell_data_insert(recv, available_cells);
1335 }
1336
1337 // finally send and receive new needs
1338 exchange_data_on_cells(new_needs, received_needs);
1339 }
1340 while (ready != 0);
1341 }
1342
1343
1344
1345 template <int dim, int spacedim, class OutVector>
1346 template <class InVector>
1347 void
1348 ExtrapolateImplementation<dim, spacedim, OutVector>::extrapolate_parallel(
1349 const InVector &u2_relevant,
1350 const DoFHandler<dim, spacedim> &dof2,
1351 OutVector &u2)
1352 {
1353 const parallel::distributed::Triangulation<dim, spacedim> *tr =
1354 (dynamic_cast<const parallel::distributed::Triangulation<dim, spacedim>
1355 *>(&dof2.get_triangulation()));
1356
1357 Assert(
1358 tr != nullptr,
1359 ExcMessage(
1360 "Extrapolate in parallel only works for parallel distributed triangulations!"));
1361
1362 communicator = tr->get_mpi_communicator();
1363
1364 compute_all_non_local_data(dof2, u2_relevant);
1365
1366 // List all DoFs that, on this mpi rank, live at the intersection between
1367 // a non-artificial cell and a more refined ghost cell (the dofs being
1368 // enumerated from the more refined side). For each of these DoFs, also
1369 // store the most refined level among the neighboring cells. This set of
1370 // DoFs naturally includes the set of DoFs shared between a refined ghost
1371 // cell and a coarser locally owned cell and can be constructed without a
1372 // recursion to find cells with common vertices (which are not necessarily
1373 // direct neighbors in 2D and 3D).
1374 const FiniteElement<dim, spacedim> &fe = dof2.get_fe();
1375 if (fe.max_dofs_per_face() > 0)
1376 {
1377 const unsigned int dofs_per_cell = fe.n_dofs_per_cell();
1378 std::vector<types::global_dof_index> indices(dofs_per_cell);
1379
1380 for (const auto &cell : dof2.active_cell_iterators())
1381 if (cell->is_ghost())
1382 for (const unsigned int face : cell->face_indices())
1383 if (!cell->at_boundary(face))
1384 {
1385 const typename DoFHandler<dim, spacedim>::cell_iterator
1386 neighbor = cell->neighbor(face);
1387 if (neighbor->is_active() && !neighbor->is_artificial() &&
1388 neighbor->level() < cell->level())
1389 {
1390 cell->get_dof_indices(indices);
1391 for (unsigned int i = 0; i < fe.n_dofs_per_face(face);
1392 ++i)
1393 {
1394 const types::global_dof_index index =
1395 indices[fe.face_to_cell_index(i, face)];
1396
1397 const bool index_stored =
1398 (dofs_at_refined_ghost_interface.find(index) !=
1399 dofs_at_refined_ghost_interface.end());
1400 const unsigned int level =
1401 index_stored ?
1402 std::max(
1403 cell->level(),
1404 dofs_at_refined_ghost_interface[index]) :
1405 cell->level();
1406 dofs_at_refined_ghost_interface[index] = level;
1407 }
1408 }
1409 }
1410 }
1411
1412 // after all dof values on
1413 // not owned patch cells
1414 // are computed, start
1415 // the interpolation
1416
1417 // Set the output vector to the neutral element of the final compress
1418 // operation
1419 if constexpr (is_la_vector<OutVector>)
1420 {
1421 if constexpr (IsBlockVector<OutVector>::value)
1422 for (unsigned int b = 0; b < u2.n_blocks(); ++b)
1423 {
1424 auto &block = u2.block(b);
1425 for (unsigned int i = 0;
1426 i < block.locally_owned_size() +
1427 block.get_partitioner()->n_ghost_indices();
1428 i++)
1429 block.local_element(i) = std::numeric_limits<
1430 typename OutVector::value_type>::lowest();
1431 }
1432 else
1433 for (unsigned int i = 0;
1434 i < u2.locally_owned_size() +
1435 u2.get_partitioner()->n_ghost_indices();
1436 i++)
1437 u2.local_element(i) =
1438 std::numeric_limits<typename OutVector::value_type>::lowest();
1439 }
1440 else
1441 u2 = typename OutVector::value_type(0.);
1442
1443 std::queue<WorkPackage> queue;
1444 {
1445 for (const auto &cell : dof2.cell_iterators_on_level(0))
1446 {
1447 if (dealii::internal::p4est::tree_exists_locally<dim>(
1448 tr->parallel_forest,
1449 tr->coarse_cell_to_p4est_tree_permutation[cell->index()]) ==
1450 false)
1451 continue;
1452
1453 typename dealii::internal::p4est::types<dim>::quadrant
1454 p4est_coarse_cell;
1455 const typename dealii::internal::p4est::types<dim>::locidx
1456 tree_index =
1457 tr->coarse_cell_to_p4est_tree_permutation[cell->index()];
1458 typename dealii::internal::p4est::types<dim>::tree *tree =
1459 tr->init_tree(cell->index());
1460
1461 dealii::internal::p4est::init_coarse_quadrant<dim>(
1462 p4est_coarse_cell);
1463
1464 queue.push({*tr->parallel_forest,
1465 *tree,
1466 tree_index,
1467 cell,
1468 p4est_coarse_cell});
1469 }
1470 }
1471
1472 while (!queue.empty())
1473 {
1474 const WorkPackage &data = queue.front();
1475
1476 const typename dealii::internal::p4est::types<dim>::forest &forest =
1477 data.forest;
1478 const typename dealii::internal::p4est::types<dim>::tree &tree =
1479 data.tree;
1480 const typename dealii::internal::p4est::types<dim>::locidx
1481 &tree_index = data.tree_index;
1482 const typename DoFHandler<dim, spacedim>::cell_iterator &dealii_cell =
1483 data.dealii_cell;
1484 const typename dealii::internal::p4est::types<dim>::quadrant
1485 &p4est_cell = data.p4est_cell;
1486
1487 interpolate_recursively(
1488 forest, tree, tree_index, dealii_cell, p4est_cell, u2_relevant, u2);
1489
1490 // traverse recursively over this tree
1491 if (dealii_cell->has_children())
1492 {
1493 Assert(dealii_cell->has_children(), ExcInternalError());
1494 typename dealii::internal::p4est::types<dim>::quadrant
1495 p4est_child[GeometryInfo<dim>::max_children_per_cell];
1496
1497 dealii::internal::p4est::init_quadrant_children<dim>(p4est_cell,
1498 p4est_child);
1499
1500 for (unsigned int c = 0;
1501 c < GeometryInfo<dim>::max_children_per_cell;
1502 ++c)
1503 queue.push({forest,
1504 tree,
1505 tree_index,
1506 dealii_cell->child(c),
1507 p4est_child[c]});
1508 }
1509 queue.pop();
1510 }
1511
1512 // Correctly synchronize values at ghost interface for all processors. For
1513 // Petsc/Trilinos, a simple compress(insert) operation allows to insert
1514 // values set by other processors into locally owned DoF, but the deal.II
1515 // implementation of the LinearAlgebra::distributed vectors and associated
1516 // compress(insert) operation does not do this. Instead, we use a
1517 // compress(max) that mimic this behavior.
1518 if constexpr (is_la_vector<OutVector>)
1519 u2.compress(VectorOperation::max);
1520 else
1521 u2.compress(VectorOperation::insert);
1522 }
1523 #endif // DEAL_II_WITH_P4EST
1524
1525 template <typename VectorType, typename dummy = void>
1526 struct BlockTypeHelper
1527 {
1528 using type = VectorType;
1529 };
1530
1531 template <typename VectorType>
1532 struct BlockTypeHelper<VectorType,
1533 std::enable_if_t<IsBlockVector<VectorType>::value>>
1534 {
1535 using type = typename VectorType::BlockType;
1536 };
1537
1538 template <typename VectorType>
1539 using BlockType = typename BlockTypeHelper<VectorType>::type;
1540
1541 template <typename VectorType, class DH>
1542 void
1543 reinit_distributed(const DH &dh, VectorType &vector)
1544 {
1545 vector.reinit(dh.n_dofs());
1546 }
1547
1548 #ifdef DEAL_II_WITH_PETSC
1549 template <int dim, int spacedim>
1550 void
1551 reinit_distributed(const DoFHandler<dim, spacedim> &dh,
1552 PETScWrappers::MPI::Vector &vector)
1553 {
1554 const parallel::distributed::Triangulation<dim, spacedim> *parallel_tria =
1555 dynamic_cast<
1556 const parallel::distributed::Triangulation<dim, spacedim> *>(
1557 &dh.get_triangulation());
1558 Assert(parallel_tria != nullptr, ExcNotImplemented());
1559
1560 const IndexSet &locally_owned_dofs = dh.locally_owned_dofs();
1561 vector.reinit(locally_owned_dofs, parallel_tria->get_mpi_communicator());
1562 }
1563 #endif // DEAL_II_WITH_PETSC
1564
1565 #ifdef DEAL_II_WITH_TRILINOS
1566 template <int dim, int spacedim>
1567 void
1568 reinit_distributed(const DoFHandler<dim, spacedim> &dh,
1569 TrilinosWrappers::MPI::Vector &vector)
1570 {
1571 const parallel::distributed::Triangulation<dim, spacedim> *parallel_tria =
1572 dynamic_cast<
1573 const parallel::distributed::Triangulation<dim, spacedim> *>(
1574 &dh.get_triangulation());
1575 Assert(parallel_tria != nullptr, ExcNotImplemented());
1576
1577 const IndexSet &locally_owned_dofs = dh.locally_owned_dofs();
1578 vector.reinit(locally_owned_dofs, parallel_tria->get_mpi_communicator());
1579 }
1580
1581
1582
1583 # ifdef DEAL_II_WITH_MPI
1584 # ifdef DEAL_II_TRILINOS_WITH_TPETRA
1585 template <int dim, int spacedim, typename Number, typename MemorySpace>
1586 void
1587 reinit_distributed(
1588 const DoFHandler<dim, spacedim> &dh,
1589 LinearAlgebra::TpetraWrappers::Vector<Number, MemorySpace> &vector)
1590 {
1591 const parallel::distributed::Triangulation<dim, spacedim> *parallel_tria =
1592 dynamic_cast<
1593 const parallel::distributed::Triangulation<dim, spacedim> *>(
1594 &dh.get_triangulation());
1595 Assert(parallel_tria != nullptr, ExcNotImplemented());
1596
1597 const IndexSet &locally_owned_dofs = dh.locally_owned_dofs();
1598 vector.reinit(locally_owned_dofs, parallel_tria->get_mpi_communicator());
1599 }
1600 # endif
1601
1602 template <int dim, int spacedim>
1603 void
1604 reinit_distributed(const DoFHandler<dim, spacedim> &dh,
1605 LinearAlgebra::EpetraWrappers::Vector &vector)
1606 {
1607 const parallel::distributed::Triangulation<dim, spacedim> *parallel_tria =
1608 dynamic_cast<
1609 const parallel::distributed::Triangulation<dim, spacedim> *>(
1610 &dh.get_triangulation());
1611 Assert(parallel_tria != nullptr, ExcNotImplemented());
1612
1613 const IndexSet &locally_owned_dofs = dh.locally_owned_dofs();
1614 vector.reinit(locally_owned_dofs, parallel_tria->get_mpi_communicator());
1615 }
1616 # endif
1617 #endif // DEAL_II_WITH_TRILINOS
1618
1619 template <int dim, int spacedim, typename Number>
1620 void
1621 reinit_distributed(const DoFHandler<dim, spacedim> &dh,
1622 LinearAlgebra::distributed::Vector<Number> &vector)
1623 {
1624 const parallel::distributed::Triangulation<dim, spacedim> *parallel_tria =
1625 dynamic_cast<
1626 const parallel::distributed::Triangulation<dim, spacedim> *>(
1627 &dh.get_triangulation());
1628 Assert(parallel_tria != nullptr, ExcNotImplemented());
1629
1630 const IndexSet &locally_owned_dofs = dh.locally_owned_dofs();
1631 vector.reinit(locally_owned_dofs, parallel_tria->get_mpi_communicator());
1632 }
1633
1634
1635
1636 template <typename VectorType, class DH>
1637 void
1638 reinit_ghosted(const DH & /*dh*/, VectorType & /*vector*/)
1639 {
1640 DEAL_II_NOT_IMPLEMENTED();
1641 }
1642
1643 #ifdef DEAL_II_WITH_PETSC
1644 template <int dim, int spacedim>
1645 void
1646 reinit_ghosted(const DoFHandler<dim, spacedim> &dh,
1647 PETScWrappers::MPI::Vector &vector)
1648 {
1649 const parallel::distributed::Triangulation<dim, spacedim> *parallel_tria =
1650 dynamic_cast<
1651 const parallel::distributed::Triangulation<dim, spacedim> *>(
1652 &dh.get_triangulation());
1653 Assert(parallel_tria != nullptr, ExcNotImplemented());
1654 const IndexSet &locally_owned_dofs = dh.locally_owned_dofs();
1655 const IndexSet locally_relevant_dofs =
1656 DoFTools::extract_locally_relevant_dofs(dh);
1657 vector.reinit(locally_owned_dofs,
1658 locally_relevant_dofs,
1659 parallel_tria->get_mpi_communicator());
1660 }
1661 #endif // DEAL_II_WITH_PETSC
1662
1663 #ifdef DEAL_II_WITH_TRILINOS
1664 template <int dim, int spacedim>
1665 void
1666 reinit_ghosted(const DoFHandler<dim, spacedim> &dh,
1667 TrilinosWrappers::MPI::Vector &vector)
1668 {
1669 const parallel::distributed::Triangulation<dim, spacedim> *parallel_tria =
1670 dynamic_cast<
1671 const parallel::distributed::Triangulation<dim, spacedim> *>(
1672 &dh.get_triangulation());
1673 Assert(parallel_tria != nullptr, ExcNotImplemented());
1674 const IndexSet &locally_owned_dofs = dh.locally_owned_dofs();
1675 const IndexSet locally_relevant_dofs =
1676 DoFTools::extract_locally_relevant_dofs(dh);
1677 vector.reinit(locally_owned_dofs,
1678 locally_relevant_dofs,
1679 parallel_tria->get_mpi_communicator());
1680 }
1681 #endif // DEAL_II_WITH_TRILINOS
1682
1683 template <int dim, int spacedim, typename Number>
1684 void
1685 reinit_ghosted(const DoFHandler<dim, spacedim> &dh,
1686 LinearAlgebra::distributed::Vector<Number> &vector)
1687 {
1688 const parallel::distributed::Triangulation<dim, spacedim> *parallel_tria =
1689 dynamic_cast<
1690 const parallel::distributed::Triangulation<dim, spacedim> *>(
1691 &dh.get_triangulation());
1692 Assert(parallel_tria != nullptr, ExcNotImplemented());
1693 const IndexSet &locally_owned_dofs = dh.locally_owned_dofs();
1694 const IndexSet locally_relevant_dofs =
1695 DoFTools::extract_locally_relevant_dofs(dh);
1696 vector.reinit(locally_owned_dofs,
1697 locally_relevant_dofs,
1698 parallel_tria->get_mpi_communicator());
1699 }
1700
1701
1702
1703 /**
1704 * Perform the extrapolation of a finite element field to patch-based
1705 * values for serial triangulations.
1706 */
1707 template <int dim, class InVector, class OutVector, int spacedim>
1708 void
1709 extrapolate_serial(const InVector &u3,
1710 const DoFHandler<dim, spacedim> &dof2,
1711 OutVector &u2)
1712 {
1713 const unsigned int dofs_per_cell = dof2.get_fe().n_dofs_per_cell();
1714 Vector<typename OutVector::value_type> dof_values(dofs_per_cell);
1715
1716 // Then traverse grid bottom up, excluding the finest level
1717 for (unsigned int level = 0;
1718 level < dof2.get_triangulation().n_levels() - 1;
1719 ++level)
1720 {
1721 for (const auto &cell : dof2.cell_iterators_on_level(level))
1722 if (cell->has_children())
1723 {
1724 // Check whether this cell has active children
1725 bool active_children = false;
1726 for (unsigned int child_n = 0; child_n < cell->n_children();
1727 ++child_n)
1728 if (cell->child(child_n)->is_active())
1729 {
1730 active_children = true;
1731 break;
1732 }
1733
1734 // If there are active children, this process
1735 // has to work on this cell. Get the values from the input
1736 // vector on this cell and interpolate it from the current
1737 // cell to its children in the other vector. If any of the
1738 // children have children themselves, then we will visit it
1739 // later in the outer loop here and overwrite the results in
1740 // u2.
1741 if (active_children)
1742 {
1743 cell->get_interpolated_dof_values(u3, dof_values);
1744 cell->set_dof_values_by_interpolation(dof_values, u2);
1745 }
1746 }
1747 }
1748 }
1749 } // namespace internal
1750
1751
1752
1753 template <int dim, class InVector, class OutVector, int spacedim>
1754 void
1755 extrapolate(const DoFHandler<dim, spacedim> &dof1,
1756 const InVector &u1,
1757 const DoFHandler<dim, spacedim> &dof2,
1758 OutVector &u2)
1759 {
1760 // Forward to the other function using an empty set of
1761 // constraints.
1762 AffineConstraints<typename OutVector::value_type> dummy;
1763 dummy.close();
1764 extrapolate(dof1, u1, dof2, dummy, u2);
1765 }
1766
1767
1768
1769 template <int dim, class InVector, class OutVector, int spacedim>
1770 void
1771 extrapolate(
1772 const DoFHandler<dim, spacedim> &dof1,
1773 const InVector &u1,
1774 const DoFHandler<dim, spacedim> &dof2,
1775 const AffineConstraints<typename OutVector::value_type> &constraints,
1776 OutVector &u2)
1777 {
1778 Assert(dof1.get_fe_collection().size() == 1, ExcNotImplemented());
1779 Assert(dof2.get_fe_collection().size() == 1, ExcNotImplemented());
1780
1781 Assert(dof1.get_fe(0).n_components() == dof2.get_fe(0).n_components(),
1782 ExcDimensionMismatch(dof1.get_fe(0).n_components(),
1783 dof2.get_fe(0).n_components()));
1784 Assert(&dof1.get_triangulation() == &dof2.get_triangulation(),
1785 ExcTriangulationMismatch());
1786 Assert(u1.size() == dof1.n_dofs(),
1787 ExcDimensionMismatch(u1.size(), dof1.n_dofs()));
1788 Assert(u2.size() == dof2.n_dofs(),
1789 ExcDimensionMismatch(u2.size(), dof2.n_dofs()));
1790
1791 // make sure that each cell on the coarsest level is at least once refined,
1792 // otherwise, these cells can't be treated and would generate a bogus result
1793 for (const auto &cell : dof2.cell_iterators_on_level(0))
1794 {
1795 (void)cell;
1796 Assert(cell->has_children() || cell->is_artificial(),
1797 ExcGridNotRefinedAtLeastOnce());
1798 }
1799
1800
1801 internal::BlockType<OutVector> u3;
1802 internal::reinit_distributed(dof2, u3);
1803 if (dynamic_cast<const parallel::distributed::Triangulation<dim, spacedim>
1804 *>(&dof2.get_triangulation()) != nullptr)
1805 {
1806 Assert(dof1.get_fe(0).reference_cell() ==
1807 ReferenceCells::get_hypercube<dim>(),
1808 ExcNotImplemented());
1809 Assert(dof2.get_fe(0).reference_cell() ==
1810 ReferenceCells::get_hypercube<dim>(),
1811 ExcNotImplemented());
1812
1813 interpolate(dof1, u1, dof2, constraints, u3);
1814
1815 internal::BlockType<OutVector> u3_relevant;
1816 internal::reinit_ghosted(dof2, u3_relevant);
1817 u3_relevant = u3;
1818
1819 internal::ExtrapolateImplementation<dim, spacedim, OutVector>
1820 implementation;
1821 implementation.extrapolate_parallel(u3_relevant, dof2, u2);
1822 }
1823 else
1824 {
1825 interpolate(dof1, u1, dof2, constraints, u3);
1826
1827 internal::extrapolate_serial(u3, dof2, u2);
1828 }
1829
1830 constraints.distribute(u2);
1831 }
1832 } // end of namespace FETools
1833
1834 DEAL_II_NAMESPACE_CLOSE
1835
1836 #endif