Gradient discretisation method

In numerical mathematics, the gradient discretisation method (GDM) is a framework which contains classical and recent numerical schemes for diffusion problems of various 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 (or may even be meshless).

Exact solution

of the p-Laplace problem on the domain [0,1] with (black line) and approximate one (blue line) computed with the first degree discontinuous Galerkin method plugged into the GDM (uniform mesh with 6 elements).

Some core properties are required to prove the convergence of a GDM. These core properties enable complete proofs of convergence of the GDM for elliptic and parabolic problems, linear or non-linear. For linear problems, stationary or transient, error estimates can be established based on three indicators specific to the GDM [1] (the quantities , and , see below). For non-linear problems, the proofs are based on compactness techniques and do not require any non-physical strong regularity assumption on the solution or the model data.[2] Non-linear models for which such convergence proof of the GDM have been carried out comprise: the Stefan problem which is modelling a melting material, two-phase flows in porous media, the Richards equation of underground water flow, the fully non-linear Leray—Lions equations.[3]

Any scheme entering the GDM framework is then known to converge on all these problems. This applies in particular to conforming Finite Elements, Mixed Finite Elements, nonconforming Finite Elements, and, in the case of more recent schemes, the Discontinuous Galerkin method, Hybrid Mixed Mimetic method, the Nodal Mimetic Finite Difference method, some Discrete Duality Finite Volume schemes, and some Multi-Point Flux Approximation schemes

The example of a linear diffusion problem

edit

Consider Poisson's equation in a bounded open domain  , with homogeneous Dirichlet boundary condition

  (1)

where  . The usual sense of weak solution [4] to this model is:

  (2)

In a nutshell, the GDM for such a model consists in selecting a finite-dimensional space and two reconstruction operators (one for the functions, one for the gradients) and to substitute these discrete elements in lieu of the continuous elements in (2). More precisely, the GDM starts by defining a Gradient Discretization (GD), which is a triplet  , where:

  • the set of discrete unknowns   is a finite dimensional real vector space,
  • the function reconstruction   is a linear mapping that reconstructs, from an element of  , a function over  ,
  • the gradient reconstruction   is a linear mapping which reconstructs, from an element of  , a "gradient" (vector-valued function) over  . This gradient reconstruction must be chosen such that   is a norm on  .

The related Gradient Scheme for the approximation of (2) is given by: find   such that

  (3)

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   cannot be computed from the function  .

The following error estimate, inspired by G. Strang's second lemma,[5] holds

  (4)

and

  (5)

defining:

  (6)

which measures the coercivity (discrete Poincaré constant),

  (7)

which measures the interpolation error,

  (8)

which measures the defect of conformity.

Note that the following upper and lower bounds of the approximation error can be derived:

  (9)

Then the core properties which are necessary and 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. More generally, these three core properties are sufficient to prove the convergence of the GDM for linear problems and for some nonlinear problems like the  -Laplace problem. For nonlinear problems such as 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

edit

Let   be a family of GDs, defined as above (generally associated with a sequence of regular meshes whose size tends to 0).

Coercivity

edit

The sequence   (defined by (6)) remains bounded.

GD-consistency

edit

For all  ,   (defined by (7)).

Limit-conformity

edit

For all  ,   (defined by (8)). This property implies the coercivity property.

Compactness (needed for some nonlinear problems)

edit

For all sequence   such that   for all   and   is bounded, then the sequence   is relatively compact in   (this property implies the coercivity property).

Piecewise constant reconstruction (needed for some nonlinear problems)

edit

Let   be a gradient discretisation as defined above. The operator   is a piecewise constant reconstruction if there exists a basis   of   and a family of disjoint subsets   of   such that   for all  , where   is the characteristic function of  .

Some non-linear problems with complete convergence proofs of the GDM

edit

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

Nonlinear stationary diffusion problems

edit
 

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

p-Laplace problem for p > 1

edit
 

In this case, the core properties must be written, replacing   by  ,   by   and   by   with  , and the GDM converges only under the coercivity, GD-consistency and limit-conformity properties.

Linear and nonlinear heat equation

edit
 

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

edit

Assume that   and   are nondecreasing Lipschitz continuous functions:

 

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

edit

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

edit

Let   be spanned by the finite basis  . The Galerkin method in   is identical to the GDM where one defines

  •  
  •  
  •  

In this case,   is the constant involved in the continuous Poincaré inequality, and, for all  ,   (defined by (8)). Then (4) and (5) are implied by Céa's lemma.

The "mass-lumped"   finite element case enters the framework of the GDM, replacing   by  , where   is a dual cell centred on the vertex indexed by  . Using mass lumping allows to get the piecewise constant reconstruction property.

Nonconforming finite element

edit

On a mesh   which is a conforming set of simplices of  , the nonconforming   finite elements are defined by the basis   of the functions which are affine in any  , and whose value at the centre of gravity of one given face of the mesh is 1 and 0 at all the others (these finite elements are used in [Crouzeix et al][6] for the approximation of the Stokes and Navier-Stokes equations). Then the method enters the GDM framework with the same definition as in the case of the Galerkin method, except for the fact that   must be understood as the "broken gradient" of  , 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

edit

The mixed finite element method consists in defining two discrete spaces, one for the approximation of   and another one for  .[7] 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.

Discontinuous Galerkin method

edit

The Discontinuous Galerkin method consists in approximating problems by a piecewise polynomial function, without requirements on the jumps from an element to the other.[8] It is plugged in the GDM framework by including in the discrete gradient a jump term, acting as the regularization of the gradient in the distribution sense.

Mimetic finite difference method and nodal mimetic finite difference method

edit

This family of methods is introduced by [Brezzi et al][9] and completed in [Lipnikov et al].[10] 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].[2]

See also

edit

References

edit
  1. ^ R. Eymard, C. Guichard, and R. Herbin. Small-stencil 3d schemes for diffusive flows in porous media. M2AN, 46:265–290, 2012.
  2. ^ a b 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.
  3. ^ J. Leray and J. Lions. Quelques résultats de Višik sur les problèmes elliptiques non linéaires par les méthodes de Minty-Browder. Bull. Soc. Math. France, 93:97–107, 1965.
  4. ^ H. Brezis. Functional analysis, Sobolev spaces and partial differential equations. Universitext. Springer, New York, 2011.
  5. ^ 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.
  6. ^ M. Crouzeix and P.-A. Raviart. Conforming and nonconforming finite element methods for solving the stationary Stokes equations. I. Rev. Française Automat. Informat. Recherche Opérationnelle Sér. Rouge, 7(R-3):33–75, 1973.
  7. ^ P.-A. Raviart and J. M. Thomas. A mixed finite element method for 2nd order elliptic problems. In Mathematical aspects of finite element methods (Proc. Conf., Consiglio Naz. delle Ricerche (C.N.R.), Rome, 1975), pages 292–315. Lecture Notes in Math., Vol. 606. Springer, Berlin, 1977.
  8. ^ D. A. Di Pietro and A. Ern. Mathematical aspects of discontinuous Galerkin methods, volume 69 of Mathématiques & Applications (Berlin) [Mathematics & Applications]. Springer, Heidelberg, 2012.
  9. ^ 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.
  10. ^ K. Lipnikov, G. Manzini, and M. Shashkov. Mimetic finite difference method. J. Comput. Phys., 257-Part B:1163–1227, 2014.
edit