Eric Chénier
email: eric.chenier@univ-mlv.fr

Robert Eymard
email: robert.eymard@univ-mlv.fr

Thierry Gallouët
email: thierry.gallouet@univ-amu.fr

Raphaèle Herbin
email: raphaele.herbin@univ-amu.fr

An extension of the MAC scheme to locally refined meshes : convergence analysis for the full tensor time-dependent Navier-Stokes equations

Keywords: MAC scheme, incompressible steady and time-dependent Navier-Stokes equations, non conforming grids. MSC2010: 65N08, 76D05

A variational formulation of the standard MAC scheme for the approximation of the Navier-Stokes problem yields an extension of the scheme to general 2D and 3D domains and more general meshes. An original discretization of the trilinear form of the nonlinear convection term is proposed; it is designed so as to vanish for discrete divergence free functions. This property allows us to give a mathematical proof of the convergence of the resulting approximate solutions, for the nonlinear Navier-Stokes equations in both steady-state and time-dependent regimes, without any small data condition. Numerical examples (analytical steady and time-dependent ones, inclined driven cavity) confirm the robustness and the accuracy of this method.

Introduction

The Marker-And-Cell (MAC) scheme, introduced in [START_REF] Harlow | Numerical calculation of time-dependent viscous incompressible flow of fluid with a free surface[END_REF] is one of the most popular methods [START_REF] Patankar | Numerical heat transfer and fluid flow[END_REF][START_REF] Wesseling | Principles of Computational Fluid Dynamics[END_REF] for the approximation of the Navier-Stokes equations in the engineering framework, because of its simplicity and of its remarkable mathematical properties. The discrete unknowns are the components of the velocity and the pressure on staggered grids; the mass conservation equation and momentum conservation equations are discretized in such a way that the kinetic energy remains controlled. The first error analysis seems to be that of [START_REF] Porsching | Error estimates for MAC-like approximations to the linear Navier-Stokes equations[END_REF] in the case of the time-dependent Stokes equations on uniform square grids. The mathematical analysis of the scheme was also performed for the Stokes equations in [START_REF] Nicolaïdes | Analysis and convergence of the mac scheme i: The linear problem[END_REF] for uniform rectangular meshes, and generalized to non uniform rectangular meshes and irregular source terms in [START_REF] Blanc | Convergence of a finite volume scheme on a MAC mesh for the Stokes problem with righthand side in H -1[END_REF]. Error estimates may be obtained by viewing the MAC scheme as a mixed finite element method of the vorticity formulation [START_REF] Girault | Finite-element error estimates for the MAC scheme[END_REF], or by a mixed method in primitive variables, with the pressures approximated by Q 1 finite elements [START_REF] Han | A new mixed finite element formulation and the MAC method for the Stokes equations[END_REF]. Along the same lines, it is proven in [START_REF] Kanschat | Divergence-free discontinuous Galerkin schemes for the Stokes equations and the MAC scheme[END_REF] that a divergence conforming DG scheme based on the lowest order Raviart-Thomas space on rectangular meshes is algebraically equivalent to the MAC scheme. Error estimates for rectangular meshes were also obtained for the related covolume method, see [START_REF] Chou | A covolume method based on rotated bilinears for the generalized Stokes problem[END_REF] and references therein.

Mathematical studies of the MAC scheme for the non linear Navier-Stokes equations are scarcer. To our knowledge, the only convergence study is that of [START_REF] Nicolaïdes | Analysis and convergence of the mac scheme ii, Navier-Stokes equations[END_REF] for the steady-state Navier-Stokes equations and for uniform rectangular grids.

Extensions of the MAC scheme on general unstructured grids are not easy to derive, and most of the mathematical analyses that we described are restricted to rectangular cells. The covolume approach [START_REF] Nicolaides | The covolume approach to computing incompressible flows[END_REF] may be seen as one way to generalize the MAC scheme on unstructured grids. MAC schemes on triangular meshes are proposed and tested in [START_REF] Vidović | A superlinearly convergent Mach-uniform finite volume method for the Euler equations on staggered unstructured grids[END_REF]. A variational MAC scheme based on acute triangles is proposed in [START_REF] Eymard | MAC schemes on triangular meshes[END_REF], and the convergence anaysis is completed.

The aim of this paper is to provide the complete mathematical analysis of an extension of the MAC scheme on possibly non conforming meshes, allowing local refinement. This extended MAC scheme is a slight modification of a MAC-like scheme which was presented in [START_REF] Chénier | An extension of the mac scheme to some unstructured meshes[END_REF]. The modification concerns the discretization of the momentum equation, which was performed on dual Voronoï cells in [START_REF] Chénier | An extension of the mac scheme to some unstructured meshes[END_REF], while it is performed by a linear finite element method on a Delaunay triangulation built from the centers of the set of edges (in 2D), or faces (in 3D) where each component of the velocity is defined. This modification was found necessary in the mathematical analysis of the scheme for the steady-state and time-dependent nonlinear Navier-Stokes equations, in order to prove the convergence of the scheme. It also allows to easily handle the case of the full tensor viscosity. The convergence of a collocated finite volume scheme was proven in [START_REF] Eymard | Convergence analysis of a colocated finite volume scheme for the incompressible Navier-Stokes equations on general 2 or 3d meshes[END_REF] for the steady state and time-dependent Navier-Stokes equations, and we shall use some of the tools therein in the present analysis.

The outline of the paper is the following. In Section 2, we give the weak form of the steady-state and time-dependent Navier-Stokes equations. In Section 3 we first write a discrete variational formulation of the standard MAC scheme on the linear Stokes problem, and use this variational formulation to extend the MAC scheme to more complex geometries. The extension to the steady-state Navier-Stokes equation is presented in Section 4 where we also prove the convergence of the approximate solutions to a weak solution. The proof of convergence relies on a proper choice of the convection term, which takes the mass conservation into account. We then consider the case of the time-dependent problem in Section 5, and again prove the convergence of the method in this case, thanks to a discrete Aubin-Simon type result. In Section 6, the efficiency of the extended scheme is illustrated by numerical examples on a non-rectangular domain, using a local refinement along the boundary of the domain. The first example is a steady-state problem on a circular domain, for which the exact solution is known so that we may assess the numerical order of convergence. We then consider the inclined driven cavity problem, which implies the discretization of a non rectangular domain. The comparison with the literature shows a very good accuracy. We finally consider the time-dependent Green-Taylor vortex problem, that we approximate on a circular domain.

Weak formulation of the Navier-Stokes equations

Let Ω be an open bounded set of R d , where d denotes the space dimension. In the remainder of this paper, we assume the domain Ω to be polygonal (d = 2) or polyhedral (d = 3), in the sense that ∂Ω is a finite union of subsets of hyperplanes of R d . Let β ∈ [0, +∞) denote the Reynolds number.

We first consider the steady state case with a time-independent forcing term f ∈ L 2 (Ω) in the momentum equation. Then, a weak solution to the steady-state Navier-Stokes equations with homogeneous Dirichlet boundary conditions is a vector function u with components (u

(i) ) i=1,...,d , such that              u ∈ E(Ω), p ∈ L 2 (Ω) with Ω p(x)dx = 0, Ω S(u, v)(x)dx + β Ω (u(x) • ∇)u(x) • v(x)dx - Ω p(x)divv(x)dx = Ω f (x) • v(x)dx, ∀v ∈ H 1 0 (Ω) d , (1)
where

E(Ω) = {v = (v (i) ) i=1,...,d ∈ H 1 0 (Ω) d , divv = 0 a.e. in Ω}.
We consider two cases for the stress tensor S(u, v), namely:

-the usual simplified form for the incompressible Stokes or Navier-Stokes problem, which reads

S(u, v)(x) = ∇u(x) : ∇v(x) = d i=1 ∇u (i) (x) • ∇v (i) (x), for a.e. x ∈ Ω, ∀u, v ∈ H 1 0 (Ω) d , (2)
-the full stress tensor

S(u, v)(x) = λdivu(x)divv(x) + 2µǫ(u)(x) : ǫ(v)(x), for a.e. x ∈ Ω, ∀u, v ∈ H 1 0 (Ω) d , (3)
where µ > 0 and 3λ + 2µ ≥ 0 (these values could depend on the space variable through a coupled variable, such as the temperature) and ǫ(u

) i,j (x) = 1 2 (∂ i u (j) (x) + ∂ j u (i) (x)), for i, j = 1, . . . , d.
The coefficient β is strictly positive in the general (nonlinear) case and is set to 0 to obtain the linear Stokes problem.

We then consider the time-dependent case, for which we consider a finite time T of study of the flow, a time-dependent forcing term f ∈ L 2 (Ω × (0, T )) d in the momentum equation, and an initial condition u ini ∈ L 2 (Ω) d . Then, a weak solution to the time-dependent Navier-Stokes equations with homogeneous Dirichlet boundary conditions is a vector function u with components (u (i) ) i=1,...,d , such that

                       u ∈ L 2 (0, T ; E(Ω)) ∩ L ∞ (0, T ; L 2 (Ω) d ), - T 0 Ω u(x, t) • ∂ t ϕ(x, t) dx dt - Ω u ini (x) • ϕ(x, 0) dx + T 0 Ω S(u, ϕ)(x, t) dx dt + β T 0 Ω (u(x, t) • ∇)u(x, t) • ϕ(x, t)dx dt = T 0 Ω f (x, t) • ϕ(x, t) dx dt, ∀ϕ ∈ L 2 (0, T ; E(Ω)) ∩ C ∞ c (Ω × (-∞, T )) d . (4)
Remark 2.1 It may be proved that any weak solution u of (4) satisfies

∂ t u ∈ L 4/d (0, T ; E(Ω) ′ ) in the following classical sense T 0 ϕ(t) ∂ t u(t), v E(Ω) ′ ,E(Ω) dt = - T 0 ϕ ′ (t) Ω u(x, t)v(x)dxdt, ∀v ∈ E(Ω), ∀ϕ ∈ C 1 c ((0, T )).

A variational MAC scheme

Our extension of the MAC scheme to non conforming meshes is based on a discrete variational formulation. Hence in this section, we begin by considering a variational formulation of the standard MAC scheme for the approximation of the Stokes problem, that is (1) with β = 0. We then extend this variational scheme to non conforming meshes.

The standard MAC scheme for conforming meshes

For the sake of simplicity, let us first consider a two dimensional square domain Ω =]x, x[×]y, y[. The domain Ω is discretized in the MAC way, that is with a staggered arrangement of the rectangular discretization cells for the pressure and each of the velocity components, as depicted in Figure 1. Let N and M be two

111111111111 111111111111 V (2) σ V (1) σ K
σ ∈ E (2) σ ∈ E (1) y j y j-

1 2 x i+ 1 2 x i x i-1 2 y j+ 1 2 y1 2 = y x1 2 = x y M + 1 2 = y x N + 1 2 = x e (1)
e (2) Figure 1: Notations for the standard MAC scheme positive integers, and let M be the set of pressure grid cells (with the notations given in Figure 1:

M = ]x i-1 2 , x i+ 1 2 [×]y j-1 2 , y j+ 1 2 [, 1 ≤ i ≤ N, 1 ≤ j ≤ M .
The above notations may easily be extended to the case d = 3. For the space dimension d equal to 2 or 3, we denote by E = ∪ d i=1 E (i) the set of the edges or faces of the mesh, where E (i) is the set of edges associated to the i-th component of the velocity. In order to define the normal velocity flux from one cell to a neighbouring one, we introduce, for any pair σ, σ ′ ∈ E (k) , k = 1 or 2, the transmissivity τ

(k) σ,σ ′ between cell V (k) σ and cell V (k) σ ′ : τ (k) σ,σ ′ = |∂V (k) σ ∩ ∂V (k) σ ′ | d(x σ , x σ ′ ) , (5)
where σ ′ , and d(x σ , x σ ′ ) denotes the distance between the points x σ and x ′ σ . For instance, for a vertical edge σ = {x i+ 1 2 }×]y j-1 2 , y j+ 1 2 [∈ E (1) , one has:

|∂V (k) σ ∩ ∂V (k) σ ′ |
τ (1) σ,σ ′ =        y j+ 1 2 -y j-1 2 x i+ 3 2 -x i+ 1 2 if σ ′ = {x i+ 3 2 }×]y j-1 2 , y j+ 1 2 [, x i+1 -x i y j+1 -y j if σ ′ = {x i+ 1 2 }×]y j+ 1 2 , y j+ 3 2 [. (6)
For any K ∈ M, we denote by E K the subset of E int containing all edges (or faces) of K which are internal, and by E (k) (k) . For an internal edge σ ∈ E int separating two cells K and L, we shall write σ ∈ K|L = L|K (at this stage, we could write σ = K|L but in the generalized MAC scheme, interfaces will be allowed to contain more than one edge or face). We denote by (e (k) ) k=1,...,d the canonical orthonormal basis of R d and, for σ ∈ K|L, with K, L ∈ M and by n K,σ the unit normal vector to σ outward to K. We then write σ ∈ --→ K|L in the case where σ ∈ K|L ⊂ E (k) for some k = 1, . . . , d and n K,σ • e (k) = 1. We finally represent by D = (M, E) the collection of all the space discretization data.

K = E K ∩E
Let us consider here the simplest case of the Stokes equations, i.e. β = 0, with the stress tensor given by [START_REF] Bramble | A proof of the inf-sup condition for the Stokes equations on Lipschitz domains[END_REF]. The standard MAC scheme may then be written:

Find (u σ ) σ∈E ⊂ R, (p K ) K∈M ⊂ R ; K∈M |K|p K = 0, d k=1 σ∈E (k) K |σ|u σ e (k) • n K,σ = 0, ∀K ∈ M, (7a)
-

σ ′ ∈E (k) τ (k) σ,σ ′ (u σ ′ -u σ ) + |σ|(p L -p K ) = V (k) σ f (k) (x)dx, (7b)
∀k = 1, . . . , d, ∀σ ∈ E (k) , and K, L ∈ M such that σ ∈ --→ K|L.

Let us define H M (Ω) as the set of piecewise functions constant in K ∈ M (pressure unknown), and

H (k) E (Ω) as the set of piecewise functions which are constant in V σ , for σ ∈ E (k) (kth component of the velocity unknown). Let H E (Ω) = {v = (v (k) ) k=1,...,d ; v (k) ∈ H (k) E (Ω)}. The piecewise constant discrete divergence of v ∈ H E (Ω) is the function div M v ∈ H M (Ω) defined by: div M v(x) = div K v = 1 |K| d k=1 σ∈E K |σ|v K,σ , for a.e. x ∈ K, ∀K ∈ M, ∀v ∈ H E (Ω), (8)
where v K,σ = v σ n K,σ • e (k) . The discrete mass conservation equation (7a) can then be simply written as:

div M u(x) = 0, for a.e. x ∈ Ω. (9)
We now introduce a variational formulation of the discrete momentum equation (7b) by recalling (see e.g. [START_REF] Eymard | Finite volume methods[END_REF]Chapter 3] that if the points x σ are the nodes of a Delaunay triangulation, then

τ (1)
σ,σ ′ = ∇ξ (1) σ (x) • ∇ξ

(1)

σ ′ (x)dx,
where the functions (ξ

σ ) σ∈E (1) are the P 1 finite element basis functions defined on the Delaunay triangulation, such as the one depicted in Figure 2 (in which the nodes are the points x σ , for all σ ∈ E (1) ). The Figure 2: Triangular mesh for the P 1 finite element approximation u (1) of u (1) . functions (ξ

(2)
σ ) σ∈E [START_REF] Bramble | A proof of the inf-sup condition for the Stokes equations on Lipschitz domains[END_REF] are defined in a similar way, and we may then define u (k) ∈ H 1 0 (Ω) such that

u (k) = σ∈E (k) u σ ξ (k) σ , ∀k = 1, . . . , d. (10)
We then define an inner product •, • E on H E (Ω) (this holds for both cases (2) and ( 3)) by

u, v E = Ω S( u, v)(x)dx, ∀u, v ∈ H E (Ω), (11)
which we expect to approximate the inner product Ω S(u, v)(x)dx of the continuous problem. We then obtain, multiplying [START_REF] Eymard | Finite volume methods[END_REF] by v σ and summing on k = 1, 2 and σ ∈ E (k) ,

u, v E - Ω p(x)div M v(x)dx = Ω f (x) • v(x)dx, ∀v ∈ H E (Ω), (12)
A discrete variational formulation of the standard MAC scheme [START_REF] Eymard | Finite volume methods[END_REF] is therefore:

Find u ∈ H E (Ω) and p ∈ H M (Ω) s. t.

K∈M

|K|p K = 0 and ( 9) and (12) hold. (13)

The extended MAC scheme for non conforming meshes

Let us now turn to an extension of the above depicted standard MAC scheme to more general meshes (including local refinement as in Figure 6; note that these local refinements may be used to follow the contours of a general non rectangular domain, as in Figures 3 and4.

We consider 2D or 3D meshes of Ω, which are such that all internal edges (2D) or faces (3D) (from now on, we only use the word "face", in 2D or 3D) have their normal vector parallel to one of the basis vector e (k) of the space R d , for some k = 1, . . . , d. In other words, all internal edges must be aligned with one of the reference axes. Note that on the other hand, the external faces, that is the faces of the mesh lying on the boundary ∂Ω need not be aligned with the axes: they are only assumed to be planar. In fact a tilted cavity such as the one depicted in Figure 3 is easily meshed with such a grid. Curved boundaries may also be meshed with such grids, by using local refinement close to the boundaries, such as in Figure 5.

We denote by M the set of pressure cells. Examples of resulting pressure grids are depicted in the left part of Figures 3 and5. For all K ∈ M, we again denote by E K the set of all internal faces of K (therefore, the faces of K which are on ∂Ω are not elements of E K ), and we define the set E as the union over K ∈ M of all the sets E K . It is assumed that a given σ ∈ E int is entirely included in an interface between two cells, say K and L; we shall write σ ∈ K|L. Note that an interface K|L is allowed to contain several faces of the mesh; this may for instance happen in adaptive mesh refinement (and de-refinement) procedures. We then introduce the set E (k) as the subset of E which contains all the internal faces whose normal is parallel to the basis vector e (k) . For any σ ∈ E, x σ denotes the center of gravity of σ.

In order to get a discrete variational MAC-like scheme, we consider, for any k = 1, . . . , d, the set of internal points V (k) int = (x σ ) σ∈E (k) and a given family of external points V (k) ext containing at least all the vertices of Ω.

The only additional difficulty on the non conforming grid is the discretization of the diffusion term, which we simply discretize by a linear finite element approximation. To this purpose, we introduce a Delaunay triangulation T (k) of Ω whose vertices are

V (k) int ∪ V (k) ext . Such a triangulation of Ω is a set of simplices: triangles in 2D, tetrahedra in 3D. Each simplex has d + 1 vertices which belong to V (k) int ∪ V (k)
ext . The triangulation is assumed to satisfy the Delaunay property, which means that the interior of the circumcircle (in 2D) or of the circumsphere (in 3D) of any simplex T ∈ T (k) does not contain any element of

V (k) int ∪ V (k) ext .
Examples of Delaunay triangulations constructed from the edge mid-points are illustrated in Figures 3 and5 (middle and right parts).

We then denote, for any σ ∈ E (k) , the function ξ

(k)
σ , which is continuous, piecewise P 1 on any T ∈ T (k) , and whose value is 1 at the point x σ and 0 at points

x σ ′ for any σ ′ ∈ E (k) \ {σ}. Let {V (k) σ , σ ∈ E (k)
} be the Voronoï mesh associated to the family (x σ ) σ∈E (k) , defining the Voronoï cells as follows:

V (k) σ = {x ∈ Ω, d(x, x σ ) < d(x, x σ ′ ), σ ′ ∈ E (k) \ {σ}}, ∀σ ∈ E (k) .
See Figures 4 and6 for examples of the superposition of the Delaunay triangulations and the Voronoï mesh construction. We finally denote by D the collection of all the space discretization data.

Remark 3.1 Note that in the case of a uniform rectangular mesh, the Voronoï cells thus defined are equal to the velocity cells defined in the previous section. However, this is no longer true if a non uniform mesh is used, even in the conforming case; indeed, in this latter case, the Voronoï cells

V (k) σ
are again rectangles, but they are not equal to the (rectangular) velocity cells of the classical MAC scheme. In the case of hanging nodes, they are no longer rectangular, as can be seen in Figure 6, where we depict the Delaunay grid and the Voronoï cells for the horizontal and vertical velocities. We may again define H M (Ω) as the set of piecewise functions constant on the pressure cells K ∈ M, the set H (k) E (Ω) of piecewise constant functions on the dual grid cells V σ , for σ ∈ E (k) ; this discrete set is the space of functions meant to approximate the k-th component of the velocity. We then denote by

H E (Ω) the set of all v = (v (k) ) k=1,...,d with v (k) ∈ H (k) E (Ω).
We then define:

v (k) = σ∈E (k) v σ ξ (k) σ ∈ H 1 0 (Ω), (14)
we denote by v = ( v (k) ) k=1,...,d , and we define the norm

v E = ∇ v L 2 (Ω) d×d , ∀v ∈ H E (Ω). (15)
The extended MAC scheme for the Stokes equations (β = 0) is again ( 8)-( 13), applying Definition (11) for •, • E . We begin by defining some interpolation operators between H E (Ω) and (H M (Ω)) d .

Definition 4.1 (From H E (Ω) to H M (Ω). . . and back) Let D be a possibly non conforming mesh as depicted in Section 4. For v ∈ H E (Ω), we define Π K v by its components

(Π K v) (k) : (Π K v) (k) = 1 σ∈E (k) K |σ| σ∈E (k) K |σ|v σ , k = 1, . . . , d, (16)
and

Π M v ∈ H M (Ω) = (H M (Ω)) d as the piecewise constant function equal to (Π K v) on cell K. We then define Π E v ∈ H E (Ω)
as the following piecewise constant function on the Voronoï cells:

Π E w = σ∈E int σ∈K|L 1 2 (Π K w + Π L w)1 Vσ , where 1 Vσ denotes the characteristic function of V σ , that is 1 Vσ (x) = 1 if x ∈ V σ and 0 otherwise,
∇ E v = ∂ (1) E v, . . . , ∂ (d)
E v t , with
∂ (i) E v = σ∈E (i) ∂ σ v 1 Vσ and ∂ σ v = (v L -v K ) |σ| |Vσ| , if σ ∈ E int , σ ∈ --→ K|L, 0, if σ ∈ E ext , (17)
where σ ∈ --→ K|L means that σ ∈ K|L ⊂ E (k) for some k = 1, . . . , d and n K,σ • e (k) = 1. We then define the following trilinear form b E on (H E (Ω)) 3 by:

b E (u, v, w) = Ω (u • ∇ E )Π M v • Π E w dx, for u, v, w ∈ H E (Ω) (18)
where, for any v ∈ H M (Ω),

(u • ∇ E ) v(x) = d i=1 σ∈E (i) u σ ∂ σ v 1 Vσ (x).
It is well-known that the continuous trilinear form satisfies b(u, v, v) = -1 2 Ω |v| 2 divu dx for all u, v ∈ H 1 0 (Ω) 2 , and therefore, b(u, v, v) = 0 if divu = 0. Similarly, we have the following result for the discrete trilinear form. Lemma 4.1 (Properties of the trilinear form) Let u, v, w ∈ H E (Ω) and let b E be defined by [START_REF] Nicolaides | The covolume approach to computing incompressible flows[END_REF]. Then:

b E (u, v, w) = K∈M σ∈E K σ∈ --→ K|L |σ|u K,σ Π L v -Π K v 2 • Π K w, ∀u, v, w ∈ H E (Ω), ( 19
)
where u K,σ = u σ n K,σ • e (k) . Moreover, b E (u, v, v) = - 1 2 Ω |Π M v| 2 div M u, ( 20
)
where the discrete divergence operator div M is defined by [START_REF] Eymard | Convergence analysis of a colocated finite volume scheme for the incompressible Navier-Stokes equations on general 2 or 3d meshes[END_REF];

therefore, if div M u = 0, b E (u, v, v) = 0.
Proof. From ( 18) we get that

b E (u, v, w) = σ∈E σ∈ --→ K|L u σ (Π L v -Π K v) |σ| 1 2 (Π K w + Π L w). = 1 2 σ∈E σ∈ --→ K|L u σ (Π L v -Π K v) |σ|Π K w + 1 2 σ∈E σ∈ --→ L|K u σ (Π K v -Π L v) |σ|Π K w.
Reordering the summation over the edges of each cell K yields [START_REF] Patankar | Numerical heat transfer and fluid flow[END_REF]. Taking w = v in [START_REF] Patankar | Numerical heat transfer and fluid flow[END_REF] then yields that

b E (u, v, v) = 1 2 K∈M σ∈E K σ∈K|L |σ|u K,σ Π L v • Π K v -|Π K v| 2 ,
which yields (20) by conservativity. The extended MAC scheme for the Navier-Stokes equation then reads:

Find u ∈ H E (Ω) and p ∈ H M (Ω) s. t. K∈M |K|p K = 0, ( 21a
)
div M u(x) = 0, for a.e. x ∈ Ω. (21b) u, v E - Ω p(x)div M v(x)dx + β b E (u, u, v) = Ω f (x) • v(x)dx, ∀v ∈ H E (Ω). ( 21c
)
Remark 4.1 (Link with the classical MAC scheme) In the case of the Stokes problem on a conforming rectangular grid, the scheme presented here is equivalent to the classical MAC scheme. In the case of the nonlinear Navier Stokes equations, the scheme is not quite the same, since the centred MAC scheme has a 3 point stencil in each direction whereas the scheme presented here has a 5 point stencil. This is due to the fact that we chose to take Π E w rather than w in the expression of the trilinear form [START_REF] Nicolaides | The covolume approach to computing incompressible flows[END_REF], in order to obtain the property [START_REF] Porsching | Error estimates for MAC-like approximations to the linear Navier-Stokes equations[END_REF], which is quite useful to obtain the estimates on u.

Mathematical analysis

Let D be a possibly non conforming mesh, such as introduced in Section 3.2. We define h D as the maximum value of the diameters of all T ∈ T (k) and all

V (k) σ , σ ∈ E (k) , k = 1, . . . , d.
The regularity θ D of D is defined as the minimum value of:

1. all ratios diam(T )/diam(T ′ ), for all neighbouring simplices T, T ′ ∈ T (k)

, k = 1, . . . , d, 2. all ratios |T |/diam(T ) d , T ∈ T (k) , k = 1, . . . , d, 3. all ratios |V (k) σ |/|T |, |T |/|V (k) σ |, diam(V (k) σ )/diam(T ), diam(T )/diam(V (k) σ ), for any T ∈ T (k) with vertex x (k) σ . 4. all ratios |σ| diam(K)/|V σ |, σ ∈ E int , K ∈ M σ .
Let us then introduce the following interpolation operators.

Definition 4.3 (Interpolation operators) For v = (v (1) , . . . , v (d) ) ∈ H 1 0 (Ω) d , let P E v ∈ H E (Ω) be de- fined by the components (P E v) (k) of its piecewise constant values on the dual cells V (k) σ , for k = 1, . . . , d. (P σ v) (k) = 1 |σ| σ v (k) ds(x), ∀σ ∈ E (k) . ( 22
)
For ϕ ∈ H 1 0 (Ω), let P M ϕ ∈ H M (Ω) be defined by its piecewise constant values on the cells K ∈ M:

(P M ϕ) K = ϕ(x K ), ∀K ∈ M. ( 23
)
Following the ideas of [START_REF] Scott | Finite element interpolation of nonsmooth functions satisfying boundary conditions[END_REF] applied to the piecewise P 1 interpolation P E v of v, one may check that the interpolation operator P E satisfies the following property.

P E v E ≤ C 1 v H 1 (Ω) d . (24)
Lemma 4.3 (Properties of the discrete divergence) Let v ∈ (H 1 0 (Ω)) d , let P E be the interpolation operator defined by [START_REF] Simon | Compact sets in the space lp(0,t;b)[END_REF].and let p ∈ H M . Then

Ω p(x)div M P E v(x)dx = Ω p(x)divv(x)dx. ( 25
)
Moreover, for any u ∈ H E , and for any q ∈ H M (Ω), one has:

Ω q(x)div M udx = - Ω ∇ E q(x) • u(x)dx. (26)
Proof. The first result is an obvious consequence of the relation 8 defining the discrete divergence operator and of the fact that p is piecewise constant on the cells K ∈ M. The second result follows from the fact that

Ω q(x)div M udx = K∈M q K d k=1 σ∈E (k) K |σ|u σ e (k) • n K,σ = σ∈ --→ K|L (q K -q L )|σ|u σ = - Ω ∇ E q(x) • u(x)dx.
The following lemma gives some estimates on the trilinear form which are used to obtain some estimates on the solutions of the schemes, for both the steady-state treated in this section and the time-dependent case in Section 5.

Lemma 4.4 (Estimates on the trilinear form) Let D be a discretization in the sense given in Section 4.1 and let b E be the trilinear form defined by [START_REF] Patankar | Numerical heat transfer and fluid flow[END_REF]. Then there exist C 2 and C 3 , only depending on any θ ≤ θ D and on Ω, such that

|b E (u, v, w)| ≤ C 2 u (L 4 (Ω)) d v E w (L 4 (Ω)) d ≤ C 3 u E v E w E , ∀u, v, w ∈ H E (Ω). ( 27
)
Moreover, there exists C 4 , only depending on Ω and θ, such that

|b E (u, u, v)| ≤ C 4 u 1/2 L 2 (Ω) u 3/2 E v E , ∀u ∈ H E (Ω); div M u = 0, ∀v ∈ H E (Ω). (28)
Proof. From the definition (18) of the trilinear form b E denoting by ṽ(j) (resp. w(j) ) the j-th component of Π M v (resp. Π E w), we get thanks to the Cauchy-Schwarz inequality, we get that:

|b E (u, v, w)| ≤ d k=1 d j=1 u (k) L 4 (Ω)) ∂ (k) E ṽ(j) L 2 (Ω))
w(j)

L 4 (Ω)) ≤ d 2 u (L 4 (Ω)) d ∇ E (Π M v) (L 2 (Ω)) d×d Π E w (L 4 (Ω)) d .
Let us then remark that the components of Π K w+Π L w 2 are barycentric combinations of neighbouring terms w σ ; hence there exists C 5 , only depending on Ω and θ, such that

Π E w (L 4 (Ω)) d ≤ C 5 w (L 4 (Ω)) d .
In order to bound the term

∇ E (Π M v) (L 2 (Ω)) d×d , we first define the functions Π (k) -v and Π (k) + v by Π (k) -v(x) = Π K v, ∀σ ∈ E (k) , for a.e. x ∈ V (k) σ , and K, L such that σ ∈ --→ K|L,
and

Π (k) + v(x) = Π L v, ∀σ ∈ E (k) , for a.e. x ∈ V (k) σ , and K, L such that σ ∈ --→ K|L.
We finally define δ (k) (x) =

|V (k) σ | |σ| for all x ∈ V (k)
σ . We then get that

∂ (k) E Π M v (L 2 (Ω)) d = Ω 1 δ (k) (x) 2 Π (k) + v(x) -Π (k) -v(x) 2 dx = d ℓ=1 Ω 1 δ (k) (x) 2 Π (k) + v (ℓ) (x) -Π (k) -v (ℓ) (x) 2 dx.
In order to apply Lemma 7.1, we first remark that, thanks to the regularity hypotheses of the mesh, there exists some C 6 > 0, only depending on θ, such that δ (k) (x) ≥ C 6 δ(x), with δ(x) defined in Lemma 7.1. Since the functions Π (k) -v (ℓ) (x) only depend on the discrete unknowns v ℓ σ , we may introduce the functions

ψ k,ℓ -,σ such that Π (k) -v (ℓ) (x) = σ∈E (ℓ) v ℓ σ ψ k,ℓ -,σ (x),
which are the piecewise constant functions defined by:

∀σ ∈ E (k) , with K, L such that σ ∈ --→ K|L, ψ k,ℓ -,σ ′ (x) =        |σ ′ | σ ′′ ∈E (ℓ) K |σ ′′ | if σ ′ ∈ E (ℓ) \ E K , for a.e. x ∈ V (k) σ , 0 if σ ′ ∈ E (ℓ) \ E K or if x / ∈ V (k) σ .
The functions ψ k,ℓ -,σ satisfy the hypothesis (49) of Lemma 7.1; furthermore, thanks to the regularity of the mesh, the mesh dependent bound C 28 defined by (50) remains bounded by a function of θ. We may thus apply Lemma 7.1, which yields (51). This implies

Ω 1 δ (k) (x) 2 Π (k) -v (ℓ) (x) -v (ℓ) (x) 2 dx ≤ C 29 (C 6 ) 2 ∇ v (ℓ) 2 L 2 (Ω) d .
Similarly, we have the same inequality with

Π (k) + v (ℓ) instead of Π (k)
-v (ℓ) , which shows the existence of C 7 > 0, only depending on θ, such that

∇ E (Π M v) (L 2 (Ω)) d×d ≤ C 7 ∇ v L 2 (Ω) d×d ,
thus concluding the left inequality of (27). Now, thanks to the equivalence of the norms proved in Lemma 7.2 in the appendix (inequality (55)), there exists C 8 ∈ R + , only depending on any θ ≤ θ D , such that

u (k) L 4 (Ω) ≤ C 8 u (k) L 4 (Ω) ,
Applying the standard Sobolev inequality

u (k) L 4 (Ω) ≤ C sob ∇ u (k) L 2 (Ω) d ,
where C sob only depends on Ω and d, we conclude that there exists C 9 , only depending on Ω and on any θ ≤ θ D , such that

u (k) L 4 (Ω) ≤ C 9 ∇ u L 2 (Ω) d×d .
Therefore, we conclude the right inequality of (27).

Let us then prove (28); since div M u = 0, we have

b D (u, u, v) = -b D (u, v, u), which proves, using (27), that |b D (u, u, v)| ≤ C 2 u 2 L 4 (Ω) v E .
Using the Cauchy-Schwarz inequality, we have:

u 2 L 4 (Ω) ≤ u 1/2 L 2 (Ω) u 3/2 L 6 (Ω) ,
We again apply Lemma 7.2: there exists C 10 ∈ R + , only depending on θ and Ω, such that

u L 6 (Ω) ≤ C 10 u L 6 (Ω) .
Applying the standard Sobolev inequality, we get that u L 6 (Ω) ≤ C sob ∇ u L 2 (Ω) d×d , where C sob ∈ R + depends only on Ω and d; therefore, by the definition (15) of the norm • E , we get:

|b D (u, u, v)| ≤ C u 1/2 L 2 (Ω) u 3/2 E v E .
which concludes the proof of Lemma 4.4.

Lemma 4.5 (Estimates on the velocity and the pressure for the Navier-Stokes problem) Let D be a discretization in the sense given in Section 4.1 and let θ ≤ θ D . Let (u, p) ∈ H E (Ω) × H M (Ω) be a solution to [START_REF] Scott | Finite element interpolation of nonsmooth functions satisfying boundary conditions[END_REF]. Then there exists C 11 , only depending on Ω (and on λ and µ in the case (3), this dependency is no longer mentioned in this paper), such that u satisfies the following estimates:

u E ≤ C 11 f (L 2 (Ω)) d . ( 29
)
Moreover, there exists C 12 only depending on β, θ and Ω such that

p L 2 (Ω) ≤ C 12 f (L 2 (Ω)) d . ( 30
)
As a direct consequence, there exists one and only one solution (if β = 0) and at least one solution (if β > 0) to the scheme [START_REF] Scott | Finite element interpolation of nonsmooth functions satisfying boundary conditions[END_REF].

Proof. We let v = u in [START_REF] Scott | Finite element interpolation of nonsmooth functions satisfying boundary conditions[END_REF]. Let us first remark that we have Ω p(x)div M u(x)dx = 0 and that by the definition [START_REF] Patankar | Numerical heat transfer and fluid flow[END_REF] of b E , we have

b E (u, u, u) = - K∈M 1 2 |Π K u| 2 d k=1 σ∈E (k) K |σ|u σ e (k) • n K,σ = 0,
since div M u(x) = 0. Hence we obtain

C 13 u 2 E ≤ S(u, u) L 1 (Ω) = Ω f (x) • u(x)dx,
where we denote by C 13 > 0 the constant involved in the Korn inequality, which holds for both cases (2) and (3). We then have, thanks to the Cauchy-Schwarz inequality,

u 2 E ≤ f L 2 (Ω) d u L 2 (Ω) d .
Let u be defined by [START_REF] Gallouët | Compactness of discrete approximate solutions to parabolic pdesapplication to a turbulence model[END_REF]. Applying Lemma 7.2, we get that there exists C 14 , only depending on θ, such that

u L 2 (Ω) d ≤ C 14 u L 2 (Ω) d .
Thanks to the Poincaré inequality, we may write

u L 2 (Ω) d ≤ diam(Ω) u E . (31)
Therefore we get (29).

Let us now turn to the proof of (30). We use the following property, first due to Nečas [START_REF] Nečas | Les méthodes directes en théorie des équations elliptiques[END_REF], see also [START_REF] Bramble | A proof of the inf-sup condition for the Stokes equations on Lipschitz domains[END_REF]: there exists v ∈ H 1 0 (Ω) d such that p(x) = divv(x) for a.e. x ∈ Ω and there exists C 15 , only depending on

Ω, such that v H 1 (Ω) d ≤ C 15 p L 2 (Ω) . (32)
Let P E be the interpolation operator defined by [START_REF] Simon | Compact sets in the space lp(0,t;b)[END_REF]. By Lemma 4.3, we have:

Ω p(x)div M P E v(x)dx = Ω p(x)divv(x)dx = Ω p(x) 2 dx.
We then get, using P E v ∈ H E (Ω) as test function in Scheme ( 21),

u, P E v E - Ω p(x) 2 dx + β b E (u, u, P E v) = Ω f (x) • P E v(x)dx. (33)
Thanks to the Cauchy-Schwarz inequality, we get that there exists C 16 (only depending on λ and µ in the case (3), this dependency is no longer recalled), such that

u, P E v E ≤ C 16 u E P E v E .
Using Inequality [START_REF] Wesseling | Principles of Computational Fluid Dynamics[END_REF], we get that there exists C 17 , only depending on θ and Ω, such that

u, P E v E ≤ C 17 u E v H 1 (Ω) d ≤ C 17 C 11 f (L 2 (Ω)) d C 15 p L 2 (Ω) .
We may also write, thanks to the Poincaré inequality and to (32),

- Ω f (x) • P E v(x)dx ≤ diam(Ω)C 15 f (L 2 (Ω)) d p L 2 (Ω) ,
Therefore, using (29) and ( 27), we get the existence of C 18 such that

p 2 L 2 (Ω) ≤ C 18 f (L 2 (Ω)) d + f 2 (L 2 (Ω)) d p L 2 (Ω) .
which concludes the proof of (30).

In the case where β = 0, the inequalities (29) and (30) suffice to prove that the square linear system issued from Scheme (21) (replacing one equation of (9) by Ω p(x)dx = 0) is invertible. If β > 0, using the topological degree argument as done in [START_REF] Eymard | Convergence analysis of a colocated finite volume scheme for the incompressible Navier-Stokes equations on general 2 or 3d meshes[END_REF], we conclude to the existence of at least one solution to Scheme [START_REF] Scott | Finite element interpolation of nonsmooth functions satisfying boundary conditions[END_REF].

The next lemma shows a property of weak convergence of the discrete gradient which is used in the passage to the limit in the scheme.

∇ E v D ) D∈F is bounded in (L 2 (Ω)) d , ( 34
) the family (v D ) D∈F converges weakly in L 2 (Ω) to v ∈ L 2 (Ω) as h D → 0. ( 35
)
Then v ∈ H 1 0 (Ω), and the family (∇ E v D ) D∈F converges to ∇v weakly in L 2 (Ω) as h D tends to 0.

Proof. Let ψ = (ψ 1 , . . . , ψ d ) ∈ (C ∞ (R d )) d ; then Ω ∇ E v D (x) • ψ(x)dx = Ω ∇ E v D (x) • P E ψ(x)ds(x) + R E
where P E is the interpolation operator defined by [START_REF] Simon | Compact sets in the space lp(0,t;b)[END_REF], and

|R E | ≤ C ψ h D ∇ E v D (L 2 (Ω)) 2 → 0 as h D → 0,
thanks to Assumption (34). Now, by ( 26) and (25) of Lemma 4.3,

Ω ∇ E v D (x) • P E ψ(x)ds(x) = - Ω v D (x)divψ(x)dx.
Therefore, by Assumption (35),

Ω ∇ E v D (x) • P E ψ(x)ds(x) → - Ω v(x)divψ(x)dx,
which shows that ∇ E v D tends to ∇v in the distribution sense. Since the sequence (∇ E ) D∈F is bounded in L 2 (Ω), we have that ∇v ∈ L 2 (Ω), and prolonging v D by 0 outside of Ω, we get that

v = 0 in R d \ Ω. Therefore, ∇ E v D tends to ∇v ∈ H 1 0 (Ω) weakly in (L 2 (Ω)) d .
Theorem 4.1 (Convergence of the scheme) Let F be a family of discretizations in the sense given in Section 4.1, such that there exists θ > 0 with θ ≤ θ D for all D ∈ F. For any

D = (M, E) ∈ F, let (u E , p M ) ∈ H E (Ω)s × H D (Ω)
denote a solution to Scheme [START_REF] Scott | Finite element interpolation of nonsmooth functions satisfying boundary conditions[END_REF]. Then there exists a weak solution (u, p) of (1) such that, up to a subsequence, u E converges in L 2 (Ω) d to u and p M converges in L 2 (Ω) d to p as h D → 0. Moreover, if β = 0, the whole family converges to the unique weak solution of (1) as h D → 0.

Proof. Let (D (ℓ) ) ℓ∈N be a sequence of elements of F, such that h D (ℓ) tends to 0 as ℓ → ∞ and such that there exists θ > 0 with θ D (ℓ) ≥ θ, for all m ∈ N. Let (u E (ℓ) , p M (ℓ) ) denote a solution of (21) for the discretization D ℓ = (M ℓ , E ℓ , δt ℓ ). From estimate (29), using Rellich's theorem, we deduce that there exists u ∈ H 1 0 (Ω) d (with u = (u (k) ) k=1,...,d ) and a subsequence of (D (ℓ) ) m∈N , again denoted by (D (ℓ) ) ℓ∈N , such that u

(k) M (ℓ) ∈ H 1 0 (Ω) weakly converges in H 1 0 (Ω) d (therefore strongly in L 2 (Ω) d ) to u (k)
as ℓ → ∞ for k = 1, . . . , d. Using Lemma 7.1 and the estimate (29), we get that u E (ℓ) also converges in L 2 (Ω) d to u as ℓ → ∞. Thanks to the estimate (30) on the pressure, we may then consider a subsequence of (D (ℓ) ) ℓ∈N , again denoted by (D (ℓ) ) ℓ∈N , such that p M (ℓ) weakly converges in L 2 (Ω) to some function p ∈ L 2 (Ω) as ℓ → ∞, with Ω p(x)dx = 0.

We now have to prove that (u, p) is a weak solution of ( 1), which we do by passing to the limit on the weak form of the scheme.

Let us first show that u ∈ E(Ω), i.e. divu(x) = 0 for a.e. x ∈ Ω. Let ϕ ∈ C ∞ c (Ω); multipying (21b) by P M ϕ and integrating over Ω yields, thanks to Lemma 4.3:

Ω P M ϕ(x) • div M u E (x)dx = Ω ∇ E P M ϕ(x) • u E (x)dx = 0.
Thanks to the regularity of the mesh, there exists C 19 depending only on ϕ and θ such that

∇ E P M ϕ (L 2 (Ω)) d ≤ C 19 .
Therefore, by Lemma 4.6, ∇ E P M ϕ tends to ∇ϕ weakly in (L 2 (Ω)) d as h D tends to 0. Hence, passing to the limit in the above equation, we get that Ω ∇ϕ(x) • u(x)dx = 0 for any ϕ ∈ C ∞ c (Ω),which shows that divu(x) = 0 for a.e.

x ∈ Ω. Let ϕ ∈ C ∞ c (Ω) d .
Let us now show (1) with v = ϕ. We take (again omitting some indices (ℓ), thus denoting D = D (ℓ) ) v E = P E ϕ ∈ H E (Ω), as defined by [START_REF] Simon | Compact sets in the space lp(0,t;b)[END_REF], as test function in Scheme [START_REF] Scott | Finite element interpolation of nonsmooth functions satisfying boundary conditions[END_REF]. We get that

u D , P E ϕ E - Ω p D (x)div M P E ϕ(x)dx + β b E (u D , u D , P E ϕ) = Ω f (x) • P E ϕ(x)dx.
We then denote

u D,δt (x, t) = u (n+ 1 2 ) (x), u D,δt (x, t) = u (n+ 1 2 ) (x), and p D,δt (x, t) = p (n+ 1 2 ) (x),
for a.e. (x, t) ∈ Ω × (t (n) , t (n+1) ), ∀n ∈ N, (40) and we define the discrete time derivative

δ D,δt u(x, t) = δ (n+ 1 2 )
D,δt u(x) for a.e. (x, t) ∈ Ω × (t (n) , t (n+1) ), ∀n ∈ N.

Remark 5.1 (Time discretization) We consider a constant time step only for the sake of clarity of notations. The mathematical analysis is still valid with a variable time step. Note that the above scheme corresponds to a Crank-Nicolson-like scheme for α = 1 2 , and to an implicit scheme for α = 1.

Mathematical analysis

Lemma 5.1 (Estimates on the velocity and the pressure) Let δt = T /N T with N T ∈ N * , let D be a discretization as defined in Section 4.1. Let the initial condition u (0) be defined by (36), and, for a given 39) holds for n = 1, . . . , N T . Then there exists C 21 , only depending on f , u ini , T and Ω, such that the following discrete L 2 (H 1 ) and L ∞ (L 2 ) estimates hold:

α ∈ [ 1 2 , 1], let (u (n+1) , u (n+ 1 2 ) , p (n+ 1 2 ) ) ∈ H E (Ω) × H E (Ω) × H M (Ω) such that (38)-(
N T -1 n=0 δt u (n+ 1 2 ) 2 E ≤ C 21 , ( 41
)
and u (n) L 2 (Ω) d ≤ C 21 , n = 0, . . . , N T . ( 42
)
Moreover we have the following L 1 (L 2 ) estimate on the pressure:

|p D,δt | L 1 (0,T ;L 2 (Ω)) ≤ C 22 , n = 0, . . . , N, (43)
where C 22 only depends on D, β, δt, f , u ini and Ω. Therefore there exists at least one solution to (38)-(39) if β > 0 and exactly one solution if β = 0.

Proof. Let us first remark that (42), for n = 0, is due to the Cauchy-Schwarz inequality applied to (36).

We let u = u (n+ 1 2 ) in (39). The nonlinear term again vanishes, which leads, using the Young, Poincaré and Korn inequalities, to:

1 2 u (n+1) 2 L 2 (Ω) d -1 2 u (n) 2 L 2 (Ω) d + (α -1 2 ) u (n+1) -u (n) 2 L 2 (Ω) d + δt C 13 u (n+ 1 2 ) 2 E ≤ diam(Ω) 2 2 f 2 (L 2 (Ω×(t (n) ,t (n+1) )) d + δt 2 u (n+ 1 2 ) 2 E .
Summing for n = 0, . . . , N -1 lead to both (41) and (42). Following the same ideas as in the proof of Lemma 4.5, we get the existence of C 23 , only depending on θ, β and Ω such that

δt p (n+ 1 2 ) L 2 (Ω) ≤ C 23 δt u (n+ 1
2 )

E + δt u (n+ 1 2 ) 2 E + u (n+1) -u (n) L 2 (Ω) d + √ δt f (L 2 (Ω×(t (n) t (n+1) ) d .
Summing the above inequality on n = 0, . . . , N T -1, using the Cauchy Schwarz inequality for the terms

δt N T -1 n=0 u (n+ 1
2 )

E and √ δt

N T -1 n=0 f (L 2 (Ω×(t (n) ,t (n+1)
)) d , inequality (41) for the term δt

N T -1 n=0 u (n+ 1 2 ) 2 E
and inequality (42) for the term

N T -1 n=0 u (n+1) -u (n) L 2 (Ω) d lead to (43).
The existence of at least one solution to the scheme is then again deduced from the use of the topological degree results, as in [START_REF] Eymard | Convergence analysis of a colocated finite volume scheme for the incompressible Navier-Stokes equations on general 2 or 3d meshes[END_REF], as well as the uniqueness of the solution if β = 0.

Since our aim is to apply Theorem 7.1, we define a second norm on H E (Ω) in the next definition.

∀ w ∈ H E (Ω), w ⋆,E = sup Ω w(x) • v(x)dx, v ∈ H E (Ω), v E = 1 and div M v = 0 . ( 44
)
Let us denote by Y E the space H E (Ω) equipped with the norm • ⋆,E . We define a continuous embedding of Y E in E(Ω) ′ (recall that E(Ω) = {v ∈ (H 1 0 (Ω)) 2 ; divv = 0}) by the relation

w, v E(Ω) ′ ,E(Ω) = Ω w(x) • P E v(x)dx, ∀w ∈ H E (Ω), ∀v ∈ E(Ω). ( 45
)
where P E v is defined by [START_REF] Simon | Compact sets in the space lp(0,t;b)[END_REF] in Lemma. ??. Note that, thanks to [START_REF] Wesseling | Principles of Computational Fluid Dynamics[END_REF] we get that

w E(Ω) ′ ≤ C 1 w ⋆,E , ∀w ∈ H E (Ω), ( 46
)
where C 1 only depends on θ and Ω.

In view of applying Theorem 7.1, let us study the dual norm of the discrete time derivative. ) be defined by (36), and, for a 39) holds for n = 1, . . . , N T . Then there exists C 24 , only depending on f , u ini , T , Ω, β and θ, such that

given α ∈ [ 1 2 , 1], let (u (n+1) , u (n+ 1 2 ) , p (n+ 1 2 ) ) ∈ H E (Ω) × H E (Ω) × H M (Ω) such that (38)-(
δ D,δt u L 4/3 (0,T ;Y E ) ≤ C 24 . (47)
(Note that, thanks to (46), a similar inequality holds on δ D,δt u L 4/3 (0,T ;E(Ω) ′ ) .)

Proof. Let us take v ∈ H E (Ω), with div M v = 0, as test function in Scheme (39). Using (45) leads to

Ω δ (n+ 1 2 ) D,δt u(x) • v(x)dx + u (n+ 1 2 ) , v E + β b D (u (n+ 1 2 ) , u (n+ 1 2 ) , v) = 1 δt t (n+1) t (n) Ω f (x, t) • v(x)dxdt.
Since u (n+ 1 2 ) satisfies (38) we get thanks to the estimate (28) of Lemma 4.4 and to the estimate (42) that:

|b D (u (n+ 1 2 ) , u (n+ 1 2 ) , v)| ≤ C 25 u (n+ 1 2 ) 3/2 E v E ,
where C 25 , only depends on f , u ini , T , Ω and θ. We then get that there exists C 26 , only depending on f , u ini , T , β, Ω and θ, such that

δ D,δt u(t) * ,E ≤ C 26   u (n+ 1
2 )

E + u (n+ 1 2 ) 3/2 E + 1 δt t (n+1) t (n) f (•, t)dt L 2 (Ω) d   .
Remarking that u (n+ 1 2 )

4 3 E ≤ 1 + u (n+ 1 2 ) 2
E and that

1 δt t (n+1) t (n) f (•, t)dt 4 3 L 2 (Ω) d ≤ 1 + 1 δt t (n+1) t (n) f (•, t) L 2 (Ω) d dt 2 ≤ 1 + 1 δt t (n+1) t (n) f (•, t) 2 L 2 (Ω) d dt,
we get that there exists C 27 , only depending on f , u ini , T , β, Ω and θ, such that δ D,δt u(t)

4 3 * ,E ≤ C 27 1 + u (n+ 1 2 ) 2 E + 1 δt t (n+1) t (n) f (•, t) 2 L 2 (Ω) d dt .
Integrating for t ∈ (0, T ) and using the discrete L 2 (H 1 ) estimate on the velocity (41), we get that there exists C 24 , only depending on f , u ini , T , Ω, β and θ, such that (47) holds, which concludes the proof.

Theorem 5.1 (Convergence of the scheme) Let F be a family of time space discretizations (D, δt), where D is a discretization in the sense given in Section 4.1 and there exists N T ∈ N * such that δt = T /N T . We assume that there exists θ > 0 with θ ≤ θ D for all D ∈ F (see Section 4.1). For any D = (M, E, δt) ∈ F, let (u E,δt , p mesh,δt ) denote a solution to Scheme (36)-( 9)-(39) for a given α ∈ [ 1 2 , 1]. Then there exists a weak solution u of (4) such that, up to a subsequence, u E,δt converges in L 2 (Ω × (0, T )) d to u as h D → 0 and δt → 0, which shows that

∂ t u L 4/3 (0,T ;E(Ω) ′ ) ≤ C 24 . (48)
Moreover, if β = 0, the whole family converges to the unique weak solution of (4) as h D → 0 and δt → 0.

Proof. Let D ℓ = (M ℓ , E ℓ , δt ℓ ) ℓ∈N be a sequence of elements of F, such that h D ℓ and δt ℓ tend to 0 as ℓ → ∞. From thereon, we denote u M ℓ ,δt ℓ by u ℓ for short.

Step 1 Proof that hypotheses (h1-h4) of Theorem 7.1 hold, and consequences.

In our setting, the space B of Theorem 7.1 is L 2 (Ω) d . We take

B ℓ = {w ∈ H E ℓ ; div D ℓ w = 0}. The norm • X ℓ is the norm • E ℓ , and the norm • Y ℓ is defined in Definition 5.1.
Let (w ℓ ) ℓ∈N be a sequence of functions of B ℓ such that w ℓ E ℓ ≤ C for some C ∈ R + . Then by definition of the norm w ℓ E ℓ and thanks to Rellich's theorem, the sequence ( w ℓ ) E ℓ converges in L 2 (Ω) d to some w ∈ L 2 (Ω) d ; therefore, by the inequality (52) of 7.1 given in the Appendix, the sequence (w ℓ ) E ℓ also converges to w in L 2 (Ω) d . Thus, assumption (h1) of Theorem 7.1 is satisfied.

Let us then show that assumption (h2) is also satisfied. Let (w ℓ ) ℓ∈N be a sequence of functions of L 2 (Ω) d such that w ℓ ∈ B ℓ and w ℓ E ℓ ≤ C for some C ∈ R + , and such that there exists w ∈ B with w ℓ → w in B and w ℓ ⋆,E ℓ → 0 as ℓ → ∞. By definition of the norm • ⋆,E ℓ , we have

Ω w ℓ (x) • w ℓ (x)dx ≤ w ℓ ⋆,E ℓ w ℓ E ℓ → 0 as ℓ → ∞,
which shows that w = 0.

From estimates (41) and (47), we get that hypotheses (h3) and (h4) of Theorem 7.1 are satisfied. Therefore, we deduce that there exists u ∈ L 1 (0, T ; L 2 (Ω) d ) and a subsequence of (D ℓ , δt ℓ ) ℓ∈N , again denoted by (D ℓ , δt ℓ ) ℓ∈N , such that u ℓ converges in L 1 (0, T ; L 2 (Ω) d ) to u as ℓ → ∞.

Step 2 Proof that u is a weak solution of (4).

As in [START_REF] Eymard | Convergence analysis of a colocated finite volume scheme for the incompressible Navier-Stokes equations on general 2 or 3d meshes[END_REF], we easily get that u ∈ L 2 (0, T ; H 1 0 (Ω) d ) and we prove the convergence in L 2 (Ω × (0, T )) d to u of u ℓ . Lemma 7.1 implies the same convergence property for u ℓ . We get that divu(x, t) = 0 in the same manner as in the steady case. The proof that u satisfies (4) follows the same steps as the Navier-Stokes steady case, using a divergence free test function. The convergence of the additional time term to the corresponding continuous limit is then classical.

Step 3 Proof that (48) holds.

Thanks to (47), extracting a subsequence such that δ D ℓ ,δt ℓ u ℓ weakly converges in the Sobolev space L 4/3 (0, T ; E(Ω) ′ ), we may pass to the limit in (45). We thus get

T 0 ϕ(t) lim ℓ→∞ δ D ℓ ,δt ℓ u ℓ (t), v E(Ω) ′ ,E(Ω) dt = - T 0 ϕ ′ (t) Ω u(x, t)v(x)dxdt, ∀v ∈ E(Ω), ∀ϕ ∈ C 1 c ((0, T )).
The preceding relation allows to conclude that

∂ t u = lim ℓ→∞ δ D ℓ ,δt ℓ u ℓ (t),
and therefore that (48) holds.

6 Numerical examples

An analytical steady problem

We consider a problem where the continuous solution of the Navier-Stokes equations (1) in the case (2) with β = 1 is given by: ū1 (x 1 , x 2 ) = 2π sin 2 (πx 1 ) cos(πx 2 ) sin(πx 2 ) ū2 (x 1 , x 2 ) = -2π cos(πx 1 ) sin(πx 1 ) sin 2 (πx 2 ) p(x 1 , x 2 ) = sin 2 (πx 1 ) sin 2 (πx 2 )

in a circle with centre (0.5, 0.5) and radius 0.45. We consider four meshes for the mass conservation M j , j = 0, . . . , 3, defined in the following way:

1. a structured square 10 × 10 is given on the square [0, 1] × [0, 1],

2. for i = 0, . . . , 3, let us split in 4 control volumes each grid block whose centre (x 1 , x 2 ) satisfies

(x 1 -0.5) 2 + (x 2 -0.5) 2 ≥ 0.45 -0.25/2 i ,
3. get rid of all the control volumes K with centre (x 1 , x 2 ) such that

(x 1 -0.5) 2 + (x 2 -0.5) 2 > 0.45.
Let us denote card(M j ) the number of control volumes of the mesh M j . We get that card(M 0 ) = 1604, card(M 1 ) = 6416, card(M 2 ) = 25592 and card(M 3 ) = 102324. The L 2 errors of unknowns u 1 , u 2 , p, respectively denoted by e 2 (u 1 ), e 2 (u 2 ), e 2 (p), are respectively computed in the Voronoï grids associated to the velocity components and in M j . Left part of Figure [START_REF] Eymard | Finite volume methods[END_REF] shows the errors log 10 (e 2 (u 1 )) and log 10 (e 2 (p)) with respect to log 10 (1/ card(M j )) for j = 0, . . . , 3. On right part of Figure 7 are plotted the stream lines for the finest mesh. The velocity components and the pressure are shown in Figure [START_REF] Eymard | Convergence analysis of a colocated finite volume scheme for the incompressible Navier-Stokes equations on general 2 or 3d meshes[END_REF] for two meshes. Although the velocity fields are accurately computed on the coarsest mesh, the pressure fields show oscillations where neighbouring control volumes have contrasted sizes. However, these oscillations are decreasing while refining the mesh.

An inclined driven cavity

We consider a 30 o inclined driven cavity, which corresponds to non homogeneous Dirichlet boundary conditions for the velocity on the horizontal upper boundary of a parallelogram (see Figure 9) in the case [START_REF] Bramble | A proof of the inf-sup condition for the Stokes equations on Lipschitz domains[END_REF]. We consider the case where the Reynolds number is equal to 1000, and we discretize the domain using refinement strategies. We thus show the flexibility of this extended MAC scheme in this case. We obtain the result shown in Figure 10. The results are compared to the literature [START_REF] Demirdzic | Fluid flow and heat transfer test problems for non-orthogonal grids: Bench-mark solutions[END_REF] in Table 1. The results show the expected precision.

) min u (1) (ξ 2 ) -1.860 • 10 -1 -1.987 • 10 -1 -1.994 • 10 -1 -1.984 • 10 -1 -1.9772 • 10 -1 ξ 2 7.500 • 10 -1 7.826 • 10 -1 7.875 • 10 -1 7.8125 • 10 -1 7.8185 • 10 -1 min u (2) (ξ 1 ) -2.143 • 10 -2 -2.251 • 10 -2 -2.065 • 10 -2 -2.010 • 10 -2 -1.9979 • 10 -2 ξ 1 3.423 • 10 -1 3.238 • 10 -1 3.146 • 10 -1 3.192 • 10 -1 3.1751 • 10 -1 max u (2) (ξ 1 ) 1.361 • 10 -2 1.361 • 10 -2 1.254 • 10 -2 1.216 • 10 -2 1.2123 • 10 -2 ξ 1 7.853 • 10 -1 8.038 • 10 -1 8.269 • 10 -1 8.246 • 10 -1 8.2656 • 10 -1
Table 1: Maximum and minimum of the velocity components along the centerlines ξ 1 and ξ 2 .

A time-dependent case

We consider the Green-Taylor case with β = 10, in the same domain Ω as the one considered in Section 6.1, which is a circle, with center (0.5, 0. We plot in Figure 11 the L 2 errors evaluated at time t = 0.1 as a function of the space step (-0.5 × log 10 (#M)). For each computation, the time step is set such that the temporal error is negligible with respect to the spatial one. The sequence of time and space steps are given in Tab. 2: the ratio of two successive time steps is 4 whereas it is only 2 for the space step. We observe that the approximate pressure does not seem to converge in the case where α = 1/2, which does not occur in the case α = 1. If we plot the values 1 2 (p (n-1 2 ) + p (n+ 1 2 ) ) instead of p (n+ 1 2 ) , we observe that this post-processed pressure numerically converges. All the converging curves show an order 2. In order to check the behaviour of the pressure in the case α = 1/2, we show, in Figures 12 and13, the pressures fields, for two meshes, the left and right figures showing two consecutive times steps, and the middle one showing the average value between these ones. This shows that, although the scheme obtained in the case α = 1/2 may lead to oscillations in pressures, it is simple to get back converging pressures.

(n-1 2 ) (left) 1 2 (p (n-1 2 ) + p (n+ 1 2
) ) (middle) and p (n+ 1 2 ) with #M = 1604 and δt = 6.25 10 -3

In order to check the convergence order with respect to the time step, we have chosen the sequence described by Table 3. The errors are plotted in Figure 14 (for the case α = 1/2, we have compared the exact pressure with the average pressure 1 2 (p (n-1 2 ) + p (n+ 1 2 ) ) instead of p (n+ 1 2 ) ). This shows an order 2 for α = 1/2, and 1 for α = 1.

Conclusion

The extension of the MAC scheme presented here seems to show interesting properties for practical computations. The grids are easy to construct, and complex domains may easily be dicretized with the possibility of local refinement. This could lead to the use of this scheme in industrial and large scale problems. Work is in progress to design a discrete nonlinear convection term which would resume to the classical MAC scheme in the case of a uniform rectangular grid, while retaining the same properties in order to obtain the mathematical convergence of the discrete solutions.

We denote by V V the set of all pairs of vertices (s, s ′ ) ∈ V 2 such that Ω ψ s ′ (x)ξ s (x)dx > 0, and we assume that a set T (s, s ′ ) ⊂ T is defined such that it contains all the elements T ∈ T with s ∈ V T , it contains at least one T ∈ T such that s ′ ∈ V T and for any pair (T, T ′ ) ∈ T (s, s ′ ), there exists a sequence of simplices T 1 , . . . , T M such that T i+1 ∈ T Ti for i = 1, . . . , M -1, T = T 1 and T ′ = T M . Let C 28 > 1 be defined by

C 28 = max{ diam(T ) d |T | , T ∈ T } ∪ { diam(T ′ ) diam(T ) , T ∈ T , T ′ ∈ T T } ∪ {#T (s, s ′ ), (s, s ′ ) ∈ V V}. ( 50
)
For (u s ) s∈V ∈ R V , let us denote u = s∈V u s ξ s and u = s∈V u s ψ s , and, for any T ∈ T and x ∈ T , let us denote δ(x) = diam(T ). Then there exists C 29 > 0 only depending on C 28 , such that

1 δ (u -u) L 2 (Ω) d ≤ C 29 ∇ u L 2 (Ω) d , (51)
so that in particular, u -u L 2 (Ω) d ≤ C 29 max T ∈T diam(T ) ∇ u L 2 (Ω) d . (52)
Proof. By definition of u and u, thanks to the fact that s∈V ξ s (x) = s∈V ψ s (x) = 1, and applying the Cauchy-Schwarz inequality, we get:

1 δ (u -u) 2 L 2 (Ω) d = Ω 1 δ(x) 2 ( s∈V u s ξ s (x) - s ′ ∈V u s ′ ψ s ′ (x)) 2 dx = Ω 1 δ(x) 2 ( s∈V s ′ ∈V (u s -u s ′ )ξ s (x)ψ s ′ (x)) 2 dx, ≤ Ω 1 δ(x) 2 (s,s ′ )∈V V (u s -u s ′ ) 2 ξ s (x)ψ s ′ (x)dx.
We remark that the closure of T (s, s ′ ) contains s, s ′ and an interior connected path from s to s ′ , whose intersection with any T ∈ T (s, s ′ ) is either a nonzero vector w(T, s, s ′ ) ∈ R d or empty (then we set w(T, s, s ′ ) = 0, and therefore satisfies T ∈T (s,s ′ ) w(T, s, s ′ ) = s ′s.

We may then write, since u is affine on each T ∈ T ,

u s -u s ′ = T ∈T (s,s ′ ) ∇ T u ẇ(T, s, s ′ ),
denoting by ∇ T u = s∈V T u s ∇ξ s (x), for all x ∈ T , the constant gradient of u in the simplex T . We get

(u s -u s ′ ) 2 ≤ T ∈T (s,s ′ ) |w(T, s, s ′ )| 2 T ∈T (s,s ′ ) |∇ T u| 2 , which provides, denoting by (L(s, s ′ )) 2 = T ∈T (s,s ′ ) diam(T ) 2 , (u s -u s ′ ) 2 ≤ (L(s, s ′ )) 2 T ∈T (s,s ′ ) |∇ T u| 2 ,
and therefore

1 δ (u -u) 2 L 2 (Ω) d ≤ Ω (s,s ′ )∈V V (L(s, s ′ )) 2 δ(x) 2 T ∈T (s,s ′ ) |∇ T u| 2 ξ s (x)ψ s ′ (x)dx = T ∈T |∇ T u| 2 Ω (s,s ′ )∈V V T (L(s, s ′ )) 2 δ(x) 2 ξ s (x)ψ s ′ (x)dx,
denoting by V V T the subset of all (s, s ′ ) ∈ V V such that T ∈ T (s, s ′ ). Let us show that there exists C 29 > 0 only depending on C 28 , such that, for any T ∈ T , Ω (s,s ′ )∈V V T (L(s, s ′ )) 2 δ(x) 2 ξ s (x)ψ s ′ (x)dx ≤ C 2 29 |T |.

We choose a point x T ∈ T . Let (s, s ′ ) ∈ V V T , let x ∈ Ω be such that ξ s (x)ψ s ′ (x) > 0. Since ξ s (x) > 0, there exists T 1 ∈ T such that x ∈ T 1 and s ∈ V T1 . Let us observe that, for any T ′ ∈ T (s, s ′ ), then diam(T ′ ) ≤ (C 28 ) M diam(T 1 ), which implies that (L(s, s ′ )) Let us turn to the proof of the right inequality of (55). Let T ∈ T and (a 1 , . . . , a d+1 ) ∈ R d+1 be given, and let, for any x ∈ T , ξ 1 (x), . . . , ξ d+1 (x) be the d + 1 barycentric coordinates of x with respect to the vertices (recall that the P 1 basis functions are defined by such coordinates in each simplex). We then denote, for a given ε ∈ (0, 1/2), which will be chosen later, by

T i (ε) = {x ∈ T, ξ i (x) ≥ 1 -ε}.
Since, on T i , we have, for j = i, ξ j (x) ≤ ε < 1 -ε, we get that all the T i , i = 1, . . . , d + 1, are disjoint.

We then have We then choose ε such that ε = min( 1 3 , 1 (3d(d + 1) p-1 ) 1/p ).

We then have

(1 -ε) p (d + 1) p-1 ≥

Discrete Aubin-Simon result

As we mentioned earlier, the compactness result that we use in our proof of convergence of the scheme is an adaptation of a previous result [START_REF] Gallouët | Compactness of discrete approximate solutions to parabolic pdesapplication to a turbulence model[END_REF]. The differences between the theorem given below and [10, Theorem 3.4] are the following;

1. Theorem 7.1 is a compactness result in L 1 (0, T ; B) where B is some Banach space, while [10, Theorem 3.4] is a compactness result in L p (0, T ; B) for p ∈ [1, +∞). We chose to restrict to L 1 for two reasons:

• The proof is much simpler in the L 1 case, especially in the case of variable time steps.

• In our framework,we can easily get the result in L 2 by using compactness in L 1 and the discrete estimates (41) and (42), using the "L p -L q compactness" property and Sobolev inequalities, see [9, Lemma 3.1].

2.

The assumption (h2) that we require here is weaker than the assumption (h2) of [10, Theorem 3.4], which does not require that ( w n Xn ) ℓ∈N be bounded. A quick look at the proofs of [10, Lemma 3.1 and Theorem 3.4] shows that in fact they only require our hypothesis (h2) (which is easier to verify in our framework).

3. We give here a version with variable time steps.

  denotes the length of the line segment which is the intersection of ∂V

Figure 3 :

 3 Figure 3: The pressure (left) and velocity grids (middle: horizontal velocity, right: vertical velocity).

Figure 4 :

 4 Figure 4: The Delaunay triangulation and the Voronoï cells (left: horizontal velocity, right: vertical velocity).

Figure 5 :

 5 Figure 5: The pressure (left) and velocity grids (middle: horizontal velocity, right: vertical velocity).

Figure 6 :

 6 Figure 6: The Delaunay triangulation and the Voronoï cells (left: horizontal velocity, right: vertical velocity).

4

  The extended MAC scheme for the steady Navier-Stokes equations 4.1 Discretization of the nonlinear convection term In order to write this generalized scheme for the Navier-Stokes equations, we only need to give a discretization of the nonlinear term Ω (u(x)•∇)u(x)•v(x)dx. To this purpose, we introduce a discrete trilinear form b E which aims at discretizing the trilinear form b defined over (H 1 0 (Ω)) 3 by b(u, v, w) = Ω (u • ∇v)w dx.

Definition 4 . 2 (

 42 Discrete gradient and convection term ) For v ∈ H M (Ω), we define its discrete gradient ∇ E v ∈ H E (Ω) by:

Lemma 4 . 2

 42 Under the assumptions of Definition 4.3, there exists C 1 , only depending on θ and Ω, such that

Lemma 4 . 6 (

 46 Weak convergence of the gradient) Let F be a family of discretizations in the sense given in Section 4.1. For any D ∈ F, let v D ∈ H M (Ω), such that: the family (

Definition 5 . 1 (

 51 Dual norm) Let us define the following dual norm on H E (Ω):

Lemma 5 . 2 (

 52 Estimate on the dual norm of the discrete time derivative) Let δt = T /N T with N T ∈ N * , let D be a discretization as defined in Section 4.1 and let θ < θ D . Let (u(0)

Figure 7 :

 7 Figure 7: Left: The L 2 error with respect to the number of control volumes. Right: Stream lines.

Figure 8 :

 8 Figure 8: Horizontal component of the velocity (left), vertical component of the velocity (middle), pressure (right) for j = 0 (top) and j = 2 (bottom).

Figure 9 :

 9 Figure 9: An example of mesh, and the two media axes ξ 1 and ξ 2 .

Figure 10 :

 10 Figure 10: Velocity components, D m2 u(1) (left) u(2) (right)Generalized MAC scheme [5] #M 924 3698 14796 59190 102400 (= 320 2 ) min u (1) (ξ 2 ) -1.860 • 10 -1 -1.987 • 10 -1 -1.994 • 10 -1 -1.984 • 10 -1 -1.9772 • 10 -1 ξ 2 7.500 • 10 -1 7.826 • 10 -1 7.875 • 10 -1 7.8125 • 10 -1 7.8185 • 10 -1 min u (2) (ξ 1 ) -2.143 • 10 -2 -2.251 • 10 -2 -2.065 • 10 -2 -2.010 • 10 -2 -1.9979 • 10 -2 ξ 1 3.423 • 10 -1 3.238 • 10 -1 3.146 • 10 -1 3.192 • 10 -1 3.1751 • 10 -1 max u (2) (ξ 1 )1.361 • 10 -2 1.361 • 10 -2 1.254 • 10 -2 1.216 • 10 -2 1.2123 • 10 -2 ξ 1 7.853 • 10 -1 8.038 • 10 -1 8.269 • 10 -1 8.246 • 10 -1 8.2656 • 10 -1

δt 6 .Table 2 : 6 -Figure 11 :

 62611 Figure 11: L 2 errors (+: velocity ×: pressure) as a function of the size of the mesh.

Figure 12 :

 12 Figure 12: An example of pressure solution at two consecutive time steps. p(n-1 2 ) (left) 1 2 (p (n-1 2 ) + p (n+ 12) ) (middle) and p (n+1 2 ) with #M = 1604 and δt = 6.25 10 -3

Figure 13 :Table 3 : 6 -

 1336 Figure 13: An example of pressure solution at two consecutive time steps. p(n-1 2 ) (left) 1 2 (p (n-1 2 ) + p (n+ 12) ) (middle) and p (n+ 1 2 ) with #M = 25592 and δt = 3.90625 10 -4 δt 0.05 0.025 0.0125 0.00635 0.003125 #M 1604 6416 25592 102324 409156

Figure 14 :

 14 Figure 14: L 2 errors (+: velocity ×: pressure) as a function of the time step.

2 ≤s ∇ξ s 2 L 2 (

 222 C 28 (C 28 ) 2M diam(T 1 ) 2 = (C 28 ) 2M +1 δ(x) 2 . (54)Since T 1 ∈ T (s, s ′ ), there exists a family of neighbouring simplices T 1 , . . . , T M , with M ≤ C 28 (using (50)), such that T = T M . Therefore, diam(T M -1 ) ≤ C 28 diam(T ), and, by induction, diam(T 1 ) ≤ (C 28 ) M -1 diam(T ). This leads to the inequality |x-x T | ≤ C 30 diam(T ), denoting by C 30 = (C 28 ) M /(C 28 -1). Therefore, we get, using (s,s′ )∈V V T ξ s (x)ψ s ′ (x) ≤ 1, that Ω (s,s ′ )∈V V T ξ s (x)ψ s ′ (x)dx ≤ |B(x T , C 30 diam(T ))|.Denoting by C 31 the real, only depending on the space dimension (2 or 3), such that |B(x T , diam(T ))| = C 31 diam(T ) d , we may write|B(x T , C 30 diam(T ))| = C 31 diam(T ) d C d 30 ≤ C 31 C 28 C d 30 |T |.Using (54), this concludes the proof of (53). Thanks to T ∈T |T ||∇ T u| 2 = s∈V u Ω) d , we then conclude (51).

Lemma 7 . 2 (

 72 Comparison between L p norms) Let Ω ⊂ R d , with d ∈ N * be an open connected set, such that there exists a H 1 conforming simplicial mesh T over Ω. We denote by T the elements of M, by V the set of all vertices. For s ∈ V, we denote by ξ s the P 1 finite element basis function associated to the node s. Then, for any p ∈ [1, +∞), there exists C(d, p) > 0, such thats∈V u s ξ s L p (Ω) d ≤ s∈V |u s | p Ω ξ s (x)dx 1/p ≤ C(d, p) s∈V u s ξ s L p (Ω) d , ∀(u s ) s∈V ∈ R V . (55)Proof. The left inequality of (55) is an immediate consequence of the convexity of the function x → |x| p , which provides s∈V u s ξ s (x) p ≤ s∈V |u s | p ξ s (x).

a

  We may write, for x ∈ T d+1 (ε),|a d+1 |(1 -ε) ≤ |a d+1 ξ d+1 (x)| ≤ d+1 i=1 a i ξ i (x) + d i=1 |a i ξ i (x)| ≤ d+1 i=1 a i ξ i (x) + ε d i=1 |a i |,and therefore, thanks to the Young inequality|a d+1 | p (1 -ε) p ≤ (d + 1)Let us remark that the measure of T i (ε) is equal to ε d |T |. We then getT d+1 i=1 a i ξ i (x) p dx ≥ ε d |T | d+1 i=1 |a i | p (1 -ε) p (d + 1) p-1i ξ i (x) p dx ≥ ε d |T | (1 -ε) p (d + 1) p-1 -dε p d+1 i=1 |a i | p .

2 p 3 pa

 23 (d + 1) p-1 ≥ 2 3(d + 1) p-1 ,and therefore(1 -ε) p (d + 1) p-1 -dε p ≥ 1 3(d + 1) p-1 .Denoting C(d, p) > 0 the quantity defined byC(d, p) p i ξ i (x) p dx ≥ C(d, p) p |T | d + 1 d+1 i=1 |a i | p ,which implies (55).

  [START_REF] Demirdzic | Fluid flow and heat transfer test problems for non-orthogonal grids: Bench-mark solutions[END_REF]) and radius 0.45, on the time domain [0, 0.1]. Nonhomogeneous Dirichlet boundary conditions are imposed. The solution is given, in the case (2), by u (1) (x 1 , x 2 , t) = -cos(πx 1 ) sin(πx 2 ) exp(-2π 2 t), u(2) (x 1 , x 2 , t) = sin(πx 1 ) cos(πx 2 ) exp(-2π 2 t),

	p(x 1 , x 2 , t) = -β	cos(2πx 1 ) + cos(2πx 2 ) 4	exp(-4π 2 t).

Using Lemma 4.3 and the fact that p D (ℓ) weakly converges in L 2 (Ω) to p ∈ L 2 (Ω), we obtain that lim ℓ→∞ Ω p D (ℓ) (x)div D (ℓ) P E (ℓ) ϕ(x)dx = Ω p(x)divϕ(x)dx.

Thanks to the weak and strong convergence properties of the different sequences, we get that lim ℓ→∞ u D (ℓ) , P E (ℓ) ϕ E (ℓ) = lim ℓ→∞ Ω S( u D (ℓ) , P E (ℓ) ϕ)(x)dx = Ω S(u, ϕ)(x)dx.

We also have, thanks to the definition [START_REF] Simon | Compact sets in the space lp(0,t;b)[END_REF] of P E ϕ,

Let us now turn to the study of the limit of b E (ℓ) (u D (ℓ) , u D (ℓ) , P E (ℓ) ϕ). By the definition [START_REF] Patankar | Numerical heat transfer and fluid flow[END_REF] of b E , again dropping some indices (ℓ), we have:

Thanks to the regularity of the mesh, the family ∇ E (Π D u E ) is bounded in (L 2 (Ω)) d . Moreover, using Lemma 7.1 and the estimate (29), we get that there exists C 20 , only depending on θ, such that

which completes the proof that (1) holds for all v ∈ H 1 0 (Ω) d by density.

5 The extended MAC scheme for the time-dependent Navier-Stokes equations

Definition of the scheme

Let D be the collection of all the space discretization data as given in Section 4.1. The discrete approximation of the time-dependent Navier-Stokes equations ( 4) is then given by the following relations. The initial condition is approximated by u (0) ∈ H E (Ω) defined by

and, for a given time step δt > 0, let us denote by t (n) = nδt for n ≥ 0. The scheme is defined by

and, for a given α ∈

Appendix Interpolation results

The first lemma that we give is a technical result which allows to bound, under adequate geometrical conditions, the difference between various interpolates by the gradient of a P 1 reconstruction.

Lemma 7.1 (Comparison between interpolates)

Let Ω ⊂ R d , with d ∈ N * be an open polygonal connected open set, such that there exists a H 1 conforming simplicial mesh T over Ω. We denote by T the elements of M, by V the set of all vertices, and by V T the set of all vertices of T and by T T ⊂ T the set of the simplices sharing a face with T . For s ∈ V, we denote by ξ s the P 1 finite element basis function associated to the node x s . We assume that are given some non-negative functions ψ s , for all s ∈ V, such that s∈V ψ s (x) = 1, for a.e. x ∈ Ω.

4. The definition (56) of u ℓ (•, t) corresponds to an α-scheme whereas that of [START_REF] Gallouët | Compactness of discrete approximate solutions to parabolic pdesapplication to a turbulence model[END_REF]Theorem 3.4] corresponds to an implicit scheme, i.e. α is equal to 1.

Theorem 7.1 (Discrete Aubin-Simon lemma) Let T > 0 and let B be a Banach space. Let (B ℓ ) ℓ∈N be a sequence of finite dimensional subspaces of B. For any ℓ ∈ N, let N ℓ ∈ N * , t

ℓ , n = 0, . . . , N ℓ } ⊂ B ℓ and let u ℓ ∈ L 1 (0, T ; B ℓ ) be defined, for a given real family (α

ℓ ), and n ∈ {1, . . . N ℓ }.

(56) Let δ ℓ u ℓ be the "discrete time derivative", defined by:

Let • X ℓ and • Y ℓ be two norms on B ℓ . We denote by X ℓ the space B ℓ endowed with the norm • X ℓ and by Y ℓ the space B ℓ endowed with the norm • Y ℓ . We assume that (h1) For any sequence (w ℓ ) ℓ∈N such that w ℓ ∈ B ℓ and ( w ℓ X ℓ ) ℓ∈N is bounded, then, up to a subsequence, there exists w ∈ B such that w ℓ → w in B as ℓ → +∞.

(h2) For any sequence (w ℓ ) ℓ∈N such that w ℓ ∈ B ℓ , ( w ℓ X ℓ ) ℓ∈N is bounded, there exists w ∈ B such that w ℓ → w in B and w ℓ Y ℓ → 0 as ℓ → +∞, then w = 0.

(h3) The family (α

Then there exists u ∈ L 1 (0, T ; B) such that, up to a subsequence, u ℓ → u in L 1 (0, T ; B) as ℓ → +∞.

Proof. The proof is mainly inspired by that of [START_REF] Gallouët | Compactness of discrete approximate solutions to parabolic pdesapplication to a turbulence model[END_REF]Theorem 3.4]. The first step is to apply [10, Lemma 3.2], which states that, under Hypothesis (h1), there exists C X > 0 such that, for all ℓ ∈ N, for all u ∈ B ℓ , u B ≤ u X ℓ . We then remark that, thanks to (h1) and (h2), for all ε > 0, there exists

following the proof of [10, Lemma 3.1]. We then remark that, using (h4), there exists C t > 0 such that ∀ℓ ∈ N,

Therefore we get from (h3) that the sequence ( u ℓ BV (0,T ;Y ℓ ) ) ℓ∈N is bounded; indeed we can write

denoting by C α a bound of the family (α

ℓ ) n=1,...,N ℓ ,ℓ∈N . We then prolong u ℓ by symmetry on (-T, 2T ), setting u ℓ (•, -t) = u ℓ (•, t) and u ℓ (•, T + t) = u ℓ (•, T -t) for a.e. t ∈ (0, T ). We then get that u ℓ ∈ BV (-T, 2T ; Y ℓ ), with u ℓ BV (-T,2T ;Y ℓ ) ≤ 3(1 + 2C α )C t . We also get, using (h3), that the sequence ( u ℓ L 1 (-T,2T ;X ℓ ) ) ℓ∈N is bounded as well, which leads that there exists C 0 independent on ℓ such that

We have, thanks to (57), for any τ ∈ (0, T ) and a.e. t ∈ (-T, 2T -τ ),

This proves that

2T -τ -T u ℓ (•, t + τ ) -u ℓ (•, t) B dt tends to 0 with τ , uniformly with respect to ℓ ∈ N. Thanks to the multiplication of u ℓ by a function ψ ∈ C ∞ c (-T, 2T ), equal to 1 on (0, T ), we may apply the compactness theorem [START_REF] Gallouët | Compactness of discrete approximate solutions to parabolic pdesapplication to a turbulence model[END_REF]Theorem 2.1] to obtain that the family (u ℓ ) ℓ∈N is relatively compact in L 1 (0, T ; B).

Remark 7.1 (The original Aubin-Simon theorem) Note that in fact, our weaker assumption (h2) has a continuous equivalent, and indeed, we may weaken one of the hypotheses of the classical Aubin-Simon theorem [START_REF] Simon | Compact sets in the space lp(0,t;b)[END_REF]; indeed, the hypothesis "B continuously embedded in Y " , which is equivalent to the following hypothesis: If w n → w in B and w n Y → 0, then w = 0, may be replaced by the weaker assumption "if (w n ) n∈N is bounded in X, converge in B to w and w n Y → 0, then w = 0".


Benoît Sagot
email: benoit.sagot@inria.fr

Géraldine Walther
email: gwalther@linguist.jussieu.fr

A Morphological Lexicon for the Persian Language

We introduce PerLex, a large-coverage and freely-available morphological lexicon for the Persian language. We describe the main features of the Persian morphology, and the way we have represented it within the Alexina formalism, on which PerLex is based. We focus on the methodology we used for constructing lexical entries from various sources, as well as the problems related to typographic normalisation. The resulting lexicon shows a satisfying coverage on a reference corpus and should therefore be a good starting point for developing a syntactic lexicon for the Persian language.

Introduction

Most Natural Language Processing (NLP) tasks such as part-of-speech tagging, shallow or deep parsing and natural language generation, as well as most NLP applications such as data mining, information extraction, or automatic translation require or strongly benefit from the availability of large-scale lexical resources. Among them, morphological lexicons are the most basic yet the most needed resources. They associate a lemma and a morphosyntactic tag with each known wordform (form, in short). However, for at least two reasons, such resources are virtually available only for a restricted set of welldescribed languages. First, many languages are resourcescarce, and existing lexical resources for these languages, if any, do not have a large coverage. Second, existing lexical resources are not always freely available, although experience shows that free availability is the fastest way to high-quality resources. In this paper, we introduce PerLex, a new large-scale and freely available morphological lexicon for the Persian language. We briefly describe the Persian language and Persian morphology, the Alexina framework used for our lexical development work, the origin of the lexical data in PerLex, and the resulting lexical resource.

Related Work

The first NLP project of importance on Persian language is the Shiraz project, targeted towards Persian to English automatic translation [START_REF] Amtrup | Persian-English machine translation: An overview of the Shiraz Project[END_REF]. It resulted, among others, in the construction of a 50,000 terms bilingual lexicon,1 based in part on a unification-based description of the Persian morphology [START_REF] Megerdoomian | Unification-based Persian morphology[END_REF], later redesigned for using the Xerox finite-state machinery [START_REF] Megerdoomian | Finite-state morphological analysis of Persian[END_REF]. Apart from the work related to the Shiraz project, some other NLP tools, such as morphological tools and lemmatisers, have been developed. Yet they have not led to the construction of a large-scale lexicon. Among those works are those of ( 2008), especially their freely available lemmatiser PerStem. 2Other recent work in the development of NLP tools and resources for Persian processing is mostly focused on designing part-of-speech taggers [START_REF] Qasemizadeh | Persian in multext-east framework[END_REF][START_REF] Tasharofi | Evaluation of statistical part of speech tagging of Persian text[END_REF][START_REF] Shamsfard | A hybrid morphology-based pos tagger for Persian[END_REF], parsers [START_REF] Hafezi | A syntactic parser of Persian sentences[END_REF][START_REF] Dehdari | A link grammar parser for Persian[END_REF] or automatic translation systems [START_REF] Feili | An application of lexicalized grammars in English-Persian translation[END_REF][START_REF] Saedi | Automatic translation between English and Persian texts[END_REF].

The Persian Language

The Persian language is a inflectional SOV language with a relatively fixed word order, belonging to the Western Iranian branch of Indo-European languages. It is spoken by around 130 million people, mainly in Iran, Afghanistan and Tajikistan and Uzbekistan but also in Pakistan, Bahrain, Iraq, Kazakhstan and the Iranian diaspora. In Iran, where Persian functions as the official language, it is also often referred to as Dari, Farsi or Parsi.

Persian Script and Transliteration

Persian is written from right to left and uses a modified version of the Arabic script. Some characters have been added, others are not used and some show a slightly modified shape. As in Arabic, the only diacritic representation of short vowels is usually not written, nor is there a difference between capital and lower case letters. Moreover, two adjacent characters may either be joined (that is written with one uninterrupted line, possible only with some letters) or juxtaposed (that is following each other directly yet without being joined) or separated by a white space. Depending on whether a given character is joined to or isolated from its adjacent characters, this same character can adopt up to three different shapes. Therefore, encoding these characters within Unicode can be done in two different ways: either one directly uses the appropriate contextual character which represents the exact shape a given character has to adopt in that one given context (left-or right-joined or not), or one resorts to the use of generic characters whose shape automatically varies according to the context. Using contextual characters has however become obsolete nowadays since they do not allow for the representation letters by one unique character each. Using the generic character therefore sometimes requires the insertion of zero-width non-joiners (ZWNJ) between two characters to indicate that in a particular case they must not be joined whereas otherwise they could. Some Persian affixes for example have to be written without being separated by a white space but must yet not be joined to the preceding morpheme even if the letters they are represented by normally would. Some of the resources we developed during on our work is based on a transliteration of Persian into Latin characters. We have adopted the bijective transliteration system which has been developed within the PerGram project and which has a version solely based on characters that can be found within the ISO-8859-2 (or Latin-2) encoding. This allows for an effortless use of tools that internally require 8-bit encodings, i.e., encodings for which the typographic and electronic notions of character coincide.3

Persian Morphology in Brief

Within Persian morphology, the nominal system is relatively simple. There is no case system, nor gender distinction (except for a few animate Arabic loanwords which take the feminine ending -e). Persian shows but two number features, singular and plural, of which only the plural is marked by either the suffix -hâ (which works for all countable nouns) or, for some animated nouns only, the more formal suffix -ân, or one of the Arabic plural markers -ât, -un, -in etc. attaching solely to Arabic loanwords [START_REF] Lazard | Grammaire du persan contemporain[END_REF]. Persian also possesses a few broken plurals directly inherited with Arabic loanwords. But those plurals are no longer treated within morphology. Further, there exists a specific enclitic particle -(y)e for marking modified nouns, called Ezafe. It can either mark a given noun or a full noun phrase as a modified element [START_REF] Samvelian | A phrasal affix analysis of the persian ezafe[END_REF][START_REF] Lazard | Grammaire du persan contemporain[END_REF]. Moreover there is an enclitic indefinite article -i which doesn't have separate forms for singular and plural; if it attaches to a noun modified by an adjective, it may either directly follow the noun or the adjective. In the first case, the noun does not take the Ezafe particle, whereas in the second case it does [START_REF] Samvelian | A phrasal affix analysis of the persian ezafe[END_REF][START_REF] Lazard | Grammaire du persan contemporain[END_REF]. Other enclitic particles are -i combined with the relative particle -ke, the optional finite marker -(h)e and object marking postposition -râ. Adjectives only vary in degree by taking the suffixes -tar for the comparative and -tarin for the superlative form. But they can also take the Ezafe enclitic when following a further modified noun or taking a direct or indirect object. This last point especially holds for adjectives derived from verbal forms [START_REF] Lazard | Grammaire du persan contemporain[END_REF]. Concerning the verbal class, Persian like most Iranian languages possesses only a very limited amount of verbal lexemes. They form a closed word class of about 200 elements. Most verbal meanings known from the more extensively described Indo-European languages are expressed through complex verbal predicates built from a light verbal head and a predicative element which can be either a noun or an adjective. Verbal morphology is slightly more complex but follows a rather simple pattern. Persian morphological descriptions usually [START_REF] Lazard | Grammaire du persan contemporain[END_REF] state the existence of two distinct verbal stems, one for the present tense forms (SI), one for the past tense forms (SII). SI is used in the formation of all present tenses, the present participle, the gerund and the imperative forms whereas SII forms the past tenses, the past participle, the participle of possibility or obligation and the two infinitives. Compound tenses as well as the passive voice are derived from the past participle. All Persian verbal paradigms consist of the combination of a given stem with a set of pre-and suffixes, such as in the following representation: Modal/Temporal Prefix(es) -Stem -Personal Suffix(es). The paradigm of temporal/modal prefixes consists of mi-and be-, respectively for building the indicative and subjunctive/imperative forms. The possible personal suffixes are -am, -i, -ad/-e/ø, -im, -id/-in and -and/-an. These combinations generate seven different tensed forms for six different persons each, as well as five nominal verbforms to which the above mentioned enclitics can be attached. The negational prefixes n-or m-(more formal, used for the imperative only) can also be attached to the thereby created verbforms [START_REF] Lazard | Grammaire du persan contemporain[END_REF]. Moreover Persian also displays two distinct paradigms of the present indicative forms for the verb budan 'to be', one being constitutive of plain words whereas the other is formed of enclitic particles which may attach to nouns or adjectives. This second paradigm is also used attached to the past participle to form both the perfect and imperfect compound tenses [START_REF] Lazard | Grammaire du persan contemporain[END_REF]. Finally, Persian also has pronominal suffixes which can combine with nouns, pronouns, verbs, prepositions, adjectives and some adverbs [START_REF] Lazard | Grammaire du persan contemporain[END_REF].

The Alexina Framework

We developed the morphological lexicon PerLex within the Alexina framework [START_REF] Sagot | The Lefff , a freely available and largecoverage morphological and syntactic lexicon for french[END_REF]. This framework covers both the morphological and the syntactic level (e.g., valency), which shall be useful in further stages of PerLex development. Alexina allows for representing lexical information in a complete, efficient and readable way, that is meant to be independent of the language and of any grammatical formalism. It is compatible with the LMF standard4 [START_REF] Francopoulo | Lexical Markup Framework (LMF)[END_REF]. Numerous resources are already being developed within this framework, such as the Lefff , a large-coverage morphological and syntactic lexicon for French [START_REF] Sagot | The Lefff , a freely available and largecoverage morphological and syntactic lexicon for french[END_REF], the Leffe for Spanish, SoraLex for Sorani Kurdish, and lexical resources for Galician, Polish, Slovak and soon English. The Alexina model is based on a two-level representation that separates the description of a lexicon from its use:

• The intensional lexicon factorises the lexical information by associating each lemma with a morphological class (defined in a formalised morphological description) and deep syntactic information; it is used for lexical resource development;

• The extensional lexicon, which is generated automatically by compiling the intensional lexicon, associates each inflected form with a detailed structure that represents all its morphological and syntactic information; it is directly used by NLP tools such as parsers.

In this paper, the syntactic level is left aside, since we are yet building the morphological lexicon.

Formalising Persian Morphology

Among the various enclitic particles listed in Section 3.2., not all shall be treated within morphology. In this matter, PerLex makes the following linguistically motivated choices [START_REF] Samvelian | A phrasal affix analysis of the persian ezafe[END_REF]:

• plural markers, the Ezafe -(y)e (when it has a written counterpart), the indefinite marker -i, comparative and superlative markers -tar and -tarin, personal suffixes and enclitic forms of the auxiliary (except when used for building the perfect forms) are considered as inflectional suffixes,

• combined with the relative ke, the enclitic particle -i forms a compound i ke that is agglutinated to the preceding form,

• other enclitics, including the copula and the -râ definite direct object marker, are considered as independent (agglutinated) forms.

Having in mind the linguistic choices mentioned in 3.2., we developed a complete description of Persian morphology in the Alexina morphological language [START_REF] Sagot | Building a morphosyntactic lexicon and a pre-syntactic processing chain for Polish[END_REF], based on the data in [START_REF] Lazard | Grammaire du persan contemporain[END_REF]. In this format, inflection is modelled as the affixation of a prefix and a suffix around a stem, while sandhi phenomena may occur at morpheme boundaries, sometimes conditioned by stem properties. Our description contains in particular 27 verb tables and 5 nouns tables.

The Construction of the PerLex Lexicon

Lexical entries have been obtained through the three following steps that we describe below: (1) constructing a basic set of lexical entries using a certain amount of resources;

(2) cleaning the obtained lexical entries; (3) adding manually missing entries that were present in the BijanKhan corpus but not yet covered by the already built lexical entries.

Gathering Lexical Information

We gathered lexical information from various sources, the importance of which is variable among categories:

• the BijanKhan corpus [START_REF] Bijankhan | The role of the corpus in writing a grammar: An introduction to a software[END_REF][START_REF] Amiri | Investigation on a feasible corpus for Persian POS tagging[END_REF], an automatically POS-annotated corpus,

• the Persian Wikipedia5

• a lexicon of Persian nouns under development by M. Ghassemi at Université Paris-Est (Ghassemi, p.c.),

• the reference grammar of [START_REF] Lazard | Grammaire du persan contemporain[END_REF],

• introspection by linguists who are native speakers of Persian.

Building a Base Lexicon

Lexical entries were obtained as follows. A list of verbal lemmas (infinitive form) was developed manually from freely available Internet resources and checked manually.

We associated each of them with one (sometimes several) inflection class(es) from our morphological description. We used the Persian Wikipedia for collecting proper nouns. Those were found through the titles of Wikipedia articles indicating either a city or a person category. We collected and normalised the titles of these articles as well as those of all the articles redirecting towards them. We were thereby able to build a lexicon for proper nouns consisting in person and city names which we completed with a list of country names found in the corresponding Wikipedia article. These tasks resulted in a set of over 10,000 proper noun lemmas which all received a inflectional noun class that doesn't allow for the formation of plural forms.

A list of nominal lemmas was extracted from Ghassemi's data. Some of them were already associated with their plural form(s). For others, a statistical look-up in the BijanKhan corpus allowed us to assign their corresponding plural form(s). The result is an inflection class associated with each nominal lemma.

Entries for other categories were extracted from the BijanKhan corpus,6 and manually completed on the basis of [START_REF] Lazard | Grammaire du persan contemporain[END_REF]. Apart from adjectives, that all receive the unique adjectival class, prepositions and some adverbs (see 3.2.), all entries for these categories are considered invariable, except for some adverbs that may receive the indefinite marker -i, the Ezafe or personal suffixes.7

Cleaning the Base Lexicon

At this stage of our lexicon development, and despite the filtering mentioned in footnote 6, there still remains a significant number of incorrect entries, notably among those extracted from the BijanKhan corpus. This follows from the fact that this corpus has been annotated automatically, that is with a nonzero error rate. We therefore removed a certain amount of lexical entries, especially all the nominal and adjectival entries that had been extracted from the BijanKhan corpus and looking like typical plural forms (that is that seemed to end in the plural suffix -hâ, followed or not by the Ezafe, the indefinite suffix or the personal suffixes). We also eliminated numerous entries which seemed to contain typographic errors, especially those whose ZWNJ had been omitted or replaced by a white space (such as the incorrect entries for the pronouns ân hâ and ânhâ instead of correct ân hâ). Finally we suppressed all superfluous characters, such as the diacritic signs for marking vocalisation. The resulting base lexicon forms the first version of our morphological lexicon for the Persian language.

Expanding the Lexicon

Once this first version of PerLex had been completed, we have searched the BijanKhan corpus for attested word forms that had not yet been taken into account by our lexicon. Those forms may as well be unknown missing forms as they may be incorrect entries or spelling or typographic errors. We therefore sorted them according to their frequency of apparition and manually completed the lexicon from the resulting list. The missing entries were mostly, on the one hand, proper nouns belonging to categories other than those extracted from the Persian Wikipedia (continent names, names of different regions of Iran, etc.), and, on the other hand, several broken plurals. However we were able to observe that a very large amount of unknown forms were in fact due to typographical errors that had not been spotted during the cleaning step.

The PerLex Lexicon

The resulting lexicon contains 35,914 lemma-level entries that generate 524,700 form-level entries corresponding to 494,488 distinct forms. Some insight into the distribution according the category is given in Table 1.

Conclusion and Future Work

We introduced the first version of a large-coverage lexicon for the Persian language. It is now restricted to the morphological level which is currently undergoing manual validation work. The next step of our lexical development work will be to add syntactic information including subcategorisation frames, starting with verbs. In parallel, PerLex will be extended for describing the important phenomenon of complex verbal predicates in Persian. Both these tasks shall be achieved by semi-automatic techniques already used for the development of other Alexina lexicons, and followed by a manual validation step. PerLex is freely available under an LGPL-LR license on the web page of the Alexina project.8

Table 1 :

 1 Quantitative data about PerLex

	Category	intentional distinct extensional
		entries	lemmas	entries
	verbs	171	139	19,776
	common nouns	9,553	9,106	177,988
	proper nous	10,996	10,938	33,076
	adjectives	11,872	11,835	290,537
	others	3,322	3,120	3,323
	total	35,914	33,454	524,700

This lexicon doesn't seem to be freely available.

http://sourceforge.net/projects/perstem/

In this paper we use a more standard phonetic transcription of the Persian words and affixes that also represents the short vowels and in that sense differs from the described transliteration.

Lexical Markup Framework, the ISO/TC37 standard for NLP lexicons.

The Persian Wikipedia is available under the following URL http://fa.wikipedia.org. We used the extracted wiki version of February 16th 2010.

For lemmas with an ambiguous category in the corpus, we discarded entries corresponding to categories that were assigned with a frequency below 1% among occurrences of this lemma. This reduces the amount of noise that comes from annotation errors in the corpus.

Adverbial entries that also exist as adjectives with the same meaning were discarded.

http://alexina.gforge.inria.fr

Acknowledgements

This work was supported in part by the PerGram French-German project, funded by the Deutsche Forschungsgemeinschaft and the Agence Nationale de la Recherche (Grant Number MU 2822/3-1) and jointly headed by Pollet Samvelian (Université Paris 3) and Stefan Müller (Freie Universität Berlin).