Debian Codegraph @

include/deal.II/distributed/tria.h

raw
1 // ------------------------------------------------------------------------
2 //
3 // SPDX-License-Identifier: LGPL-2.1-or-later
4 // Copyright (C) 2010 - 2024 by the deal.II authors
5 //
6 // This file is part of the deal.II library.
7 //
8 // Part of the source code is dual licensed under Apache-2.0 WITH
9 // LLVM-exception OR LGPL-2.1-or-later. Detailed license information
10 // governing the source code and code contributions can be found in
11 // LICENSE.md and CONTRIBUTING.md at the top level directory of deal.II.
12 //
13 // ------------------------------------------------------------------------
14
15 #ifndef dealii_distributed_tria_h
16 #define dealii_distributed_tria_h
17
18
19 #include <deal.II/base/config.h>
20
21 #include <deal.II/base/enable_observer_pointer.h>
22 #include <deal.II/base/mpi_stub.h>
23 #include <deal.II/base/observer_pointer.h>
24 #include <deal.II/base/template_constraints.h>
25
26 #include <deal.II/distributed/p4est_wrappers.h>
27 #include <deal.II/distributed/tria_base.h>
28
29 #include <deal.II/grid/tria.h>
30
31 #include <boost/range/iterator_range.hpp>
32
33 #include <functional>
34 #include <list>
35 #include <set>
36 #include <type_traits>
37 #include <utility>
38 #include <vector>
39
40 #ifdef DEAL_II_WITH_P4EST
41 # include <p4est.h>
42 # include <p4est_connectivity.h>
43 # include <p4est_ghost.h>
44 # include <p8est.h>
45 # include <p8est_connectivity.h>
46 # include <p8est_ghost.h>
47 #endif
48
49 DEAL_II_NAMESPACE_OPEN
50
51 // Forward declarations
52 #ifndef DOXYGEN
53
54 namespace FETools
55 {
56 namespace internal
57 {
58 template <int, int, class>
59 class ExtrapolateImplementation;
60 }
61 } // namespace FETools
62
63 // forward declaration of the data type for periodic face pairs
64 namespace GridTools
65 {
66 template <typename CellIterator>
67 struct PeriodicFacePair;
68 }
69
70 namespace parallel
71 {
72 namespace distributed
73 {
74 template <int, int>
75 class TemporarilyMatchRefineFlags;
76 }
77 } // namespace parallel
78
79 namespace internal
80 {
81 namespace parallel
82 {
83 namespace distributed
84 {
85 namespace TriangulationImplementation
86 {
87 template <int dim, int spacedim>
88 void
89 exchange_refinement_flags(
90 dealii::parallel::distributed::Triangulation<dim, spacedim> &);
91 }
92 } // namespace distributed
93 } // namespace parallel
94 } // namespace internal
95 #endif
96
97
98
99 #ifdef DEAL_II_WITH_P4EST
100
101 namespace parallel
102 {
103 namespace distributed
104 {
105 /**
106 * This class acts like the dealii::Triangulation class, but it
107 * distributes the mesh across a number of different processors when using
108 * MPI. The class's interface does not add a lot to the
109 * dealii::Triangulation class but there are a number of difficult
110 * algorithms under the hood that ensure we always have a load-balanced,
111 * fully distributed mesh. Use of this class is explained in step-40,
112 * step-32, the
113 * @ref distributed
114 * documentation topic, as well as the
115 * @ref distributed_paper.
116 * See there for more information. This class satisfies the
117 * @ref ConceptMeshType "MeshType concept".
118 *
119 * @note This class does not support anisotropic refinement, because it
120 * relies on the p4est library that does not support this. Attempts to
121 * refine cells anisotropically will result in errors.
122 *
123 * @note There is currently no support for distributing 1d triangulations.
124 *
125 *
126 * <h3> Interaction with boundary description </h3>
127 *
128 * Refining and coarsening a distributed triangulation is a complicated
129 * process because cells may have to be migrated from one processor to
130 * another. On a single processor, materializing that part of the global
131 * mesh that we want to store here from what we have stored before
132 * therefore may involve several cycles of refining and coarsening the
133 * locally stored set of cells until we have finally gotten from the
134 * previous to the next triangulation. This process is described in more
135 * detail in the
136 * @ref distributed_paper.
137 * Unfortunately, in this process, some information can get lost relating
138 * to flags that are set by user code and that are inherited from parent
139 * to child cell but that are not moved along with a cell if that cell is
140 * migrated from one processor to another.
141 *
142 * An example are boundary indicators. Assume, for example, that you start
143 * with a single cell that is refined once globally, yielding four
144 * children. If you have four processors, each one owns one cell. Assume
145 * now that process 1 sets the boundary indicators of the external
146 * boundaries of the cell it owns to 42, using code such as this that
147 * is run right after creating the mesh:
148 * @code
149 * for (const auto &cell : triangulation.active_cell_iterators())
150 * if (cell->is_locally_owned())
151 * for (const auto &face : cell->face_iterators())
152 * face->set_boundary_id(42);
153 * @endcode
154 * On the other hand, process 0 does not own this cell (but has it as one
155 * of its ghost cells). Consequently, on process 0, executing the code above
156 * sets the boundary id of the cells the process owns, but not on the ghost
157 * cell and in particular not if the cell is just an artificial cell on that
158 * process (which in that case may not even correspond to an active cell
159 * on any other process). Now, assume we do several mesh refinement cycles
160 * and end up with a configuration where process 0 suddenly finds itself as
161 * the owner of this cell that was previously owned by process 1. If
162 * boundary indicator 42 means that we need
163 * to integrate Neumann boundary conditions along this boundary, then
164 * processor 0 will forget to do so because it has never set the boundary
165 * indicator along this cell's boundary to 42.
166 *
167 * The way to avoid this dilemma is through one of two ways. The easier one
168 * is if you can set boundary ids and materials ids already correctly on
169 * the *coarse* mesh because a parallel::distributed::Triangulation keeps
170 * the entire coarse mesh around for its entire life time. In other words,
171 * if you can set boundary ids correctly already immediately after creating
172 * the coarse mesh (i.e., before any of its cells are ever refined), then
173 * the whole re-partitioning process will always ensure that every face
174 * inherits the boundary id from its parent which we know is already
175 * correct. This is, for example, what you would do if you had a cube domain
176 * in which each of the six faces has its own unique boundary id: You can
177 * already assign these at the very beginning, and the children will always
178 * have the right boundary id. It is important that if you want to go this
179 * way, right after creation, you assign the boundary ids for the boundary
180 * faces of *all* cells, not just the locally owned cells.
181 *
182 * In more complex cases, it is necessary to assign boundary ids later on,
183 * for example because what type a boundary face should have changes over
184 * time, changes with the solution (e.g., whether it's an inflow or outflow
185 * boundary condition), or because not all faces should have the same
186 * boundary id as their parent (say, because only part of one of the six
187 * faces of a cube should carry boundary id 42, whereas the rest should have
188 * boundary id 43; in other words, the decision must be made on a
189 * case-by-case basis on the faces of the *finest* mesh, rather than the
190 * faces of the coarse mesh). In such cases, the solution is to make sure
191 * that things like setting boundary indicators or material ids is done
192 * immediately every time a parallel triangulation is refined or
193 * partitioned. This is not necessary for sequential triangulations because,
194 * there, these flags are inherited from parent to child cell (or, for
195 * boundary ids, from parent to child face) and remain with a cell or face
196 * even if it is refined and the children are later coarsened again. But
197 * this does not hold for distributed triangulations. It is made even more
198 * difficult by the fact that in the process of refining a parallel
199 * distributed triangulation, the triangulation may call
200 * dealii::Triangulation::execute_coarsening_and_refinement multiple times
201 * and this function needs to know about boundaries. In other words, it is
202 * <i>not</i> enough to just set boundary indicators on newly created
203 * faces only <i>after</i> calling
204 * <tt>distributed::parallel::TriangulationBase::execute_coarsening_and_refinement</tt>:
205 * it actually has to happen while that function is still running.
206 *
207 * The way to do this is by writing a function that sets boundary
208 * indicators and that will be called by the dealii::Triangulation class.
209 * The triangulation does not provide a pointer to itself to the function
210 * being called, nor any other information, so the trick is to get this
211 * information into the function. C++ provides a nice mechanism for this
212 * that is best explained using an example:
213 * @code
214 * #include <functional>
215 *
216 * template <int dim>
217 * void set_boundary_ids (
218 * parallel::distributed::Triangulation<dim> &triangulation)
219 * {
220 * ... set boundary indicators on the triangulation object ...
221 * }
222 *
223 * template <int dim>
224 * void
225 * MyClass<dim>::create_coarse_mesh (
226 * parallel::distributed::Triangulation<dim> &coarse_grid) const
227 * {
228 * ... create the coarse mesh ...
229 *
230 * coarse_grid.signals.post_refinement.connect(
231 * [&coarse_grid](){
232 * set_boundary_ids<dim>(coarse_grid);
233 * });
234 * }
235 * @endcode
236 *
237 * The object passed as argument to <code>connect</code> is an object
238 * that can be called like a function with no arguments. It does so by
239 * wrapping a function that does, in fact, take an argument but this one
240 * argument is stored as a reference to the coarse grid triangulation when
241 * the lambda function is created. After each refinement step, the
242 * triangulation will then call the object so created which will in turn
243 * call <code>set_boundary_ids<dim></code> with the reference to the coarse
244 * grid as argument.
245 *
246 * This approach can be generalized. In the example above, we have used a
247 * global function that will be called. However, sometimes it is necessary
248 * that this function is in fact a member function of the class that
249 * generates the mesh, for example because it needs to access run-time
250 * parameters. This can be achieved as follows: assuming the
251 * <code>set_boundary_ids()</code> function has been declared as a
252 * (non-static, but possibly private) member function of the
253 * <code>MyClass</code> class, then the following will work:
254 * @code
255 * #include <functional>
256 *
257 * template <int dim>
258 * void
259 * MyClass<dim>::set_boundary_ids (
260 * parallel::distributed::Triangulation<dim> &triangulation) const
261 * {
262 * ... set boundary indicators on the triangulation object ...
263 * }
264 *
265 * template <int dim>
266 * void
267 * MyClass<dim>::create_coarse_mesh (
268 * parallel::distributed::Triangulation<dim> &coarse_grid) const
269 * {
270 * ... create the coarse mesh ...
271 *
272 * coarse_grid.signals.post_refinement.connect(
273 * [this, &coarse_grid]()
274 * {
275 * this->set_boundary_ids(coarse_grid);
276 * });
277 * }
278 * @endcode
279 * The lambda function above again is an object that can
280 * be called like a global function with no arguments, and this object in
281 * turn calls the current object's member function
282 * <code>set_boundary_ids</code> with a reference to the triangulation to
283 * work on. Note that
284 * because the <code>create_coarse_mesh</code> function is declared as
285 * <code>const</code>, it is necessary that the
286 * <code>set_boundary_ids</code> function is also declared
287 * <code>const</code>.
288 *
289 * <b>Note:</b>For reasons that have to do with the way the
290 * parallel::distributed::Triangulation is implemented, functions that
291 * have been attached to the post-refinement signal of the triangulation
292 * are called more than once, sometimes several times, every time the
293 * triangulation is actually refined.
294 *
295 *
296 * @ingroup distributed
297 *
298 * @dealiiConceptRequires{(concepts::is_valid_dim_spacedim<dim, spacedim>)}
299 */
300 template <int dim, int spacedim = dim>
301 DEAL_II_CXX20_REQUIRES((concepts::is_valid_dim_spacedim<dim, spacedim>))
302 class Triangulation
303 : public dealii::parallel::DistributedTriangulationBase<dim, spacedim>
304 {
305 public:
306 /**
307 * An alias that is used to identify cell iterators. The concept of
308 * iterators is discussed at length in the
309 * @ref Iterators "iterators documentation topic".
310 *
311 * The current alias identifies cells in a triangulation. You can find
312 * the exact type it refers to in the base class's own alias, but it
313 * should be TriaIterator<CellAccessor<dim,spacedim> >. The TriaIterator
314 * class works like a pointer that when you dereference it yields an
315 * object of type CellAccessor. CellAccessor is a class that identifies
316 * properties that are specific to cells in a triangulation, but it is
317 * derived (and consequently inherits) from TriaAccessor that describes
318 * what you can ask of more general objects (lines, faces, as well as
319 * cells) in a triangulation.
320 *
321 * @ingroup Iterators
322 */
323 using cell_iterator =
324 typename dealii::Triangulation<dim, spacedim>::cell_iterator;
325
326 /**
327 * An alias that is used to identify
328 * @ref GlossActive "active cell iterators".
329 * The concept of iterators is discussed at length in the
330 * @ref Iterators "iterators documentation topic".
331 *
332 * The current alias identifies active cells in a triangulation. You
333 * can find the exact type it refers to in the base class's own alias,
334 * but it should be TriaActiveIterator<CellAccessor<dim,spacedim> >. The
335 * TriaActiveIterator class works like a pointer to active objects that
336 * when you dereference it yields an object of type CellAccessor.
337 * CellAccessor is a class that identifies properties that are specific
338 * to cells in a triangulation, but it is derived (and consequently
339 * inherits) from TriaAccessor that describes what you can ask of more
340 * general objects (lines, faces, as well as cells) in a triangulation.
341 *
342 * @ingroup Iterators
343 */
344 using active_cell_iterator =
345 typename dealii::Triangulation<dim, spacedim>::active_cell_iterator;
346
347 /**
348 * Configuration flags for distributed Triangulations to be set in the
349 * constructor. Settings can be combined using bitwise OR.
350 */
351 enum Settings
352 {
353 /**
354 * Default settings, other options are disabled.
355 */
356 default_setting = 0x0,
357 /**
358 * If set, the deal.II mesh will be reconstructed from the coarse mesh
359 * every time a repartitioning in p4est happens. This can be a bit more
360 * expensive, but guarantees the same memory layout and therefore cell
361 * ordering in the deal.II mesh. As assembly is done in the deal.II
362 * cell ordering, this flag is required to get reproducible behavior
363 * after snapshot/resume.
364 */
365 mesh_reconstruction_after_repartitioning = 0x1,
366 /**
367 * This flags needs to be set to use the geometric multigrid
368 * functionality. This option requires additional computation and
369 * communication.
370 */
371 construct_multigrid_hierarchy = 0x2,
372 /**
373 * Setting this flag will disable automatic repartitioning of the cells
374 * after a refinement cycle. It can be executed manually by calling
375 * repartition().
376 */
377 no_automatic_repartitioning = 0x4,
378 /**
379 * Setting this flag will communicate vertices to p4est. This way one
380 * can use the 'find_point_owner_rank()' to find the MPI rank of the
381 * active cell that owns an arbitrary point in case all attached
382 * manifolds are flat.
383 */
384 communicate_vertices_to_p4est = 0x8
385 };
386
387
388
389 /**
390 * Constructor.
391 *
392 * @param mpi_communicator The MPI communicator to be used for
393 * the triangulation.
394 *
395 * @param smooth_grid Degree and kind of mesh smoothing to be applied to
396 * the mesh. See the dealii::Triangulation class for a description of
397 * the kinds of smoothing operations that can be applied.
398 *
399 * @param settings See the description of the Settings enumerator.
400 * Providing <code>construct_multigrid_hierarchy</code> enforces
401 * <code>Triangulation::limit_level_difference_at_vertices</code>
402 * for smooth_grid.
403 *
404 * @note This class does not currently support the
405 * <code>check_for_distorted_cells</code> argument provided by the base
406 * class.
407 *
408 * @note While it is possible to pass all of the mesh smoothing flags
409 * listed in the base class to objects of this type, it is not always
410 * possible to honor all of these smoothing options if they would
411 * require knowledge of refinement/coarsening flags on cells not locally
412 * owned by this processor. As a consequence, for some of these flags,
413 * the ultimate number of cells of the parallel triangulation may depend
414 * on the number of processors into which it is partitioned. On the
415 * other hand, if no smoothing flags are passed, if you always mark the
416 * same cells of the mesh, you will always get the exact same refined
417 * mesh independent of the number of processors into which the
418 * triangulation is partitioned.
419 */
420 explicit Triangulation(
421 const MPI_Comm mpi_communicator,
422 const typename dealii::Triangulation<dim, spacedim>::MeshSmoothing
423 smooth_grid = (dealii::Triangulation<dim, spacedim>::none),
424 const Settings settings = default_setting);
425
426 /**
427 * Destructor.
428 */
429 virtual ~Triangulation() override;
430
431 /**
432 * Reset this triangulation into an empty state by deleting all data.
433 *
434 * Note that this operation is only allowed if no subscriptions to this
435 * object exist any more, such as DoFHandler objects using it.
436 */
437 virtual void
438 clear() override;
439
440 /**
441 * Return if multilevel hierarchy is supported and has been constructed.
442 */
443 bool
444 is_multilevel_hierarchy_constructed() const override;
445
446 /**
447 * Return if vertices will be communicated to p4est.
448 */
449 bool
450 are_vertices_communicated_to_p4est() const;
451
452 /**
453 * Transfer data across forests.
454 *
455 * Besides the actual @p parallel_forest, which has been already refined
456 * and repartitioned, this function also needs information about its
457 * previous state, i.e. the locally owned intervals in p4est's
458 * sc_array of each processor. This information needs to be memcopyied
459 * out of the old p4est object and has to be provided via the parameter
460 * @p previous_global_first_quadrant.
461 *
462 * Data has to be previously packed with
463 * DistributedTriangulationBase::DataTransfer::pack_data().
464 */
465 void
466 execute_transfer(
467 const typename dealii::internal::p4est::types<dim>::forest
468 *parallel_forest,
469 const typename dealii::internal::p4est::types<dim>::gloidx
470 *previous_global_first_quadrant);
471
472 /**
473 * Implementation of the same function as in the base class.
474 *
475 * @note This function can be used to copy a serial Triangulation to a
476 * parallel::distributed::Triangulation but only if the serial
477 * Triangulation has never been refined.
478 */
479 virtual void
480 copy_triangulation(
481 const dealii::Triangulation<dim, spacedim> &other_tria) override;
482
483 /**
484 * Create a triangulation as documented in the base class.
485 *
486 * This function also sets up the various data structures necessary to
487 * distribute a mesh across a number of processors. This will be
488 * necessary once the mesh is being refined, though we will always keep
489 * the entire coarse mesh that is generated by this function on all
490 * processors.
491 */
492 virtual void
493 create_triangulation(const std::vector<Point<spacedim>> &vertices,
494 const std::vector<CellData<dim>> &cells,
495 const SubCellData &subcelldata) override;
496
497 /**
498 * @copydoc Triangulation::create_triangulation()
499 *
500 * @note Not implemented yet.
501 */
502 virtual void
503 create_triangulation(
504 const TriangulationDescription::Description<dim, spacedim>
505 &construction_data) override;
506
507 /**
508 * Find the MPI rank of the cell that contains this point in a distributed
509 * mesh.
510 *
511 * @note This function calls `find_point_owner_rank(const std::vector<Point<dim>> &points)`
512 * (requires p4est v2.2 and higher). Please see the documentation of
513 * `find_point_owner_rank(const std::vector<Point<dim>> &points)`.
514 */
515 types::subdomain_id
516 find_point_owner_rank(const Point<dim> &p);
517
518 /**
519 * Find the MPI rank of the cells that contain the input points in a
520 * distributed mesh. If any point is not owned by any mesh cell its return
521 * value will be `numbers::invalid_subdomain_id`.
522 *
523 * @note The query points do not need to be owned locally or in the ghost layer.
524 *
525 * @note This function can only be used with p4est v2.2 and higher, flat manifolds
526 * and requires the settings flag
527 * `Settings::communicate_vertices_to_p4est` to be set.
528 *
529 * @note The algorithm is free of communication.
530 *
531 * @param[in] points a list of query points
532 * @return list of owner ranks
533 */
534 std::vector<types::subdomain_id>
535 find_point_owner_rank(const std::vector<Point<dim>> &points);
536
537 /**
538 * Coarsen and refine the mesh according to refinement and coarsening
539 * flags set.
540 *
541 * Since the current processor only has control over those cells
542 * it owns (i.e. the ones for which <code>cell-@>subdomain_id()
543 * == this-@>locally_owned_subdomain()</code>), refinement and
544 * coarsening flags are only respected for those locally owned
545 * cells. Flags set on other cells will be ignored: the decision
546 * to refine the global mesh will only be affected by flags set
547 * on locally owned cells.
548 *
549 * This is a
550 * @ref GlossCollectiveOperation "collective operation"
551 * and needs to be called by all participating MPI ranks.
552 *
553 * @note This function by default partitions the mesh in such a way that
554 * the number of cells on all processors is roughly equal. If you want
555 * to set weights for partitioning, e.g. because some cells are more
556 * expensive to compute than others, you can use the signal `weight`
557 * as documented in the dealii::Triangulation class. This function will
558 * check whether a function is connected to the signal and if so use it.
559 * If you prefer to repartition the mesh yourself at user-defined
560 * intervals only, you can create your triangulation object by passing
561 * the parallel::distributed::Triangulation::no_automatic_repartitioning
562 * flag to the constructor, which ensures that calling the current
563 * function only refines and coarsens the triangulation, but doesn't
564 * partition it. You can then call the repartition() function manually.
565 * The usage of the `weight` signal is identical in both cases, if a
566 * function is connected to the signal it will be used to balance the
567 * calculated weights, otherwise the number of cells is balanced.
568 */
569 virtual void
570 execute_coarsening_and_refinement() override;
571
572 /**
573 * Prepare the triangulation for coarsening and refinement.
574 *
575 * This function performs necessary modifications of the
576 * coarsening and refinement flags to be consistent in parallel,
577 * to conform to smoothing flags set, and to conform to 2:1
578 * hanging node constraints.
579 *
580 * This is a
581 * @ref GlossCollectiveOperation "collective operation"
582 * and needs to be called by all participating MPI ranks.
583 */
584 virtual bool
585 prepare_coarsening_and_refinement() override;
586
587 /**
588 * Manually repartition the active cells between processors. Normally
589 * this repartitioning will happen automatically when calling
590 * execute_coarsening_and_refinement() (or refine_global()) unless the
591 * @p no_automatic_repartitioning is set in the constructor. Setting the
592 * flag and then calling repartition() gives the same result.
593 *
594 * If you want to transfer data (using SolutionTransfer or manually with
595 * register_data_attach() and notify_ready_to_unpack()), you need to set
596 * it up twice: once when calling execute_coarsening_and_refinement(),
597 * which will handle coarsening and refinement but obviously won't ship
598 * any data between processors, and a second time when calling
599 * repartition(). Here, no coarsening and refinement will be done but
600 * information will be packed and shipped to different processors. In
601 * other words, you probably want to treat a call to repartition() in
602 * the same way as execute_coarsening_and_refinement() with respect to
603 * dealing with data movement (SolutionTransfer, etc.).
604 *
605 * @note If no function is connected to the `weight` signal described
606 * in the dealii::Triangulation class, this function will balance the
607 * number of cells on each processor. If one or more functions are
608 * connected, it will calculate the sum of the weights and balance the
609 * weights across processors. The only requirement on the weights is
610 * that every cell's weight is positive and that the sum over all
611 * weights on all processors can be formed using a 64-bit integer.
612 * Beyond that, it is your choice how you want to interpret the weights.
613 * A common approach is to consider the weights proportional to the cost
614 * of doing computations on a cell, e.g., by summing the time for
615 * assembly and solving. In practice, determining this cost is of course
616 * not trivial since we don't solve on isolated cells, but on the entire
617 * mesh. In such cases, one could, for example, choose the weight equal
618 * to the number of unknowns per cell (in the context of hp-finite
619 * element methods), or using a heuristic that estimates the cost on
620 * each cell depending on whether, for example, one has to run some
621 * expensive algorithm on some cells but not others (such as forming
622 * boundary integrals during the assembly only on cells that are
623 * actually at the boundary, or computing expensive nonlinear terms only
624 * on some cells but not others, e.g., in the elasto-plastic problem in
625 * step-42).
626 */
627 void
628 repartition();
629
630 /**
631 * Return the local memory consumption in bytes.
632 */
633 virtual std::size_t
634 memory_consumption() const override;
635
636 /**
637 * Return the local memory consumption contained in the p4est data
638 * structures alone. This is already contained in memory_consumption()
639 * but made available separately for debugging purposes.
640 */
641 virtual std::size_t
642 memory_consumption_p4est() const;
643
644 /**
645 * A
646 * @ref GlossCollectiveOperation "collective operation"
647 * that produces a sequence of output files with
648 * the given file base name that contain the mesh in VTK format.
649 *
650 * More than anything else, this function is useful for debugging the
651 * interface between deal.II and p4est.
652 *
653 * @note To use the function the flag
654 * `Settings::communicate_vertices_to_p4est` must be set.
655 */
656 void
657 write_mesh_vtk(const std::string &file_basename) const;
658
659 /**
660 * Produce a check sum of the triangulation. This is a collective
661 * operation and is mostly useful for debugging purposes.
662 */
663 unsigned int
664 get_checksum() const;
665
666 /**
667 * Save the mesh and associated information into a number of files
668 * that all use the provided basename as a starting prefix, plus some
669 * suffixes that indicate the specific use of that file. These files all
670 * need to be reachable from all nodes in the
671 * computation on a shared network file system. See the SolutionTransfer
672 * class on how to store solution vectors into this file. Additional
673 * cell-based data can be saved using
674 * DistributedTriangulationBase::DataTransfer::register_data_attach().
675 */
676 virtual void
677 save(const std::string &file_basename) const override;
678
679 /**
680 * Load the refinement information saved with save() back in. The mesh
681 * must contain the same coarse mesh that was used in save() before
682 * calling this function.
683 *
684 * You do not need to load with the same number of MPI processes that
685 * you saved with. Rather, if a mesh is loaded with a different number
686 * of MPI processes than used at the time of saving, the mesh is
687 * repartitioned so that the number of cells is balanced among all
688 * processes. Individual repartitioning with non-identical weights for
689 * each cell, e.g., based on the number of dofs or particles per cell,
690 * needs to be invoked manually by calling repartition() afterwards.
691 *
692 * Cell-based data that was saved with
693 * DistributedTriangulationBase::DataTransfer::register_data_attach() can
694 * be read in with
695 * DistributedTriangulationBase::DataTransfer::notify_ready_to_unpack()
696 * after calling load().
697 */
698 virtual void
699 load(const std::string &file_basename) override;
700
701 /**
702 * Load the refinement information from a given parallel forest. This
703 * forest might be obtained from the function call to
704 * parallel::distributed::Triangulation::get_p4est().
705 */
706 void
707 load(const typename dealii::internal::p4est::types<dim>::forest *forest);
708
709 /**
710 * Return a permutation vector for the order the coarse cells are handed
711 * off to p4est. For example the value of the $i$th element in this
712 * vector is the index of the deal.II coarse cell (counting from
713 * begin(0)) that corresponds to the $i$th tree managed by p4est.
714 */
715 const std::vector<types::global_dof_index> &
716 get_p4est_tree_to_coarse_cell_permutation() const;
717
718 /**
719 * Return a permutation vector for the mapping from the coarse deal
720 * cells to the p4est trees. This is the inverse of
721 * get_p4est_tree_to_coarse_cell_permutation.
722 */
723 const std::vector<types::global_dof_index> &
724 get_coarse_cell_to_p4est_tree_permutation() const;
725
726 /**
727 * This returns a pointer to the internally stored p4est object (of type
728 * p4est_t or p8est_t depending on @p dim).
729 *
730 * @warning If you modify the p4est object, internal data structures
731 * can become inconsistent.
732 */
733 const typename dealii::internal::p4est::types<dim>::forest *
734 get_p4est() const;
735
736 /**
737 * In addition to the action in the base class Triangulation, this
738 * function joins faces in the p4est forest for periodic boundary
739 * conditions. As a result, each pair of faces will differ by at most one
740 * refinement level and ghost neighbors will be available across these
741 * faces.
742 *
743 * The vector can be filled by the function
744 * GridTools::collect_periodic_faces.
745 *
746 * For more information on periodic boundary conditions see
747 * GridTools::collect_periodic_faces,
748 * DoFTools::make_periodicity_constraints and step-45.
749 *
750 * @note Before this function can be used the Triangulation has to be
751 * initialized and must not be refined. Calling this function more than
752 * once is possible, but not recommended: The function destroys and
753 * rebuilds the p4est forest each time it is called.
754 */
755 virtual void
756 add_periodicity(
757 const std::vector<dealii::GridTools::PeriodicFacePair<cell_iterator>> &)
758 override;
759
760
761 private:
762 /**
763 * store the Settings.
764 */
765 Settings settings;
766
767 /**
768 * A flag that indicates whether the triangulation has actual content.
769 */
770 bool triangulation_has_content;
771
772 /**
773 * A data structure that holds the connectivity between trees. Since
774 * each tree is rooted in a coarse grid cell, this data structure holds
775 * the connectivity between the cells of the coarse grid.
776 */
777 typename dealii::internal::p4est::types<dim>::connectivity *connectivity;
778
779 /**
780 * A data structure that holds the local part of the global
781 * triangulation.
782 */
783 typename dealii::internal::p4est::types<dim>::forest *parallel_forest;
784
785 /**
786 * A data structure that holds some information about the ghost cells of
787 * the triangulation.
788 */
789 typename dealii::internal::p4est::types<dim>::ghost *parallel_ghost;
790
791 /**
792 * Go through all p4est trees and record the relations between locally
793 * owned p4est quadrants and active deal.II cells in the private member
794 * vector local_cell_relations.
795 *
796 * The vector contains an active cell iterator for every locally owned
797 * p4est quadrant, as well as a CellStatus flag to describe their
798 * relation.
799 *
800 * The stored vector will be ordered by the occurrence of quadrants in
801 * the corresponding local sc_array of the parallel_forest. p4est requires
802 * this specific ordering for its transfer functions. Therefore, the size
803 * of this vector will be equal to the number of locally owned quadrants
804 * in the parallel_forest object.
805 *
806 * These relations will be established for example in the mesh refinement
807 * process: after adapting the parallel_forest, but before applying these
808 * changes to this triangulation, we will record how cells will change in
809 * the refinement process. With this information, we can prepare all
810 * buffers for data transfer accordingly.
811 */
812 void
813 update_cell_relations();
814
815 /**
816 * Two arrays that store which p4est tree corresponds to which coarse
817 * grid cell and vice versa. We need these arrays because p4est goes
818 * with the original order of coarse cells when it sets up its forest,
819 * and then applies the Morton ordering within each tree. But if coarse
820 * grid cells are badly ordered this may mean that individual parts of
821 * the forest stored on a local machine may be split across coarse grid
822 * cells that are not geometrically close. Consequently, we apply a
823 * hierarchical preordering according to
824 * SparsityTools::reorder_hierarchical() to ensure that the part of the
825 * forest stored by p4est is located on geometrically close coarse grid
826 * cells.
827 */
828 std::vector<types::global_dof_index>
829 coarse_cell_to_p4est_tree_permutation;
830 std::vector<types::global_dof_index>
831 p4est_tree_to_coarse_cell_permutation;
832
833 /**
834 * Return a pointer to the p4est tree that belongs to the given
835 * dealii_coarse_cell_index()
836 */
837 typename dealii::internal::p4est::types<dim>::tree *
838 init_tree(const int dealii_coarse_cell_index) const;
839
840 /**
841 * The function that computes the permutation between the two data
842 * storage schemes.
843 */
844 void
845 setup_coarse_cell_to_p4est_tree_permutation();
846
847 /**
848 * Take the contents of a newly created triangulation we are attached to
849 * and copy it to p4est data structures.
850 *
851 * This function exists in 2d and 3d variants.
852 */
853 void copy_new_triangulation_to_p4est(std::integral_constant<int, 2>);
854 void copy_new_triangulation_to_p4est(std::integral_constant<int, 3>);
855
856 /**
857 * Copy the local part of the refined forest from p4est into the
858 * attached triangulation.
859 */
860 void
861 copy_local_forest_to_triangulation();
862
863 /**
864 * Internal function notifying all registered slots to provide their
865 * weights before repartitioning occurs. Called from
866 * execute_coarsening_and_refinement() and repartition().
867 *
868 * @return A vector of unsigned integers representing the weight or
869 * computational load of every cell after the refinement/coarsening/
870 * repartition cycle. Note that the number of entries does not need to
871 * be equal to either n_active_cells() or n_locally_owned_active_cells(),
872 * because the triangulation is not updated yet. The weights are sorted
873 * in the order that p4est will encounter them while iterating over
874 * them.
875 */
876 std::vector<unsigned int>
877 get_cell_weights() const;
878
879 /**
880 * This method returns a bit vector of length tria.n_vertices()
881 * indicating the locally active vertices on a level, i.e., the vertices
882 * touched by the locally owned level cells for use in geometric
883 * multigrid (possibly including the vertices due to periodic boundary
884 * conditions) are marked by true.
885 *
886 * Used by DoFHandler::Policy::ParallelDistributed.
887 */
888 std::vector<bool>
889 mark_locally_active_vertices_on_level(const int level) const;
890
891 virtual unsigned int
892 coarse_cell_id_to_coarse_cell_index(
893 const types::coarse_cell_id coarse_cell_id) const override;
894
895 virtual types::coarse_cell_id
896 coarse_cell_index_to_coarse_cell_id(
897 const unsigned int coarse_cell_index) const override;
898
899 template <int, int, class>
900 friend class dealii::FETools::internal::ExtrapolateImplementation;
901
902 template <int, int>
903 friend class TemporarilyMatchRefineFlags;
904 };
905
906
907 /**
908 * Specialization of the general template for the 1d case. There is
909 * currently no support for distributing 1d triangulations. Consequently,
910 * all this class does is throw an exception.
911 *
912 * @dealiiConceptRequires{(concepts::is_valid_dim_spacedim<1, spacedim>)}
913 */
914 template <int spacedim>
915 DEAL_II_CXX20_REQUIRES((concepts::is_valid_dim_spacedim<1, spacedim>))
916 class Triangulation<1, spacedim>
917 : public dealii::parallel::DistributedTriangulationBase<1, spacedim>
918 {
919 public:
920 /**
921 * dummy settings
922 */
923 enum Settings
924 {
925 default_setting = 0x0,
926 mesh_reconstruction_after_repartitioning = 0x1,
927 construct_multigrid_hierarchy = 0x2,
928 no_automatic_repartitioning = 0x4,
929 communicate_vertices_to_p4est = 0x8
930 };
931
932 /**
933 * Constructor. The argument denotes the MPI communicator to be used for
934 * the triangulation.
935 */
936 Triangulation(
937 const MPI_Comm mpi_communicator,
938 const typename dealii::Triangulation<1, spacedim>::MeshSmoothing
939 smooth_grid = (dealii::Triangulation<1, spacedim>::none),
940 const Settings settings = default_setting);
941
942 /**
943 * Destructor.
944 */
945 virtual ~Triangulation() override;
946
947 /**
948 * Return a permutation vector for the order the coarse cells are
949 * handed of to p4est. For example the first element i in this vector
950 * denotes that the first cell in hierarchical ordering is the ith deal
951 * cell starting from begin(0).
952 */
953 const std::vector<types::global_dof_index> &
954 get_p4est_tree_to_coarse_cell_permutation() const;
955
956 /**
957 * This function is not implemented, but needs to be present for the
958 * compiler.
959 */
960 virtual void
961 load(const std::string &filename) override;
962
963 /**
964 * This function is not implemented, but needs to be present for the
965 * compiler.
966 */
967 virtual void
968 save(const std::string &filename) const override;
969
970 /**
971 * This function is not implemented, but needs to be present for the
972 * compiler.
973 */
974 virtual bool
975 is_multilevel_hierarchy_constructed() const override;
976
977 /**
978 * This function is not implemented, but needs to be present for the
979 * compiler.
980 */
981 bool
982 are_vertices_communicated_to_p4est() const;
983
984 /**
985 * This function is not implemented, but needs to be present for the
986 * compiler.
987 */
988 void
989 update_cell_relations();
990
991 /**
992 * Dummy arrays. This class isn't usable but the compiler wants to see
993 * these variables at a couple places anyway.
994 */
995 std::vector<types::global_dof_index>
996 coarse_cell_to_p4est_tree_permutation;
997 std::vector<types::global_dof_index>
998 p4est_tree_to_coarse_cell_permutation;
999
1000 /**
1001 * This method, which is only implemented for dim = 2 or 3,
1002 * needs a stub because it is used in dof_handler_policy.cc
1003 */
1004 virtual std::map<unsigned int, std::set<dealii::types::subdomain_id>>
1005 compute_level_vertices_with_ghost_neighbors(
1006 const unsigned int level) const;
1007
1008 /**
1009 * Like above, this method, which is only implemented for dim = 2 or 3,
1010 * needs a stub because it is used in dof_handler_policy.cc
1011 */
1012 virtual std::vector<bool>
1013 mark_locally_active_vertices_on_level(const unsigned int level) const;
1014
1015 virtual unsigned int
1016 coarse_cell_id_to_coarse_cell_index(
1017 const types::coarse_cell_id coarse_cell_id) const override;
1018
1019 virtual types::coarse_cell_id
1020 coarse_cell_index_to_coarse_cell_id(
1021 const unsigned int coarse_cell_index) const override;
1022
1023 template <int, int>
1024 friend class TemporarilyMatchRefineFlags;
1025 };
1026 } // namespace distributed
1027 } // namespace parallel
1028
1029
1030 #else // DEAL_II_WITH_P4EST
1031
1032 namespace parallel
1033 {
1034 namespace distributed
1035 {
1036 /**
1037 * Dummy class the compiler chooses for parallel distributed
1038 * triangulations if we didn't actually configure deal.II with the p4est
1039 * library. The existence of this class allows us to refer to
1040 * parallel::distributed::Triangulation objects throughout the library
1041 * even if it is disabled.
1042 *
1043 * Since the constructor of this class is deleted, no such objects
1044 * can actually be created as this would be pointless given that
1045 * p4est is not available.
1046 *
1047 * @dealiiConceptRequires{(concepts::is_valid_dim_spacedim<dim, spacedim>)}
1048 */
1049 template <int dim, int spacedim = dim>
1050 DEAL_II_CXX20_REQUIRES((concepts::is_valid_dim_spacedim<dim, spacedim>))
1051 class Triangulation
1052 : public dealii::parallel::DistributedTriangulationBase<dim, spacedim>
1053 {
1054 public:
1055 /**
1056 * Dummy settings to allow defining the deleted constructor.
1057 */
1058 enum Settings
1059 {
1060 default_setting = 0x0,
1061 mesh_reconstruction_after_repartitioning = 0x1,
1062 construct_multigrid_hierarchy = 0x2,
1063 no_automatic_repartitioning = 0x4,
1064 communicate_vertices_to_p4est = 0x8
1065 };
1066
1067 /**
1068 * Constructor. Deleted to make sure that objects of this type cannot be
1069 * constructed (see also the class documentation).
1070 */
1071 explicit Triangulation(
1072 const MPI_Comm /*mpi_communicator*/,
1073 const typename dealii::Triangulation<dim, spacedim>::MeshSmoothing
1074 /*smooth_grid*/
1075 = (dealii::Triangulation<dim, spacedim>::none),
1076 const Settings /*settings*/ = default_setting) = delete;
1077
1078 /**
1079 * Dummy replacement to allow for better error messages when compiling
1080 * this class.
1081 */
1082 virtual bool
1083 is_multilevel_hierarchy_constructed() const override
1084 {
1085 return false;
1086 }
1087
1088 /**
1089 * Dummy replacement to allow for better error messages when compiling
1090 * this class.
1091 */
1092 bool
1093 are_vertices_communicated_to_p4est() const
1094 {
1095 return false;
1096 }
1097
1098 /**
1099 * Dummy replacement to allow for better error messages when compiling
1100 * this class.
1101 */
1102 virtual void
1103 save(const std::string & /*filename*/) const override
1104 {}
1105
1106 /**
1107 * Dummy replacement to allow for better error messages when compiling
1108 * this class.
1109 */
1110 virtual void
1111 load(const std::string & /*filename*/) override
1112 {}
1113
1114 /**
1115 * Dummy replacement to allow for better error messages when compiling
1116 * this class.
1117 */
1118 void
1119 update_cell_relations()
1120 {}
1121 };
1122 } // namespace distributed
1123 } // namespace parallel
1124
1125
1126 #endif
1127
1128
1129
1130 namespace parallel
1131 {
1132 namespace distributed
1133 {
1134 /**
1135 * This class temporarily modifies the refine and coarsen flags of all
1136 * active cells to match the p4est oracle.
1137 *
1138 * The modification only happens on parallel::distributed::Triangulation
1139 * objects, and persists for the lifetime of an instantiation of this
1140 * class.
1141 *
1142 * The TemporarilyMatchRefineFlags class should only be used in
1143 * combination with the Triangulation::Signals::post_p4est_refinement
1144 * signal. At this stage, the p4est oracle already has been refined, but
1145 * the triangulation is still unchanged. After the modification, all
1146 * refine and coarsen flags describe how the triangulation will actually
1147 * be refined.
1148 *
1149 * The use of this class is demonstrated in step-75.
1150 */
1151 template <int dim, int spacedim = dim>
1152 class TemporarilyMatchRefineFlags : public EnableObserverPointer
1153 {
1154 public:
1155 /**
1156 * Constructor.
1157 *
1158 * Stores the refine and coarsen flags of all active cells if the
1159 * provided Triangulation is of type
1160 * parallel::distributed::Triangulation.
1161 *
1162 * Adjusts them to be consistent with the p4est oracle.
1163 */
1164 TemporarilyMatchRefineFlags(dealii::Triangulation<dim, spacedim> &tria);
1165
1166 /**
1167 * Destructor.
1168 *
1169 * Returns the refine and coarsen flags of all active cells on the
1170 * parallel::distributed::Triangulation into their previous state.
1171 */
1172 ~TemporarilyMatchRefineFlags();
1173
1174 private:
1175 /**
1176 * The modified parallel::distributed::Triangulation.
1177 */
1178 const ObserverPointer<
1179 dealii::parallel::distributed::Triangulation<dim, spacedim>>
1180 distributed_tria;
1181
1182 /**
1183 * A vector that temporarily stores the refine flags before they have
1184 * been modified on the parallel::distributed::Triangulation.
1185 */
1186 std::vector<bool> saved_refine_flags;
1187
1188 /**
1189 * A vector that temporarily stores the coarsen flags before they have
1190 * been modified on the parallel::distributed::Triangulation.
1191 */
1192 std::vector<bool> saved_coarsen_flags;
1193 };
1194 } // namespace distributed
1195 } // namespace parallel
1196
1197
1198 DEAL_II_NAMESPACE_CLOSE
1199
1200 #endif