| 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 |