R Abgrall

Some remarks about conservation for residual distribution schemes

Some remarks about conservation for residual distribution schemes

Remi Abgrall

Introduction

In this paper, we are interested in the approximation of non-linear hyperbolic problems. To make things more precise, our target are the Euler equations in the compressible regime, other examples are the MHD equations. The case of parabolic problems in which the elliptic terms play an important role only in some area of the computational domain, such as the Navier-Stokes equations in the compressible regime, or the resistive MHD equations, can be dealt with in a similar way. In a series of papers [START_REF] Abgrall | Toward the ultimate conservative scheme: Following the quest[END_REF][START_REF] Abgrall | Essentially non-oscillatory residual distribution schemes for hyperbolic problems[END_REF][START_REF] Abgrall | High-order fluctuation schemes on triangular meshes[END_REF][START_REF] Abgrall | A residual method using discontinuous elements for the computation of possibly non smooth flows[END_REF][START_REF] Abgrall | Development of residual distribution schemes for discontinuous Galerkin methods[END_REF][START_REF] Abgrall | Construction of very high order residual distribution schemes for steady inviscid flow problems on hybrid unstructured meshes[END_REF][START_REF] Ricchiuto | Explicit Runge-Kutta residual distribution schemes for time dependent problems: second order case[END_REF][START_REF] Abgrall | High-order preserving residual distribution schemes for advection-diffusion scalar problems on arbitrary grids[END_REF][START_REF] Abgrall | Linear and non-linear high order accurate residual distribution schemes for the discretization of the steady compressible Navier-Stokes equations[END_REF][START_REF] Abgrall | High order schemes for hyperbolic problems using globally continuous approximation and avoiding mass matrices[END_REF], following the pioneering work of Roe and Deconinck [START_REF] Struijs | Fluctuation splitting schemes for the 2D Euler equations[END_REF], we have developed, with collaborators 1 , a class of schemes that borrow some features from the finite element methods, and others, such as a local maximum principle and a non-linear stabilisation from the finite difference/finite volume methods. Though the methods have been developed with some rigour, there is a lack of a more theoretical analysis, and also to explain in a clearer way the connections with more familiar methods such as the continuous finite elements methods or the discontinuous Galerkin ones.

The ambition of this paper is to provide this link through a discussion about conservation and entropy stability. In most of the paper, we consider steady problems in the scalar case. The extension to the system case is immediate. Examples of schemes are given in the paper and the appendix. Their extensions to the system case can be found in [START_REF] Abgrall | Construction of very high order residual distribution schemes for steady inviscid flow problems on hybrid unstructured meshes[END_REF] for the pure hyperbolic case and in [START_REF] Abgrall | High-order preserving residual distribution schemes for advection-diffusion scalar problems on arbitrary grids[END_REF][START_REF] Abgrall | Linear and non-linear high order accurate residual distribution schemes for the discretization of the steady compressible Navier-Stokes equations[END_REF] for the Navier Stokes equations.

The model problem is div f (u) = 0 in Ω (1a)

subjected to min(∇ u f (u) • n(x), 0)(u -u b ) = 0 on ∂Ω. (1b)
The domain Ω is assumed to be bounded, and regular. We assume for simplicity that its boundary is never characteristic. We also assume that it has a polygonal shape and thus any triangulation that we consider covers Ω exactly. In (1b), n(x) is the outward unit vector at x ∈ ∂Ω and u b is a regular enough function.

The weak formulation of (1) is: u ∈ L ∞ (Ω) is a weak solution of (1) if for any ϕ ∈ C 1 0 (Ω),

-

Ω ∇v • f (u h ) dx + ∂Ω v F n (u, u b ) -f (u) • n dγ = 0 (2)
1 in particular M. Ricchiuto, from INRIA Bordeaux Sud-Ouest

1
where F n is a flux that is almost everywhere the upwind flux:

F n (u, u b ) = f (u b ) • n if ∇ u f (u) • n > 0 f (u) • n else.
In a first part, we present the class of schemes (nicknamed as Residual Distribution Schemes or RD or RDS for short) we are interested in, and show their link with more classical methods such as finite element ones. Then we recall a condition that guarantees that the numerical solution will converge to a weak solution of the problem. In the third part, we show that the RD schemes are also finite volume schemes: we compute explicitly the flux. In the fourth part, show that the now classical condition given by Tadmor in [START_REF] Tadmor | The numerical viscosity of entropy stable schemes for systems of conservation laws, I[END_REF][START_REF] Tadmor | Entropy stability theory for difference approximations of nonlinear conservation laws and related time-dependent problems[END_REF] in one dimension fits very naturally in our framework.

Notations

From now on, we assume that Ω has a polyhedric boundary. This simplification is by no mean essential. We denote by E h the set of internal edges/faces of T h , and by F h those contained in ∂Ω. K stands either for an element K or a face/edge e ∈ E h ∪ F h . The boundary faces/edges are denoted by Γ. The mesh is assumed to be shape regular, h K represents the diameter of the element K. Similarly, if e ∈ E h ∪ F h , h e represents its diameter.

Throughout this paper, we follow Ciarlet's definition [START_REF] Ciarlet | The finite element method for elliptic problems[END_REF][START_REF] Ern | Theory and practice of finite elements[END_REF] of a finite element approximation: we have a set of degrees of freedom Σ K of linear forms acting on the set P k of polynomials of degree k such that the linear mapping q ∈ P k → σ 1 (q), . . . , σ

|Σ K | (q)
is one-to-one. The space P k is spanned by the basis function {ϕ σ } σ∈Σ K defined by ∀σ, σ , σ(ϕ σ ) = δ σ σ .

We have in mind either Lagrange interpolations where the degrees of freedom are associated to points in K, or other type of polynomials approximation such as Bézier polynomials where we will also do the same geometrical identification. Considering all the elements covering Ω, the set of degrees of freedom is denoted by S and a generic degree of freedom by σ. We note that for any K,

∀x ∈ K, σ∈K ϕ σ (x) = 1.
For any element K, #K is the number of degrees of freedom in K. If Γ is a face or a boundary element, #Γ is also the number of degrees of freedom in Γ.

The integer k is assumed to be the same for any element. We define

V h = K {v ∈ L 2 (K), v |K ∈ P k }.
The solution will be sought for in a space V h that is:

• Either V h = V h .
In that case, the elements of V h can be discontinuous across internal faces/edges of T h . There is no conformity requirement on the mesh.

• Or V h = V h ∩ C 0 (Ω) in which case the mesh needs to be conformal.

Throughout the text, we need to integrate functions. This is done via quadrature formula, and the symbol used in volume integrals

K v(x) dx or boundary integrals ∂K v(x) dγ
means that these integrals are done via user defined numerical quadratures.

If e ∈ E h , represents any internal edge, i.e. e ⊂ K ∩ K + for two elements K and K + , we define for any function ψ the jump [∇ψ] = ∇ψ |K -∇ψ |K + . Here the choice of K and K + is important, hence also see relation (40) in section 5.2 where these element are defined in the relevant context. Similarly, {v} = 1 2 v |K + v |K + . If x and y are two vectors of R q , for q integer, x, y is their scalar product. In some occasions, it can also be denoted as x • y or x T y. We also use x • y when x is a matrix and y a vector: it is simply the matrix-vector multiplication.

In sections 4 and 5, we have to deal with oriented graph. Given two vertices of this graph σ and σ , we write σ > σ to say that [σ, σ ] is a direct edge.

3 Schemes and conservation

Schemes

We begin this section by recalling the notion of flux. Let us consider any common edge or face Γ of K + and K -, two elements. Let n be the normal to Γ, see Figure 1. Depending on the context, n is a scaled normal or ||n|| = 1. The symbols S ± represent set of states, where S + is associated to K + and S -to K -. A flux

K + K - n 1 Figure 1: Geometrical setting fn (S + , S -) between K + and K -has to satisfy fn (S + , S -) = -f-n (S -, S + ). ( 3a
)
and the consistency condition when the sets S ± reduce to u

fn (S, S) = f (u) • n. ( 3b
)
For a first order finite volume scheme, we have S + = u K+ and S -= u K-, the average values of u in K + and K -. For the other schemes, for example high order schemes, the definition is more involved. In order to integrate the steady version of (1) on a domain Ω ⊂ R d with the boundary conditions (1b), on each element K and any degree of freedom σ ∈ S belonging to K, we define residuals Φ K σ (u h ). Following [START_REF] Abgrall | Construction of very high order residual distribution schemes for steady inviscid flow problems on hybrid unstructured meshes[END_REF][START_REF] Abgrall | High-order preserving residual distribution schemes for advection-diffusion scalar problems on arbitrary grids[END_REF], they are assumed to satisfy the following conservation relations: For any element K,

σ∈K Φ K σ (u h ) = ∂K fn (u h , u h,-) dγ, (4)
where u h,-is the approximation of the solution on the other side of the local edge/face of K. Note that in the case of a conformal mesh and with globally continuous elements, the condition reduces to

σ∈K Φ K σ (u h ) = ∂K f (u h ) • n dγ.
Similarly, we consider residuals on the boundary elements Γ. On any such Γ, for any degree of freedom σ ∈ S ∩ Γ, we consider boundary residuals Φ Γ σ (u h ) that will satisfy the conservation relation

σ∈Γ Φ Γ σ (u h ) = Γ F n (u h , u b ) -f (u h ) • n dγ. ( 5
)
Once this is done, the discretisation of ( 1) is achieved via: for any σ ∈ S, K⊂Ω,σ∈K

Φ K σ (u h ) + Γ⊂∂Ω,σ∈Γ Φ Γ σ (u h ) = 0. (6)
In [START_REF] Abgrall | Toward the ultimate conservative scheme: Following the quest[END_REF], the first term represents the contribution of the internal elements. The second exists if σ ∈ ∂Ω and represents the contribution of the boundary conditions. In fact, the formulation ( 6) is very natural. Consider a variational formulation of the steady version of (1):

find

u h ∈ V h such that for any v h ∈ V h , a(u h , v h ) = 0.
Let us show on three examples that this variational formulation leads to [START_REF] Abgrall | Toward the ultimate conservative scheme: Following the quest[END_REF]. They are

• The SUPG [21] variational formulation, with u h , v h ∈ V h = V h ∩ C 0 (Ω): a(u h , v h ) := - Ω ∇v h • f (u h ) dx + K⊂Ω h K K ∇f (u h ) • ∇v h τ K ∇f (u h ) • ∇u h dx + ∂Ω v h F n (u h , u b ) -f (u h ) • n dγ. (7)
Here τ K is a positive parameter.

• The Galerkin scheme with jump stabilization, see [START_REF] Burman | Edge stabilization for Galerkin approximation of convection-diffusionreaction problems[END_REF] for details. We have

a(u h , v h ) := - Ω ∇v h • f (u h ) dx + e⊂Ω θ e h 2 e e ∇v h • ∇u h dγ + ∂Ω v h F n (u h , u b ) -f (u h ) • n dγ. (8)
Here, u h , v h ∈ V h = V h ∩ C 0 (Ω), and θ e is a positive parameter.

• The discontinuous Galerkin formulation: we look for

u h , v h ∈ V h = V h such that a(u h , v h ) := K⊂Ω - K ∇v h • f (u h )dx + ∂K v h • fn (u h , u h,-) dγ . (9)
In [START_REF] Abgrall | A residual method using discontinuous elements for the computation of possibly non smooth flows[END_REF], the boundary integral is a sum of integrals on the faces of K, and here for any face of K u h,- represents the approximation of u on the other side of that face in the case of internal elements, and u b when that face is on ∂Ω. Note that to fully comply with (6), we should have defined for boundary faces u h,-= u h , and then ( 9) is rewritten as

a(u h , v h ) := K⊂Ω - K ∇v h •f (u h )dx+ ∂K v h fn (u h , u h,-) dγ + Γ⊂∂Ω Γ v h • F n (u h , u b )-f (u h )•n dγ.
(10) In [START_REF] Abgrall | A residual method using discontinuous elements for the computation of possibly non smooth flows[END_REF], we have implicitly assumed fn = F n on the boundary edges.

In the SUPG, Galerkin scheme with jump stabilisation or the DG scheme, the boundary flux can be chosen different from F. This can lead to boundary layers if these flux are not "enough" upwind, but we are not interested in these issues here.

Using the fact that the basis functions that span V h have a compact support, then each scheme can be rewritten in the form [START_REF] Abgrall | Toward the ultimate conservative scheme: Following the quest[END_REF] with the following expression for the residuals:

• For the SUPG scheme [START_REF] Abgrall | Essentially non-oscillatory residual distribution schemes for hyperbolic problems[END_REF], the residual are defined by

Φ K σ (u h ) = ∂K ϕ σ f (u h ) • n dγ - K ∇ϕ σ • f (u h ) dx + h K K ∇ u f (u h ) • ∇ϕ σ τ K ∇ u f (u h ) • ∇u h dx. (11)
• For the Galerkin scheme with jump stabilization [START_REF] Abgrall | High-order fluctuation schemes on triangular meshes[END_REF], the residuals are defined by:

Φ K σ (u h ) = ∂K ϕ σ f (u h ) • n dγ - K ∇ϕ σ • f (u h ) dx + e faces of K θ e 2 h 2 e ∂K [∇u h ] • [∇ϕ σ ] dγ (12)
with θ e > 0. Here, since the mesh is conformal, any internal edge e (or face in 3D) is the intersection of the element K and another element denoted by K + .

• For the discontinuous Galerkin scheme,

Φ K σ (u h ) = - K ∇ϕ σ • f (u h )dx + ∂K ϕ σ • fn (u h , u h,-) dγ (13)
using the second definition of u h,-.

• The boundary residuals are

Φ Γ σ (u h ) = Γ ϕ σ F n (u h , u b ) -f (u h ) • n dγ (14)
All these residuals satisfy the relevant conservation relations, namely (4) or [START_REF] Abgrall | On a class of high order schemes for hyperbolic problems[END_REF], depending if we are dealing with element residuals or boundary residuals.

For now, we are just rephrasing classical finite element schemes into a purely numerical framework. However, considering the pure numerical point of view and forgetting the variational framework, we can go further and define schemes that have no clear variational formulation. These are the limited Residual Distributive Schemes, see [START_REF] Abgrall | Construction of very high order residual distribution schemes for steady inviscid flow problems on hybrid unstructured meshes[END_REF][START_REF] Abgrall | High-order preserving residual distribution schemes for advection-diffusion scalar problems on arbitrary grids[END_REF], namely

Φ K σ (u h ) = β σ ∂K f (u h ) • n dγ (15)
or

Φ K σ (u h ) = β σ ∂K f (u h ) • n dγ + θ K h K K ∇ u f (u h ) • ∇ϕ σ τ K ∇ u f (u h ) • ∇u h dx, θ K ≥ 0 (16) or Φ K σ (u h ) = β σ ∂K f (u h ) • n dγ + θ e h 2 e ∂K [∇u h ] • [∇ϕ σ ] dγ θ e ≥ 0 ( 17
)
where the parameters β σ are defined to guarantee conservation,

σ∈K β σ = 1
and such that (16) without the streamline term and (17) without the jump term satisfy a discrete maximum principle. The streamline term and jump term are introduced because one can easily see that spurious modes may exist, but their role is very different compared to [START_REF] Abgrall | Construction of very high order residual distribution schemes for steady inviscid flow problems on hybrid unstructured meshes[END_REF] and [START_REF] Ricchiuto | Explicit Runge-Kutta residual distribution schemes for time dependent problems: second order case[END_REF] where they are introduced to stabilize the Galerkin scheme: if formally the maximum principle is violated, experimentally the violation is extremely small if existent at all. See [START_REF] Abgrall | Essentially non-oscillatory residual distribution schemes for hyperbolic problems[END_REF][START_REF] Abgrall | Construction of very high order residual distribution schemes for steady inviscid flow problems on hybrid unstructured meshes[END_REF] for more details.

A similar construction can be done starting from a discontinuous Galerkin scheme, see [START_REF] Abgrall | Development of residual distribution schemes for discontinuous Galerkin methods[END_REF][START_REF] Abgrall | A residual method using discontinuous elements for the computation of possibly non smooth flows[END_REF]. A second order version is described in appendix A.

The non-linear stability is provided by the coefficient β σ which is a non-linear function of u h . Possible values of β σ are described in remark 3.1 bellow.

Remark 3.1. The coefficients β σ introduced in the relations ( 16) and ( 17) are defined by:

β σ = max(0, Φσ Φ ) σ ∈K max(0, Φ σ Φ ) . ( 18
)
These coefficients are always defined and garantee a local maximum principle for ( 16) and (17): this is again a consequence of the conservation properties, see e.g. [START_REF] Abgrall | Construction of very high order residual distribution schemes for steady inviscid flow problems on hybrid unstructured meshes[END_REF]. Note this is true for any order of interpolation.

Conservation

From ( 6), using the conservation relations ( 5) and ( 4), we obtain for any

v h ∈ V h , v h = σ∈S v σ ϕ σ ,
the following relation:

0 = - Ω ∇v h • f (u h ) dx + ∂Ω v h fn (u h , u b ) -f (u h ) • n dγ + e∈E h e [v h ] fn (u h , u h,-) dγ + K⊂Ω 1 #K σ,σ ∈K (v σ -v σ ) Φ K σ (u h ) -Φ K,Gal σ (u h ) + Γ⊂∂Ω 1 #Γ σ,σ ∈Γ (v σ -v σ )(Φ Γ σ u h , u b ) -Φ Gal,Γ σ (u h , u b ) (19)
where

Φ K,Gal σ (u h ) = - K ∇ϕ σ •f (u h ) dx+ ∂K ϕ σ fn (u h , u h,-) dγ, Φ Γ,Gal σ (u h , u b ) = Γ ϕ σ fn (u h , u b )-f (u h )•n dγ.
Proof. We start from ( 6) which is multiplied by v σ , and these relations are added for each σ ∈ S. We get:

0 = σ∈S v σ K⊂Ω,σ∈K Φ K σ (u h ) + Γ⊂∂Ω,σ∈Γ Φ Γ σ (u h , u b ) .
Permuting the sums on σ and K, then on σ and Γ, we get:

0 = K⊂Ω σ∈K v σ Φ K σ (u h ) + Γ⊂∂Ω σ∈Γ v σ Φ Γ σ (u h , u b ) .
We look at the first term, the second is done similarly. We have, introducing Φ K,Gal σ and #K the number of degrees of freedom in K,

σ∈K v σ Φ K σ (u h ) = σ∈K v σ Φ K,Gal σ (u h ) + σ∈K v σ Φ K σ (u h ) -Φ K,Gal σ (u h ) = - K ∇v h • f (u h ) dx + ∂K v h fn (u h , u h,-) dγ + σ∈K v σ Φ K σ (u h ) -Φ K,Gal σ (u h ) = - K ∇v h • f (u h ) dx + ∂K v h fn (u h , u h,-) dγ + 1 #K σ,σ ∈K (v σ -v σ ) Φ K σ (u h ) -Φ K,Gal σ (u h ) because σ∈K Φ K σ (u h ) -Φ K,Gal σ (u h ) = 0.
Similarly, we have

σ∈Γ v σ Φ Γ σ (u h ) = Γ v h fn (u h , u b ) -f (u h ) • n dγ + 1 #Γ σ,σ ∈Γ (v σ -v σ )(Φ Γ σ u h , u b ) -Φ Gal,Γ σ (u h , u b )
Adding all the relations, we get:

0 = K⊂Ω - K ∇v h • f (u h ) dx + ∂K v h fn (u h , u h,-) dγ + Γ⊂∂Ω Γ v h fn (u h , u b ) -f (u h ) • n dγ + K⊂Ω 1 #K σ,σ ∈K (v σ -v σ ) Φ K σ (u h ) -Φ K,Gal σ (u h ) + Γ⊂∂Ω 1 #Γ σ,σ ∈Γ (v σ -v σ )(Φ Γ σ u h , u b ) -Φ Gal,Γ σ (u h , u b )
i.e. after having defined [v h ] = v hv h,-and chosen one orientation of the internal edges e ∈ E h , we get [START_REF] Ciarlet | The finite element method for elliptic problems[END_REF].

The relation [START_REF] Ciarlet | The finite element method for elliptic problems[END_REF] is instrumental in proving the following results. The first one is proved in [START_REF] Abgrall | High-order fluctuation schemes on triangular meshes[END_REF], and is a generalisation of the classical Lax-Wendroff theorem. Theorem 3.2. Assume the family of meshes T = (T h ) is shape regular. We assume that the residuals {Φ K σ } σ∈K , for K an element or a boundary element of T h , satisfy:

• For any M ∈ R + , there exists a constant C which depends only on the family of meshes T h and M such that for any

u h ∈ V h with ||u h || ∞ ≤ M , then Φ K σ (u h |K ) ≤ C σ,σ ∈K |u h σ -u h σ |
• The conservation relations (4) and (5).

Then if there exists a constant C max such that the solutions of the scheme (6

) satisfy ||u h || ∞ ≤ C max and a function v ∈ L 2 (Ω) such that (u h ) h or at least a sub-sequence converges to v in L 2 (Ω), then v is a weak solution of (1)
Proof. The proof can be found in [START_REF] Abgrall | High-order fluctuation schemes on triangular meshes[END_REF], it uses [START_REF] Ciarlet | The finite element method for elliptic problems[END_REF] and some adaptation of the ideas of [START_REF] Kröner | A Lax-Wendroff type theorem for upwind finite volume schemes in 2-d[END_REF]. One of the key arguments comes from the consistency of the flux f as well as (3a)

Another consequence of ( 19) is the following result on entropy inequalities: Proposition 3.3. Let (U, g) be a entropy-flux couple for (1) and ĝn be a numerical entropy flux consistent with g • n. Assume that the residuals satisfy: for any element K,

σ∈K ∇ u U (u σ ), Φ K σ ≥ ∂K ĝn (u h , u h,-) dγ (20a)
and for any boundary edge e,

σ∈e ∇ u U (u σ ), Φ e σ ≥ e ĝn (u h , u b ) -g(u h ) • n dγ. (20b)
Then, under the assumptions of theorem 3.2, the limit weak solution also satisfies the following entropy inequality: for any ϕ ∈ C 1 (Ω), ϕ ≥ 0,

- Ω ∇ϕ • g(u) dx + ∂Ω - ϕ g(u b ) • n dγ ≤ 0.
Proof. The proof is similar to that of theorem 3.2.

Another consequence of ( 19) is the following condition under which one can guarantee to have a k + 1-th order accurate scheme. We first introduce the (weak) truncation error

E u h , ϕ = σ∈S h ϕ σ K⊂Ω,σ∈K Φ K σ + Γ⊂∂Ω,σ∈Γ Φ Γ σ . (21)
If the solution of the steady problem u is smooth enough and the residuals, computed with the interpolant π h (u) of the solution, are such that for any element K and boundary element Γ

Φ K σ (π h (u)) = O h k+d , Φ Γ σ (π h (u)) = O h k+d-1 (22)
and if the approximation f u h of f (u) is accurate with order k + 1, then the truncation error satisfies the following relation

|E π h (u), ϕ | ≤ C(f , u) ||ϕ|| H 1 (Ω) h k+1 ,
with C a constant which depends only on f , and ||u|| ∞ .

Proof. We first show that Φ K,Gal σ (π h (u)) = O h k+d . Since u is regular enough, we have pointwise div f (u) = 0 on K, so that, by consistency of the flux,

0 = - K ∇ϕ • f (u) dx + ∂K ϕ fn (u, u) dγ. Then, Φ K,Gal σ (π h (u)) = - K ∇ϕ σ • f (π h (u)) -f (u) dx + ∂K ϕ σ fn (π h (u), π h (u)) -fn (u, u) dγ = |K| × O(h -1 ) × O(h k+1 ) + |∂K| × O(1)O(h k+1 ) = O(h d ) × O(h -1 ) × O(h k+1 ) + O(h d-1 ) × O(1) × O(h k+1 ) = O(h d+k )
because the flux is Lipschitz continuous and the mesh is regular.

The result on the boundary term is similar since the boundary numerical flux is upwind and the boundary of Ω is not characteristic: only two types of boundary faces exists, the upwind and downwind ones. On the downwind faces, the boundary flux vanishes. On the upwind ones, we get the estimate for the Galerkin boundary residuals thanks to the same approximation argument.

The mesh is assumed to be regular: the number of elements (resp. edges

) is O(h -d ) (resp. O(h -d+1
)). Let us assume [START_REF] Burman | Edge stabilization for Galerkin approximation of convection-diffusionreaction problems[END_REF]. Let v ∈ C 1 0 (Ω). Using [START_REF] Ciarlet | The finite element method for elliptic problems[END_REF] for π h (u),

E u h , ϕ = - Ω ∇π h (v) • f (π h (u)) dx + ∂Ω π h (v) fn (π h (u), u b ) -f (π h (u)) • n dγ + e∈E h e [π h (v)] fn (π h (u), π h (u) -) dγ + K⊂Ω 1 #K σ,σ ∈K (v σ -v σ ) Φ K σ (π h (u)) -Φ K,Gal σ (π h (u)) + Γ⊂∂Ω 1 #Γ σ,σ ∈Γ (v σ -v σ )(Φ Γ σ π h (u), u b ) -Φ Gal,Γ σ (π h (u), u b ) .
where π h (u) -represents the interpolant of u on K -. We have, using

- Ω ∇π h (v) • f (u) dx + ∂Ω π h (v) F n (u, u b ) -f (u) • n dγ = 0, - Ω ∇π h (v) • f (π h (u)) dx + ∂Ω π h (v) fn (π h (u), u b ) -f (π h (u)) • n dγ = - Ω ∇π h (v) • f (π h (u)) -f (u) dx + ∂Ω π h (v) fn (π h (u), u b ) -fn (u, u b ) dγ - ∂Ω π h (v) f (π h (u)) -f (u) • n dγ = O(h k+1 )
since the flux on the boundary is the upwind flux F n , and using the approximation properties of π h (u). Then

e∈E h e [π h (v)] fn (π h (u), π h (u) -) dγ = O(h -d+1 ) × O(h d-1 ) × O(h k+1 ) × O(1) = O(h k+1 ), K⊂Ω 1 #K σ,σ ∈K (v σ -v σ ) Φ K σ (π h (u)) -Φ K,Gal σ (π h (u)) = O(h -d ) × O(h) × O(h k+d ) = O(h k+1 ),
and similarly

Γ⊂∂Ω 1 #Γ σ,σ ∈Γ (v σ -v σ )(Φ Γ σ π h (u), u b ) -Φ Gal,Γ σ (π h (u), u b ) = O(h -d+1 ) × O(h) × O(h k+d-1 ) = O(h k+1 )
thanks to the regularity of the mesh, that π h (v) is the interpolant of a C 1 function and the previous estimates.

Remark 3.4 (Numerical integration). In practice, the integrals are evaluated by numerical integration. The results still holds true provided the quadrature formula are of order k + 1. This is in contrast with the common practice, but let us emphasis this is valid only for steady problems. However, similar arguments can be developed for unsteady problems, see [START_REF] Ricchiuto | Explicit Runge-Kutta residual distribution schemes for time dependent problems: second order case[END_REF][START_REF] Abgrall | High order schemes for hyperbolic problems using globally continuous approximation and avoiding mass matrices[END_REF].

Flux formulation of Residual Distribution schemes

In this section we show that the scheme (6) also admits a flux formulation, with an explicit form of the flux: the method is also locally conservative. Local conservation is of course well known for the Finite Volume and discontinuous Galerkin approximations. It is much less understood for the continuous finite elements methods, despite the papers [START_REF] Hughes | A new finite element formulation for CFD: I. symmetric forms of the compressible Euler and Navier-Stokes equations and the second law of thermodynamics[END_REF][START_REF] Burman | Interior penalty continuous and discontinuous finite element approximations of hyperbolic equations[END_REF]. Referring to (3), the aim of this section is to define f and S ± in the RDS case.

We first show why a finite volume can be reinterpreted as an RD scheme. This helps to understand the structure of the problem. Then we show that any RD scheme can be equivalently rephrased as a finite volume scheme, we explicitly provide the flux formula as well as the control volumes. In order to illustrate this result, we give several examples: the general RD scheme with P 1 and P 2 approximation on simplex, the case of a P 1 RD scheme using a particular form of the residuals so that one can better see the connection with more standard formulations, and finally an example with a discontinuous Galerkin formulation using P 1 approximation.

Finite volume as Residual distribution schemes

Here, we rephrase [START_REF] Abgrall | Toward the ultimate conservative scheme: Following the quest[END_REF]. The notations are defined in Figure 2. Again, we specialize ourselves to the case of triangular elements, but exactly the same arguments can be given for more general elements, provided a conformal approximation space can be constructed. This is the case for triangle elements, and we can take k = 1.

The control volumes in this case are defined as the median cell, see figure 2. We concentrate on the approximation of div f , see equation [START_REF] Chen | Entropy stable high order discontinuous Galerkin methods with suitable quadrature rules for hyperbolic conservation laws[END_REF]. Since the boundary of C σ is a closed polygon, the scaled outward normals n γ to ∂C σ sum up to 0:

γ⊂∂Cσ n γ = 0
where γ is any of the segment included in ∂C σ , such as P G on Figure 2. Hence

γ⊂∂Cσ fnγ (u σ , u -) = γ⊂∂Cσ fnγ (u σ , u -) - γ⊂∂Cσ n γ • f (u σ ) = K,σ∈K γ⊂∂Cσ∩K fnγ (u σ , u -) -f (u σ ) • n γ
To make things explicit, in K, the internal boundaries are P G, QG and RG, and those around σ ≡ 1 are P G and RG. We set

Φ K σ (u h ) = γ⊂∂Cσ∩K fnγ (u σ , u -) -f (u σ ) • n γ = γ⊂∂(Cσ∩K) fnγ (u σ , u -). ( 23
)
The last relation uses the consistency of the flux and the fact that C σ ∩ K is a closed polygon. The quantity Φ K σ (u h ) is the normal flux on C σ ∩ K. If now we sum up these three quantities and get:

σ∈K Φ K σ (u h ) = fn12 (u 1 , u 2 ) -fn13 (u 1 , u 3 ) -f (u 1 ) • n 12 + f (u 1 ) • n 31 + fn23 (u 2 , u 3 ) -fn12 (u 2 , u 1 ) + f (u 2 ) • n 12 -f (u 2 ) • n 23 + -fn23 (u 3 , u 2 ) + fn31 (u 3 , u 1 ) -f (u 3 ) • n 23 + f (u 3 ) • n 31 = f (u 1 ) • n 12 -n 31 + f (u 2 ) • -n 23 + n 31 + f (u 3 ) • n 31 -n 23 = f (u 1 ) • n 1 2 + f (u 2 ) • n 2 2 + f (u 3 ) • n 3 2
where n j is the scaled inward normal of the edge opposite to vertex σ j , i.e. twice the gradient of the P 1 basis function ϕ σj associated to this degree of freedom. Thus, we can reinterpret the sum as the boundary integral of the Lagrange interpolant of the flux. The finite volume scheme is then a residual distribution scheme with residual defined by [START_REF] Kröner | A Lax-Wendroff type theorem for upwind finite volume schemes in 2-d[END_REF] and a total residual defined by

Φ K := ∂K f h • n, f h = σ∈K f (u σ )ϕ σ . (24)
4.2 Residual distribution schemes as finite volume schemes.

In this section, we show how to interpret RD schemes as finite volume schemes. This amounts to defining control volumes and flux functions. We first have to adapt the notion of consistency. As recalled in the section 3.2, two of the key arguments in the proof of the Lax-Wendroff theorem are related to the structure of the flux, for classical finite volume schemes. In [START_REF] Abgrall | High-order fluctuation schemes on triangular meshes[END_REF], the proof is adapted to the case of Residual Distribution schemes. The property that stands for the consistency is that if all the states are identical in an element, then each of the residuals vanishes. Hence, we define a multidimensional flux as follows: We proceed first with the general case and show the connection with elementary fact about graphs, and then provide several examples. The results of this section apply to any finite element method but also to discontinuous Galerkin methods. There is no need for exact evaluation of integral formula (surface or boundary), so that these results apply to schemes as they are implemented.

General case

One can deal with the general case, i.e when K is a polytope contained in R d with degrees of freedoms on the boundary of K. The set S is the set of degrees of freedom. We consider a triangulation T K of K whose vertices are exactly the elements of S. Choosing an orientation of K, it is propagated on T K : the edges are oriented.

The problem is to find quantities fσ,σ for any edge [σ, σ ] of T K such that:

Φ σ = edges [σ,σ ] fσ,σ + f b σ (25a) with fσ,σ = -fσ ,σ (25b)
and f b σ is the 'part' of ∂K fn (u h , u h,-) dγ associated to σ. The control volumes will be defined by their normals so that we get consistency.

Note that (25b) implies the conservation relation

σ∈K Φ σ = σ∈K f b σ . (25c)
In short, we will consider

f b σ = ∂K ϕ σ fn (u h , u h,-) dγ, (25d)
but other examples can be considered provided the consistency (25c) relation holds true, see for example section 4.2.2. Any edge [σ, σ ] is either direct or, if not, [σ , σ] is direct. Because of (25b), we only need to know fσ,σ for direct edges. Thus we introduce the notation f{σ,σ } for the flux assigned to the direct edge whose extremities are σ and σ . We can rewrite (25a) as, for any σ ∈ S,

σ ∈S ε σ,σ f{σ,σ } = Ψ σ := Φ σ -f b σ , (26)
with

ε σ,σ =    0 if σ and σ are not on the same edge of T , 1 if [σ, σ ] is an edge and σ → σ is direct, -1 if [σ, σ ] is an edge and σ → σ is direct. E + represents the set of direct edges.
Hence the problem is to find a vector f = ( f{σ,σ } ) {σ,σ } direct edges such that

A f = Ψ
where Ψ = (Ψ σ ) σ∈S and A σσ = ε σ,σ . We have the following lemma which shows the existence of a solution.

Lemma 4.2. For any couple {Φ σ } σ∈S and { f b σ } σ∈S satisfying the condition (25c), there exists numerical flux functions fσ,σ that satisfy [START_REF] Chung | Spectral Graph Theory[END_REF]. Recalling that the matrix of the Laplacian of the graph is L = AA T , we have 1. The rank of L is |S| -1 and its image is span{1}) ⊥ . We still denote the inverse of L on span{1}) ⊥ by L -1 , 2. With the previous notations, a solution is

f{σ,σ } {σ,σ } direct edges = A T L -1 Ψ σ σ∈S . (27)
Proof. We first have

1 T A = 0: Im A ⊂ span {1} ⊥ (⊂ R |S| ).
Let us show that we have equality. In order to show this, we notice that the matrix A is nothing more that the incidence matrix of the oriented graph G defined by the triangulation T . It is known [START_REF] Chung | Spectral Graph Theory[END_REF] that its null space of L is equal to the number of connected components of the graph, i.e. here dim ker L = 1. Since

L 1 = 0,
we see that ker L = span {1}, so that Im L = span {1} T because L is symmetric. We can define the inverse of L on Im L, denoted by L -1 . Let x ∈ span {1} ⊥ = Im L. There exists y ∈ R |S| such that x = Ly = A(A T y): this shows that

x ∈ Im A and thus Im A = span {1} ⊥ = Im L ⊥ . From this we deduce that rank

A = |S| -1 because Im A ⊂ R |S| .
Let Ψ ∈ R |S| be such that 1, Ψ = 0. We know there exists a unique z ∈ span {1}

⊥ such that Lz = Ψ, i.e. A(A T z) = Ψ.
This shows that a solution is given by ( 27).

This set of flux are consistent and we can estimate the normals n σ,σ . In the case of a constant state, we have Φ σ = 0 for all σ ∈ K. Let us assume that

f b σ = f (u h ) • N σ ( 28
)
with σ∈K N σ = 0: this is the case for all the examples we consider. The flux f (u h ) has components on the canonical basis of

R d : f (u h ) = f 1 (u h ), . . . , f d (u h ) , so that f b σ = d i=1 f i (u h )N i σ .
Applying this to f b σ1 , . . . , f b σ #K , we see that the j-th component of n σ,σ for [σ, σ ] direct, must satisfy:

for any σ ∈ K, N j σ = [σ,σ ] edge ε σ,σ n j σ,σ i.e. N j σ1 , . . . , N j σ #K T = A n j σ,σ [σ,σ ]∈E + .
We can solve the system and the solution, with some abuse of language, is

n σ,σ [σ,σ ]∈E + = A T L -1 N σ1 , . . . , N σ #K T (29)
This also defines the control volumes since we know their normals. We can state: Proposition 4.3. If the residuals (Φ σ ) σ∈K and the boundary fluxes ( f b σ ) σ∈K satisfy (25c), and if the boundary fluxes satisfy the consistency relations (28), then we can find a set of consistent flux ( fσ,σ ) [σ,σ ] satisfying [START_REF] Chung | Spectral Graph Theory[END_REF]. They are given by [START_REF] Deconinck | A multidimensional generalization of Roe's flux difference splitter for the euler equations[END_REF]. In addition, for a constant state,

fσ,σ (u h ) = f (u h ) • n σ,σ
for the normals defined by (29).

We can state a couple of general remarks: Remark 4.4.

1. The flux fσ,σ depend on the Ψ σ and not directly on the f b σ . We can design the fluxes independently of the boundary flux, and their consistency directly comes from the consistency of the boundary fluxes.

2. The residuals depends on more than 2 arguments. For stabilized finite element methods, or the non linear stable residual distribution schemes, see e.g. [START_REF] Hughes | A new finite element formulation for CFD: I. symmetric forms of the compressible Euler and Navier-Stokes equations and the second law of thermodynamics[END_REF][START_REF] Struijs | Fluctuation splitting schemes for the 2D Euler equations[END_REF][START_REF] Abgrall | Construction of very high order residual distribution schemes for steady inviscid flow problems on hybrid unstructured meshes[END_REF], the residuals depend on all the states on K. Thus the formula [START_REF] Deconinck | A multidimensional generalization of Roe's flux difference splitter for the euler equations[END_REF] shows that the flux depends on more than two states in contrast to the 1D case. In the finite volume case however, the support of the flux function is generally larger than the three states of K, think for example of an ENO/WENO method, or a simpler MUSCL one.

3. The formula [START_REF] Deconinck | A multidimensional generalization of Roe's flux difference splitter for the euler equations[END_REF] are influenced by the form of the total residual [START_REF] Burman | Interior penalty continuous and discontinuous finite element approximations of hyperbolic equations[END_REF]. We show in the next paragraph how this can be generalized.

4. The formula (27) make no assumption on the approximation space V h : they are valid for continuous and discontinuous approximations. The structure of the approximation space appears only in the total residual.

Some particular cases: fully explicit formula

Let K be a fixed triangle. We are given a set of residues {Φ K σ } σ∈K , our aim here is to define a flux function such that relations similar to [START_REF] Kröner | A Lax-Wendroff type theorem for upwind finite volume schemes in 2-d[END_REF] hold true. We explicitly give the formula for P 1 and P 2 interpolant.

The general P 1 case. The adjacent matrix is

A =   1 0 -1 -1 1 0 0 -1 1   .
A straightforward calculation shows that the matrix L = A T A has eigenvalues 0 and 3 with multiplicity 2 with eigenvectors

R =    1 √ 3 1 √ 2 1 √ 6 1 √ 3 -1 √ 2 1 √ 6 1 √ 3 0 -2 √ 6   
To solve A f = Ψ, we decompose Ψ on the eigenbasis:

Ψ = α 2 R 2 + α 3 R 3
where explicitly

α 2 = 1 √ 2 Ψ 1 -2Ψ 2 + Ψ 3 α 3 = 3 2 Ψ 1 -Ψ 3 so that f = 1 3   Ψ 1 -Ψ 3 Ψ 2 -Ψ 3 Ψ 3 -Ψ 2   .
In order to describe the control volumes, we first have to make precise the normals n σ in that case. It is easy to see that in all the cases described above, we have

N σ = - n σ 2 .
Then a short calculation shows that  

n 12 n 23 n 31   = 1 6   n 1 -n 2 n 2 -n 3 n 3 -n 1   .
Using elementary geometry of the triangle, we see that these are the normals of the elements of the dual mesh. For example, the normal n 12 is the normal of P G, see figure 2.

Relying more on the geometrical interpretation (once we know the control volumes), we can recover the same formula by elementary calculations, see [START_REF] Abgrall | On a class of high order schemes for hyperbolic problems[END_REF].

The general example of the P 2 approximation.

Using a similar method, we get (see figure 3 for some notations):

f14 = 1 12 Ψ 1 -Ψ 4 + 1 36 Ψ 6 -Ψ 5 + 7 36 Ψ 1 -Ψ 2 + 5 36 Ψ 3 -Ψ 1 f16 = 1 12 Ψ 4 -Ψ 1 + 5 36 Ψ 5 -Ψ 1 ) + 7 36 Ψ 6 -Ψ 1 + 1 36 Ψ 3 -Ψ 2 f46 = 2 9 Ψ 2 -Ψ 6 + 1 9 Ψ 3 -Ψ 5 f54 = 2 9 Ψ 5 -Ψ 2 + 1 9 Ψ 5 -Ψ 1 f42 = 7 36 Ψ 2 -Ψ 3 + 5 36 Ψ 1 -Ψ 3 + 1 12 Ψ 6 -Ψ 3 + 1 36 Ψ 5 -Ψ 4 f25 = 1 36 Ψ 2 -Ψ 1 + 5 36 Ψ 3 -Ψ 5 + 7 36 Ψ 3 -Ψ 5 + 1 12 Ψ 3 -Ψ 6 f53 = 1 36 Ψ 1 -Ψ 6 + 5 36 Ψ 3 -Ψ 5 + 7 36 Ψ 4 -Ψ 5 + 1 12 Ψ 2 -Ψ 5 f63 = 1 36 Ψ 4 -Ψ 3 + 5 36 Ψ 5 -Ψ 1 + 7 36 Ψ 5 -Ψ 6 + 1 12 Ψ 5 -Ψ 2 f65 = 1 9 Ψ 1 -Ψ 3 + 2 9 Ψ 6 -Ψ 4
Then we choose the boundary flux:

f b σ = ∂K ϕ σ n dγ
and get:

N l = - n l 6 if l = 1, 2, 3 N 4 = n 3 3 N 5 = n 1 3 N 6 = n 2 3
The normals are given by:

n 14 = 1 12 N 1 -N 4 + 1 36 N 6 -N 5 + 7 36 N 1 -N 2 + 5 36 N 3 -N 1 n 16 = 1 12 N 4 -N 1 + 5 36 N 5 -N 1 ) + 7 36 N 6 -N 1 + 1 36 N 3 -N 2 n 46 = 2 9 N 2 -N 6 + 1 9 N 3 -N 5 n 54 = 2 9 N 5 -N 2 + 1 9 N 5 -N 1 n 42 = 7 36 N 2 -N 3 + 5 36 N 1 -N 3 + 1 12 N 6 -N 3 + 1 36 N 5 -N 4 n 25 = 1 36 N 2 -N 1 + 5 36 N 3 -N 5 + 7 36 N 3 -N 5 + 1 12 N 3 -N 6 n 53 = 1 36 N 1 -N 6 + 5 36 N 3 -N 5 + 7 36 N 4 -N 5 + 1 12 N 2 -N 5 n 63 = 1 36 N 4 -N 3 + 5 36 N 5 -N 1 + 7 36 N 5 -N 6 + 1 12 N 5 -N 2 n 65 = 1 9 N 1 -N 3 + 2 9 N 6 -N 4
There is not uniqueness, and it is possible to construct different solutions to the problem. In what follows, we show another possible construction. We consider the set-up defined by Figure 3. The triangle is split first into 4 sub-triangles K 1 , K 2 , K 3 and K 4 . From this sub-triangulation, we can construct a dual mesh as in the P 1 case and we have represented the 6 sub-zones that are the intersection of the dual control volumes and the triangle K. Our notations are as follow: given any sub-triangle K ξ , if γ ij is intersection between two adjacent control volumes (associated to σ i and σ j vertices of K ξ ), the normal to γ ij in the direction σ i to σ j is denoted by n ξ ij . Similarly the flux across γ ij is denoted f ξ ij . Then we need to define boundary fluxes. If σ belongs to K l , we denote the boundary flux as f

K l σ . A rather natural condition is that f K l l = f b l l = 1, 2, 3 f K l 4 = 1 3 f b 4 l = 1, 2, 4 f K l 5 = 1 3 f b 5 l = 2, 3, 4 f K l 6 = 1 3 f b 6 l = 1, 3, 4.
We recover the conservation relation. Other choices are possible since this one is arbitrary: the only true condition is that the sum of the boundary flux is equal to the sum of the f b j for j = 1, . . . , 6: this is the conservation relation.

Then we set:

Φ 1 = -f 1 n61 + f 1 n14 + f b 1 Φ 2 = -f 2 n42 + f 2 n25 + f b 2 Φ 3 = -f 3 n53 + f 3 n36 + f b 3 Φ 4 = -f 1 n14 + f 1 n46 -f 4 n64 + f 4 n45 -f 2 n54 + f 2 n42 + f b 4 Φ 5 = -f 2 n25 + f 2 n54 -f 4 n45 + f 4 n56 -f 3 n65 + f 3 n53 + f b 5 Φ 6 = -f 3 n36 + f 3 n65 -f 4 n56 + f 4 n64 -f 1 n46 + f 1 n61 + f b 6 ( 30
)
We can group the terms in (30) by sub-triangles, namely:

Φ 1 = -f 1 n61 + f 1 n14 + f b 1 Φ 2 = -f 2 n42 + f 2 n25 + f b 2 Φ 3 = -f 3 n53 + f 3 n36 + f b 3 Φ 4 = -f 1 n14 + f 1 n46 + f K1 4 + -f 4 n64 + f 4 n45 + f K4 1 + -f 2 n54 + f 2 n42 + f K2 4 Φ 5 = -f 2 n25 + f 2 n54 + f K2 5 + -f 4 n45 + f 4 n56 + f K4 5 + -f 3 n65 + f 3 n53 + f K3 5 Φ 6 = -f 3 n36 + f 3 n65 + f K3 6 + -f 4 n56 + f 4 n64 + f K4 6 + -f 1 n46 + f 1 n61 + f K1 6 . (31)
Then we define the sub-residuals per sub elements:

Φ 1 1 = -f 1 n61 + f 1 n14 + f b 1 , Φ 2 4 = -f 2 n54 + f 2 n42 + f K2 4 Φ 1 4 = -f 1 n14 + f 1 n46 + f K1 4 , Φ 2 2 = -f 2 n42 + f 2 n25 + f K2 2 Φ 1 6 = -f 1 n46 + f 1 n61 + f K1 6 , Φ 2 5 = -f 2 n25 + f 2 n54 + f K2 5 Φ 3 5 = -f 3 n65 + f 3 n53 + f K3 5 , Φ 4 4 = -f 4 n64 + f 4 n45 + f K4 4 Φ 3 3 = -f 3 n36 + f 3 n65 + f K3 3 , Φ 4 5 = -f 4 n45 + f 4 n56 + f K4 5 Φ 3 6 = -f 3 n36 + f 3 n65 + f K3 6 , Φ 4 6 = -f 4 n56 + f 4 n64 + f K4 6 , (32)
so we are back to the P 1 case: in each sub-triangle, we can define flux that will depend on the 6 states of the element via the boundary flux. This is legitimate because in the P 1 case, we have not used the fact that the interpolation is linear, we have only used the fact that we have 3 vertices. Clearly the fluxes are consistent in the sense of definition 4.1.

The same argument can be clearly extended to higher degree element, as well as to non triangular element: what is needed is to subdivide the element into sub-triangles.

The two solutions we have presented for the P 2 case are different: the control volumes are different, since they have more sides in the second case than in the first one.

More specific examples

In what follow we look at the flux form on specific numerical schemes: an extension of the Rusanov scheme, what is called the N scheme after P.L. Roe and a discontinuous Galerkin method.

Rusanov residual. Here we assume a global continuous approximation. Assuming that the total residual is evaluated using the Lagrange interpolation of the flux, f h = σ ∈K f (u σ )ϕ σ , we define (the integrals can be evaluated exactly in that case)

Φ σ (u h ) = ∂K ϕ σ f h • n dγ - K ∇ϕ σ • f h dx + α(u σ -ū), ū = σ ∈K u σ #K (33)
where #K is the number of degrees of freedom in K and α is a parameter that will become explicit later. Since 0 = K ϕ σ div (1) dx = -K ∇ϕ σ dx + ∂K ϕ σ n dγ and

σ ∈K ϕ σ = 1, we have Φ σ (u h ) = σ ∈K f (u σ ) • - K ϕ σ ∇ϕ σ dx + ∂K ϕ σ ϕ σ n dγ + α(u σ -ū) = σ ∈K f (u σ ) -f (u σ ) • - K ϕ σ ∇ϕ σ dx + ∂K ϕ σ ϕ σ n dγ + α(u σ -ū) = σ ∈K f (u σ ) -f (u σ ) • - K ϕ σ ∇ϕ σ dx + ∂K ϕ σ ϕ σ n dγ + α #K u σ -u σ = σ ∈K c σσ (u σ -u σ )
with

c σσ = - f (u σ ) -f (u σ ) u σ -u σ • - K ϕ σ ∇ϕ σ dx + ∂K ϕ σ ϕ σ n dγ + α #K .
A local maximum principle is obtained if for any element, and any couple of degrees of freedom in that element, we have c σσ ≥ 0. In the present case, we take

α ≥ #K max σ,σ ∈K f (u σ ) -f (u σ ) u σ -u σ • - K ϕ σ ∇ϕ σ dx + ∂K ϕ σ ϕ σ n dγ .
In the case of triangular elements with P 1 approximation, we have fσσ

= 1 2 K ∇ ϕ σ -ϕ σ • f h dγ + α(u σ -u σ ).
Using simple geometry (see figure 2-a), we get

fσσ = 1 |K| K f h dx • n σσ + α(u σ -u σ ). ( 34
)
We see that this flux is not exactly the classical Rusanov flux

f Rus σσ = 1 2 f σ + f σ ) • n σσ + α(u σ -u σ ),
but is formally very close to it: it is the sum of a centered part (the surface integral) and a dissipation. We also note that the flux (34) is not necessarily monotone, but it is monotone combined with the flux f b n .

The N scheme. Considering the problem (1) with triangular elements. We assume the existence of an average vector

∇ u f such that 1 2 σ f σ • n σ = |K| ∇ u f • ∇u h .
Here, again both f and u are approximated by a linear Lagrange interpolant.

A simple example of such situation is given by the Burgers problem where f (u) = ( u 2 2 , u) T . Here

∇ u f = ū, 1) T
where u is the arithmetic average of the nodal values. This average is a generalisation of the Roe average [START_REF] Roe | Approximate Riemann solvers, parameter vectors, and difference schemes[END_REF], a version for the Euler equations can be found in [START_REF] Deconinck | A multidimensional generalization of Roe's flux difference splitter for the euler equations[END_REF]. Using this average, the N scheme, see [START_REF] Roe | Optimum positive linear schemes for advection in two and three dimensions[END_REF], can be defined as follows:

Φ σ = k + σ u σ -ũ (35a) with k σ = 1 |K| K ∇ u f • ∇ϕ σ dx, k + σ = max(k σ , 0), k - σ = min(k σ , 0) (35b) and ũ = N σ ∈K k - σ u σ , N -1 = σ ∈K k - σ (35c)
The value of N is chosen such that the conservation (4) holds true. When looking at the flux fn σ,σ , no particular nice looking structure appears, except in the case of a thin triangle, where the associated flux is a generalisation of Roe's flux. Note that Remark 3.1 also applies here, provided that the Rusanov residuals are replaced by those of the N scheme in the definition of β σ , see [START_REF] Tadmor | Entropy stability theory for difference approximations of nonlinear conservation laws and related time-dependent problems[END_REF].

Discontinuous Galerkin schemes (P 1 case). The residual is simply

Φ K σ = ∂K ϕ σ fn (u h , u h,-) dγ - K ∇ϕ σ • f (u h ) dx.
In the P 1 case, the flux between two DOFs σ and σ is given by fσ

,σ (u h , u h,-) = ∂K (ϕ σ -ϕ σ ) fn (u h , u h,-) dγ - K ∇ ϕ σ -ϕ σ • f (u h ) dx. Again, from simple geometry, ∇ ϕ σ -ϕ σ = - n σσ |K| , so that fσ,σ (u h , u h,-) = ∂K (ϕ σ -ϕ σ ) fn (u h , u h,-) dγ + K f (u h ) dx |K| • n σσ .
Note that ∂K (ϕ σϕ σ ) dγ = 0 if we take the same quadrature formula on each edge, as it is usually done. Hence, denoting by ū the cell average of u h on K, we can rewrite the flux as

fσ,σ (u h , u h,-) = K f (u h ) dx |K| • n σσ + ∂K (ϕ σ -ϕ σ ) fn (u h , u h,-) -f (ū) • n dγ (36)
so that the second term can be interpreted as a dissipation. The control volume is depicted in figure 4.

Referring to figure 4 for the DOF #1, the flux on the faces I1J is ∂K ϕ 1 fn (u h , u h,-) dγ. In order to respect

Entropy dissipation

In this section, we consider the system version of (1). Our results on the flux are similar, since we never have used we were dealing with residual belonging to R or to some R p .

The 1 D case revisited

We start by recalling Tadmor's work [START_REF] Tadmor | The numerical viscosity of entropy stable schemes for systems of conservation laws, I[END_REF][START_REF] Tadmor | Entropy stability theory for difference approximations of nonlinear conservation laws and related time-dependent problems[END_REF]. Let us start from a finite volume scheme semi-discretized in time:

∆x dv i dt + fi+1/2 -fi-1/2 = 0.
If v is the entropy variable, we have:

∆x v i , du i dt + v i , fi+1/2 -v i , fi-1/2 = 0 Then v i , fi+1/2 = v i + v i+1 2 , fi+1/2 + v i -v i+1 2 , fi+1/2
Following Tadmor, we introduce the potential:

θ = v, f -g
where g is the entropy flux, so that the entropy flux is defined by: ĝi+1/2 :=

v i + v i+1 2 , fi+1/2 - θ i + θ i+1 2
Remark 5.2. Starting from a consistent flux f , a simple way to construct a numerical flux f that satisfies (42) is to consider:

f n (v h , v h,-) = fn (v h , v h,-) + α v h -v h,-
with α chosen so that (42) holds true. If the original flux is Lipschitz continuous, this is always possible. Hence the satisfaction of (42) is not an issue. Note this does not spoil the accuracy conditions [START_REF] Burman | Edge stabilization for Galerkin approximation of convection-diffusionreaction problems[END_REF]. Given a numerical flux, it is always possible to construct residuals that satisfies the conservation relation with that given flux. In the appendix, we show how to proceed for discontinuous representations. The next paragraph shows how to enforce a local entropy condition, in general.

We can rework the relation (41b) in order to show some links with the recent paper [START_REF] Chen | Entropy stable high order discontinuous Galerkin methods with suitable quadrature rules for hyperbolic conservation laws[END_REF]. Using the flux definitions, we can rewrite

σ v σ , Ψ σ + K θ n dγ as 1 2 σ>σ v σ -v σ , fσ,σ -θ σ -θ σ • n σ,σ + 1 2 σ>σ θ σ -θ σ • n σ,σ
Then, we see that

1 2 σ>σ θ σ -θ σ • n σσ = σ∈∂K θ σ • N σ dγ = ∂K θ h K dγ.
This relation is the motivation for defining θ h in (37). Thanks to this, we can write the condition as:

1 2 σ>σ v σ -v σ , fσ,σ -θ σ -θ σ • n σσ + ∂K θ(v h ) • n dγ - σ∈∂K θ σ • N σ ≥ 0.
with 1 2 σ>σ v σv σ , fσ,σθ σθ σ • n σσ ≥ 0.

We see that, as in [START_REF] Chen | Entropy stable high order discontinuous Galerkin methods with suitable quadrature rules for hyperbolic conservation laws[END_REF], if the fluxes fσ,σ are entropy stable, we get entropy stability at the element level.

Conclusion

This paper shows some links between now classical schemes, such as the finite volume scheme, the continuous finite element methods, the discontinuous Galerkin methods and more generally a class of method nicknamed as Residual Distribution (RD) methods. We show that, under a proper definition of a consistent flux, all these schemes enjoy a flux formulation, and hence are locally conservative. This is well known for most schemes, less known for some of them. The fluxes are explicitly given. We also show that Tadmor's entropy stability condition can be reformulated very simply in the Residual Distribution context. Using this we have shown some connections with the recent work [START_REF] Chen | Entropy stable high order discontinuous Galerkin methods with suitable quadrature rules for hyperbolic conservation laws[END_REF]. However the discussion here is certainly not finished, it will be the topic of another paper. The emphasis of this paper is put on the steady case, but the unsteady state is similar, see [START_REF] Ricchiuto | Explicit Runge-Kutta residual distribution schemes for time dependent problems: second order case[END_REF] and [START_REF] Abgrall | High order schemes for hyperbolic problems using globally continuous approximation and avoiding mass matrices[END_REF].

A A DG RDS scheme

Let us consider problem (1) defined on Ω ⊂ R 2 . In this case, the approximation can be discontinuous across edges: u h ∈ V h . In a first step, we consider a conformal triangulation of Ω using triangles. This is not essential but simplifies a bit the text. The 3D case can be dealt with in a similar way.

In K, we say that the degrees of freedom are located at the vertices, and we represent the approximated solution in K by the degree one interpolant polynomial at the vertices of K. Let us denote by u h this piecewise linear approximation, that is in principle discontinuous at across edges. In the following, we use the notations described in Figure 5.

In [START_REF] Abgrall | Development of residual distribution schemes for discontinuous Galerkin methods[END_REF], the degrees of freedom are located at the midpoint of the edges that connect the centroid of K and its vertices. This choice was motivated by the fact that the P 1 basis functions associated to these nodes are orthogonal in L 2 (K). This property enables us to reinterpret the DG schemes as RD schemes, and hence to adapt the stabilization techniques of RD to DG. In particular, we are able to enforce a L ∞ stability property. However, this method was a bit complex, and it is not straightforward to generalize it to more general elements than triangles.

The geometrical idea behind the version that we describe now is to forget the RD interpretation of the DG scheme and to let the geometrical localization of the degrees of freedom move to the vertices of the element.

With this in mind, we define two types of total residuals:

• A total residual per element K

Φ K (u h ) = ∂K f (u h ) • n dγ.

Figure 2 :

 2 Figure 2: Notations for the finite volume schemes. On the left: definition of the control volume for the degree of freedom σ. The vertex σ plays the role of the vertex 1 on the left picture for the triangle K. The control volume C σ associated to σ = 1 is green on the right and corresponds to 1P GR on the left. The vectors n ij are normal to the internal edges scaled by the corresponding edge length

Definition 4 . 1 .

 41 A multidimensional flux fn := fn (u 1 , . . . , u N ) is consistent if, when u 1 = u 2 = . . . = u N = u then fn (u, . . . , u) = f (u) • n.

Figure 3 :

 3 Figure 3: Geometrical elements for the P 2 I ij is the mid-point between the vertices i and j. The intersections of the dotted lines are the centroids of the sub-elements.

1 Figure 4 :

 14 Figure 4: Representation of the control volume associated to DOF 1.

Acknowledgements

The author has been funded in part by the SNSF project 200021 153604 "High fidelity simulation for compressible materials". I would also like to thanks Anne Burbeau (CEA-DEN) for her critical reading of the first draft of this paper. Her input has hopefully helped to improve the readability of this paper. The two referees and the editor are also warmly thanked for their patience, their comments and ability to trace typos. The remaining mistakes are mine.

and we get

Thus,

This leads to the definition of entropy stable schemes:

Definition 5.1 (Tadmor [START_REF] Tadmor | The numerical viscosity of entropy stable schemes for systems of conservation laws, I[END_REF][START_REF] Tadmor | Entropy stability theory for difference approximations of nonlinear conservation laws and related time-dependent problems[END_REF]). A scheme is entropy dissipative if for any j,

and entropy stable if we have an equality.

In residue form, we have

so that for any j φ

(note this term is the one formulated in proposition 3.3), we get, using

This suggests natural generalisation to the multidimensional case, i.e. the relation (20a).

The multidimensional case

Let us recall the entropy condition (20a),

Written like this, it seems that the residuals and the consistent entropy flux can be chosen independently, which is not exactly the case.

From the previous analysis, we have

with the condition (25c). This suggests to choose

Here we have set

We introduce the potential θ h in K by

Then we define ĝn by ĝn

The numerical flux is defined only on ∂K and {a} is the arithmetic average of the left and right states of a on the boundary of ∂K. The condition (20a) becomes

Here, the jump definition is consistent with Tadmor's definition in the one dimensional case: for any function w,

From this we see that a sufficient condition for local entropy stability is that:

1. In K, we have

where

2. On the boundary of K we ask that the numerical flux f is entropy stable so that

Note that this condition is automatically met for a continuous u h .

The condition (41c) is automatically met is the flux f is entropy stable in the sense of Tadmor:

Note that these conditions do not make any assumptions on the quadrature formulas on the boundary of K or in K. This is in contrast with the conditions on SAT-SBP schemes [START_REF] Gassner | A skew-symmetric discontinuous Galerkin spectral element discretisation and its relation to SBP-SAT finite difference methods[END_REF][START_REF] Hicke | Multidimensional summation-by-part operators: general theory and application to simplex elements[END_REF][START_REF] Chen | Entropy stable high order discontinuous Galerkin methods with suitable quadrature rules for hyperbolic conservation laws[END_REF][START_REF] Hiltebrand | Entropy stable shock capturing spacetime discontinuous Galerkin schemes for systems of conservation laws[END_REF].

⃗ n

Figure 5: Geometrical elements for defining the scheme.

• A total residual per edge Γ, i.e.

Here, if n is the outward unit normal to K (see figure 5), which enables us to define a right side and a left side. Hence we set

We notice that Φ Γ only depends on the values of u on each side of Γ.

The idea is to split the total residuals into sub-residuals so that a monotonicity preserving scheme can be defined. Here, we choose the Rusanov scheme, but other choices could be possible. Thus we consider • For the element K and any vertex σ ∈ K,

and

, for example the Euclidean norm.

• and for the edge Γ, any σ ∈ Γ,

where and α Γ ≥ max 5 for a definition of K ± .

We have the following conservation relations

The choice

|| are justified by the following standard argument. If we set Q = K or Γ, we can rewrite the two residuals as

with c Q σσ ≥ 0 under the above mentioned conditions. Indeed, using u hu σ = σ ∈K (u σu σ )ϕ σ , we get (for

which proves the result. Using standard arguments, as defining u h as the limit of the solution of

with

we see that we have a maximum principle. It is possible to construct a scheme that is formally second order accurate by setting

As in the "classical" RD framework, the coefficients β are well defined thanks to the conservation relations (4). The scheme is written as (48) where the residuals Φ K σ (u h ) (resp. Φ Γ σ (u h )) are replaced by Φ K, σ (u h ) (resp. Φ Γ, σ (u h ). The solution u h is defined: find u h linear in each triangle K such that for any degree of freedom σ (i.e. vertex of the triangulation),

We have a first order approximation just by replacing the "starred" residuals by the first order ones. The system (48) is solved by an iterative method such as(45).


I Zitouni
email: zitouni@loria.fr

K Smaïli
email: smaili@loria.fr

J-P Haton

BEYOND THE CONVENTIONAL STATISTICAL LANGUAGE MODELS: THE VARIABLE-LENGTH SEQUENCES APPROACH

In natural language, several sequences of words are very frequent. A classical language model, like n-gram, does not adequately take into account such sequences, because it underestimates their probabilities. A better approach consists in modelling word sequences as if they were individual dictionary elements. Sequences are considered as additional entries of the word lexicon, on which language models are computed. In this paper, we present an original method for automatically determining the most important phrases in corpora. This method is based on information theoretic criteria, which insure a high statistical consistency, and on French grammatical classes which include additional type of linguistic dependencies. In addition, the perplexity is used in order to make the decision of selecting a potential sequence more accurate. We propose also several variants of language models with and without word sequences. Among them, we present a model in which the trigger pairs are more significant linguistically. The originality of this model, compared with the commonly used trigger approaches, is the use of word sequences to estimate the trigger pair without limiting itself to single words. Experimental tests, in terms of perplexity and recognition rate, are carried out on a vocabulary of 20000 words and a corpus of 43 million words. The use of word sequences proposed by our algorithm reduces perplexity by more than 16% compared to those, which are limited to single words. The introduction of these word sequences in our dictation machine improves the accuracy by approximately 15%.

INTRODUCTION

The role of a statistical language model is to estimate the prior probability of the word sequences occurring in the task. In speech recognition, words are commonly used as the basic lexical units. Nevertheless, a consistent number of short phrases have a very high frequency. To take advantage of this fact, we propose to build a language model which bundles sequences of words, which are extracted from, frequent phrases. The tokens can be both single words and sequences of words. However, introducing word sequences as additional dictionary entries makes the problem of sparseness data more crucial and thus deteriorates the language model. Therefore, word sequences must not be arbitrarily included in the initial vocabulary.

One way that word sequences improve the language model is by capturing longer contexts. Indeed, with variable-length sequences, the fixed context of language models, like n-gram or n-class, is dynamically enhanced depending on the length of word sequences. Some sequences may have meanings that differ from those of the individual words. Such sequences (e.g. "write-off") may have different statistical properties from the component words ("write", "off"). Sequence-based language models may also improve automatic speech recognition (ASR) accuracy by allowing a better acoustic modelling of inter-word boundaries (e.g. "in-the" or "you-all") and the utilisation of inter-word pronunciation variants. The output of the speech decoder contains consequently more linguistic information than the word string. This is due to the fact that several word sequences often have linguistic structures, which contribute to the recognition of a sentence.

We present in this paper a new approach that aims at retrieving sequential variable-length regularities within streams of observations by reducing perplexity. These typical variable-length sequences are automatically extracted from text data, by using mutual information criterion. One of the originalities of our approach is the use of linguistic dependencies obtained by French syntactic classes. This approach aims at building variable-length sequences of words drawn from a large vocabulary (20000 words).

The purpose of this paper is also to discuss and to evaluate the performances brought by these typical word sequences on the most successful approach: n-gram and n-class. We denote by n-SeqGram and n-SeqClass the extension brought to n-gram and nclass respectively, by the set of typical word sequences. To include additional types of dependencies, we propose the idea of a trigger pair as the basic information-bearing element. If a word sequence A is significantly correlated with another word sequence B, then (AB) is considered as a "trigger pair", with A being the trigger and B the triggered sequence. When A occurs in the document, it triggers B, causing its probability estimate to change. The originality of this method, compared to the commonly used trigger approaches, is the use of word sequences to estimate the "trigger pair" without limiting itself to single words.

PRINCIPAL VARIABLE-LENGTH SEQUENCE MODELS

Several statistical-based procedures building automatically compound words have already been described in the literature.

Mercer creates typical sequences based on the concept of mutual information between two adjacent words [START_REF] Jelinek | Self-Organized Language Modelling for Speech Recognition[END_REF]. Two words are considered as a sequence if their mutual information and occurrence number are both greater than predefined thresholds.

Giachin suggests to determine the word sequences automatically with an optimisation criterion, which reduces perplexity [START_REF] Giachin | Phrase Bigrams for Continuous Speech Recognition[END_REF]. The basic idea of this approach is to choose at each iteration, the pair of words that best reduces the log-probability of the training class corpus. Then, this one is kept as a candidate. If the perplexity is reduced when the candidate pair is used as a unit, then this one is added as a unit in the vocabulary. The process is repeated until perplexity stop decreasing. Ries also uses perplexity as an optimisation criterion [START_REF] Ries | Class Phrase models for Language Modelling[END_REF]. The only difference with Giachin is that Ries extracts, at each iteration, a set of candidate word sequences and integrates into its vocabulary only those sequences that reduce perplexity.

Suhm [START_REF] Suhm | Towards Better Language Models for Spontaneous Speech[END_REF] as well as Kenne [START_REF] Kenne | Language Modeling of Spontaneous Speech in a Court Context[END_REF] use the same concept suggested by Giachin, with the difference that he chooses the class candidates according to their mutual information, instead of probability.

Beaujard and Jardino in [START_REF] Beaujard | Language Modeling Based on Automatic Word Concatenations[END_REF] use different measurements compared to those presented before: bigram counts, mutual information, probability of the current unit given the precedent one and the probability of the current unit given the following one. This approach starts by sorting adjacent unit couples in descending order according to one of the preceding measurements. Then, the sequences, which improve the corpus likelihood, are added to the dictionary. This process is repeated until the corpus liklihood stops improving.

The weakness of the above mentioned methods is their complexity. Therefore, they have been used only on few hundred words vocabularies.

Deligne builds word sequences (n-multigrams) by optimising the likelihood of word strings [START_REF] Deligne | Language Modeling by Variable Length Sequences: Theoretical Formulation and Evaluation of Multigrams[END_REF]. The adjacent words likelihood is computed by summing up the likelihood values of all possible sentence segmentations. Note that the huge number of possible sequences built from a vocabulary of thousands of words requires intensive computation.

WORD SEQUENCES SELECTION

Considering the success of class based approaches to cope with the sparseness of data in traditional n-gram modelling, we have explored their potential in our method [START_REF] Zitouni | Variable-Length Sequence Language Model for Large Vocabulary Continuous Dictation Machine: The n-SeqGram Approach[END_REF]. This one is entirely automatic and minimises the perplexity by making local optimisations. We begin by tagging the corpus with a set of syntactic classes C, where words are partitioned into manually determined equivalence classes [START_REF] Smaïli | An Hybrid Language Model for a Continuous Dictation Prototype[END_REF]. After fixing the maximum length of a word sequence q, the model starts by identifying the set of word sequences obtained by the concatenation of two classes or class sequences that produce a perplexity reduction. We choose all the candidate sequences whose class mutual information is close to the maximum in the corpus and whose count is above a given threshold. Let V be the word vocabulary and T J be the threshold of the mutual information:

where p denotes the coefficient used to compute T J , and J(c i , c j ) denotes the mutual information of the class couple or the class sequences on the training corpus:

where N(.) denotes the count function and T denotes the size of the training corpus. A large value of J(c i ,c j ) indicates that c i and c j occur as a sequence much more frequently than can be expected from pure chance. Let T min and T occ be the minimum count of a candidate class and word sequence respectively. Then, the procedure proceeds as follows:

1. Determine, on the training corpus, the couples c i ,c j for which the mutual information J(c i ,c j ) is greater than T J . The total number of classes in each couple of classes or class sequences should be less than q;

2. Add the set of new class sequences obtained in 1 to the class vocabulary, building C', and label the class corpus accordingly;

3. Use the word corpus and the corresponding class corpus labelled by C', to extract the corresponding word sequences; 4. Add the set of new sequences {s i ,s j } obtained in 3 with occurrence greater than T occ , to the vocabulary and modify the corpus accordingly;

5. Repeat until perplexity doesn't decrease.

Though the perplexity is computed on a "shrunk" corpus, when some phrases have been replaced by single symbols (word sequences), we have to keep the original number of words, unchanged because it is the actual number of words in the corpus [START_REF] Adda | Text Normalisation and Speech Recognition in French[END_REF].

It is important to note that, in order to generate long word sequences (e.g., "what time is it"); many shorter sequences have to be generated before (e.g., "what time"). Some of these shorter sequences are no longer useful after the longer ones have been generated, so they have to be discarded and their original component words should be used instead. However, in our approach we discard all shorter sequences that decrease the test perplexity when their original component words are used instead.

Figure 1 presents the convergence, in terms of perplexity, of the procedure cited above, according to iterations, and number of words in a sequence. The results show that the procedure reaches its optimum for a value of q equal to 6 in only 10 iterations.

EXTENSION OF BASIC LANGUAGE MODELS

) 1 ( ) , ( max , j i C c C c j c c J p T j i    ) 2 ( ) ( ) ( ) , ( log ) , ( j i j i j i c N c N T c c N c c J 

The n-SeqGram and the n-SeqClass Models

In automatic speech recognition, the most widely used and successful language model are the so-called n-gram and nclass models, where the dependency of the word under consideration is limited to the immediate predecessor words. To evaluate the performance brought by the typical word sequences extracted by the algorithm presented above, we developed a n-gram and a n-class models on an extended vocabulary that include both single words (which are still necessary to model the less frequent phrases) and word sequences. In other words, typical word sequences are treated as they were single lexicon entries. We denote by n-SeqGram and n-SeqClass the extension brought to n-gram and n-class respectively.

Sequence Trigger Based Modelling

It is clear that several sort of long-distance dependencies exist as well. To include long-distance dependencies in language models, we propose to use trigger pairs. Unlike the commonly approaches presented in the literature, where A and B are restricted to single words [START_REF] Tillmann | Selection Criteria for Word Trigger Pairs in Language Modeling[END_REF], the selection criterion used in this paper is based on trigger pairs where both the triggered and the triggering events are single words or word sequences.

A natural measure of the information provided by A on B is their average mutual information. We used this measure to extract the K best trigger pairs that reduce the perplexity of the language model. The value of K was estimated experimentally on a test corpus.

As usual, triggers are used as an additional component to a basic language model, like n-gram. Hence, trigger pairs are advantageous by the further information they provide to a basic language model.

The language model we use is a linear interpolation between a n-SeqGram, a cache and a trigger models. To build the trigger and the cache models, we use the same principle as in [START_REF] Tillmann | Selection Criteria for Word Trigger Pairs in Language Modeling[END_REF].

EVALUATION

To evaluate our model in real conditions, we obviously carried out experiments in terms of perplexity and implemented it in our dictation machine MAUD. In the following, we give a brief overview of its recognizer and describe the different.

Data Description

To build language models, we use a French corpus (LeM) which represents 2 years (87-88) of "Le Monde" newspaper (43 million words). To estimate the n-SeqClass and the n-class models, we use a set of 233 French syntactic classes [START_REF] Smaïli | An Hybrid Language Model for a Continuous Dictation Prototype[END_REF]. The test and training corpora used in this approach are by a set of 233 classes [START_REF] Smaïli | A new algorithm for word classification based on an improved simulated annealing technique[END_REF]. It is important to note that a word can belong to different classes (ex: the word "orange" can be a noun or an adjective). The vocabulary is compounded of the most frequent 20000 words of LeM corpus.

The number of typical word sequences is approximately equal to 4000. The number of pair triggers is estimated to 500000. To estimate the HMM2 phones, we use Bref80 spoken corpus [START_REF] Lamel | BREF: a Large Vocabulary Spoken Corpus for French[END_REF].

Acoustic Model

Each phoneme is modelled by 3 states second order Markov model (HMM2) [START_REF] Mari | Automatic Word Recognition Based on Second-Order Hidden Markov Models[END_REF]. Thus, each single word in the vocabulary is represented by the concatenation of the HMM2 phones which compose it. If the vocabulary unit is a typical word sequence, we introduce an optional HMM2 silence phone between single words, which compose it. Thus, for each 2 adjacent words A and B in a sequence, we evaluate on a training corpus the transition probabilities between the output HMM2 phones of A, the HMM2 silence phone and the input HMM2 phones of B.

Perplexity Results

Perplexity is usually considered as a performance measure of language models. It is therefore interesting to look at the test perplexity values obtained by the language models with and without typical word. The test corpus (5 million words) on which the perplexity was computed does not appear in the training corpus.

The language models evaluated in terms of perplexity are partitioned on 2 sets: language models based on single words S1 and their corresponding models using typical word sequences S2.

The S1 set includes bigram (P1), trigram (P2), biclass (P3), triclass (P4), linear interpolation between bigram, cache and single word triggers (P5), and linear interpolation between trigram, cache and single word triggers (P6). The S2 set includes 2-SeqGram (PS1), 3-SeqGram (PS2), 2-SeqClass (PS3), 3-SeqClass (PS4), linear interpolation between 2-SeqGram, cache and word sequences triggers (PS5), and linear interpolation between 3-SeqGram, cache and word sequences triggers (PS6). We use the "back-off" method to estimate language models [START_REF] Katz | Estimation of Probabilities from Sparse Data for the Language Model Component of a Speech Recognizer[END_REF]. A summary of test perplexity results is presented in Table 1. A comparison between these language models, in terms of perplexity, shows that each time, the introduction of typical word sequences has been done, it outperforms the basic model. For instance, the 3-Seqgram improves the trigram by 16,7%.

S1

MAUD System and Recognition Results

An evaluation was also done with MAUD [START_REF] Fohr | MAUD: Un prototype de machine à dicter vocale[END_REF], a continuous dictation system using a stochastic language model.

CONCLUSION AND PERSPECTIVES

We proposed in this paper an approach to overcome the limit of classical language models. This approach is based on typical variable-length word sequences as well as on single words. Typical word sequences to be modelled are automatically determined by a procedure that follows a perplexity minimisation combined with mutual information criterion. Test perplexity achieved more than 16% reduction and 15% accuracy improvement over language models based on single words.

Very interesting statement can be done about the nature of the discovered sequences. Some are merely group of words that frequently occur in a corpus. Most of them, however, are sensible word sequences representing linguistic constituents. For instance, several are syntactic groups, few of them have a semantic nature, etc.

Another manner to build "trigger pairs", linguistically more significant, has been proposed. Compared with the commonly used trigger approaches based only on single words, the trigger A and the triggered B units in the model we propose can be a variable-length word sequence.

To improve the performance of this approach, we propose to combine it with the multigram approach [START_REF] Deligne | Language Modeling by Variable Length Sequences: Theoretical Formulation and Evaluation of Multigrams[END_REF]. It also seems interesting to investigate the application of this approach to other problems: e.g., looking for semantic equivalence classes between word sequences in view of tagging concept and speech to speech automatic translation.

Figure 1 :

 1 Figure 1: convergence in terms of perplexity of the algorithm,

Table 1 :

 1 Test perplexity of different language models with and without typical word sequences.

		P1	P2	P3	P4	P5	P6
	PP	121.53 74.65 135.11 84.18 117.53 72.69
	S2	PS1	PS2	PS3	PS4	PS5	PS6
	PP	83.63	63.96	89.12	73.80	80.00	60.95

Table 2 :

 2 To evaluate the performance brought by the introduction of typical word sequences, we considered several versions of MAUD system: M1 which is the base version presented above without word sequences; MS1 which uses a 2-SeqGram in the second step and a 3-SeqGram in the third step (with typical word sequences); M2 which is similar to M1 with the difference that we use biclass and triclass instead of bigram and trigram respectively; MS2 in which we introduce typical word sequences and we replace the biclass and the triclass models by the 2-SeqClass and the 3-SeqClass respectively; M3 in which we add single word triggers and cache models to the third step of the M1 version, and MS3 in which we add word sequences triggers and cache models to the third step of the MS1 version of MAUD.A summary of recognition results (accuracy) is presented in Table2. In these experiments, the recognition is done on the 300 test sentences delivered by AUPELF-UREF for the evaluation campaign. Accuracy (Acc.) of different versions of MAUD system with and without typical word sequences.

	The basic