3.2.2 Requirements for Finite Element Meshes

Such well pronounced requirements based on a different criterion can be formulated for a specific application of the finite element method. The basis is the maximum principle which is the most important property of solutions to convection-diffusion equations. In its simplest form it states that both the maximum and the minimum concentrations occur on the boundary or at the initial time. This implies that if the boundary and initial values are positive, the solution must be positive everywhere and concentrations may never reach negative values. It is desirable that the employed discretization also satisfies a maximum principle. As is well known, this is guaranteed, if the system matrix resulting from the discretization is an M-matrix^3.2 [69,125].

The system matrix $\mathbf{K}$ for a simple diffusion with a standard Galerkin weighted residual approach, linear elements, and backward Euler time discretization has the following form

$$\mathbf{K} = \frac{1}{\Delta t}\mathbf{M} + D \mathbf{S}$$ (3.8)

where $\mathbf{M}$ denotes the mass matrix, $\mathbf{S}$ is the stiffness matrix, and $D$ is the diffusion constant. $\mathbf{K}$ becomes an M-matrix if the mass matrix is lumped and $\mathbf{S}$ is an M-matrix. Since $\mathbf{S}$ only depends on the mesh this condition translates to a constraint on the mesh. The off-diagonal entries $s_{ij}, i \neq j$ of $\mathbf{S}$ must not be positive. These coefficients can be generally expressed as

$$s_{ij} = \sum_{elements} \int_{e} \nabla N_{i} \! \cdot \! \nabla N_{j} \, dA$$ (3.9)

where $N_{i}, N_{j}$ denote the basis functions and $A$ is the area (volume) of element $e$. The in-product $(\nabla N_{i} \cdot \nabla N_{j})$ has a simple geometrical meaning and leads to an angle criterion for each edge in the mesh, which was recently introduced by [189]. It is an important consideration in three-dimensional finite element mesh generation for diffusion applications with a high concentration gradient.

Criterion 3.3 (sum of dihedral angles)   Let $e_{i,j}$ be an edge with $n$ adjacent tetrahedra $t_{k}$. For each $t_{k}$ two planes exist which do not contain $e_{i,j}$ and which span a dihedral angle $\theta_{k}$. The two planes share an edge with length $l_{k}$. The sum over $k=1 \dots n$ of the cotangens of $\theta_{k}$ weighted by $l_{k}$ must be greater or equal than zero.

$$\sum_{k=1}^{n} l_{k} \cot \theta_{k} \geq 0$$ (3.10)

Figure 3.6 depicts an example where this criterion is violated for the interior edge $e_{i,j}$. Four adjacent tetrahedra exist of which two span a $90^{\circ}$ angle. Hence, $\cot \theta_{3} =0$ and $\cot \theta_{4} =0$. As one can see from the figure $\cot \theta_{1} = \cot \theta_{2} = - \frac{1}{\sqrt{2}}$ ($\theta_{1}$, $\theta_{2}$ are obtuse, $\sim 125.3^{\circ}$) and hence the total sum is negative.

In two dimensions (3.10) can be written as

$$\cot \theta_{1} + \cot \theta_{2} \geq 0$$ (3.11)

where $\theta_{1}$ and $\theta_{2}$ are the angles of two triangles sharing a common edge $e_{i,j}$ as shown in Fig. 3.5. It can be assumed that

$$0 < \theta_{1,2} < 180^{\circ}$$ (3.12)

and therefore

$$\sin\theta_{1} \sin\theta_{2} > 0$$ (3.13)

Hence, multiplying (3.11) with $\sin\theta_{1} \sin\theta_{2}$ results in

$$\sin\theta_{2}\cos\theta_{1} + \sin\theta_{1}\cos\theta_{2} \geq 0$$ (3.14)

which is equivalent to

$$\sin(\theta_{1}+\theta_{2}) \geq 0$$ (3.15)

Due to (3.12) and (3.15) the finite element mesh criterion (Crit. 3.3) can be expressed in two dimensions as

$$\theta_{1} + \theta_{2} \leq 180^{\circ}$$ (3.16)

Figure 3.5: Finite element mesh criterion for two dimensions.

In two dimensions (3.7) describes the relation between the circumcircle radius, the edge length, and the opposite angle in a triangle. In three dimensions a relation for the circumsphere radius, the edge length, and the opposite dihedral angle $\theta_{k}$ (which is important for Crit. 3.3) in a tetrahedron does not exist as was explained in Fig. 3.3. This leads to a very interesting conclusion. It can be shown due to the existing relation (3.7) that the finite element mesh requirement (Crit. 3.3) is in two dimensions identical to the box integration mesh requirement which is based on empty circumcircles (Crit. 3.1 and Delaunay Crit. 5.2). To see this equivalence of the angle condition (3.16) and the Delaunay criterion dependent on (3.7) consider the extreme case where (3.16) becomes

$$\theta_{1} + \theta_{2} = 180^{\circ}$$ (3.17)

It follows that

$$\sin \theta_{1} = \sin \theta_{2}$$ (3.18)

and furthermore with (3.7)

$$\frac{l_{ij}}{2R_{1}} = \frac{l_{ij}}{2R_{2}}$$ (3.19)

The two triangles with the common edge $e_{i,j}$ (Fig. 3.5) must possess circumcircles with equally sized radii. Because of (3.17) the circumcircles must be in fact identical. Each circumcircle passes therefore through all four vertices of the two triangles and the Delaunay criterion is ``just'' fulfilled. With a decreasing sum $(\theta_{1}+\theta_{2})$ the distance between the two circumcenters (centers of the circumcircles) increases and the Delaunay criterion is definitely satisfied.

As expected, in two dimensions the finite volume and the finite element method lead to the same discretization with identical requirements. They both rely on Delaunay meshes to fulfill the maximum principle. For other finite element applications than diffusion, like stationary problems or problems with less high gradients, the use of Delaunay meshes can be omitted. In three dimensions Crit. 3.3 and the Delaunay criterion are of quite different nature as will be shown with simple examples in the next section. In practice finite element mesh generators may generally try to avoid extremely obtuse (dihedral) angles and badly shaped elements without too much concern on the Delaunay property and without a technique to directly enforce Crit. 3.3. Such a technique remains open to further research.

Figure 3.6: $T_{6}$ tessellation and Crit. 3.3.

Figure 3.7: $T_{5}$ tessellation, no obtuse dihedral angles.