Debian Codegraph @

include/deal.II/grid/grid_refinement.h

raw
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&ouml;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&ouml;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 &lt; a &lt; 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