Debian Codegraph @

include/deal.II/numerics/smoothness_estimator.h

raw
1 // ------------------------------------------------------------------------
2 //
3 // SPDX-License-Identifier: LGPL-2.1-or-later
4 // Copyright (C) 2020 - 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_smoothness_estimator_h
16 #define dealii_smoothness_estimator_h
17
18
19 #include <deal.II/base/config.h>
20
21 #include <deal.II/fe/component_mask.h>
22
23 #include <deal.II/numerics/vector_tools_common.h>
24
25 #include <functional>
26 #include <vector>
27
28
29 DEAL_II_NAMESPACE_OPEN
30
31
32 // forward declarations
33 #ifndef DOXYGEN
34 template <typename Number>
35 class Vector;
36
37 template <int dim, int spacedim>
38 DEAL_II_CXX20_REQUIRES((concepts::is_valid_dim_spacedim<dim, spacedim>))
39 class DoFHandler;
40
41 namespace FESeries
42 {
43 template <int dim, int spacedim>
44 class Fourier;
45 template <int dim, int spacedim>
46 class Legendre;
47 } // namespace FESeries
48
49 namespace hp
50 {
51 template <int dim, int spacedim>
52 class FECollection;
53 } // namespace hp
54 #endif
55
56
57 /**
58 * A namespace for various smoothness estimation strategies for hp-adaptive FEM.
59 *
60 * Smoothness estimation is one strategy to decide whether a cell with a large
61 * error estimate should undergo h- or p-refinement. Typical strategies decide
62 * to increase the polynomial degree on a cell if the solution is particularly
63 * smooth, whereas one would refine the mesh if the solution on the cell is
64 * singular, has kinks in some derivative, or is otherwise not particularly
65 * smooth. All of these strategies rely on a way to identify how "smooth" a
66 * function is on a given cell.
67 */
68 namespace SmoothnessEstimator
69 {
70 /**
71 * Smoothness estimation strategy based on the decay of Legendre expansion
72 * coefficients.
73 *
74 * In one dimension, the finite element solution on cell $K$ with polynomial
75 * degree $p$ can be written as
76 * @f{eqnarray*}{
77 * u_h(x) &=& \sum_j u_j \varphi_j (x) \\
78 * u_{h, k}(x) &=& \sum_{k=0}^{p} a_k \widetilde P_k (x),
79 * \quad a_k = \sum_j {\cal L}_{k,j} u_j
80 * @f}
81 * where $u_j$ are degrees of freedom and $\varphi_j$ are the corresponding
82 * shape functions. $\{\widetilde P_k(x)\}$ are Legendre polynomials on cell
83 * $K$. $a_k$ and ${\cal L}_{k,j}$ are coefficients and transformation
84 * matrices from the Legendre expansion of each shape function. For practical
85 * reasons, we will perform the calculation of these matrices and coefficients
86 * only on the reference cell $\hat K$. We only have to calculate the
87 * transformation matrices once this way. However, results are only applicable
88 * if the mapping from the reference cell to the actual cell is affine. We use
89 * the class FESeries::Legendre to determine all coefficients $a_k$.
90 *
91 * A function is analytic, i.e., representable by a power series, if and only
92 * if their Legendre expansion coefficients decay as (see @cite eibner2007hp)
93 * @f[
94 * |a_k| \sim c \, \exp(-\sigma k)
95 * @f]
96 * We determine their decay rate $\sigma$ by performing the linear regression
97 * fit of
98 * @f[
99 * \ln |a_k| \sim C - \sigma k
100 * @f]
101 * for $k=0,\ldots,p$, with $p$ the polynomial degree of the finite element.
102 * The rate of the decay $\sigma$ can be used to estimate the smoothness. For
103 * example, one strategy to implement hp-refinement criteria is to perform
104 * p-refinement if $\sigma>1$ (see @cite mavriplis1994hp).
105 */
106 namespace Legendre
107 {
108 /**
109 * In this variant of the estimation strategy for higher dimensions, we will
110 * consider all mode vectors $\bf k$ describing Legendre polynomials
111 * $\widetilde P_{\bf k}$ and perform one least-squares fit over all
112 * coefficients at once. If there are multiple coefficients corresponding to
113 * the same absolute value of modes $\|{\bf k}\|_1$, we take the maximum
114 * among those. Thus, the least-squares fit is performed on
115 * @f{eqnarray*}{
116 * \widetilde P_{\bf k}({\bf x}) &=&
117 * \widetilde P_{k_1} (x_1) \ldots \widetilde P_{k_d} (x_d) \\
118 * \ln \left( \max\limits_{\|{\bf k}\|_1} |a_{\bf k}| \right) &\sim&
119 * C - \sigma \|{\bf k}\|_1
120 * @f}
121 * for ${\bf k}=(k_1,\ldots,k_d)$ and $k_i=0,\ldots,p$, with $p$ the
122 * polynomial degree of the finite element.
123 *
124 * For a finite element approximation @p solution, this function writes the
125 * decay rate for every cell into the output vector @p smoothness_indicators.
126 *
127 * @param [in] fe_legendre FESeries::Legendre object to calculate coefficients.
128 * This object needs to be initialized to have at least $p+1$ coefficients
129 * in each direction for every finite element in the collection, where $p$
130 * is its polynomial degree.
131 * @param [in] dof_handler A DoFHandler.
132 * @param [in] solution A solution vector.
133 * @param [out] smoothness_indicators A vector for smoothness indicators.
134 * @param [in] regression_strategy Determines which norm will be used on the
135 * subset of coefficients $\mathbf{k}$ with the same absolute value
136 * $\|{\bf k}\|_1$. Default is VectorTools::Linfty_norm for a maximum
137 * approximation.
138 * @param [in] smallest_abs_coefficient The smallest absolute value of the
139 * coefficient to be used in linear regression. Note that Legendre
140 * coefficients of some functions may have a repeating pattern of zero
141 * coefficients (i.e. for functions that are locally symmetric or
142 * antisymmetric about the midpoint of the element in any coordinate
143 * direction). Thus this parameters allows to ignore small (in absolute
144 * value) coefficients within the linear regression fit. In case there are
145 * less than two nonzero coefficients, the returned value for this cell will
146 * be $\sigma=\infty$.
147 * @param [in] only_flagged_cells Smoothness indicators are usually used to
148 * decide whether to perform h- or p-adaptation. So in most cases, we only
149 * need to calculate those indicators on cells flagged for refinement or
150 * coarsening. This parameter controls whether this particular subset or all
151 * cells will be considered. By default, all cells will be considered. When
152 * only flagged cells are supposed to be considered, smoothness indicators
153 * will only be set on those vector entries of flagged cells; the others
154 * will be set to a signaling NaN.
155 *
156 * For more theoretical details see @cite mavriplis1994hp
157 * @cite houston2005hp @cite eibner2007hp.
158 */
159 template <int dim, int spacedim, typename VectorType>
160 void
161 coefficient_decay(FESeries::Legendre<dim, spacedim> &fe_legendre,
162 const DoFHandler<dim, spacedim> &dof_handler,
163 const VectorType &solution,
164 Vector<float> &smoothness_indicators,
165 const VectorTools::NormType regression_strategy =
166 VectorTools::Linfty_norm,
167 const double smallest_abs_coefficient = 1e-10,
168 const bool only_flagged_cells = false);
169
170 /**
171 * In this variant of the estimation strategy for higher dimensions, we only
172 * consider modes in each coordinate direction, i.e., only mode vectors
173 * $\bf k$ with one nonzero entry. We perform the least-squares fit in
174 * each coordinate direction separately and take the lowest decay rate
175 * $\sigma$ among them.
176 *
177 * For a finite element approximation @p solution, this function writes the
178 * decay rate for every cell into the output vector @p smoothness_indicators.
179 *
180 * @param [in] fe_legendre FESeries::Legendre object to calculate coefficients.
181 * This object needs to be initialized to have at least $p+1$ coefficients
182 * in each direction, where $p$ is the maximum polynomial degree to be used.
183 * @param [in] dof_handler A DoFHandler
184 * @param [in] solution A solution vector
185 * @param [out] smoothness_indicators A vector for smoothness indicators
186 * @param [in] coefficients_predicate A predicate to select Legendre
187 * coefficients $a_j$, $j=0,\ldots,p$ for linear regression in each
188 * coordinate direction. The user is responsible for updating the vector of
189 * `flags` provided to this function. Note that its size is $p+1$, where $p$
190 * is the polynomial degree of the FE basis on a given element. The default
191 * implementation will use all Legendre coefficients in each coordinate
192 * direction, i.e. set all elements of the vector to `true`.
193 * @param [in] smallest_abs_coefficient The smallest absolute value of the
194 * coefficient to be used in linear regression in each coordinate direction.
195 * Note that Legendre coefficients of some functions may have a repeating
196 * pattern of zero coefficients (i.e. for functions that are locally
197 * symmetric or antisymmetric about the midpoint of the element in any
198 * coordinate direction). Thus this parameters allows to ignore small (in
199 * absolute value) coefficients within the linear regression fit. In case
200 * there are less than two nonzero coefficients for a coordinate direction,
201 * this direction will be skipped. If all coefficients are zero, the
202 * returned value for this cell will be $\sigma=\infty$.
203 * @param [in] only_flagged_cells Smoothness indicators are usually used to
204 * decide whether to perform h- or p-adaptation. So in most cases, we only
205 * need to calculate those indicators on cells flagged for refinement or
206 * coarsening. This parameter controls whether this particular subset or all
207 * cells will be considered. By default, all cells will be considered. When
208 * only flagged cells are supposed to be considered, smoothness indicators
209 * will only be set on those vector entries of flagged cells; the others
210 * will be set to NaN.
211 *
212 * For more theoretical details and the application within the deal.II
213 * library see @cite davydov2017hp.
214 */
215 template <int dim, int spacedim, typename VectorType>
216 void
217 coefficient_decay_per_direction(
218 FESeries::Legendre<dim, spacedim> &fe_legendre,
219 const DoFHandler<dim, spacedim> &dof_handler,
220 const VectorType &solution,
221 Vector<float> &smoothness_indicators,
222 const ComponentMask &coefficients_predicate = {},
223 const double smallest_abs_coefficient = 1e-10,
224 const bool only_flagged_cells = false);
225
226 /**
227 * Returns a FESeries::Legendre object for Legendre series expansions with
228 * the default configuration for smoothness estimation purposes.
229 *
230 * For each finite element of the provided @p fe_collection, we use as many
231 * modes as its polynomial degree plus two. This includes the first Legendre
232 * polynomial which is just a constant. Further for each element, we use a
233 * Gaussian quadrature designed to yield exact results for the highest order
234 * Legendre polynomial used.
235 *
236 * As the Legendre expansion can only be performed on scalar fields, this
237 * class does not operate on vector-valued finite elements and will
238 * therefore throw an assertion. However, each component of a finite element
239 * field can be treated as a scalar field, respectively, on which Legendre
240 * expansions are again possible. For this purpose, the optional parameter
241 * @p component defines which component of each FiniteElement will be used.
242 * The default value of @p component only applies to scalar FEs, in which
243 * case it indicates that the sole component is to be decomposed. For
244 * vector-valued FEs, a non-default value must be explicitly provided.
245 */
246 template <int dim, int spacedim>
247 FESeries::Legendre<dim, spacedim>
248 default_fe_series(
249 const hp::FECollection<dim, spacedim> &fe_collection,
250 const unsigned int component = numbers::invalid_unsigned_int);
251 } // namespace Legendre
252
253
254
255 /**
256 * Smoothness estimation strategy based on the decay of Fourier expansion
257 * coefficients.
258 *
259 * From the definition, we can write our Fourier series expansion
260 * $a_{\bf k}$ of the finite element solution on cell $K$ with polynomial
261 * degree $p$ as a matrix product
262 * @f{eqnarray*}{
263 * u_h({\bf x}) &=& \sum_j u_j \varphi_j ({\bf x}) \\
264 * u_{h, {\bf k}}({\bf x}) &=&
265 * \sum_{{\bf k}, \|{\bf k}\|\le p} a_{\bf k} \phi_{\bf k}({\bf x}),
266 * \quad a_{\bf k} = \sum_j {\cal F}_{{\bf k},j} u_j
267 * @f}
268 * with $u_j$ the degrees of freedom and $\varphi_j$ the corresponding shape
269 * functions. $\{\phi_{\bf k}({\bf x}) = \exp(i \, 2 \pi \, {\bf k} \cdot
270 * {\bf x}) \}$ are exponential functions on cell $K$. $a_{\bf k}$ and ${\cal
271 * F}_{{\bf k},j}$ are coefficients and transformation matrices from the
272 * Fourier expansion of each shape function. For practical reasons, we will
273 * perform the calculation of these matrices and coefficients only on the
274 * reference cell $\hat K$. We only have to calculate the transformation
275 * matrices once this way. However, results are only applicable if mapping
276 * from the reference cell to the actual cell is linear. We use the class
277 * FESeries::Fourier to determine all coefficients $a_{\bf k}$.
278 *
279 * If the finite element approximation on cell $K$ is part of the Hilbert
280 * space $H^s(K)$, then the following integral must exist for both the finite
281 * element and spectral representation of our solution
282 * @f{eqnarray*}{
283 * \| \nabla^s u_h({\bf x}) \|_{L^2(K)}^2 &=&
284 * \int\limits_K \left| \nabla^s u_h({\bf x}) \right|^2 d{\bf x} <
285 * \infty \\
286 * \| \nabla^s u_{h, {\bf k}}({\bf x}) \|_{L^2(K)}^2 &=&
287 * \int\limits_K \left| \sum\limits_{\bf k} (-i \, 2 \pi {\bf k})^s \,
288 * a_{\bf k} \, \phi_{\bf k}({\bf x}) \right|^2 d{\bf x} =
289 * (2 \pi)^{2s} \sum\limits_{\bf k} \left| a_{\bf k} \right|^2
290 * \|{\bf k}\|_2^{2s} < \infty
291 * @f}
292 * The sum is finite only if the summands decay at least with order
293 * @f[
294 * |a_{\bf k}|^2 \|{\bf k}\|_2^{2s} \|{\bf k}\|_2^{d - 1} =
295 * {\cal O}\left( \|{\bf k}\|_2^{-1-\epsilon} \right)
296 * @f]
297 * for all $\epsilon > 0$. The additional factor stems from the fact that,
298 * since we sum over all multi-indices ${\bf k}$ that are located on a
299 * dim-dimensional sphere, we actually have, up to a constant,
300 * $\|{\bf k}\|_2^{d-1}$ modes located in each increment $\|{\bf k}\|_2 +
301 * d\|{\bf k}\|_2$ that need to be taken into account. By a comparison of
302 * exponents, we can rewrite this condition as
303 * @f[
304 * |a_{\bf k}| = {\cal O}\left(\|{\bf k}\|_2^
305 * {-\left(s + \frac d2 + \epsilon \right)} \right)
306 * @f]
307 *
308 * The next step is to estimate how fast these coefficients
309 * decay with $\|{\bf k}\|_2$. Thus, we perform a least-squares fit
310 * @f[
311 * \min_{\alpha,\sigma}
312 * \frac 12 \sum_{{\bf k}, \|{\bf k}\|_2 \le p}
313 * \left( |a_{\bf k}| - \alpha \|{\bf k}\|_2^{-\sigma}\right)^2
314 * @f]
315 * with regression coefficients $\alpha$ and $\sigma$. For simplification, we
316 * apply a logarithm on our minimization problem
317 * @f[
318 * \min_{\beta,\sigma}
319 * Q(\beta,\sigma) =
320 * \frac 12 \sum_{{\bf k}, \|{\bf k}\|_2 \le p}
321 * \left( \ln |a_{\bf k}| - \beta + \sigma \ln \|{\bf k}\|_2
322 * \right)^2,
323 * @f]
324 * where $\beta=\ln \alpha$. This is now a problem for which the optimality
325 * conditions $\frac{\partial Q}{\partial\beta}=0,
326 * \frac{\partial Q}{\partial\sigma}=0$, are linear in $\beta,\sigma$. We can
327 * write these conditions as follows:
328 * @f[
329 * \left(\begin{array}{cc}
330 * \sum_{{\bf k}, \|{\bf k}\|_2 \le p} 1 &
331 * \sum_{{\bf k}, \|{\bf k}\|_2 \le p} \ln \|{\bf k}\|_2
332 * \\
333 * \sum_{{\bf k}, \|{\bf k}\|_2 \le p} \ln \|{\bf k}\|_2 &
334 * \sum_{{\bf k}, \|{\bf k}\|_2 \le p} (\ln \|{\bf k}\|_2)^2
335 * \end{array}\right)
336 * \left(\begin{array}{c}
337 * \beta \\ -\sigma
338 * \end{array}\right)
339 * =
340 * \left(\begin{array}{c}
341 * \sum_{{\bf k}, \|{\bf k}\|_2\le p} \ln |a_{{\bf k}}|
342 * \\
343 * \sum_{{\bf k}, \|{\bf k}\|_2\le p} \ln |a_{{\bf k}}| \ln \|{\bf
344 * k}\|_2 \end{array}\right)
345 * @f]
346 * Solving for $\beta$ and $\sigma$ is just a linear regression fit and to do
347 * that we will use FESeries::linear_regression().
348 *
349 * While we are not particularly interested in the actual value of
350 * $\beta$, the formula above gives us a means to calculate the value of
351 * the exponent $\sigma$ that we can then use to determine that
352 * $u(\hat{\bf x})$ is in $H^s(K)$ with $s=\sigma-\frac d2$. The
353 * decay rates $\sigma$ will suffice as our smoothness indicators and
354 * will be calculated on each cell for any provided solution.
355 *
356 * @note An extensive demonstration of the use of these functions is
357 * provided in step-27.
358 */
359 namespace Fourier
360 {
361 /**
362 * In this variant of the estimation strategy for higher dimensions, we will
363 * consider all mode vectors $\bf k$ describing Fourier polynomials
364 * $P_{\bf k}$ and perform one least-squares fit over all coefficients
365 * at once. If there are multiple coefficients corresponding to the same
366 * absolute value of modes $\|\bf k\|_2$, we take the maximum among those.
367 * Thus, the least-squares fit is performed on
368 * @f[
369 * \ln \left( \max\limits_{\|{\bf k}\|_2} |a_{\bf k}| \right) \sim
370 * C - \sigma \ln \|{\bf k}\|_2
371 * @f]
372 * for ${\bf k}=(k_1,\ldots,k_d)$ and $k_i=0,\ldots,p$, with $p$ the
373 * polynomial degree of the finite element. We exclude the $\|{\bf k}\|_2=0$
374 * modes to avoid the singularity of the logarithm.
375 *
376 * The @p regression_strategy parameter determines which norm will be used
377 * on the subset of coefficients $\bf k$ with the same absolute value
378 * $\|{\bf k}\|_2$. Default is VectorTools::Linfty_norm for a maximum
379 * approximation.
380 *
381 * For a provided solution vector @p solution defined on a DoFHandler
382 * @p dof_handler, this function returns a vector @p smoothness_indicators
383 * with as many elements as there are cells where each element contains the
384 * estimated regularity $\sigma$.
385 *
386 * A series expansion object @p fe_fourier has to be supplied, which needs
387 * to be constructed with the same FECollection object as the @p dof_handler.
388 *
389 * The parameter @p smallest_abs_coefficient allows to ignore small (in
390 * absolute value) coefficients within the linear regression fit. In case
391 * there are less than two nonzero coefficients for a coordinate direction,
392 * this direction will be skipped. If all coefficients are zero, the
393 * returned value for this cell will be $\sigma=\infty$.
394 *
395 * Smoothness indicators are usually used to decide whether to perform h- or
396 * p-adaptation. So in most cases, we only need to calculate those
397 * indicators on cells flagged for refinement or coarsening. The parameter
398 * @p only_flagged_cells controls whether this particular subset or all
399 * cells will be considered. By default, all cells will be considered.
400 * When only flagged cells are supposed to be considered, smoothness
401 * indicators will only be set on those vector entries of flagged cells;
402 * the others will be set to a signaling NaN.
403 */
404 template <int dim, int spacedim, typename VectorType>
405 void
406 coefficient_decay(FESeries::Fourier<dim, spacedim> &fe_fourier,
407 const DoFHandler<dim, spacedim> &dof_handler,
408 const VectorType &solution,
409 Vector<float> &smoothness_indicators,
410 const VectorTools::NormType regression_strategy =
411 VectorTools::Linfty_norm,
412 const double smallest_abs_coefficient = 1e-10,
413 const bool only_flagged_cells = false);
414
415 /**
416 * In this variant of the estimation strategy for higher dimensions, we only
417 * consider modes in each coordinate direction, i.e., only mode vectors
418 * $\bf k$ with one nonzero entry. We perform the least-squares fit in
419 * each coordinate direction separately and take the lowest decay rate
420 * $\sigma$ among them.
421 *
422 * The @p coefficients_predicate parameter selects Fourier coefficients
423 * $a_j$, $j=0,\ldots,p$ for linear regression in each coordinate
424 * direction. The user is responsible for updating the vector of `flags`
425 * provided to this function. Note that its size is $p+1$, where $p$ is the
426 * polynomial degree of the FE basis on a given element. The default
427 * implementation will use all Fourier coefficients in each coordinate
428 * direction, i.e., set all the elements of the vector to `true`.
429 *
430 * For a provided solution vector @p solution defined on a DoFHandler
431 * @p dof_handler, this function returns a vector @p smoothness_indicators
432 * with as many elements as there are cells where each element contains the
433 * estimated regularity $\sigma$.
434 *
435 * A series expansion object @p fe_fourier has to be supplied, which needs
436 * to be constructed with the same FECollection object as the @p dof_handler.
437 *
438 * The parameter @p smallest_abs_coefficient allows to ignore small (in
439 * absolute value) coefficients within the linear regression fit. In case
440 * there are fewer than two nonzero coefficients for a coordinate direction,
441 * this direction will be skipped. If all coefficients are zero, the
442 * returned value for this cell will be $\sigma=\infty$.
443 *
444 * Smoothness indicators are usually used to decide whether to perform h- or
445 * p-adaptation. So in most cases, we only need to calculate those
446 * indicators on cells flagged for refinement or coarsening. The parameter
447 * @p only_flagged_cells controls whether this particular subset or all
448 * cells will be considered. By default, all cells will be considered.
449 * When only flagged cells are supposed to be considered, smoothness
450 * indicators will only be set on those vector entries of flagged cells;
451 * the others will be set to a signaling NaN.
452 */
453 template <int dim, int spacedim, typename VectorType>
454 void
455 coefficient_decay_per_direction(
456 FESeries::Fourier<dim, spacedim> &fe_fourier,
457 const DoFHandler<dim, spacedim> &dof_handler,
458 const VectorType &solution,
459 Vector<float> &smoothness_indicators,
460 const ComponentMask &coefficients_predicate = {},
461 const double smallest_abs_coefficient = 1e-10,
462 const bool only_flagged_cells = false);
463
464 /**
465 * Returns a FESeries::Fourier object for Fourier series expansions with
466 * the default configuration for smoothness estimation purposes.
467 *
468 * For each finite element of the provided @p fe_collection, we use as many
469 * modes as its polynomial degree plus two. Further for each element, we use
470 * a 5-point Gaussian quarature iterated in each dimension by the maximal
471 * wave number, which is the number of modes decreased by one since we start
472 * with $k = 0$.
473 *
474 * As the Fourier expansion can only be performed on scalar fields, this
475 * class does not operate on vector-valued finite elements and will
476 * therefore throw an assertion. However, each component of a finite element
477 * field can be treated as a scalar field, respectively, on which Fourier
478 * expansions are again possible. For this purpose, the optional parameter
479 * @p component defines which component of each FiniteElement will be used.
480 * The default value of @p component only applies to scalar FEs, in which
481 * case it indicates that the sole component is to be decomposed. For
482 * vector-valued FEs, a non-default value must be explicitly provided.
483 */
484 template <int dim, int spacedim>
485 FESeries::Fourier<dim, spacedim>
486 default_fe_series(
487 const hp::FECollection<dim, spacedim> &fe_collection,
488 const unsigned int component = numbers::invalid_unsigned_int);
489 } // namespace Fourier
490 } // namespace SmoothnessEstimator
491
492
493 DEAL_II_NAMESPACE_CLOSE
494
495 #endif