Debian Codegraph @

include/deal.II/numerics/derivative_approximation.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_derivative_approximation_h
16 #define dealii_derivative_approximation_h
17
18 #include <deal.II/base/config.h>
19
20 #include <deal.II/base/exceptions.h>
21 #include <deal.II/base/synchronous_iterator.h>
22
23 #include <deal.II/dofs/dof_handler.h>
24
25 #include <deal.II/fe/fe_update_flags.h>
26 #include <deal.II/fe/mapping.h>
27
28 #include <deal.II/grid/filtered_iterator.h>
29
30 #include <deal.II/lac/vector.h>
31 #ifdef _MSC_VER
32 # include <deal.II/dofs/dof_accessor.h>
33 #endif
34 #include <utility>
35
36 DEAL_II_NAMESPACE_OPEN
37
38 /**
39 * This namespace provides functions that compute a cell-wise approximation of
40 * the norm of a derivative of a finite element field by taking difference
41 * quotients between neighboring cells. This is a rather simple but efficient
42 * form to get an error indicator, since it can be computed with relatively
43 * little numerical effort and yet gives a reasonable approximation.
44 *
45 * The way the difference quotients are computed on cell $K$ is the following
46 * (here described for the approximation of the gradient of a finite element
47 * field, but see below for higher derivatives): let $K'$ be a neighboring
48 * cell, and let $y_{K'}=x_{K'}-x_K$ be the distance vector between the
49 * centers of the two cells, then $ \frac{u_h(x_{K'}) - u_h(x_K)}{ \|y_{K'}\|
50 * }$ is an approximation of the directional derivative $ \nabla u(x_K) \cdot
51 * \frac{y_{K'}}{ \|y_{K'}\| }.$ By multiplying both terms by $\frac{y_{K'}}{
52 * \|y_{K'}\| }$ from the left and summing over all neighbors $K'$, we obtain
53 * $ \sum_{K'} \left( \frac{y_{K'}}{ \|y_{K'}\|} \frac{y_{K'}^T}{ \|y_{K'}\| }
54 * \right) \nabla u(x_K) \approx \sum_{K'} \left( \frac{y_{K'}}{ \|y_{K'}\|}
55 * \frac{u_h(x_{K'}) - u_h(x_K)}{ \|y_{K'}\| } \right).$
56 *
57 * Thus, if the matrix $ Y = \sum_{K'} \left( \frac{y_{K'}}{\|y_{K'}\|}
58 * \frac{y_{K'}^T}{ \|y_{K'}\| } \right)$ is regular (which is the case when
59 * the vectors $y_{K'}$ to all neighbors span the whole space), we can obtain
60 * an approximation to the true gradient by $ \nabla u(x_K) \approx Y^{-1}
61 * \sum_{K'} \left( \frac{y_{K'}}{\|y_{K'}\|} \frac{u_h(x_{K'}) - u_h(x_K)}{
62 * \|y_{K'}\| } \right).$ This is a quantity that is easily computed. The
63 * value returned for each cell when calling the @p approximate_gradient
64 * function of this class is the $l_2$ norm of this approximation to the
65 * gradient. To make this a useful quantity, you may want to scale each
66 * element by the correct power of the respective cell size.
67 *
68 * The computation of this quantity must fail if a cell has only neighbors for
69 * which the direction vectors $y_K$ do not span the whole space, since then
70 * the matrix $Y$ is no longer invertible. If this happens, you will get an
71 * error similar to this one:
72 * @code
73 * --------------------------------------------------------
74 * An error occurred in line <749>
75 * of file <source/numerics/derivative_approximation.cc> in function
76 * void DerivativeApproximation::approximate(...)
77 * [with DerivativeDescription = DerivativeApproximation::Gradient<3>, int
78 * dim = 3, InputVector = Vector<double>, spacedim = 3]
79 * The violated condition was:
80 * determinant(Y) != 0
81 * The name and call sequence of the exception was:
82 * ExcInsufficientDirections()
83 * Additional Information:
84 * (none)
85 * --------------------------------------------------------
86 * @endcode
87 * As can easily be verified, this can only happen on very coarse grids, when
88 * some cells and all their neighbors have not been refined even once. You
89 * should therefore only call the functions of this class if all cells are at
90 * least once refined. In practice this is not much of a restriction.
91 *
92 *
93 * <h3>Approximation of higher derivatives</h3>
94 *
95 * Similar to the reasoning above, approximations to higher derivatives can be
96 * computed in a similar fashion. For example, the tensor of second
97 * derivatives is approximated by the formula $ \nabla^2 u(x_K) \approx Y^{-1}
98 * \sum_{K'} \left( \frac{y_{K'}}{\|y_{K'}\|} \otimes \frac{\nabla u_h(x_{K'})
99 * - \nabla u_h(x_K)}{ \|y_{K'}\| } \right), $ where $\otimes$ denotes the
100 * outer product of two vectors. Note that unlike the true tensor of second
101 * derivatives, its approximation is not necessarily symmetric. This is due to
102 * the fact that in the derivation, it is not clear whether we shall consider
103 * as projected second derivative the term $\nabla^2 u y_{KK'}$ or $y_{KK'}^T
104 * \nabla^2 u$. Depending on which choice we take, we obtain one approximation
105 * of the tensor of second derivatives or its transpose. To avoid this
106 * ambiguity, as result we take the symmetrized form, which is the mean value
107 * of the approximation and its transpose.
108 *
109 * The returned value on each cell is the spectral norm of the approximated
110 * tensor of second derivatives, i.e. the largest eigenvalue by absolute
111 * value. This equals the largest curvature of the finite element field at
112 * each cell, and the spectral norm is the matrix norm associated to the $l_2$
113 * vector norm.
114 *
115 * Even higher than the second derivative can be obtained along the same lines
116 * as exposed above.
117 *
118 *
119 * <h3>Refinement indicators based on the derivatives</h3>
120 *
121 * If you would like to base a refinement criterion upon these approximation
122 * of the derivatives, you will have to scale the results of this class by an
123 * appropriate power of the mesh width. For example, since $\|u-u_h\|^2_{L_2}
124 * \le C h^2 \|\nabla u\|^2_{L_2}$, it might be the right thing to scale the
125 * indicators as $\eta_K = h \|\nabla u\|_K$, i.e. $\eta_K = h^{1+d/2}
126 * \|\nabla u\|_{\infty;K}$, i.e. the right power is $1+d/2$.
127 *
128 * Likewise, for the second derivative, one should choose a power of the mesh
129 * size $h$ one higher than for the gradient.
130 *
131 *
132 * <h3>Implementation</h3>
133 *
134 * The formulae for the computation of approximations to the gradient and to
135 * the tensor of second derivatives shown above are very much alike. The basic
136 * difference is that in one case the finite difference quotient is a scalar,
137 * while in the other case it is a vector. For higher derivatives, this would
138 * be a tensor of even higher rank. We then have to form the outer product of
139 * this difference quotient with the distance vector $y_{KK'}$, symmetrize it,
140 * contract it with the matrix $Y^{-1}$ and compute its norm. To make the
141 * implementation simpler and to allow for code reuse, all these operations
142 * that are dependent on the actual order of the derivatives to be
143 * approximated, as well as the computation of the quantities entering the
144 * difference quotient, have been separated into auxiliary nested classes
145 * (names @p Gradient and @p SecondDerivative) and the main algorithm is
146 * simply passed one or the other data types and asks them to perform the
147 * order dependent operations. The main framework that is independent of this,
148 * such as finding all active neighbors, or setting up the matrix $Y$ is done
149 * in the main function @p approximate.
150 *
151 * Due to this way of operation, the class may be easily extended for higher
152 * order derivatives than are presently implemented. Basically, only an
153 * additional class along the lines of the derivative descriptor classes @p
154 * Gradient and @p SecondDerivative has to be implemented, with the respective
155 * alias and functions replaced by the appropriate analogues for the
156 * derivative that is to be approximated.
157 *
158 * @ingroup numerics
159 */
160 namespace DerivativeApproximation
161 {
162 /**
163 * This function is used to obtain an approximation of the gradient. Pass it
164 * the DoF handler object that describes the finite element field, a nodal
165 * value vector, and receive the cell-wise Euclidean norm of the
166 * approximated gradient.
167 *
168 * The last parameter denotes the solution component, for which the gradient
169 * is to be computed. It defaults to the first component. For scalar
170 * elements, this is the only valid choice; for vector-valued ones, any
171 * component between zero and the number of vector components can be given
172 * here.
173 *
174 * In a parallel computation the @p solution vector needs to contain the
175 * locally relevant unknowns.
176 */
177 template <int dim, class InputVector, int spacedim>
178 void
179 approximate_gradient(const Mapping<dim, spacedim> &mapping,
180 const DoFHandler<dim, spacedim> &dof,
181 const InputVector &solution,
182 Vector<float> &derivative_norm,
183 const unsigned int component = 0);
184
185 /**
186 * Call the function above with <tt>mapping=MappingQ@<dim@>(1)</tt>.
187 */
188 template <int dim, class InputVector, int spacedim>
189 void
190 approximate_gradient(const DoFHandler<dim, spacedim> &dof,
191 const InputVector &solution,
192 Vector<float> &derivative_norm,
193 const unsigned int component = 0);
194
195 /**
196 * This function is the analogue to the one above, computing finite
197 * difference approximations of the tensor of second derivatives. Pass it
198 * the DoF handler object that describes the finite element field, a nodal
199 * value vector, and receive the cell-wise spectral norm of the approximated
200 * tensor of second derivatives. The spectral norm is the matrix norm
201 * associated to the $l_2$ vector norm.
202 *
203 * The last parameter denotes the solution component, for which the gradient
204 * is to be computed. It defaults to the first component. For scalar
205 * elements, this is the only valid choice; for vector-valued ones, any
206 * component between zero and the number of vector components can be given
207 * here.
208 *
209 * In a parallel computation the @p solution vector needs to contain the
210 * locally relevant unknowns.
211 */
212 template <int dim, class InputVector, int spacedim>
213 void
214 approximate_second_derivative(const Mapping<dim, spacedim> &mapping,
215 const DoFHandler<dim, spacedim> &dof,
216 const InputVector &solution,
217 Vector<float> &derivative_norm,
218 const unsigned int component = 0);
219
220 /**
221 * Call the function above with <tt>mapping=MappingQ@<dim@>(1)</tt>.
222 */
223 template <int dim, class InputVector, int spacedim>
224 void
225 approximate_second_derivative(const DoFHandler<dim, spacedim> &dof,
226 const InputVector &solution,
227 Vector<float> &derivative_norm,
228 const unsigned int component = 0);
229
230 /**
231 * This function calculates the <tt>order</tt>-th order approximate
232 * derivative and returns the full tensor for a single cell.
233 *
234 * The last parameter denotes the solution component, for which the gradient
235 * is to be computed. It defaults to the first component. For scalar
236 * elements, this is the only valid choice; for vector-valued ones, any
237 * component between zero and the number of vector components can be given
238 * here.
239 *
240 * In a parallel computation the @p solution vector needs to contain the
241 * locally relevant unknowns.
242 */
243 template <int dim, int spacedim, class InputVector, int order>
244 void
245 approximate_derivative_tensor(
246 const Mapping<dim, spacedim> &mapping,
247 const DoFHandler<dim, spacedim> &dof,
248 const InputVector &solution,
249 #ifndef _MSC_VER
250 const typename DoFHandler<dim, spacedim>::active_cell_iterator &cell,
251 #else
252 const TriaActiveIterator<dealii::DoFCellAccessor<dim, spacedim, false>>
253 &cell,
254 #endif
255 Tensor<order, dim> &derivative,
256 const unsigned int component = 0);
257
258 /**
259 * Same as above, with <tt>mapping=MappingQ@<dim@>(1)</tt>.
260 */
261 template <int dim, int spacedim, class InputVector, int order>
262 void
263 approximate_derivative_tensor(
264 const DoFHandler<dim, spacedim> &dof,
265 const InputVector &solution,
266 #ifndef _MSC_VER
267 const typename DoFHandler<dim, spacedim>::active_cell_iterator &cell,
268 #else
269 const TriaActiveIterator<dealii::DoFCellAccessor<dim, spacedim, false>>
270 &cell,
271 #endif
272 Tensor<order, dim> &derivative,
273 const unsigned int component = 0);
274
275 /**
276 * Return the norm of the derivative.
277 */
278 template <int dim, int order>
279 double
280 derivative_norm(const Tensor<order, dim> &derivative);
281
282 /**
283 * Exception
284 */
285 DeclException2(ExcVectorLengthVsNActiveCells,
286 int,
287 int,
288 << "The output vector needs to have a size equal "
289 "to the number of active cells of your triangulation "
290 "but has length "
291 << arg1 << "There are " << arg2
292 << " active cells in your triangulation.");
293 /**
294 * Exception
295 */
296 DeclExceptionMsg(ExcInsufficientDirections,
297 "While computing a finite difference approximation to "
298 "derivatives, the algorithm encountered a cell on which "
299 "the number of linearly "
300 "independent directions that span the matrix Y (discussed "
301 "in the documentation of the DerivativeApproximation "
302 "class) is not equal to dim. The matrix Y then is "
303 "rank deficient and can not be inverted. A common reason "
304 "why this might be happening is if a cell has neither "
305 "left/right (or up/down, or front/back) neighbors, for "
306 "example because the mesh is too coarse.");
307 } // namespace DerivativeApproximation
308
309
310
311 DEAL_II_NAMESPACE_CLOSE
312
313 #endif