Debian Codegraph @

include/deal.II/grid/tria_description.h

raw
1 // ------------------------------------------------------------------------
2 //
3 // SPDX-License-Identifier: LGPL-2.1-or-later
4 // Copyright (C) 2020 - 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_grid_tria_description_h
16 #define dealii_grid_tria_description_h
17
18 #include <deal.II/base/config.h>
19
20 #include <deal.II/base/memory_space.h>
21 #include <deal.II/base/mpi_stub.h>
22
23 #include <deal.II/grid/cell_data.h>
24 #include <deal.II/grid/cell_id.h>
25 #include <deal.II/grid/reference_cell.h>
26 #include <deal.II/grid/tria.h>
27
28
29 DEAL_II_NAMESPACE_OPEN
30 #ifndef DOXYGEN
31 namespace LinearAlgebra
32 {
33 namespace distributed
34 {
35 template <typename Number, typename MemorySpace>
36 class Vector;
37 }
38 } // namespace LinearAlgebra
39 #endif
40
41 /*------------------------------------------------------------------------*/
42
43
44 /**
45 * A namespace dedicated to the struct Description, which can be used in
46 * one of the overloads of Triangulation::create_triangulation(). All
47 * triangulations in deal.II are, in one way or the other, created by
48 * calling Triangulation::create_triangulation(); for example, all of the
49 * functions in class GridIn and namespace GridGenerator call these
50 * functions. Most of these call the overload that takes a vector of
51 * vertices plus a vector of CellData objects that describe which vertices
52 * form each cell (along with some other information). But there are other
53 * overloads of Triangulation::create_triangulation() that require more
54 * elaborate descriptions of triangulations, and these typically use an
55 * object of type TriangulationDescription::Description declared in this
56 * namespace.
57 */
58 namespace TriangulationDescription
59 {
60 /**
61 * Configuration flags for Triangulation objects.
62 * Settings can be combined using bitwise OR.
63 */
64 enum Settings
65 {
66 /**
67 * Default settings, other options are disabled.
68 */
69 default_setting = 0x0,
70 /**
71 * This flag needs to be set to use the geometric multigrid
72 * functionality. This option requires additional computation and
73 * communication.
74 */
75 construct_multigrid_hierarchy = 0x1
76 };
77
78 /**
79 * This class stores information needed for creating a locally relevant
80 * cell when calling the overload of Triangulation::create_triangulation()
81 * that takes an object of type TriangulationDescription::Description.
82 * Objects of the current type are stored in Description. In contrast to
83 * the dealii::CellData class, the current class also stores information
84 * relevant for the parallel partitioning of a triangulation, such as
85 * a global cell id, the subdomain_id, and the level_subdomain_id as well as
86 * information related to manifold_id and boundary_id.
87 *
88 * In contrast to dealii::CellData, it does not store geometric information
89 * such as vertex locations. This information is only needed on the coarsest
90 * level of a triangulation (whereas the current structure is also used for
91 * refined levels of a triangulation) and is stored separately by
92 * the Description class.
93 */
94 template <int dim>
95 struct CellData
96 {
97 /**
98 * Constructor
99 */
100 CellData();
101
102 /**
103 * Read or write the data of this object to or from a stream for the
104 * purpose of serialization using the [BOOST serialization
105 * library](https://www.boost.org/doc/libs/1_74_0/libs/serialization/doc/index.html).
106 */
107 template <class Archive>
108 void
109 serialize(Archive &ar, const unsigned int /*version*/);
110
111 /**
112 * Comparison operator.
113 */
114 bool
115 operator==(const CellData<dim> &other) const;
116
117 /**
118 * Unique CellID of the cell.
119 */
120 CellId::binary_type id;
121
122 /**
123 * subdomain_id of the cell.
124 */
125 types::subdomain_id subdomain_id;
126
127 /**
128 * level_subdomain_id of the cell.
129 */
130 types::subdomain_id level_subdomain_id;
131
132 /**
133 * Manifold id of the cell.
134 */
135 types::manifold_id manifold_id;
136
137 /**
138 * Manifold id of all lines of the cell.
139 *
140 * @note Only used for 2d and 3d.
141 */
142 std::array<types::manifold_id, GeometryInfo<dim>::lines_per_cell>
143 manifold_line_ids;
144
145 /**
146 * Manifold id of all face quads of the cell.
147 *
148 * @note Only used for 3d.
149 */
150 std::array<types::manifold_id,
151 dim == 1 ? 1 : GeometryInfo<3>::quads_per_cell>
152 manifold_quad_ids;
153
154 /**
155 * List of face number and boundary id of all non-internal faces of the
156 * cell.
157 */
158 std::vector<std::pair<unsigned int, types::boundary_id>> boundary_ids;
159 };
160
161
162 /**
163 * Data used in the Triangulation::create_triangulation() overloads that
164 * builds a triangulation out of objects of the current type. The contents
165 * of this kind of object are typically creates by functions such as
166 * TriangulationDescription::Utilities::create_description_from_triangulation().
167 */
168 template <int dim, int spacedim = dim>
169 struct Description
170 {
171 /**
172 * Constructor.
173 */
174 Description();
175
176 /**
177 * Read or write the data of this object to or from a stream for the
178 * purpose of serialization using the [BOOST serialization
179 * library](https://www.boost.org/doc/libs/1_74_0/libs/serialization/doc/index.html).
180 */
181 template <class Archive>
182 void
183 serialize(Archive &ar, const unsigned int /*version*/);
184
185 /**
186 * Comparison operator.
187 */
188 bool
189 operator==(const Description<dim, spacedim> &other) const;
190
191 /**
192 * Cells of the locally-relevant coarse-grid triangulation.
193 */
194 std::vector<dealii::CellData<dim>> coarse_cells;
195
196 /**
197 * Vertices of the locally-relevant coarse-grid triangulation.
198 */
199 std::vector<Point<spacedim>> coarse_cell_vertices;
200
201 /**
202 * List that for each locally-relevant coarse cell provides the
203 * corresponding global
204 * @ref GlossCoarseCellId.
205 */
206 std::vector<types::coarse_cell_id> coarse_cell_index_to_coarse_cell_id;
207
208 /**
209 * CellData for each locally relevant cell on each level. cell_infos[i]
210 * contains the CellData for each locally relevant cell on the ith
211 * level.
212 */
213 std::vector<std::vector<CellData<dim>>> cell_infos;
214
215 /**
216 * The MPI communicator used to create this struct. It will be compared
217 * to the communicator inside of the Triangulation
218 * and an assert is thrown if they do not match.
219 *
220 * @note Please note this is necessary since the communicator inside of
221 * parallel::TriangulationBase is const and cannot be changed after the
222 * constructor has been called.
223 */
224 MPI_Comm comm;
225
226 /**
227 * Properties to be use in the construction of the triangulation.
228 */
229 Settings settings;
230
231 /**
232 * Mesh smoothing type.
233 */
234 typename Triangulation<dim, spacedim>::MeshSmoothing smoothing;
235 };
236
237
238 /**
239 * A namespace for TriangulationDescription::Description utility functions.
240 */
241 namespace Utilities
242 {
243 /**
244 * Construct a TriangulationDescription::Description object that for the
245 * current process, using a given triangulation `tria` describes how
246 * one can re-create a partitioned triangulation (such as a
247 * parallel::fullydistributed::Triangulation).
248 * The input triangulation can be either
249 * a serial triangulation of type dealii::Triangulation which has been
250 * colored (i.e., for which the subdomain_id and/or level_subdomain_id have
251 * been set to create partitions), or a distributed triangulation of type
252 * dealii::parallel::distributed::Triangulation, where the output of
253 * this function takes over the existing partitioning unaltered.
254 *
255 * An example for a serial Triangulation looks like this:
256 * @code
257 * Triangulation<dim, spacedim> tria_base;
258 *
259 * // Create a serial triangulation (here by reading an external mesh):
260 * GridIn<dim, spacedim> grid_in;
261 * grid_in.attach_triangulation(tria_base);
262 * grid_in.read(file_name);
263 *
264 * // Partition serial triangulation:
265 * GridTools::partition_triangulation(
266 * Utilities::MPI::n_mpi_processes(comm), tria_base);
267 *
268 * // Create building blocks:
269 * const TriangulationDescription::Description<dim, spacedim> description =
270 * TriangulationDescription::Utilities::
271 * create_description_from_triangulation(tria_base, comm);
272 *
273 * // Create a fully distributed triangulation:
274 * parallel::fullydistributed::Triangulation<dim, spacedim> tria_pft(comm);
275 * tria_pft.create_triangulation(description);
276 * @endcode
277 * In this example, *all* processes in a parallel universe read the same
278 * mesh, and partition it in the same way based on the subdomain ids set
279 * by GridTools::partition_triangulation(). Then, on each process,
280 * the current function creates building blocks that extract information
281 * about those cells whose subdomain ids match the current process's
282 * rank (plus perhaps other necessary information), and in a last step,
283 * we create a fully distributed triangulation out of these building blocks.
284 *
285 * In contrast, when starting with a parallel::distributed::Triangulation
286 * object, partitioning can be skipped, since the triangulation has already
287 * been partitioned and the corresponding code looks as follows:
288 * @code
289 * parallel::distributed::Triangulation<dim, spacedim> tria_base(comm);
290 *
291 * // Create a triangulation (not shown, see for example step-40)
292 * ...
293 *
294 * // Create building blocks:
295 * const TriangulationDescription::Description<dim, spacedim> description =
296 * TriangulationDescription::Utilities::
297 * create_description_from_triangulation(tria_base, comm);
298 *
299 * // Create a fully distributed triangulation:
300 * parallel::fullydistributed::Triangulation<dim, spacedim> tria_pft(comm);
301 * tria_pft.create_triangulation(description);
302 * @endcode
303 * This code therefore takes a dealii::parallel::distributed::Triangulation
304 * object (such as the ones used, for example, in step-40 and many other
305 * tutorial programs) and converts it into a
306 * dealii::parallel::fullydistributed::Triangulation.
307 *
308 * @param[in] tria The input triangulation. This function uses the
309 * partitioning provided by either explicitly setting subdomain_ids (if the
310 * triangulation is sequential) or based on how the existing triangulation
311 * is already distributed to different processes.
312 * @param[in] comm The MPI communicator to be used. If the input
313 * triangulation is parallel, then the communicators have to match.
314 * @param[in] settings See the description of the Settings enumerator.
315 * @param[in] my_rank_in Construct Description for the specified rank. This
316 * parameter can only be set for serial input triangulations that have
317 * been partitioned by functions like GridTools::partition_triangulation().
318 * For parallel input triangulations, `my_rank_in` needs to equal to the
319 * default value, or to the rank of the current process within the given
320 * communicator.
321 * @return The Description object that can then be used to set up a
322 * dealii::parallel::fullydistributed::Triangulation.
323 *
324 * @note If `construct_multigrid_hierarchy` is set in the @p settings, then
325 * the input triangulation has to be set up with
326 * `limit_level_difference_at_vertices` among the triangulation's
327 * smoothing flags provided to the triangulation constructor.
328 */
329 template <int dim, int spacedim = dim>
330 Description<dim, spacedim>
331 create_description_from_triangulation(
332 const dealii::Triangulation<dim, spacedim> &tria,
333 const MPI_Comm comm,
334 const TriangulationDescription::Settings settings =
335 TriangulationDescription::Settings::default_setting,
336 const unsigned int my_rank_in = numbers::invalid_unsigned_int);
337
338 /**
339 * Similar to the above function but the desired owners of active cells are
340 * not provided via the subdomain_ids of cells, but rather by the
341 * corresponding values of a cell vector (see also
342 * parallel::TriangulationBase::global_active_cell_index_partitioner() and
343 * CellAccessor::global_active_cell_index()). This function allows
344 * repartitioning Triangulation objects that are already distributed and
345 * that may be partitioned differently than the desired partitioning.
346 *
347 * If the setup of multigrid levels is requested by the @p settings argument,
348 * they are partitioned according to a first-child policy. In other words,
349 * a process owns a (non-active) cell if it owns its first child. If that
350 * first child is not active itself, the policy is applied recursively.
351 *
352 * The partitioning of cells is determined based on the elements of the
353 * `partition` vector. While that vector stores elements of type `double`,
354 * actual values must be integers and be within the range of process
355 * ranks of the relevant communicator.
356 *
357 * @note The communicator is extracted from the vector @p partition.
358 *
359 * @note The triangulation @p tria can be set up on a subcommunicator of the
360 * communicator of @p partitioner. All processes that are not part of that
361 * subcommunicator need to set up the local triangulation with the
362 * special-purpose communicator MPI_COMM_NULL.
363 *
364 * @note The multigrid levels are currently not constructed, since
365 * @p partition only describes the partitioning of the active level.
366 */
367 template <int dim, int spacedim>
368 Description<dim, spacedim>
369 create_description_from_triangulation(
370 const Triangulation<dim, spacedim> &tria,
371 const LinearAlgebra::distributed::Vector<double, MemorySpace::Host>
372 &partition,
373 const TriangulationDescription::Settings settings =
374 TriangulationDescription::Settings::default_setting);
375
376 /**
377 * Similar to the above function but allowing the user to prescribe the
378 * partitioning of the multigrid levels. As with the other function,
379 * while both the global and level-wise partition vectors store elements
380 * with data type `double`, actual elements must be integers and equal
381 * possible process ranks within the relevant communicator.
382 */
383 template <int dim, int spacedim>
384 Description<dim, spacedim>
385 create_description_from_triangulation(
386 const Triangulation<dim, spacedim> &tria,
387 const LinearAlgebra::distributed::Vector<double, MemorySpace::Host>
388 &partition,
389 const std::vector<
390 LinearAlgebra::distributed::Vector<double, MemorySpace::Host>>
391 &mg_partitions,
392 const TriangulationDescription::Settings settings =
393 TriangulationDescription::Settings::default_setting);
394
395 /**
396 * Construct a TriangulationDescription::Description. In contrast
397 * to the function above, this function is also responsible for creating
398 * a serial triangulation and for its partitioning (by calling the
399 * provided `std::function` objects). Internally only selected processes
400 * (every n-th/each root of a group of size `group_size`) create a serial
401 * triangulation and the TriangulationDescription::Description for all
402 * processes in its group, which is then communicated.
403 *
404 * This function can also be used to read an external mesh only once (by
405 * the root process), by setting `group_size` to the number of MPI ranks
406 * and therefore creating a single group. The following
407 * code snippet shows a modified version of the example provided in the
408 * documentation of create_description_from_triangulation().
409 * Function calls that only need to be performed by the root process
410 * (read and partition mesh) have been moved into `std::function` objects.
411 *
412 * @code
413 * // create and partition serial triangulation and create description
414 * const TriangulationDescription::Description<dim, spacedim> description =
415 * TriangulationDescription::Utilities::
416 * create_description_from_triangulation_in_groups<dim, spacedim>(
417 * [file_name](auto &tria_base) {
418 * GridIn<dim, spacedim> grid_in;
419 * grid_in.attach_triangulation(tria_base);
420 * grid_in.read(file_name);
421 * },
422 * [](auto &tria_base, const auto comm, const auto group_size) {
423 * GridTools::partition_triangulation(
424 * Utilities::MPI::n_mpi_processes(comm), tria_base);
425 * },
426 * comm,
427 * Utilities::MPI::n_mpi_processes(comm));
428 *
429 * // create triangulation
430 * parallel::fullydistributed::Triangulation<dim, spacedim> tria_pft(comm);
431 * tria_pft.create_triangulation(description);
432 * @endcode
433 *
434 * @note A reasonable group size is the size of a NUMA domain or the
435 * size of a compute node.
436 *
437 * @param serial_grid_generator A function which creates a serial triangulation.
438 * @param serial_grid_partitioner A function which can partition a serial
439 * triangulation, i.e., sets the sudomain_ids of the active cells.
440 * The function takes as the first argument a serial triangulation,
441 * as the second argument the MPI communicator, and as the third
442 * argument the group size.
443 * @param comm MPI communicator.
444 * @param group_size The size of each group.
445 * @param smoothing Mesh smoothing type.
446 * @param setting See the description of the Settings enumerator.
447 * @return Description to be used to set up a Triangulation.
448 *
449 * @note If construct_multigrid_hierarchy is set in the settings, the
450 * @p smoothing parameter is extended with the
451 * limit_level_difference_at_vertices flag.
452 */
453 template <int dim, int spacedim = dim>
454 Description<dim, spacedim>
455 create_description_from_triangulation_in_groups(
456 const std::function<void(dealii::Triangulation<dim, spacedim> &)>
457 &serial_grid_generator,
458 const std::function<void(dealii::Triangulation<dim, spacedim> &,
459 const MPI_Comm,
460 const unsigned int)> &serial_grid_partitioner,
461 const MPI_Comm comm,
462 const int group_size = 1,
463 const typename Triangulation<dim, spacedim>::MeshSmoothing smoothing =
464 dealii::Triangulation<dim, spacedim>::none,
465 const TriangulationDescription::Settings setting =
466 TriangulationDescription::Settings::default_setting);
467
468 } // namespace Utilities
469
470
471
472 template <int dim>
473 CellData<dim>::CellData()
474 : subdomain_id(numbers::invalid_subdomain_id)
475 , level_subdomain_id(numbers::invalid_subdomain_id)
476 , manifold_id(numbers::flat_manifold_id)
477 {
478 std::fill(id.begin(), id.end(), numbers::invalid_unsigned_int);
479 std::fill(manifold_line_ids.begin(),
480 manifold_line_ids.end(),
481 numbers::flat_manifold_id);
482 std::fill(manifold_quad_ids.begin(),
483 manifold_quad_ids.end(),
484 numbers::flat_manifold_id);
485 }
486
487
488
489 template <int dim>
490 template <class Archive>
491 void
492 CellData<dim>::serialize(Archive &ar, const unsigned int /*version*/)
493 {
494 ar &id;
495 ar &subdomain_id;
496 ar &level_subdomain_id;
497 ar &manifold_id;
498 if (dim >= 2)
499 ar &manifold_line_ids;
500 if (dim >= 3)
501 ar &manifold_quad_ids;
502 ar &boundary_ids;
503 }
504
505
506
507 template <int dim, int spacedim>
508 Description<dim, spacedim>::Description()
509 : comm(MPI_COMM_NULL)
510 , settings(Settings::default_setting)
511 , smoothing(Triangulation<dim, spacedim>::MeshSmoothing::none)
512 {}
513
514
515
516 template <int dim, int spacedim>
517 template <class Archive>
518 void
519 Description<dim, spacedim>::serialize(Archive &ar,
520 const unsigned int /*version*/)
521 {
522 ar &coarse_cells;
523 ar &coarse_cell_vertices;
524 ar &coarse_cell_index_to_coarse_cell_id;
525 ar &cell_infos;
526 ar &settings;
527 ar &smoothing;
528 }
529
530
531
532 template <int dim>
533 bool
534 CellData<dim>::operator==(const CellData<dim> &other) const
535 {
536 if (this->id != other.id)
537 return false;
538 if (this->subdomain_id != other.subdomain_id)
539 return false;
540 if (this->level_subdomain_id != other.level_subdomain_id)
541 return false;
542 if (this->manifold_id != other.manifold_id)
543 return false;
544 if (dim >= 2 && this->manifold_line_ids != other.manifold_line_ids)
545 return false;
546 if (dim >= 3 && this->manifold_quad_ids != other.manifold_quad_ids)
547 return false;
548 if (this->boundary_ids != other.boundary_ids)
549 return false;
550
551 return true;
552 }
553
554
555
556 template <int dim, int spacedim>
557 bool
558 Description<dim, spacedim>::operator==(
559 const Description<dim, spacedim> &other) const
560 {
561 if (this->coarse_cells != other.coarse_cells)
562 return false;
563 if (this->coarse_cell_vertices != other.coarse_cell_vertices)
564 return false;
565 if (this->coarse_cell_index_to_coarse_cell_id !=
566 other.coarse_cell_index_to_coarse_cell_id)
567 return false;
568 if (this->cell_infos != other.cell_infos)
569 return false;
570 if (this->settings != other.settings)
571 return false;
572 if (this->smoothing != other.smoothing)
573 return false;
574
575 return true;
576 }
577 } // namespace TriangulationDescription
578
579
580 DEAL_II_NAMESPACE_CLOSE
581
582 #endif