Gradient discretisation method

Navier–Stokes differential equations used to simulate airflow around an obstruction.

Scope

Natural sciences Engineering
Astronomy Physics Chemistry Biology Geology
Applied mathematics
Continuum mechanics Chaos theory Dynamical systems
Social sciences
Economics Population dynamics

Classification

Types

By variable type
Ordinary Partial Differential-algebraic Integro-differential Fractional Linear Non-linear
Dependent and independent variables Autonomous Complex Coupled / Decoupled Exact Homogeneous / Nonhomogeneous
Features
Order Operator Notation

Relation to processes

Difference (discrete analogue)

Solution

General topics

Lyapunov / Asymptotic / Exponential stability
Rate of convergence
Series / Integral solutions

Solution methods

People

In numerical mathematics, the gradient discretisation method (GDM) is a framework which contains classical and recent discretisation schemes for diffusion problems of different kinds: linear or non-linear, steady-state or time-dependent. The schemes may be conforming or non-conforming and may rely on very general polygonal or polyhedral meshes.

Some core properties are required to prove the convergence of a GDM. Owing to these core properties, it is possible to prove the convergence of a GDM for standard elliptic and parabolic problems, linear or non-linear. As a consequence, any scheme entering the GDM framework is then known to converge on these problems; this occurs in the case of the conforming Finite Elements, the Raviart—Thomas Mixed Finite Elements, or the $P^{1}$ non-conforming Finite Elements, or in the case of more recent schemes, such as the Hybrid Mixed Mimetic or Nodal Mimetic methods, some Discrete Duality Finite Volume schemes, and some Multi-Point Flux Approximation schemes.

The example of a linear diffusion problem

Let us consider Poisson's equation in a bounded open domain $\Omega \subset \mathbb {R} ^{d}$ , with homogeneous Dirichlet boundary condition

\quad (1)\qquad \qquad -\Delta {\overline {u}}=f,

where $f\in L^{2}(\Omega )$ , and the solution ${\overline {u}}\in H_{0}^{1}(\Omega )$ is such that

\quad (2)\qquad \qquad \forall {\overline {v}}\in H_{0}^{1}(\Omega ),\qquad \int _{\Omega }\nabla {\overline {u}}(x)\cdot \nabla {\overline {v}}(x)dx=\int _{\Omega }f(x){\overline {v}}(x)dx.

A Gradient Discretization (GD) is defined by a triplet $D=(X_{D,0},\Pi _{D},\nabla _{D})$ , where:

the set of discrete unknowns $X_{D,0}$ is a finite dimensional real vector space,
the function reconstruction $\Pi _{D}~:~X_{D,0}\to L^{2}(\Omega )$ is a linear mapping that reconstructs, from an element of $X_{D,0}$ , a function over $\Omega$ ,
the gradient reconstruction $\nabla _{D}~:~X_{D,0}\to L^{2}(\Omega )^{d}$ is a linear mapping which reconstructs, from an element of $X_{D,0}$ , a "gradient" (vector-valued function) over $\Omega$ . This gradient reconstruction must be chosen such that $\Vert \nabla _{D}\cdot \Vert _{L^{2}(\Omega )^{d}}$ is a norm on $X_{D,0}$ .

The related Gradient Scheme for the approximation of (2) is given by: find $u\in X_{D,0}$ such that

\quad (3)\qquad \qquad \forall v\in X_{D,0},\qquad \int _{\Omega }\nabla _{D}u(x)\cdot \nabla _{D}v(x)dx=\int _{\Omega }f(x)\Pi _{D}v(x)dx.

The GDM is then in this case a nonconforming method for the approximation of (2), which includes the nonconforming finite element method. Note that the reciprocal is not true, in the sense that the GDM framework includes methods such that the function $\nabla _{D}u$ cannot be computed from the function $\Pi _{D}u$ .

The following error estimate, inspired by [Strang,1972], holds

\quad (4)\qquad \qquad \Vert \nabla {\overline {u}}-\nabla _{D}u_{D}\Vert _{L^{2}(\Omega )^{d}}\leq W_{D}(\nabla {\overline {u}})+2S_{D}({\overline {u}}),

and

\quad (5)\qquad \qquad \Vert {\overline {u}}-\Pi _{D}u_{D}\Vert _{L^{2}(\Omega )}\leq C_{D}W_{D}(\nabla {\overline {u}})+(C_{D}+1)S_{D}({\overline {u}}),

defining:

\quad (6)\qquad \qquad C_{D}=\max _{v\in X_{D,0}\setminus \{0\}}{\frac {\Vert \Pi _{D}v\Vert _{L^{2}(\Omega )}}{\Vert \nabla _{D}v\Vert _{L^{2}(\Omega )^{d}}}},

which measures the coercivity (discrete Poincaré constant),

\quad (7)\qquad \qquad \forall \varphi \in H_{0}^{1}(\Omega ),\,S_{D}(\varphi )=\min _{v\in X_{D,0}}\left(\Vert \Pi _{D}v-\varphi \Vert _{L^{2}(\Omega )}+\Vert \nabla _{D}v-\nabla \varphi \Vert _{L^{2}(\Omega )^{d}}\right),

which measures the interpolation error,

\quad (8)\qquad \qquad \forall \varphi \in H_{\operatorname {div} }(\Omega ),\,W_{D}(\varphi )=\max _{v\in X_{D,0}\setminus \{0\}}{\frac {\left|\int _{\Omega }\left(\nabla _{D}v(x)\cdot \varphi (x)+\Pi _{D}v(x)\operatorname {div} \varphi (x)\right)\,dx\right|}{\Vert \nabla _{D}v\Vert _{L^{2}(\Omega )^{d}}}},

which measures the defect of conformity.

Then the core properties which are sufficient for the convergence of the method are, for a family of GDs, the coercivity, the GD-consistency and the limit-conformity properties, as defined in the next section. These three core properties are sufficient to prove the convergence of the GDM for linear problems. For nonlinear problems (nonlinear diffusion, degenerate parabolic problems...), we add in the next section two other core properties which may be required.

The core properties allowing for the convergence of a GDM

Let $(D_{m})_{m\in \mathbb {N} }$ be a family of GDs, defined as above (generally associated with a sequence of regular meshes whose size tends to 0).

Coercivity

The sequence $(C_{D_{m}})_{m\in \mathbb {N} }$ (defined by (6)) remains bounded.

GD-consistency

For all $\varphi \in H_{0}^{1}(\Omega )$ , $\lim _{m\to \infty }S_{D_{m}}(\varphi )=0$ (defined by (7)).

Limit-conformity

For all $\varphi \in H_{\operatorname {div} }(\Omega )$ , $\lim _{m\to \infty }W_{D_{m}}(\varphi )=0$ (defined by (8)).

Compactness (needed for some nonlinear problems)

For all sequence $(u_{m})_{m\in \mathbb {N} }$ such that $u_{m}\in X_{D_{m},0}$ for all $m\in \mathbb {N}$ and $(\Vert u_{m}\Vert _{D_{m}})_{m\in \mathbb {N} }$ is bounded, then the sequence $(\Pi _{D_{m}}u_{m})_{m\in \mathbb {N} }$ is relatively compact in $L^2(\Omega)$ (this property implies the coercivity property).

Piecewise constant reconstruction (needed for some nonlinear problems)

Let $D=(X_{D,0},\Pi _{D},\nabla _{D})$ be a gradient discretisation as defined above. The operator $\Pi _{D}$ is a piecewise constant reconstruction if there exists a basis $(e_{i})_{i\in B}$ of $X_{D,0}$ and a family of disjoint subsets $(\Omega _{i})_{i\in B}$ of $\Omega$ such that $\Pi _{D}u=\sum _{i\in B}u_{i}\chi _{\Omega _{i}}$ for all $u=\sum _{i\in B}u_{i}e_{i}\in X_{D,0}$ , where $\chi _{\Omega _{i}}$ is the characteristic function of $\Omega _{i}$ .

Review of some problems which may be approximated by a GDM

We review some problems for which the GDM can be proved to converge when the above core properties are satisfied.

Nonlinear stationary diffusion problems

\quad \qquad \qquad -\operatorname {div} (\Lambda ({\overline {u}})\nabla {\overline {u}})=f

In this case, the GDM converges under the coercivity, GD-consistency, limit-conformity and compactness properties.

p-Laplace problem for p > 1

\quad \qquad \qquad -\operatorname {div} (|\nabla {\overline {u}}|^{p-2}\nabla {\overline {u}})=f

In this case, the core properties must be written, replacing $L^2(\Omega)$ by $L^{p}(\Omega )$ , $H_{0}^{1}(\Omega )$ by $W_{0}^{1,p}(\Omega )$ and $H_{\operatorname {div} }(\Omega )$ by $W_{\operatorname {div} }^{p'}(\Omega )$ with ${\frac {1}{p}}+{\frac {1}{p'}}=1$ , and the GDM converges only under the coercivity, GD-consistency and limit-conformity properties.

Linear and nonlinear heat equation

\quad \qquad \qquad \partial _{t}{\overline {u}}-\operatorname {div} (\Lambda ({\overline {u}})\nabla {\overline {u}})=f

In this case, the GDM converges under the coercivity, GD-consistency (adapted to space-time problems), limit-conformity and compactness (for the nonlinear case) properties.

Degenerate parabolic problems

Assume that $\beta$ and $\zeta$ are nondecreasing Lipschitz continuous functions:

\quad \qquad \qquad \partial _{t}\beta ({\overline {u}})-\Delta \zeta ({\overline {u}})=f

Note that, for this problem, the piecewise constant reconstruction property is needed, in addition to the coercivity, GD-consistency (adapted to space-time problems), limit-conformity and compactness properties.

Review of some numerical methods which are GDM

All the methods below satisfy the first four core properties of GDM (coercivity, GD-consistency, limit-conformity, compactness), and in some cases the fifth one (piecewise constant reconstruction).

Galerkin methods and conforming finite element methods

Let $V_{h}\subset H_{0}^{1}(\Omega )$ be spanned by the finite basis $(\psi _{i})_{i\in I}$ . The Galerkin method in $V_h$ is identical to the GDM where one defines

$X_{D,0}=\{u=(u_{i})_{i\in I}\}=\mathbb {R} ^{I},$
$\Pi _{D}u=\sum _{i\in I}u_{i}\psi _{i}$
$\nabla _{D}u=\sum _{i\in I}u_{i}\nabla \psi _{i}.$

In this case, $C_{D}$ is the constant involved in the continuous Poincaré inequality, and, for all $\varphi \in H_{\operatorname {div} }(\Omega )$ , $W_{D}(\varphi )=0$ (defined by (8)). Then (4) and (5) are implied by Céa's lemma.

The "mass-lumped" $P^{1}$ finite element case enters the framework of the GDM, replacing $\Pi _{D}u$ by ${\widetilde {\Pi }}_{D}u=\sum _{i\in I}u_{i}\chi _{\Omega _{i}}$ , where $\Omega _{i}$ is a dual cell centred on the vertex indexed by $i\in I$ . Using mass lumping allows to get the piecewise constant reconstruction property.

Nonconforming P¹ finite element

On a mesh $T$ which is a conforming set of simplices of $\mathbb {R} ^{d}$ , the nonconforming $P^{1}$ finite elements are defined by the basis $(\psi _{i})_{i\in I}$ of the functions which are affine in any $K\in T$ , and whose value at the centre of gravity of one given face of the mesh is 1 and 0 at all the others. Then the method enters the GDM framework with the same definition as in the case of the Galerkin method, except for the fact that $\nabla \psi _{i}$ must be understood as the "broken gradient" of $\psi_i$ , in the sense that it is the piecewise constant function equal in each simplex to the gradient of the affine function in the simplex.

Mixed finite element

The mixed finite element method consists in defining two discrete spaces, one for the approximation of $\nabla {\overline {u}}$ and another one for $\overline{u}$ . It suffices to use the discrete relations between these approximations to define a GDM. Using the low degree Raviart–Thomas basis functions allows to get the piecewise constant reconstruction property.

Mimetic finite difference method and nodal mimetic finite difference method

This family of methods is introduced by [Brezzi et al, 2005] and completed in [Lipnikov et al, 2014]. It allows the approximation of elliptic problems using a large class of polyhedral meshes. The proof that it enters the GDM framework is done in [Droniou et al, 2013].

References

F. Brezzi, K. Lipnikov, and M. Shashkov. Convergence of the mimetic finite difference method for diffusion problems on polyhedral meshes. SIAM J. Numer. Anal., 43(5):1872–1896, 2005.
J. Droniou, R. Eymard, T. Gallouët, and R. Herbin. Gradient schemes: a generic framework for the discretisation of linear, nonlinear and nonlocal elliptic and parabolic equations. Math. Models Methods Appl. Sci. (M3AS), 23(13):2395–2432, 2013.
K. Lipnikov, G. Manzini, and M. Shaskov. Mimetic finite difference method. J. Comput. Phys., 257-Part B:1163–1227, 2014.
G. Strang. Variational crimes in the finite element method. In The mathematical foundations of the finite element method with applications to partial differential equations (Proc. Sympos., Univ. Maryland, Baltimore, Md., 1972), pages 689–710. Academic Press, New York, 1972.

External links

The Gradient Discretisation Method by Jérôme Droniou, Robert Eymard, Thierry Gallouët, Cindy Guichard and Raphaèle Herbin

Numerical partial differential equations by method

Finite difference

Parabolic	Forward-time central-space (FTCS) Crank–Nicolson

Hyperbolic	Lax–Friedrichs Lax–Wendroff MacCormack Upwind Method of characteristics

Others	Alternating direction-implicit (ADI) Finite-difference time-domain (FDTD)

Finite volume

Finite element

Meshless/Meshfree

Smoothed-particle hydrodynamics (SPH)
Moving Particle Semi-implicit Method (MPS)
Material point method (MPM)

Domain decomposition

Others

This article is issued from Wikipedia - version of the 11/16/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.