These html pages are based on the PhD thesis "Cluster-Based Parallelization of Simulations on Dynamically Adaptive Grids and Dynamic Resource Management" by Martin Schreiber.
There is also more information and a PDF version available.

2.12 Adaptive refining and coarsening matrices R and C

With a simulation on a dynamically adaptive grid, we refine and coarsen our cells during runtime by splitting triangles into two triangles and merging them respectively. Then, the conserved quantities require projection to the refined or restricted grid cells.

2.12.1 Coefficient matrix

We start by determining a way to compute the coefficients of the approximating solution on our reference triangle based on the weights of given basis functions. This also leads to computations of the weights of the basis functions from a given approximating solution.

We start by denoting the coefficients of the monomials which assemble the basis polynomials (see Section 2.3) φi(x,y) := (a,b)αi(a,b)xayb, with αi(a,b). Here, it holds that 0 a + b d, 0 a and 0 b. We construct a d × n coefficient matrix

        (   (0,0)   (0,0)       (0,0))
          α 1    α2     ... αN
        || α (11,0)  α(21,0)  ... α(N1,0)||
        ||   ..      ..     ..    ..  ||
        ||   .      .     .    .  ||
B (φ) := | α (01,1) α(20,1)  ... α(N0,1)|
        ||   ..      ..     ..    ..  ||
        ||   .      .     .    .  ||
        ( α (01,d)  α(20,d)  ... α(N0,d))
with the coefficients for each basis function polynomial given in a respective column and coefficients for identical monomials of basis functions in each row. With qi a single DoF corresponding to the basis function ϕi, we can then rewrite our approximated solution φ(x,y) := iqiφi(x,y) in the reference space to a matrix-vector product
⃗α = B (φ) ⃗q.
Then the entries α(a,b) in the vector ⃗α represent the coefficients of the monomials of our approximated solution φ(x,y) := iqiφi(x,y).

In case of only one conserved quantity, we are now able to compute the coefficients of the polynomial related to our approximating solution

          ∑d d∑-a
U(x,y) :=        ⃗α (a,b)xayb.
          a=0 b=0
with a matrix-vector product. For multiple conserved quantities, a matrix-matrix product can be used.

We use this matrix formulation for computing the basis function weights ⃗q k of the basis functions for a given approximating solution by inverting the coefficient matrix B(φ), yielding

⃗qk := B (φ )-1⃗α.

2.12.2 Affine transformations to and from the child space

pict              pict

Figure 2.5: Left image: parent’s reference space split for left and right child triangle. Right images: child reference spaces. Mapping to and from reference space can be expressed by scaling, rotation and translation.

Due to splits and joins, a transformation of the DoF to and from different triangles is required, see Fig. 2.5. We respectively denote the triangle space which is split as the parent triangle space and both split ones which have to be possibly joined as the children triangle spaces.


        (                )
         cosα   - sin α  0
R(α ) = (sinα    cosα   0)
           0      0     1

be a two-dimensional rotation matrix computing rotations in clockwise direction for positive α,

          (       )
           1  0  ξ
T (ξ,η) = (0  1  η)
           0  0  1

a translation matrix and

       ( s 0  0)
       (       )
S(s) =  0  s  0
        0  0  1

a scaling matrix. A transformation matrix returning the sampling point in the child’s left reference space if sampling in parent reference space is then given by

           (    )  (   )
PM    := R   3π  S  √2-- T (- 1,- 1)
 toLeft       4                2  2
with the corresponding function
                      (  )   (           )
                M       ξ      - ξ - η + 1
PtoLeft(ξ,η) := P toLeft ⋅ η  =     ξ - η     ,
applying the matrix at the point (ξ,η) given as parameters. E.g. this transforms the point (1,0) in the parents reference space, thus at the right triangle corner, to (0,1) in the parents reference space. An example is given in the left image of Fig. 2.5: First the left child’s origin is translated to the origin of the parent’s reference space, then the child’s space is scaled up followed by a final rotation.

For the right reference triangle, this yields

             (     )
  M             3-    ( √-)   (  1)
P toRight := R - 4 π  S   2  T  - 2
                        (ξ)    (  - ξ + η  )
PtoRight(ξ,η) := PMtoRight ⋅    =              .
                         η       - ξ - η + 1
Projections from the child triangles to parent triangles are then similarly given by
                               (  )    (  1    1    1)
  PfromLeft(ξ,η)  :=  (PM )-t1oLeft ⋅ ξ  =   - 21ξ + 21η + 21    and        (2.22)
                                 η(  )  - 2(ξ - 2η + 2   )
                       M -1         ξ      - 12ξ - 12η + 12
PfromRight(ξ,η)  :=  (P  )fromRight ⋅ η  =    1ξ - 1η + 1   .         (2.23)
                                            2    2    2

2.12.3 Prolongation to child space

Sampling of the child’s approximated solution using reference coordinates from the parent reference space then gives

φtoLeft(ξ,η) := φ (PtoLeft(ξ,η))    and    φtoRight(ξ,η) :=  φ(PtoRight(ξ,η))      (2.24)

By using a representation of the child’s basis functions in parent’s reference space, the refinement matrix is determined by first computing the polynomial coefficients for the approximating polynomial in parent space with B(φ) and then reconstructing the weight qk for the child’s polynomials by using the representation of the child’s polynomials φ

toLeft(ξ,η) in the parent space:

                - 1                                  -1
Rleft := B (φtoLeft)  B(φ)    and    Rright := B (φtoRight)  B(φ )         (2.25)

2.12.4 Restriction to the parent space

Restriction operations can be computed in a similar manner to the prolongation (see Eq. (2.25)). However, due to the discontinuity at the shared edges of the children, the approximated solution of both children cannot be represented by a single parent triangle.

We choose a restriction which is averaging the polynomial basis functions of both children extended to the parent’s support yielding

φtoLeft(ξ,η) :=  φ(PtoLeft(ξ,η))      φtoRight(ξ,η ) := φ(PtoRight(ξ,η))      (2.26)
C      :=  1-(B (φ)-1B (φ      ) + B (φ )-1B(φ        ))
  parent   2            fromLeft              fromRight

Such an averaging is obviously not able to reconstruct the polynomial accurately in case of discontinuities at the shared edges as this is typically the case for our DG simulations. We want to emphasize, that other coarsening computations, e.g. reconstructing the basis polynomial with minimization with respect to a norm, can yield improved results. With improved reconstruction methods being transparent to the determined interface requirements and since this section focuses on the determination of the basic requirements for the computation of DG-based simulations, we continue using this coarsening method.

The derived restriction and prolongation matrices can be applied transparently to either nodal or modal basis functions since their construction is based on the coefficient matrix, which is again based on the coefficients of the basis polynomials.

2.12.5 Adaptivity based on error indicators

To trigger refining or coarsening requests on our grid, we use error indicators to distinguish between refining, coarsening or no cell modifications.

For this work, we considered two different adaptivity indicators:

If an indicator exceeds a particular refinement threshold value, a split of the cell is requested. In case of undershooting the coarsening threshold value, the indicator allows joining this cell with an adjacent one in case of both cells agreeing in the coarsening process.