| 1 |
// ------------------------------------------------------------------------ |
| 2 |
// |
| 3 |
// SPDX-License-Identifier: LGPL-2.1-or-later |
| 4 |
// Copyright (C) 2000 - 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_grid_refinement_h |
| 16 |
#define dealii_grid_refinement_h |
| 17 |
|
| 18 |
|
| 19 |
#include <deal.II/base/config.h> |
| 20 |
|
| 21 |
#include <deal.II/base/exceptions.h> |
| 22 |
|
| 23 |
#include <deal.II/numerics/vector_tools_common.h> |
| 24 |
|
| 25 |
#include <limits> |
| 26 |
|
| 27 |
DEAL_II_NAMESPACE_OPEN |
| 28 |
|
| 29 |
// forward declarations |
| 30 |
#ifndef DOXYGEN |
| 31 |
template <int dim, int spacedim> |
| 32 |
DEAL_II_CXX20_REQUIRES((concepts::is_valid_dim_spacedim<dim, spacedim>)) |
| 33 |
class Triangulation; |
| 34 |
template <typename Number> |
| 35 |
class Vector; |
| 36 |
#endif |
| 37 |
|
| 38 |
/** |
| 39 |
* This namespace provides a collection of functions that aid in refinement |
| 40 |
* and coarsening of triangulations. Despite the name of the namespace, the |
| 41 |
* functions do not actually <i>refine</i> the triangulation, but only |
| 42 |
* <i>mark cells for refinement or coarsening</i>. In other words, they |
| 43 |
* perform the "mark" part of the typical "solve-estimate-mark-refine" |
| 44 |
* cycle of the adaptive finite element loop. |
| 45 |
* |
| 46 |
* The functions in this namespace form two categories. There are the |
| 47 |
* auxiliary functions refine() and coarsen(). More important for users are |
| 48 |
* the other functions, which implement refinement strategies, as being found |
| 49 |
* in the literature on adaptive finite element methods. For mathematical |
| 50 |
* discussion of these methods, consider works by Dörfler, Morin, |
| 51 |
* Nochetto, Rannacher, Stevenson, and others. |
| 52 |
* |
| 53 |
* @ingroup grid |
| 54 |
*/ |
| 55 |
namespace GridRefinement |
| 56 |
{ |
| 57 |
/** |
| 58 |
* Return a pair of double values of which the first is adjusted refinement |
| 59 |
* fraction of cells and the second is adjusted coarsening fraction of |
| 60 |
* cells. |
| 61 |
* |
| 62 |
* |
| 63 |
* @param[in] current_n_cells The current cell number. |
| 64 |
* |
| 65 |
* @param[in] max_n_cells The maximal number of cells. If current cell |
| 66 |
* number @p current_n_cells is already exceeded maximal cell number @p |
| 67 |
* max_n_cells, refinement fraction of cells will be set to zero and |
| 68 |
* coarsening fraction of cells will be adjusted to reduce cell number to |
| 69 |
* @p max_n_cells. If cell number is going to be exceeded only upon |
| 70 |
* refinement, then refinement and coarsening fractions are going to be |
| 71 |
* adjusted with a same ratio in an attempt to reach the maximum number of |
| 72 |
* cells. Be aware though that through proliferation of refinement due to |
| 73 |
* Triangulation::MeshSmoothing, this number is only an indicator. The |
| 74 |
* default value of this argument is to impose no limit on the number of |
| 75 |
* cells. |
| 76 |
* |
| 77 |
* @param[in] top_fraction_of_cells The requested fraction of active |
| 78 |
* cells to be refined. |
| 79 |
* |
| 80 |
* @param[in] bottom_fraction_of_cells The requested fraction of |
| 81 |
* active cells to be coarsened. |
| 82 |
* |
| 83 |
* @note Usually you do not need to call this function explicitly. Pass @p |
| 84 |
* max_n_cells to function refine_and_coarsen_fixed_number() or function |
| 85 |
* refine_and_coarsen_fixed_fraction() and they will call this function if |
| 86 |
* necessary. |
| 87 |
*/ |
| 88 |
template <int dim> |
| 89 |
std::pair<double, double> |
| 90 |
adjust_refine_and_coarsen_number_fraction( |
| 91 |
const types::global_cell_index current_n_cells, |
| 92 |
const types::global_cell_index max_n_cells, |
| 93 |
const double top_fraction_of_cells, |
| 94 |
const double bottom_fraction_of_cells); |
| 95 |
|
| 96 |
/** |
| 97 |
* This function provides a strategy to mark cells for refinement and |
| 98 |
* coarsening with the goal of providing predictable growth in |
| 99 |
* the size of the mesh by refining a given fraction of all cells. |
| 100 |
* |
| 101 |
* The function takes a vector of refinement @p criteria and two values |
| 102 |
* between zero and one denoting the fractions of cells to be refined and |
| 103 |
* coarsened. It flags cells for further processing by |
| 104 |
* Triangulation::execute_coarsening_and_refinement() according to the |
| 105 |
* following greedy algorithm: |
| 106 |
* |
| 107 |
* <ol> |
| 108 |
* |
| 109 |
* <li> Sort the cells according to descending values of @p criteria. |
| 110 |
* |
| 111 |
* <li> Mark the @p top_fraction_of_cells times |
| 112 |
* Triangulation::n_active_cells() active cells with the largest |
| 113 |
* refinement criteria for refinement. |
| 114 |
* |
| 115 |
* <li> Mark the @p bottom_fraction_of_cells times |
| 116 |
* Triangulation::n_active_cells() active cells with the smallest |
| 117 |
* refinement criteria for coarsening. |
| 118 |
* |
| 119 |
* </ol> |
| 120 |
* |
| 121 |
* As an example, with no coarsening, setting @p top_fraction_of_cells to |
| 122 |
* 1/3 will result in approximately doubling the number of cells in two |
| 123 |
* dimensions. That is because each of these 1/3 of cells will be replaced by |
| 124 |
* its four children, resulting in $4\times \frac 13 N$ cells, whereas the |
| 125 |
* remaining 2/3 of cells remains untouched -- thus yielding a total of |
| 126 |
* $4\times \frac 13 N + \frac 23 N = 2N$ cells. |
| 127 |
* The same effect in three dimensions is achieved by refining |
| 128 |
* 1/7th of the cells. These values are therefore frequently used because |
| 129 |
* they ensure that the cost of computations on subsequent meshes become |
| 130 |
* expensive sufficiently quickly that the fraction of time spent on |
| 131 |
* the coarse meshes is not too large. On the other hand, the fractions |
| 132 |
* are small enough that mesh adaptation does not refine too many cells |
| 133 |
* in each step. |
| 134 |
* |
| 135 |
* @note This function only sets the coarsening and refinement flags. The |
| 136 |
* mesh is not changed until you call |
| 137 |
* Triangulation::execute_coarsening_and_refinement(). |
| 138 |
* |
| 139 |
* @param[in,out] triangulation The triangulation whose cells this function |
| 140 |
* is supposed to mark for coarsening and refinement. |
| 141 |
* |
| 142 |
* @param[in] criteria The refinement criterion for each mesh cell. Entries |
| 143 |
* may not be negative. |
| 144 |
* |
| 145 |
* @param[in] top_fraction_of_cells The fraction of cells to be refined. If |
| 146 |
* this number is zero, no cells will be refined. If it equals one, the |
| 147 |
* result will be flagging for global refinement. |
| 148 |
* |
| 149 |
* @param[in] bottom_fraction_of_cells The fraction of cells to be |
| 150 |
* coarsened. If this number is zero, no cells will be coarsened. |
| 151 |
* |
| 152 |
* @param[in] max_n_cells This argument can be used to specify a maximal |
| 153 |
* number of cells. If this number is going to be exceeded upon refinement, |
| 154 |
* then refinement and coarsening fractions are going to be adjusted in an |
| 155 |
* attempt to reach the maximum number of cells. Be aware though that |
| 156 |
* through proliferation of refinement due to Triangulation::MeshSmoothing, |
| 157 |
* this number is only an indicator. The default value of this argument is |
| 158 |
* to impose no limit on the number of cells. |
| 159 |
*/ |
| 160 |
template <int dim, typename Number, int spacedim> |
| 161 |
void |
| 162 |
refine_and_coarsen_fixed_number( |
| 163 |
Triangulation<dim, spacedim> &triangulation, |
| 164 |
const Vector<Number> &criteria, |
| 165 |
const double top_fraction_of_cells, |
| 166 |
const double bottom_fraction_of_cells, |
| 167 |
const unsigned int max_n_cells = std::numeric_limits<unsigned int>::max()); |
| 168 |
|
| 169 |
/** |
| 170 |
* This function provides a strategy to mark cells for refinement and |
| 171 |
* coarsening with the goal of controlling the reduction of |
| 172 |
* the error estimate. |
| 173 |
* |
| 174 |
* Also known as the <b>bulk criterion</b> or Dörfler marking, |
| 175 |
* this function computes the thresholds for refinement and coarsening |
| 176 |
* such that the @p criteria of cells getting flagged for refinement make |
| 177 |
* up for a certain fraction of the total error. We explain its operation |
| 178 |
* for refinement, coarsening works analogously. |
| 179 |
* |
| 180 |
* Let <i>c<sub>K</sub></i> be the criterion of cell <i>K</i>. Then the |
| 181 |
* total error estimate is computed by the formula |
| 182 |
* @f[ |
| 183 |
* E = \sum_{K\in \cal T} c_K. |
| 184 |
* @f] |
| 185 |
* |
| 186 |
* If <i> 0 < a < 1</i> is @p top_fraction, then we refine the |
| 187 |
* smallest subset $\cal M$ of the Triangulation $\cal T$ such that |
| 188 |
* @f[ |
| 189 |
* a E \le \sum_{K\in \cal M} c_K |
| 190 |
* @f] |
| 191 |
* |
| 192 |
* The algorithm is performed by the greedy algorithm described in |
| 193 |
* refine_and_coarsen_fixed_number(). |
| 194 |
* |
| 195 |
* @note The often used formula with squares on the left and right is |
| 196 |
* recovered by actually storing the square of <i>c<sub>K</sub></i> in the |
| 197 |
* vector @p criteria. |
| 198 |
* |
| 199 |
* From the point of view of implementation, this time we really need to |
| 200 |
* sort the array of criteria. Just like the other strategy described |
| 201 |
* above, this function only computes the threshold values and then passes |
| 202 |
* over to refine() and coarsen(). |
| 203 |
* |
| 204 |
* @param[in,out] tria The triangulation whose cells this function is |
| 205 |
* supposed to mark for coarsening and refinement. |
| 206 |
* |
| 207 |
* @param[in] criteria The refinement criterion computed on each mesh cell. |
| 208 |
* Entries may not be negative. |
| 209 |
* |
| 210 |
* @param[in] top_fraction The fraction of the total estimate which should |
| 211 |
* be refined. If this number is zero, no cells will be refined. If it |
| 212 |
* equals one, the result will be flagging for global refinement. |
| 213 |
* |
| 214 |
* @param[in] bottom_fraction The fraction of the estimate coarsened. If |
| 215 |
* this number is zero, no cells will be coarsened. |
| 216 |
* |
| 217 |
* @param[in] max_n_cells This argument can be used to specify a maximal |
| 218 |
* number of cells. If this number is going to be exceeded upon refinement, |
| 219 |
* then refinement and coarsening fractions are going to be adjusted in an |
| 220 |
* attempt to reach the maximum number of cells. Be aware though that |
| 221 |
* through proliferation of refinement due to Triangulation::MeshSmoothing, |
| 222 |
* this number is only an indicator. The default value of this argument is |
| 223 |
* to impose no limit on the number of cells. |
| 224 |
* |
| 225 |
* @param[in] norm_type To determine thresholds, combined errors on |
| 226 |
* subsets of cells are calculated as norms of the criteria on these |
| 227 |
* cells. Different types of norms can be used for this purpose, from |
| 228 |
* which VectorTools::L1_norm and |
| 229 |
* VectorTools::L2_norm are currently supported. |
| 230 |
*/ |
| 231 |
template <int dim, typename Number, int spacedim> |
| 232 |
void |
| 233 |
refine_and_coarsen_fixed_fraction( |
| 234 |
Triangulation<dim, spacedim> &tria, |
| 235 |
const Vector<Number> &criteria, |
| 236 |
const double top_fraction, |
| 237 |
const double bottom_fraction, |
| 238 |
const unsigned int max_n_cells = std::numeric_limits<unsigned int>::max(), |
| 239 |
const VectorTools::NormType norm_type = VectorTools::L1_norm); |
| 240 |
|
| 241 |
|
| 242 |
|
| 243 |
/** |
| 244 |
* This function flags cells of a triangulation for refinement with the |
| 245 |
* aim to reach a grid that |
| 246 |
* is optimal with respect to an objective function that tries to balance |
| 247 |
* reducing the error and increasing the numerical cost when the mesh is |
| 248 |
* refined. Specifically, this function makes the assumption that if you |
| 249 |
* refine a cell $K$ with error indicator $\eta_K$ provided by the second |
| 250 |
* argument to this function, then the error on the children (for all |
| 251 |
* children together) will only be $2^{-\text{order}}\eta_K$ where |
| 252 |
* <code>order</code> is the third argument of this function. This makes the |
| 253 |
* assumption that the error is only a local property on a mesh and can be |
| 254 |
* reduced by local refinement -- an assumption that is true for the |
| 255 |
* interpolation operator, but not for the usual Galerkin projection, |
| 256 |
* although it is approximately true for elliptic problems where the Greens |
| 257 |
* function decays quickly and the error here is not too much affected by a |
| 258 |
* too coarse mesh somewhere else. |
| 259 |
* |
| 260 |
* With this, we can define the objective function this function tries to |
| 261 |
* optimize. Let us assume that the mesh currently has $N_0$ cells. Then, if |
| 262 |
* we refine the $m$ cells with the largest errors, we expect to get (in $d$ |
| 263 |
* space dimensions) |
| 264 |
* @f[ |
| 265 |
* N(m) = (N_0-m) + 2^d m = N_0 + (2^d-1)m |
| 266 |
* @f] |
| 267 |
* cells ($N_0-m$ are not refined, and each of the $m$ cells we refine yield |
| 268 |
* $2^d$ child cells. On the other hand, with refining $m$ cells, and using |
| 269 |
* the assumptions above, we expect that the error will be |
| 270 |
* @f[ |
| 271 |
* \eta^\text{exp}(m) |
| 272 |
* = |
| 273 |
* \sum_{K, K\; \text{will not be refined}} \eta_K |
| 274 |
* + |
| 275 |
* \sum_{K, K\; \text{will be refined}} 2^{-\text{order}}\eta_K |
| 276 |
* @f] |
| 277 |
* where the first sum extends over $N_0-m$ cells and the second over the |
| 278 |
* $m$ cells that will be refined. Note that $N(m)$ is an increasing |
| 279 |
* function of $m$ whereas $\eta^\text{exp}(m)$ is a decreasing function. |
| 280 |
* |
| 281 |
* This function then tries to find that number $m$ of cells to mark for |
| 282 |
* refinement for which the objective function |
| 283 |
* @f[ |
| 284 |
* J(m) = N(m)^{\text{order}/d} \eta^\text{exp}(m) |
| 285 |
* @f] |
| 286 |
* is minimal. |
| 287 |
* |
| 288 |
* The rationale for this function is two-fold. First, compared to the |
| 289 |
* refine_and_coarsen_fixed_fraction() and refine_and_coarsen_fixed_number() |
| 290 |
* functions, this function has the property that if all refinement |
| 291 |
* indicators are the same (i.e., we have achieved a mesh where the error |
| 292 |
* per cell is equilibrated), then the entire mesh is refined. This is based |
| 293 |
* on the observation that a mesh with equilibrated error indicators is the |
| 294 |
* optimal mesh (i.e., has the least overall error) among all meshes with |
| 295 |
* the same number of cells. (For proofs of this, see R. Becker, M. Braack, |
| 296 |
* R. Rannacher: "Numerical simulation of laminar flames at low Mach number |
| 297 |
* with adaptive finite elements", Combustion Theory and Modelling, Vol. 3, |
| 298 |
* Nr. 3, p. 503-534 1999; and W. Bangerth, R. Rannacher: "Adaptive Finite |
| 299 |
* Element Methods for Differential Equations", Birkhauser, 2003.) |
| 300 |
* |
| 301 |
* Second, the function uses the observation that ideally, the error behaves |
| 302 |
* like $e \approx c N^{-\alpha}$ with some constant $\alpha$ that depends |
| 303 |
* on the dimension and the finite element degree. It should - given optimal |
| 304 |
* mesh refinement - not depend so much on the regularity of the solution, |
| 305 |
* as it is based on the idea, that all singularities can be resolved by |
| 306 |
* refinement. Mesh refinement is then based on the idea that we want to |
| 307 |
* make $c=e N^\alpha$ small. This corresponds to the functional $J(m)$ |
| 308 |
* above. |
| 309 |
* |
| 310 |
* @note This function was originally implemented by Thomas Richter. It |
| 311 |
* follows a strategy described in @cite Richter2005. See in particular |
| 312 |
* Section 4.3, pp. 42-43. |
| 313 |
*/ |
| 314 |
template <int dim, typename Number, int spacedim> |
| 315 |
void |
| 316 |
refine_and_coarsen_optimize(Triangulation<dim, spacedim> &tria, |
| 317 |
const Vector<Number> &criteria, |
| 318 |
const unsigned int order = 2); |
| 319 |
|
| 320 |
/** |
| 321 |
* Mark all mesh cells for which the value in @p criteria exceeds @p |
| 322 |
* threshold for refinement, but only flag up to @p max_to_mark cells. |
| 323 |
* |
| 324 |
* The vector @p criteria contains a nonnegative value for each active cell, |
| 325 |
* ordered in the canonical order of Triangulation::active_cell_iterator. |
| 326 |
* |
| 327 |
* The cells are only flagged for refinement, they are not actually refined. |
| 328 |
* To do so, you have to call |
| 329 |
* Triangulation::execute_coarsening_and_refinement(). |
| 330 |
* |
| 331 |
* This function does not implement a refinement strategy, it is more a |
| 332 |
* helper function for the actual strategies. |
| 333 |
*/ |
| 334 |
template <int dim, typename Number, int spacedim> |
| 335 |
void |
| 336 |
refine(Triangulation<dim, spacedim> &tria, |
| 337 |
const Vector<Number> &criteria, |
| 338 |
const double threshold, |
| 339 |
const unsigned int max_to_mark = numbers::invalid_unsigned_int); |
| 340 |
|
| 341 |
/** |
| 342 |
* Mark all mesh cells for which the value in @p criteria is less than @p |
| 343 |
* threshold for coarsening. |
| 344 |
* |
| 345 |
* The vector @p criteria contains a nonnegative value for each active cell, |
| 346 |
* ordered in the canonical order of Triangulation::active_cell_iterator. |
| 347 |
* |
| 348 |
* The cells are only flagged for coarsening, they are not actually |
| 349 |
* coarsened. To do so, you have to call |
| 350 |
* Triangulation::execute_coarsening_and_refinement(). |
| 351 |
* |
| 352 |
* This function does not implement a refinement strategy, it is more a |
| 353 |
* helper function for the actual strategies. |
| 354 |
*/ |
| 355 |
template <int dim, typename Number, int spacedim> |
| 356 |
void |
| 357 |
coarsen(Triangulation<dim, spacedim> &tria, |
| 358 |
const Vector<Number> &criteria, |
| 359 |
const double threshold); |
| 360 |
|
| 361 |
/** |
| 362 |
* An exception thrown if the vector with cell criteria contains negative |
| 363 |
* values |
| 364 |
*/ |
| 365 |
DeclException0(ExcNegativeCriteria); |
| 366 |
|
| 367 |
/** |
| 368 |
* One of the threshold parameters causes trouble. Or the refinement and |
| 369 |
* coarsening thresholds overlap. |
| 370 |
*/ |
| 371 |
DeclException0(ExcInvalidParameterValue); |
| 372 |
} // namespace GridRefinement |
| 373 |
|
| 374 |
|
| 375 |
|
| 376 |
DEAL_II_NAMESPACE_CLOSE |
| 377 |
|
| 378 |
#endif // dealii_grid_refinement_h |