Debian Codegraph @

include/deal.II/matrix_free/shape_info.h

raw
1 // ------------------------------------------------------------------------
2 //
3 // SPDX-License-Identifier: LGPL-2.1-or-later
4 // Copyright (C) 2012 - 2024 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
16 #ifndef dealii_matrix_free_shape_info_h
17 #define dealii_matrix_free_shape_info_h
18
19
20 #include <deal.II/base/config.h>
21
22 #include <deal.II/base/aligned_vector.h>
23 #include <deal.II/base/exceptions.h>
24 #include <deal.II/base/quadrature.h>
25 #include <deal.II/base/table.h>
26 #include <deal.II/base/vectorization.h>
27
28
29 DEAL_II_NAMESPACE_OPEN
30
31
32 // forward declaration
33 template <int dim, int spacedim>
34 class FiniteElement;
35
36
37 namespace internal
38 {
39 namespace MatrixFreeFunctions
40 {
41 /**
42 * An enum that encodes the type of element detected during
43 * initialization. FEEvaluation will select the most efficient algorithm
44 * based on the given element type.
45 *
46 * There is an implied ordering in the type ElementType::tensor_symmetric
47 * in the sense that both ElementType::tensor_symmetric_collocation and
48 * ElementType::tensor_symmetric_hermite are also of type
49 * ElementType::tensor_symmetric. Likewise, a configuration of type
50 * ElementType::tensor_symmetric is also of type
51 * ElementType::tensor_general. As a consequence, we support `<=`
52 * operations between the types with this sorting, but not against the
53 * even higher indexed types such as ElementType::truncated_tensor.
54 *
55 * @ingroup matrixfree
56 */
57 enum ElementType
58 {
59 /**
60 * Tensor product shape function where the shape value evaluation in the
61 * quadrature point corresponds to the identity operation and no
62 * interpolation needs to be performed (collocation approach, also
63 * called spectral evaluation). This is for example the case for an
64 * element with nodes in the Gauss-Lobatto support points and
65 * integration in the Gauss-Lobatto quadrature points of the same order.
66 */
67 tensor_symmetric_collocation = 0,
68
69 /**
70 * Symmetric tensor product shape functions fulfilling a Hermite
71 * identity with values and first derivatives zero at the element end
72 * points in 1d.
73 */
74 tensor_symmetric_hermite = 1,
75
76 /**
77 * Usual tensor product shape functions whose shape values and
78 * quadrature points are symmetric about the midpoint of the unit
79 * interval 0.5
80 */
81 tensor_symmetric = 2,
82
83 /**
84 * For function spaces that are not equivalent to a polynom of degree p,
85 * which the assumption of collocation is.
86 */
87 tensor_symmetric_no_collocation = 3,
88
89 /**
90 * Tensor product shape functions without further particular properties
91 */
92 tensor_general = 4,
93
94 /**
95 * Polynomials of complete degree rather than tensor degree which can be
96 * described by a truncated tensor product
97 */
98 truncated_tensor = 5,
99
100 /**
101 * Tensor product shape functions that are symmetric about the midpoint
102 * of the unit interval 0.5 that additionally add a constant shape
103 * function according to FE_Q_DG0.
104 */
105 tensor_symmetric_plus_dg0 = 6,
106
107 /**
108 * Special case of the FE_RaviartThomasNodal element with anisotropic
109 * tensor product shape functions, i.e degree (k + 1) in normal direction,
110 * and k in tangential direction.
111 */
112 tensor_raviart_thomas = 7,
113
114 /**
115 * Shape functions without a tensor product properties.
116 */
117 tensor_none = 8
118
119
120 };
121
122
123
124 /**
125 * This struct stores the shape functions, their gradients and Hessians
126 * evaluated for a one-dimensional section of a tensor product finite
127 * element and tensor product quadrature formula in reference
128 * coordinates. This data structure also includes the evaluation of
129 * quantities at the cell boundary and on the sub-interval $(0, 0.5)$ and
130 * $(0.5, 1)$ for face integrals.
131 */
132 template <typename Number>
133 struct UnivariateShapeData
134 {
135 /**
136 * Empty constructor. Sets default configuration.
137 */
138 UnivariateShapeData();
139
140 /**
141 * Return the memory consumption of this class in bytes.
142 */
143 std::size_t
144 memory_consumption() const;
145
146 /**
147 * Evaluate the finite element shape functions at the points of the
148 * given quadrature formula, filling the fields
149 * shape_[values,gradients,hessians] and related information.
150 *
151 * The two last arguments 'lexicographic' and 'direction' are used to
152 * describe the unknowns along a single dimension, and the respective
153 * direction of derivatives.
154 */
155 template <int dim, int spacedim>
156 void
157 evaluate_shape_functions(const FiniteElement<dim, spacedim> &fe,
158 const Quadrature<1> &quad,
159 const std::vector<unsigned int> &lexicographic,
160 const unsigned int direction);
161
162 /**
163 * Evaluate the auxiliary polynomial space associated with the Lagrange
164 * polynomials in points of the given quadrature formula, filling the
165 * fields shape_[gradients,hessians]_collocation and related
166 * information.
167 */
168 template <int dim, int spacedim>
169 void
170 evaluate_collocation_space(const FiniteElement<dim, spacedim> &fe,
171 const Quadrature<1> &quad,
172 const std::vector<unsigned int> &lexicographic,
173 const unsigned int direction);
174
175 /**
176 * Check whether we have symmetries in the shape values. In that case,
177 * also fill the shape_???_eo fields.
178 */
179 bool
180 check_and_set_shapes_symmetric();
181
182 /**
183 * Check whether symmetric 1d basis functions are such that the shape
184 * values form a diagonal matrix, i.e., the nodal points are collocated
185 * with the quadrature points. This allows for specialized algorithms
186 * that save some operations in the evaluation.
187 */
188 bool
189 check_shapes_collocation() const;
190
191 /**
192 * Encodes the type of element detected at construction. FEEvaluation
193 * will select the most efficient algorithm based on the given element
194 * type.
195 */
196 ElementType element_type;
197
198 /**
199 * Stores the shape values of the 1d finite element evaluated at all 1d
200 * quadrature points. The length of
201 * this array is <tt>n_dofs_1d * n_q_points_1d</tt> and quadrature
202 * points are the index running fastest.
203 */
204 AlignedVector<Number> shape_values;
205
206 /**
207 * Stores the shape gradients of the 1d finite element evaluated at all
208 * 1d quadrature points. The length of
209 * this array is <tt>n_dofs_1d * n_q_points_1d</tt> and quadrature
210 * points are the index running fastest.
211 */
212 AlignedVector<Number> shape_gradients;
213
214 /**
215 * Stores the shape Hessians of the 1d finite element evaluated at all
216 * 1d quadrature points. The length of
217 * this array is <tt>n_dofs_1d * n_q_points_1d</tt> and quadrature
218 * points are the index running fastest.
219 */
220 AlignedVector<Number> shape_hessians;
221
222 /**
223 * Stores the shape gradients of the shape function space associated to
224 * the quadrature (collocation), given by FE_DGQ<1>(Quadrature<1>).
225 */
226 AlignedVector<Number> shape_gradients_collocation;
227
228 /**
229 * Stores the shape hessians of the shape function space associated to
230 * the quadrature (collocation), given by FE_DGQ<1>(Quadrature<1>).
231 */
232 AlignedVector<Number> shape_hessians_collocation;
233
234 /**
235 * Stores the shape values in a different format, namely the so-called
236 * even-odd scheme where the symmetries in shape_values are used for
237 * faster evaluation.
238 */
239 AlignedVector<Number> shape_values_eo;
240
241 /**
242 * Stores the shape gradients in a different format, namely the
243 * so-called even-odd scheme where the symmetries in shape_gradients are
244 * used for faster evaluation.
245 */
246 AlignedVector<Number> shape_gradients_eo;
247
248 /**
249 * Stores the shape second derivatives in a different format, namely the
250 * so-called even-odd scheme where the symmetries in shape_hessians are
251 * used for faster evaluation.
252 */
253 AlignedVector<Number> shape_hessians_eo;
254
255 /**
256 * Stores the shape gradients of the shape function space associated to
257 * the quadrature (collocation), given by FE_DGQ<1>(Quadrature<1>). This
258 * array provides an alternative representation of the
259 * shape_gradients_collocation field in the even-odd format.
260 */
261 AlignedVector<Number> shape_gradients_collocation_eo;
262
263 /**
264 * Stores the shape hessians of the shape function space associated to
265 * the quadrature (collocation), given by FE_DGQ<1>(Quadrature<1>). This
266 * array provides an alternative representation of the
267 * shape_hessians_collocation field in the even-odd format.
268 */
269 AlignedVector<Number> shape_hessians_collocation_eo;
270
271 /**
272 * Stores the inverse transformation from the data at quadrature points
273 * to the basis defined by the shape_values fields. The data at
274 * quadrature points is interpreted either implicitly by its polynomial
275 * interpolation, or explicitly in terms of separate polynomials such as
276 * with the `_collocation` fields. The size of the array equals the
277 * layout of the `shape_values` array, and it is combined with the shape
278 * values array such that this matrix is the pseudo inverse of
279 * shape_values. In case the number of 1d quadrature points equals the
280 * size of the basis, this array is exactly the inverse of the
281 * shape_values array. The length of this array is <tt>n_dofs_1d *
282 * n_q_points_1d</tt> and quadrature points are the index running
283 * fastest.
284 */
285 AlignedVector<Number> inverse_shape_values;
286
287 /**
288 * Stores the even-odd variant of the `inverse_shape_values` field.
289 */
290 AlignedVector<Number> inverse_shape_values_eo;
291
292 /**
293 * Collects all data of 1d shape values evaluated at the point 0 and 1
294 * (the vertices) in one data structure. The sorting of data is to
295 * start with the values, then gradients, then second derivatives.
296 */
297 std::array<AlignedVector<Number>, 2> shape_data_on_face;
298
299 /**
300 * Collects all data of 1d nodal shape values (defined by the Lagrange
301 * polynomials in the points of the quadrature rule) evaluated at the
302 * point 0 and 1 (the vertices) in one data structure.
303 *
304 * This data structure can be used to interpolate from the cell to the
305 * face quadrature points. The sorting of data is to start with the
306 * values, then gradients, then second derivatives.
307 */
308 std::array<AlignedVector<Number>, 2> quadrature_data_on_face;
309
310 /**
311 * Stores one-dimensional values of shape functions on subface. Since
312 * there are two subfaces, store two variants.
313 */
314 std::array<AlignedVector<Number>, 2> values_within_subface;
315
316 /**
317 * Stores one-dimensional gradients of shape functions on subface. Since
318 * there are two subfaces, store two variants.
319 */
320 std::array<AlignedVector<Number>, 2> gradients_within_subface;
321
322 /**
323 * Stores one-dimensional gradients of shape functions on subface. Since
324 * there are two subfaces, store two variants.
325 */
326 std::array<AlignedVector<Number>, 2> hessians_within_subface;
327
328 /**
329 * A 1d subface interpolation matrices to the first and second quadrant.
330 * This data structure is only set up for FE_Q for dim > 1.
331 */
332 std::array<AlignedVector<Number>, 2> subface_interpolation_matrices;
333
334 /**
335 * Same as above but stored in a scalar format independent of the type of
336 * Number
337 */
338 std::array<AlignedVector<typename dealii::internal::VectorizedArrayTrait<
339 Number>::value_type>,
340 2>
341 subface_interpolation_matrices_scalar;
342
343 /**
344 * We store a copy of the one-dimensional quadrature formula
345 * used for initialization.
346 */
347 Quadrature<1> quadrature;
348
349 /**
350 * Stores the degree of the element.
351 */
352 unsigned int fe_degree;
353
354 /**
355 * Stores the number of quadrature points per dimension.
356 */
357 unsigned int n_q_points_1d;
358
359 /**
360 * Indicates whether the basis functions are nodal in 0 and 1, i.e., the
361 * end points of the unit cell.
362 */
363 bool nodal_at_cell_boundaries;
364
365 /**
366 * Stores the shape values of the finite element evaluated at all
367 * quadrature points for all faces and orientations (no tensor-product
368 * structure exploited).
369 */
370 Table<3, Number> shape_values_face;
371
372 /**
373 * Stores the shape gradients of the finite element evaluated at all
374 * quadrature points for all faces, orientations, and directions
375 * (no tensor-product structure exploited).
376 */
377 Table<3, Number> shape_gradients_face;
378 };
379
380
381
382 /**
383 * This struct stores a tensor (Kronecker) product view of the finite
384 * element and quadrature formula used for evaluation. It is based on a
385 * single or a collection of UnivariateShapeData object(s) that describe
386 * one-dimensional ingredients, plus some additional information about how
387 * these are combined and how indices are laid out in the multi-dimensional
388 * case such as the hierarchical -> lexicographic ordering of FE_Q.
389 *
390 * @ingroup matrixfree
391 */
392 template <typename Number>
393 struct ShapeInfo
394 {
395 /**
396 * Encodes the type of element detected at construction. FEEvaluation
397 * will select the most efficient algorithm based on the given element
398 * type.
399 */
400 ElementType element_type;
401
402 /**
403 * Empty constructor. Does nothing.
404 */
405 ShapeInfo();
406
407 /**
408 * Constructor that initializes the data fields using the reinit method.
409 */
410 template <int dim, int spacedim, int dim_q>
411 ShapeInfo(const Quadrature<dim_q> &quad,
412 const FiniteElement<dim, spacedim> &fe,
413 const unsigned int base_element = 0);
414
415 /**
416 * Initializes the data fields. Takes a one-dimensional quadrature
417 * formula and a finite element as arguments and evaluates the shape
418 * functions, gradients and Hessians on the one-dimensional unit cell.
419 * This function assumes that the finite element is derived from a
420 * one-dimensional element by a tensor product and that the zeroth shape
421 * function in zero evaluates to one.
422 */
423 template <int dim, int spacedim, int dim_q>
424 void
425 reinit(const Quadrature<dim_q> &quad,
426 const FiniteElement<dim, spacedim> &fe_dim,
427 const unsigned int base_element = 0);
428
429 /**
430 * Return whether an element is supported by MatrixFree.
431 *
432 * The following scalar elements are supported:
433 * - FE_Nothing, FE_DGP, and FE_Q_DG0
434 * - polynomial tensor-product elements based on
435 * Polynomials::Polynomial (FE_Q, FE_DGQ, FE_DGQArbitraryNodes,
436 * FE_DGQHermite, FE_DGQLegendre) or Polynomials::PiecewisePolynomial
437 * (FE_Q_iso_Q1).
438 * - elements for simplex, pyramids, and wedges (FE_SimplexP,
439 * FE_SimplexDGP, FE_PyramidP, FE_PyramidDGP, FE_WedgeP, FE_WedgeDGP)
440 *
441 * In the case of vectorial elements, FE_RaviartThomasNodal
442 * and FESystem with base elements from the scalar elements
443 * listed above are supported.
444 */
445 template <int dim, int spacedim>
446 static bool
447 is_supported(const FiniteElement<dim, spacedim> &fe);
448
449 /**
450 * Compute a table with numbers of re-orientation for all versions of
451 * face flips, orientation, and rotation (relating only to 3d elements).
452 */
453 static Table<2, unsigned int>
454 compute_orientation_table(const unsigned int n_points_per_dim);
455
456 /**
457 * Return data of univariate shape functions which defines the
458 * dimension @p dimension of tensor product shape functions
459 * regarding vector component @p component of the underlying
460 * finite element.
461 */
462 const UnivariateShapeData<Number> &
463 get_shape_data(const unsigned int dimension = 0,
464 const unsigned int component = 0) const;
465
466 /**
467 * Return the memory consumption of this class in bytes.
468 */
469 std::size_t
470 memory_consumption() const;
471
472 /**
473 * Renumbering from deal.II's numbering of cell degrees of freedom to
474 * lexicographic numbering used inside the FEEvaluation schemes of the
475 * underlying element in the DoFHandler. For vector-valued elements, the
476 * renumbering starts with a lexicographic numbering of the first
477 * component, then everything of the second component, and so on.
478 */
479 std::vector<unsigned int> lexicographic_numbering;
480
481 /**
482 * Stores data of univariate shape functions defining the
483 * underlying tensor product finite element.
484 */
485 std::vector<UnivariateShapeData<Number>> data;
486
487 /**
488 * Grants access to univariate shape function data of given
489 * dimension and vector component. Rows identify dimensions and
490 * columns identify vector components.
491 */
492 dealii::Table<2, UnivariateShapeData<Number> *> data_access;
493
494 /**
495 * Stores the number of space dimensions.
496 */
497 unsigned int n_dimensions;
498
499 /**
500 * Stores the number of vector components of the underlying
501 * vector-valued finite element.
502 */
503 unsigned int n_components;
504
505 /**
506 * Stores the number of quadrature points in @p dim dimensions for a
507 * cell.
508 */
509 unsigned int n_q_points;
510
511 /**
512 * Stores the number of DoFs per cell of the scalar element in @p dim
513 * dimensions.
514 */
515 unsigned int dofs_per_component_on_cell;
516
517 /**
518 * Stores the number of quadrature points per face in @p dim dimensions.
519 */
520 unsigned int n_q_points_face;
521
522 /**
523 * Stores the number of quadrature points of a face in @p dim dimensions
524 * for simplex, wedge and pyramid reference cells.
525 */
526 std::vector<unsigned int> n_q_points_faces;
527
528 /**
529 * Stores the number of DoFs per face in @p dim dimensions.
530 */
531 unsigned int dofs_per_component_on_face;
532
533 /**
534 * For nodal basis functions with nodes located at the boundary of the
535 * unit cell, face integrals that involve only the values of the shape
536 * functions (approximations of first derivatives in DG) do not need to
537 * load all degrees of freedom of the cell but rather only the degrees
538 * of freedom located on the face. While it would also be possible to
539 * compute these indices on the fly, we choose to simplify the code and
540 * store the indirect addressing in this class.
541 *
542 * The first table index runs through the faces of a cell, and the
543 * second runs through the nodal degrees of freedom of the face, using
544 * @p dofs_per_face entries.
545 *
546 * The indices stored in this member variable are as follows. Consider
547 * for example a 2d element of degree 3 with the following degrees of
548 * freedom in lexicographic numbering:
549 * @code
550 * 12 13 14 15
551 * 8 9 10 11
552 * 4 5 6 7
553 * 0 1 2 3
554 * @endcode
555 *
556 * The first row stores the indices on the face with index 0, i.e., the
557 * numbers <code>0, 4, 8, 12</code>, the second row holds the indices
558 * <code>3, 7, 11, 15</code> for face 1, the third row holds the indices
559 * <code>0, 1, 2, 3</code> for face 2, and the last (fourth) row holds
560 * the indices <code>12, 13, 14, 15</code>. Similarly, the indices are
561 * stored in 3d. (Note that the y faces in 3d use indices reversed in
562 * terms of the lexicographic numbers due to the orientation of the
563 * coordinate system.)
564 *
565 * @note This object is only filled in case @p nodal_at_cell_boundaries
566 * evaluates to @p true.
567 */
568 dealii::Table<2, unsigned int> face_to_cell_index_nodal;
569
570 /**
571 * The @p face_to_cell_index_nodal provides a shortcut for the
572 * evaluation of values on the faces. For Hermite-type basis functions,
573 * one can go one step further and also use shortcuts to get derivatives
574 * more cheaply where only two layers of degrees of freedom contribute
575 * to the derivative on the face. In the lexicographic ordering, the
576 * respective indices is in the next "layer" of degrees of freedom as
577 * compared to the nodal values. This array stores the indirect
578 * addressing of both the values and the gradient.
579 *
580 * The first table index runs through the faces of a cell, and the
581 * second runs through the pairs of the nodal degrees of freedom of the
582 * face and the derivatives, using <code>2*dofs_per_face</code> entries.
583 *
584 * The indices stored in this member variable are as follows. Consider
585 * for example a 2d element of degree 3 with the following degrees of
586 * freedom in lexicographic numbering:
587 * @code
588 * 20 21 22 23 24
589 * 15 16 17 18 19
590 * 10 11 12 13 14
591 * 5 6 7 8 9
592 * 0 1 2 3 4
593 * @endcode
594 *
595 * The first row stores the indices for values and gradients on the face
596 * with index 0, i.e., the numbers <code>0, 1, 5, 6, 10, 11, 15, 16, 20,
597 * 21</code>, the second row holds the indices <code>4, 3, 9, 8, 14, 13,
598 * 19, 18, 24, 23</code> for face 1, the third row holds the indices
599 * <code>0, 5, 1, 6, 2, 7, 3, 8, 4, 9</code> for face 2, and the last
600 * (fourth) row holds the indices <code>20, 15, 21, 16, 22, 17, 23, 18,
601 * 24, 19</code>. Similarly, the indices are stored in 3d. (Note that
602 * the y faces in 3d use indices reversed in terms of the lexicographic
603 * numbers due to the orientation of the coordinate system.)
604 *
605 * @note This object is only filled in case @p element_type evaluates to
606 * @p tensor_symmetric_hermite.
607 */
608 dealii::Table<2, unsigned int> face_to_cell_index_hermite;
609
610 /**
611 * For unknowns located on faces, the basis functions are not
612 * in the correct order if a face is not in the standard orientation
613 * to a given element. This data structure is used to re-order the
614 * basis functions to represent the correct order.
615 */
616 dealii::Table<2, unsigned int> face_orientations_dofs;
617
618 /**
619 * For interpretation of values at quadrature points, the order of
620 * points is not correct if a face is not in the standard orientation to
621 * a given element. This data structure is used to re-order the
622 * quadrature points to represent the correct order.
623 */
624 dealii::Table<2, unsigned int> face_orientations_quad;
625 };
626
627
628
629 // ------------------------------------------ inline functions
630
631 template <typename Number>
632 inline const UnivariateShapeData<Number> &
633 ShapeInfo<Number>::get_shape_data(const unsigned int dimension,
634 const unsigned int component) const
635 {
636 AssertDimension(n_dimensions, data_access.size(0));
637 AssertDimension(n_components, data_access.size(1));
638 AssertIndexRange(dimension, n_dimensions);
639 AssertIndexRange(component, n_components);
640 return *(data_access(dimension, component));
641 }
642
643 } // end of namespace MatrixFreeFunctions
644
645 } // end of namespace internal
646
647 DEAL_II_NAMESPACE_CLOSE
648
649 #endif