Debian Codegraph @

include/deal.II/multigrid/mg_tools.h

raw
1 // ------------------------------------------------------------------------
2 //
3 // SPDX-License-Identifier: LGPL-2.1-or-later
4 // Copyright (C) 2005 - 2023 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_mg_tools_h
16 #define dealii_mg_tools_h
17
18 #include <deal.II/base/config.h>
19
20 #include <deal.II/base/index_set.h>
21
22 #include <deal.II/dofs/dof_handler.h>
23 #include <deal.II/dofs/dof_tools.h>
24
25 #include <set>
26 #include <vector>
27
28
29 DEAL_II_NAMESPACE_OPEN
30
31 // Forward declarations
32 #ifndef DOXYGEN
33 template <int dim, int spacedim>
34 DEAL_II_CXX20_REQUIRES((concepts::is_valid_dim_spacedim<dim, spacedim>))
35 class DoFHandler;
36 class MGConstrainedDoFs;
37 #endif
38
39 /**
40 * addtogroup mg
41 * @{
42 */
43
44 /**
45 * This is a collection of functions operating on, and manipulating the
46 * numbers of degrees of freedom in a multilevel triangulation. It is similar
47 * in purpose and function to the @p DoFTools namespace, but operates on
48 * levels of DoFHandler objects. See there and the documentation of the member
49 * functions for more information.
50 */
51 namespace MGTools
52 {
53 /**
54 * Compute row length vector for multilevel methods.
55 */
56 template <int dim, int spacedim>
57 void
58 compute_row_length_vector(
59 const DoFHandler<dim, spacedim> &dofs,
60 const unsigned int level,
61 std::vector<unsigned int> &row_lengths,
62 const DoFTools::Coupling flux_couplings = DoFTools::none);
63
64 /**
65 * Compute row length vector for multilevel methods with optimization for
66 * block couplings.
67 */
68 template <int dim, int spacedim>
69 void
70 compute_row_length_vector(const DoFHandler<dim, spacedim> &dofs,
71 const unsigned int level,
72 std::vector<unsigned int> &row_lengths,
73 const Table<2, DoFTools::Coupling> &couplings,
74 const Table<2, DoFTools::Coupling> &flux_couplings);
75
76 /**
77 * Write the sparsity structure of the matrix belonging to the specified @p
78 * level. The sparsity pattern is not compressed, so before creating the
79 * actual matrix you have to compress the matrix yourself, either using
80 * SparsityPattern::compress() or by copying to a SparsityPattern.
81 *
82 * The optional AffineConstraints argument allows to define constraints of
83 * the level matrices like Dirichlet boundary conditions. Note that there is
84 * need to consider hanging nodes on the typical level matrices, since only
85 * one level is considered. See DoFTools::make_sparsity_pattern() for more
86 * details about the arguments.
87 */
88 template <int dim, int spacedim, typename number = double>
89 void
90 make_sparsity_pattern(const DoFHandler<dim, spacedim> &dof_handler,
91 SparsityPatternBase &sparsity,
92 const unsigned int level,
93 const AffineConstraints<number> &constraints = {},
94 const bool keep_constrained_dofs = true);
95
96 /**
97 * Make a sparsity pattern including fluxes of discontinuous Galerkin
98 * methods.
99 * @see
100 * @ref make_sparsity_pattern
101 * and
102 * @ref DoFTools
103 */
104 template <int dim, int spacedim, typename number = double>
105 void
106 make_flux_sparsity_pattern(const DoFHandler<dim, spacedim> &dof_handler,
107 SparsityPatternBase &sparsity,
108 const unsigned int level,
109 const AffineConstraints<number> &constraints = {},
110 const bool keep_constrained_dofs = true);
111
112
113 /**
114 * Create sparsity pattern for the fluxes at refinement edges. The matrix
115 * maps a function of the fine level space @p level to the coarser space.
116 *
117 * make_flux_sparsity_pattern()
118 */
119 template <int dim, int spacedim>
120 void
121 make_flux_sparsity_pattern_edge(const DoFHandler<dim, spacedim> &dof_handler,
122 SparsityPatternBase &sparsity,
123 const unsigned int level);
124 /**
125 * This function does the same as the other with the same name, but it gets
126 * two additional coefficient matrices. A matrix entry will only be
127 * generated for two basis functions, if there is a non-zero entry linking
128 * their associated components in the coefficient matrix.
129 *
130 * There is one matrix for couplings in a cell and one for the couplings
131 * occurring in fluxes.
132 */
133 template <int dim, int spacedim>
134 void
135 make_flux_sparsity_pattern(const DoFHandler<dim, spacedim> &dof,
136 SparsityPatternBase &sparsity,
137 const unsigned int level,
138 const Table<2, DoFTools::Coupling> &int_mask,
139 const Table<2, DoFTools::Coupling> &flux_mask);
140
141 /**
142 * Create sparsity pattern for the fluxes at refinement edges. The matrix
143 * maps a function of the fine level space @p level to the coarser space.
144 * This is the version restricting the pattern to the elements actually
145 * needed.
146 *
147 * make_flux_sparsity_pattern()
148 */
149 template <int dim, int spacedim>
150 void
151 make_flux_sparsity_pattern_edge(
152 const DoFHandler<dim, spacedim> &dof_handler,
153 SparsityPatternBase &sparsity,
154 const unsigned int level,
155 const Table<2, DoFTools::Coupling> &flux_mask);
156
157
158 /**
159 * Create sparsity pattern for interface_in/out matrices used in a multigrid
160 * computation. These matrices contain an entry representing the coupling of
161 * degrees of freedom on a refinement edge to those not on the refinement edge
162 * of a certain level.
163 */
164 template <int dim, int spacedim>
165 void
166 make_interface_sparsity_pattern(const DoFHandler<dim, spacedim> &dof_handler,
167 const MGConstrainedDoFs &mg_constrained_dofs,
168 SparsityPatternBase &sparsity,
169 const unsigned int level);
170
171
172 /**
173 * Count the dofs block-wise on each level.
174 *
175 * Result is a vector containing for each level a vector containing the
176 * number of dofs for each block (access is <tt>result[level][block]</tt>).
177 */
178 template <int dim, int spacedim>
179 void
180 count_dofs_per_block(
181 const DoFHandler<dim, spacedim> &dof_handler,
182 std::vector<std::vector<types::global_dof_index>> &dofs_per_block,
183 std::vector<unsigned int> target_block = {});
184
185 /**
186 * Count the dofs component-wise on each level.
187 *
188 * Result is a vector containing for each level a vector containing the
189 * number of dofs for each component (access is
190 * <tt>result[level][component]</tt>).
191 */
192 template <int dim, int spacedim>
193 void
194 count_dofs_per_component(
195 const DoFHandler<dim, spacedim> &mg_dof,
196 std::vector<std::vector<types::global_dof_index>> &result,
197 const bool only_once = false,
198 std::vector<unsigned int> target_component = {});
199
200 /**
201 * Generate a list of those degrees of freedom at the boundary of the domain
202 * that should be eliminated from the matrix because they will be
203 * constrained by Dirichlet boundary conditions.
204 *
205 * This is the multilevel equivalent of
206 * VectorTools::interpolate_boundary_values, but since the multilevel method
207 * does not have its own right hand side, the function values returned by
208 * the function object that is part of the function_map argument are
209 * ignored.
210 *
211 * @arg <tt>boundary_indices</tt> is a vector which on return contains all
212 * indices of degrees of freedom for each level that are at the part of the
213 * boundary identified by the function_map argument. Its length has to match
214 * the number of levels in the dof handler object.
215 *
216 * Previous content in @p boundary_indices is not overwritten,
217 * but added to.
218 */
219 template <int dim, int spacedim>
220 void
221 make_boundary_list(
222 const DoFHandler<dim, spacedim> &mg_dof,
223 const std::map<types::boundary_id, const Function<spacedim> *>
224 &function_map,
225 std::vector<std::set<types::global_dof_index>> &boundary_indices,
226 const ComponentMask &component_mask = {});
227
228 /**
229 * The same function as above, but return an IndexSet rather than a
230 * std::set<unsigned int> on each level.
231 *
232 * Previous content in @p boundary_indices is not overwritten,
233 * but added to.
234 */
235 template <int dim, int spacedim>
236 void
237 make_boundary_list(const DoFHandler<dim, spacedim> &mg_dof,
238 const std::map<types::boundary_id,
239 const Function<spacedim> *> &function_map,
240 std::vector<IndexSet> &boundary_indices,
241 const ComponentMask &component_mask = {});
242
243 /**
244 * The same function as above, but return an IndexSet rather than a
245 * std::set<unsigned int> on each level and use a std::set of boundary_ids
246 * as input.
247 *
248 * Previous content in @p boundary_indices is not overwritten, but added to.
249 */
250 template <int dim, int spacedim>
251 void
252 make_boundary_list(const DoFHandler<dim, spacedim> &mg_dof,
253 const std::set<types::boundary_id> &boundary_ids,
254 std::vector<IndexSet> &boundary_indices,
255 const ComponentMask &component_mask = {});
256
257 /**
258 * For each level in a multigrid hierarchy, produce an IndexSet that
259 * indicates which of the degrees of freedom are along interfaces of this
260 * level to cells that only exist on coarser levels.
261 */
262 template <int dim, int spacedim>
263 void
264 extract_inner_interface_dofs(const DoFHandler<dim, spacedim> &mg_dof_handler,
265 std::vector<IndexSet> &interface_dofs);
266
267 /**
268 * Return the highest possible level that can be used as the coarsest level in
269 * a Multigrid computation, that is, the highest level in the hierarchy whose
270 * mesh covers the entire domain. This corresponds to the minimum level of a
271 * cell on the active mesh. Since each processor only has a local view of the
272 * mesh, each processor must call this function. Note that this is a global
273 * minimum over the entire mesh and therefore each processor will return the
274 * same value.
275 */
276 template <int dim, int spacedim>
277 unsigned int
278 max_level_for_coarse_mesh(const Triangulation<dim, spacedim> &tria);
279
280 /**
281 * This function returns the local work of each level, i.e., the
282 * number of locally-owned cells on each multigrid level.
283 *
284 * @note This function requires that
285 * parallel::TriangulationBase::is_multilevel_hierarchy_constructed()
286 * is true, which can be controlled by setting the
287 * construct_multigrid_hierarchy flag when constructing the
288 * Triangulation.
289 */
290 template <int dim, int spacedim>
291 std::vector<types::global_dof_index>
292 local_workload(const Triangulation<dim, spacedim> &tria);
293
294 /**
295 * Similar to the above function but for a vector of triangulations as created
296 * e.g. by
297 * MGTransferGlobalCoarseningTools::create_geometric_coarsening_sequence().
298 * This returns the number of locally-owned cells on each of the
299 * triangulations.
300 */
301 template <int dim, int spacedim>
302 std::vector<types::global_dof_index>
303 local_workload(
304 const std::vector<std::shared_ptr<const Triangulation<dim, spacedim>>>
305 &trias);
306
307 /**
308 * Return the imbalance of the parallel distribution of the multigrid
309 * mesh hierarchy, based on the local workload provided by local_workload().
310 * Ideally this value is equal to 1 (every processor owns
311 * the same number of cells on each level, approximately true for most
312 * globally refined meshes). Values greater than 1 estimate the slowdown
313 * one should see in a geometric multigrid v-cycle as compared with the same
314 * computation on a perfectly distributed mesh hierarchy.
315 *
316 * @note This function is a collective MPI call between all ranks of the
317 * Triangulation and therefore needs to be called from all ranks.
318 *
319 * @note This function requires that
320 * parallel::TriangulationBase::is_multilevel_hierarchy_constructed()
321 * is true, which can be controlled by setting the
322 * construct_multigrid_hierarchy flag when constructing the
323 * Triangulation.
324 */
325 template <int dim, int spacedim>
326 double
327 workload_imbalance(const Triangulation<dim, spacedim> &tria);
328
329 /**
330 * Similar to the above function but for a vector of triangulations as created
331 * e.g. by
332 * MGTransferGlobalCoarseningTools::create_geometric_coarsening_sequence().
333 */
334 template <int dim, int spacedim>
335 double
336 workload_imbalance(
337 const std::vector<std::shared_ptr<const Triangulation<dim, spacedim>>>
338 &trias);
339
340 /**
341 * Return the vertical communication cost between levels.
342 * The returned vector contains for each level the number
343 * of cells that have the same owning process as their
344 * corresponding coarse cell (parent) and the number of cells that have not
345 * the same owning process as their corresponding coarse cell.
346 */
347 template <int dim, int spacedim>
348 std::vector<std::pair<types::global_dof_index, types::global_dof_index>>
349 local_vertical_communication_cost(const Triangulation<dim, spacedim> &tria);
350
351 /**
352 * Similar to the above function but for a vector of triangulations as created
353 * e.g. by
354 * MGTransferGlobalCoarseningTools::create_geometric_coarsening_sequence().
355 *
356 * @note This function is a collective MPI call between all ranks of the
357 * Triangulation and therefore needs to be called from all ranks.
358 */
359 template <int dim, int spacedim>
360 std::vector<std::pair<types::global_dof_index, types::global_dof_index>>
361 local_vertical_communication_cost(
362 const std::vector<std::shared_ptr<const Triangulation<dim, spacedim>>>
363 &trias);
364
365 /**
366 * Share of fine cells that have the same owning process as their
367 * corresponding coarse cell (parent). This quantity gives an
368 * indication on the efficiency of a multigrid transfer operator
369 * and on how much data has to be sent around. A small number indicates
370 * that most of the data has to be completely permuted, involving a large
371 * volume of communication.
372 *
373 * @note This function is a collective MPI call between all ranks of the
374 * Triangulation and therefore needs to be called from all ranks.
375 */
376 template <int dim, int spacedim>
377 double
378 vertical_communication_efficiency(const Triangulation<dim, spacedim> &tria);
379
380 /**
381 * Similar to the above function but for a vector of triangulations as created
382 * e.g. by
383 * MGTransferGlobalCoarseningTools::create_geometric_coarsening_sequence().
384 */
385 template <int dim, int spacedim>
386 double
387 vertical_communication_efficiency(
388 const std::vector<std::shared_ptr<const Triangulation<dim, spacedim>>>
389 &trias);
390
391
392 } // namespace MGTools
393
394 /** @} */
395
396 DEAL_II_NAMESPACE_CLOSE
397
398 #endif