switch to 2018 intel
[dealii.wiki.git] / Tensor-product-structures-for-polynomials-and-quadrature.md
1 # Rationale
2
3 Most of the local objects in dealii have a tensor product
4 structure. Quadrature formulas are tensor products of one-dimensional
5 formulas. Shape functions are tensor products of polynomials in
6 different coordinate directions. Even spaces like Nédéléc and
7 Raviart-Thomas have such structures in each component. Katharina
8 Kormann and Martin Kronbichler have shown that exploiting these
9 structures can boost performance of local integrals
10 considerably. Therefore, adapting finite element and quadrature
11 classes to their concepts is a valuable task.
12
13 An important ingredient required for the optimization of local
14 integrals is that the length of all loops is known at compile
15 time. Therefore, the number of quadrature points and the number of
16 shape functions must become template arguments.
17
18 The class `FEValues` was originally introduced to allow for
19 optimizations based on the internal structure of finite element shape
20 function spaces, but this was never exploited. Additionally, `FEValues`
21 stores a lot of data to avoid recomputation. Data, which is highly
22 redundant. At a time where computers had a single working thread and
23 computations were expensive, this was in part justified. Now, that
24 most algorithms become memory-bound, we must consider retiring
25 `FEValues`.
26
27 ## Discussion
28
29 - Implementation of *hp* methods
30 - Efficient implementation of methods where we do not have tensor
31   product structure
32   - XFEM
33   - Overlapping nonmatching grids
34 - Note: *hp* adaptivity is supported by the `FEEvaluation` class.
35
36 ## Design and limitations of the `FEEvaluation` class
37
38 The matrix-free implementation uses the class `FEEvaluation` instead of `FEValues`. Different from the `FEValues` class, information about the degrees of freedom and the mapping from physical to unit cell is precomputed and stored. The degrees of freedom are numbered MPI-local and the constraints are incorporated into the DoF list in order to provide direct array access into vectors.
39 This enables e.g. fast evaluation of the shape functions at the quadrature points. On the other hand, only values, gradients, etc. that are precomputed can be accessed while the `FEValues` object enables on-the-fly computations of more general evaluations.
40 The main task would therefore be to merge the different functionalities of the two classes.
41
42
43 # Tensor product quadrature
44
45 It is suggested to introduce a new class template inheriting from
46 `Quadrature`, say `TensorProductQuadrature`. In a compatibility mode,
47 this class fills the fields in `Quadrature` (deferred execution
48 preferred). Quadrature points are stored in a `TensorProductPoints`,
49 where the access operator `[]` returns a `Point<dim>` created on the
50 fly. Additionally, it allows direct access to the one-dimensional
51 point sets. Similarly, we can consider a class `TensorProductWeights`.
52
53 Note that while we are currently not making use of this (**this is false**: 
54 there are classes to integrate singularities which are not based on tensor 
55 product quadrature formulas...),
56 `Quadrature` is not restricted to tensor products. Therefore,
57 `TensorProductQuadrature` is not going to be an equivalent
58 replacement.
59
60 ## Discussion
61
62 * We will need anisotropic tensor products. Do we want an isotropic
63   class as well?
64 * If anisotropic, are variadic templates the only option?
65 * The order of the quadrature point (do we make any assumptions yet?)
66   - Currently: lexicographic, low to high abscissa
67   - Low to high weight for numerical stability?
68   - End points of intervals first to conform to finite elements?
69 * Not inheriting from `Quadrature` would on one hand mean that we have
70   two independent quadrature sets, on the other hand we would not need
71   to link to the library, which is important for off-loading.
72
73 ## Draft of the classes
74
75 The convention for the indices shall be that `d=1,...,dim`, `di`
76 enumerates the coordinates in direction `d`, and `i` enumerates all
77 quadrature points.
78
79 ```cpp
80 template <typename number, int dim, int...>
81 class TensorProductPoints
82 {
83   public:
84     template <typename number2>
85     void set_coordinates (const unsigned int d, const std::vector<number2>&);
86     
87     number operator() (const unsigned int d, const unsigned int di) const;
88     Point<dim> point(const unsigned int i) const;
89 };
90 ```
91
92 The class `TensorProductWeights` is similar and
93 `TensorProductQuadrature` combines the two.
94
95 # Tensor product structure of polynomials
96
97 As Katharina and Martin point out, combining tensor product quadrature
98 with tensor product polynomials can generate very efficient code. This
99 has been known to the spectral element community for a while, but
100 widely ignored by us. It is implemented in the matrix free framework,
101 but only for certain elements and with limited functionality. One goal
102 of these new structures is making efficient matrix free computations
103 available throughout the library.
104
105 ### Example: Lagrange polynomials
106
107 Given polynomials of degree `p-1` and `q` quadrature points in each
108 direction, the current `FEValues` in 3D computes and stores `p^3 q^3`
109 shape function values, three times as many derivatives and nine times
110 as many second derivatives. In (isotropic) tensor product
111 representation, we need `p q` values, derivatives, and second
112 derivatives. This means, that now even higher derivatives and 4D become
113 feasible. As for computation of these values, some polynomial spaces
114 allow for a recursive computation of the values of higher order
115 members. Thus, here is another point where we can reduce the
116 computational complexity by a factor up to `p`.
117
118 ### Example: vector valued elements
119
120 `FE_Nedelec` as well as `FE_RaviartThomas` can be implemented such
121 that each component is an anisotropic tensor product.
122
123 ### Example: `FE_DGP`
124
125 This example differs from the previous ones in that all multivariate
126 polynomials are still products of 1D ones, but that not all possible
127 combinations are admitted. This is true for serendipity elements as
128 well. For these we need truncated tensor products.
129
130 ## Discussion
131
132 - The matrix free code currently does a renumbering to tensor product
133   numbering of the shape functions, which is the inversion of a
134   similar process when we generate the functions. Should we reconsider
135   the ordering in `DoFHandler`?
136 - `FEEvaluation` currently knows the elements `FE_Q`, `FE_DGQ`, `FE_DGP` and `FE_Q_DG0`.

In the beginning the Universe was created. This has made a lot of people very angry and has been widely regarded as a bad move.

Douglas Adams


Typeset in Trocchi and Trocchi Bold Sans Serif.