Nicolas Forcadel

Comparison principle for a Generalized Fast Marching Method

Keywords: AMS Classification: 65M06, 65M12, 49L25 Eikonal equation, fast marching scheme, monotone scheme, convergence

 for which we state a general comparison principle. We also prove the convergence of the new algorithm.

Introduction

In this paper, we are interested in the Fast Marching Method (FMM). This method has been introduced by Sethian [START_REF] Sethian | A fast marching level set method for monotonically advancing fronts[END_REF][START_REF]Level set methods and fast marching methods[END_REF] (see also Tsitsiklis [START_REF] Tsitsiklis | Efficient algorithms for globally optimal trajectories[END_REF] for a previous single-pass method) and adapted for general given normal velocity c(x, t) in [START_REF] Carlini | Convergence of a generalized fast marching method for a non-convex eikonal equation[END_REF] (we refer to [START_REF] Carlini | Convergence of a generalized fast marching method for a non-convex eikonal equation[END_REF] for a detailed discussion and for more references on Fast Marching Method). More precisely, in [START_REF] Carlini | Convergence of a generalized fast marching method for a non-convex eikonal equation[END_REF] the authors have proposed a generalization of the classical FMM for the following equation (1.1) θ t = c(x, t)|Dθ| in R N × (0, +∞), θ(•, 0) = 1 Ω0 -1 Ω c 0 on R N , and we have proved a convergence result in the class of discontinuous viscosity solutions for our Generalized Fast Marching Method (GFMM). A major improvement of our GFMM is that it can deal with a velocity changing sign. A drawback of this algorithm is that it was not completely monotone (see Subsection 5.2). In (1.1) and throughout the paper, θ t denotes the time derivative of θ and Dθ its gradient in space.

The goal of this paper is to propose a GFMM slightly different from the one developed in [START_REF] Carlini | Convergence of a generalized fast marching method for a non-convex eikonal equation[END_REF], which is now truly monotone (see the comparison principle Theorem 3.4). The monotony of a scheme is a very important property. Indeed it is a key ingredient to prove the convergence of the scheme (see the general proof of convergence of Barles and Souganidis [START_REF] Barles | Convergence of approximation schemes for fully nonlinear second order equations[END_REF]), but it can also be used to prove some error estimate (we refer to Crandall, Lions [START_REF] Crandall | Two approximations of solutions of Hamilton-Jacobi equations[END_REF]). In this direction, we give some heuristic error estimate in Theorem 8.1. We will explore more carefully the rate of convergence of our GFMM in a future work.

The comparison principle can also be useful to prove convergence result for non-local dynamics. We will use, in particular, this algorithm in a future work [START_REF] Carlini | Generalized fast marching method for dislocation dynamics[END_REF] to study numerically the dynamics of one dislocation line (see Alvarez, Hoch, Le Bouar, Monneau [START_REF] Alvarez | Dislocation dynamics: short time existence and uniqueness of the solution[END_REF] for a description of the mathematical model).

Organization of the paper

In Section 2, we give the modified version of the GFMM. The main results are presented in Section 3. In Section 4, we give some general properties of the algorithm. Sections 5 and 6 are devoted to the proof of the comparison principle Theorem 3.4. We also give a counter-example for the GFMM of [START_REF] Carlini | Convergence of a generalized fast marching method for a non-convex eikonal equation[END_REF]. In Section 7, we prove the convergence of the algorithm (see Theorem 3.6) and we provide an heuristic error estimate (Theorem 8.1).

The monotone GFMM algorithm

We begin this section by describing the new feature of our algorithm which makes it monotone.

Let us first recall the basic ideas of the classical FMM (as well as the GFMM of [START_REF] Carlini | Convergence of a generalized fast marching method for a non-convex eikonal equation[END_REF]). One feature of the classical FMM is to generate a sequence of times t n . In the GFMM algorithm (and also in the FMM) we also need a phase parameter θ n I with values +1 or -1 (which is in fact represented by the frozen points and its complementary set in the classical FMM) defined at each step n of the algorithm and for any I ∈ Z N . This θ n I should be thought as a discretisation of the solution θ of equation (1.1) at time t n and at point x I = I∆x (∆x being the space step).

To make evolve the front (i.e. the discontinuity of θ n I ), the FMM also needs to introduce a time u n I defined for I in the whole front at the n-th iteration of the algorithm. This time u n I can be interpreted in the classical FMM as the time when the front reaches the point I (this interpretation is essentially true for our GFMM algorithm except in the more delicate case where the velocity vanishes). The goal is then to find the next point reached by the front. To do this, the idea is to compute a tentative value ũn I (at the n-th iteration and at the point x I ) of the arrival time for all points which can be immediately reached by the front (which is called the Narrow Band). The computation of the tentative value ũn I uses the time u n J for J in the neighbourhood of I. The next points reached by the front is then the ones which have the minimum tentative value. We then denote by t n+1 this minimum value and we accept (i.e. we change the θ) at time t n+1 the points that realize the minimum and we iterate.

In the case of positive velocity, it has been proved that the GFMM scheme of [START_REF] Carlini | Convergence of a generalized fast marching method for a non-convex eikonal equation[END_REF] is monotone (as well as the classical FMM). This is not the case when the velocity can change sign (see the counter example in Subsection 5.2). This essentially comes from the change of the sign in time of the velocity. Indeed, to compute the tentative value ũn I , when the velocity changes sign, the good notion to use is the time when the front begins to go from a neighbour J of I to I, and not the time when the front reaches the point J. This two notions are the same when the velocity is of constant sign in time but they differ when the velocity changes sign. Moreover, for a point J, the time when the front begins to go from J to each direction can be different. This is the reason why we have to introduce several times for each node, in fact a time for each direction (see the details of the algorithm in Section 2).

With this new notion, we recover a good interpretation of the computation (even when the velocity vanishes or changes sign) and it is in fact sufficient to recover the monotonicity of the scheme.

Preliminaries

We consider a modified version of the GFMM algorithm introduced in [START_REF] Carlini | Convergence of a generalized fast marching method for a non-convex eikonal equation[END_REF]. Let us consider a lattice Q = {x I = (x i1 , .., x iN ) = (i 1 ∆x, .., i N ∆x), I = (i 1 , .., i N ) ∈ Z N } with space step ∆x. We will also use a time step ∆t > 0 (which does not satisfy any CFL condition). The following definitions will be useful in the following.

Definition 2.1

The neighbourhood of the node I ∈ Z N is the set

V (I) ≡ {J ∈ Z N : |J -I| ≤ 1}.
Definition 2.2 Given the speed c n I ≡ c(x I , t n ) we define the function

c n I ≡ 0 if there exists J ∈ V (I) such that (c n I c n J < 0 and |c n I | ≤ |c n J |), c n I otherwise. Definition 2.3 The numerical boundary ∂E of a set E ⊂ Z N is ∂E ≡ V (E)\E with V (E) = J ∈ Z N , ∃I ∈ E, J ∈ V (I)
Definition 2.4 Given a field θ n : Z N → {+1, -1}, we define the two phases

Θ n ± ≡ {I : θ n I = ±1},
and the fronts

F n ± ≡ ∂Θ n ∓ , F n ≡ F n + ∪ F n -.
We now describe our modified GFMM algorithm for unsigned velocity. As in the classical FMM, we define the Narrow Band (NB) which consists on the points I ∈ Z N that can be immediately reached by the front:

N B n = {I ∈ Z N , ∃ J ∈ V (I), θ n I = -θ n J and θ n I ĉn I < 0}, N B n ± = N B n ∩ {I, θ n I = ±1}.
We observe that the Narrow Bands N B n ± are related with the previous definition of fronts set as following:

N B n + = F n + ∩ {I, ĉn I < 0}, N B n -= F n -∩ {I, ĉn I > 0}.
Fig. 1 shows the Front and the Narrow Band, the white part of the picture represents the domain where the speed is negative and the grey part the domain with speed positive.

Figure 1: The Front F + (white spot), the front F -(black spot), the Narrow Band N B + (circled white spot) and the Narrow Band N B -(circled black spot). In the white domain the speed is negative, in the grey domain the speed is positive.

As in the FMM, for all I ∈ N B n , we have to compute a tentative value (which we denote ũn I in the sequel) of the arrival time of the front at point I. To compute this tentative value, we define the points that are useful for I, i.e. that we will use in the computation of ũn I :

U n (I) = {J ∈ V (I), θ n I = -θ n J }, U n = ∪ I∈N B n U n (I).
For all the points J that are useful for a point I ∈ N B n (i.e. J ∈ U n (I)) we will introduce a time u n J→I . This time u n J→I can be interpreted as the time when the front F n begin to go from point J to point I and will be used to compute the tentative value at point I.

The algorithm is now very similar to the classical Fast Marching Method. Once we have computed the tentative values for all points of the Narrow Band, we denote by tn the minimum of all this values. Unfortunately, this sequence of "candidate" time is not non-decreasing, so we have to truncate tn to define t n such that (see Step 6 of the algorithm): 0 ≤ t nt n-1 ≤ ∆t for a fixed ∆t (independent on ∆x). We then accept (in most of the cases, see Step 7 of the algorithm) all the points that realize the minimum (i.e., we change the value of the θ), we redefine the values u n J→I and we iterate.

The algorithm step-by-step

We now give the details of the algorithm: Let I ∈ N B n-1 , then we compute ũn-1 I as the solution of the following second order equation:

N k=1 max ± 0, ũn-1 I -u n-1 I k,± →I 2 = (∆x) 2 | c n-1 I | 2 , (2.1)
where

I k,± = (i 1 , .., i k-1 , i k ± 1, i k+1 , .., i N ).
5. tn = min ũn-1

I , I ∈ N B n-1 .
6. Truncate tn t n = max(t n-1 , min{ tn , t n-1 + ∆t})

7. if t n = t n-1 + ∆t and t n < tn go to 4 with n := n + 1, θ n = θ n-1 and u n = u n-1 .

Initialize the new accepted points

N A n ± = {I ∈ N B n-1 ± , ũn-1 I = tn }, N A n = N A n + ∪ N A n - 9. Reinitialize θ n θ n I = -θ n-1 I for I ∈ N A n θ n-1 I otherwise 10. Reinitialize u n I→K u n I→K = min(u n-1 I→K , t n ) if I ∈ U n (K)) and K ∈ N B n +∞ otherwise 11.
Set n := n + 1 and go to 4

Remark 2.5 In Step 12 of the algorithm described in [START_REF] Carlini | Convergence of a generalized fast marching method for a non-convex eikonal equation[END_REF], we defined u n on all the front F n , but in the modified version of the GFFM, we define finite values of u n (the useful time) only on the side of the front where we need the values to propagate our computation. Moreover, in this new version, the time at point I (u n I→K ) depends on the neighbours K and is defined as the first time the point I becomes useful for K.

Remark 2.6 We refer to [4, Subsection 2.3] for a detailed discussion on the complexity and on the implementation of the algorithm.

Main results

The physical sequence of time {t n , n ∈ N}, defined at the step 6 in the algorithm is non-decreasing and we can extract a subsequence {t n k , k ∈ N} strictly increasing such that

t n k = t n k +1 = ... = t n k+1 -1 < t n k+1 .
We denote by S k I the square cell

S k I = [x I , x I + ∆x[×[t n k , t n k+1 [ with [x I , x I + ∆x[= Π N α=1 [x iα , x iα + ∆x[
and by ε the couple ε = (∆x, ∆t).

Let us define the following functions:

(3.1) θ ε (x, t) = θ n k+1 -1 I if (x, t) ∈ S k I .

Definition 3.1 (Comparable and compared times)

Let T > 0 and let us consider two velocities c u and c v . We denote by (t n ) n and (u n J→K ) n (resp. (s m ) m and (v m J→K ) m ) the sequences of times and of useful times associated to the velocity c u (resp. c v ). We say that s m and t n are comparable if the property C(t n , s m ) holds true:

(C(t n , s m ))    t n ≤ s m < t n+1 and s m < s m+1 or s m ≤ t n < s m+1 and t n < t n+1 .
We say that θ m v and θ n u are compared and we denote this by

θ m v θ n u if for all J ∈ Z N ,            θ m v,J > θ n u,J , or    θ m v,J = θ n u,J =: σ J = ±1 and (with some obvious notation) σ J u n J→K ≥ σ J v m J→K for all K ∈ V (J)\{J} such that J ∈ U n u (K) ∩ U m v (K). Remark 3.2
The notation θ m v θ n u is abusive. Indeed, this is not an order relation and we also compare the value u n and v m in certain cases.

Remark 3.3

In the definition of θ m v θ n u , the fact that the inequality σ J u n J→K ≥ σ J v m J→K depends on σ J can seem curious a priori. The reason is that we search the minimum time and so when σ J = 1, since the point K has to be accepted for v before to be accepted for u, we should ask that u n J→K ≥ v m J→K . On the contrary, when σ J = -1, the point K has to be accepted for u before to be accepted for v and so we should ask the reverse inequality.

Theorem 3.4 (Comparison principle for the

θ ε ) Let T > 0. Let two velocities c u and c v . Given θ 0 u,J (resp. θ 0 v,J ) for all J ∈ Z N and u 0 J→K for all J ∈ U 0 u (K), K ∈ N B 0 u (resp. v 0 J→K for all J ∈ U 0 v (K), K ∈ N B 0 v ), we assume that t 0 := sup J∈U 0 u (K),K∈N B 0 u u 0 J→K ≤ T, resp. s 0 := sup J∈U 0 v (K),K∈N B 0 v v 0 J→K ≤ T for a given T > 0.
We also assume that the two velocities satisfy for all

(x, t) ∈ R N × [min(t 0 , s 0 ), T -∆t] inf s∈[t,t+∆t] c v (x, s) ≥ sup s∈[t,t+∆t] c u (x, s). If C(t 0 , s 0 ) and θ 0 v θ 0 u , then θ ε v (x, t) ≥ θ ε u (x, t) for all (x, t) ∈ R N × [max(t 0 , s 0 ), T ]. Remark 3.5 If we choose u 0 J→K = 0 for all J ∈ U 0 u (K), K ∈ N B 0 u and v 0 J→K = 0 for all J ∈ U 0 v (K), K ∈ N B 0 v , then the condition θ 0 v θ 0 u is equivalent to θ 0 v,I ≥ θ 0 u,I for all I ∈ Z N .
The basic idea to prove this comparison principle is that when a point K is such that

K ∈ N B n u ∩ N B m v
with t n and s m comparable (i.e. C(t n , s m ) is true), then all the points J such that J ∈ U n u (K) ∩ U m v (K) has become useful for v before to become useful for u. Using the definition of the time u n J→K and v m J→K (Step 10 of the algorithm), we can prove that this implies that v m J→K ≤ u n J→K and we then get that ṽm K ≤ ũn K (using the monotonicity of the computation of the candidate time, see Step 4 of the algorithm). It then implies that the point K will be accepted for v before to be accepted for u. This preserves the comparison of θ u and θ v .

We see here that the introduction of a time on each direction is crucial because it allows us to get that v m J→K ≤ u n J→K from the fact that J has become useful for v before to become useful for u. This implication is not true if we impose that the time on a point is the same in each direction.

We now give the convergence result for the modified GFMM (presented in Subsection 2.2). To do this, we make the following assumption

(A) The velocity c ∈ W 1,∞ (R N × [0, T ]), for some constant L > 0 we have |c(x ′ , t ′ ) -c(x, t)| ≤ L(|x ′ -x| + |t ′ -t|), and Ω 0 is a C 2 open set, with bounded boundary ∂Ω 0 .
We also have to define the half-relaxed limits of θ ε :

(3.2) θ 0 (x, t) = lim sup ε→0,y→x,s→t θ ε (y, s), θ 0 (x, t) = lim inf ε→0,y→x,s→t
θ ε (y, s).

Theorem 3.6 (Convergence Result)

Under assumption (A), θ 0 (resp. θ 0 ) is a viscosity sub-solution (resp. super-solution) of (1.1). In particular, if (1.1) satisfies a comparison principle, then θ 0 = (θ 0 ) * and (θ 0 ) * = θ 0 is the unique discontinuous viscosity solution of (1.1).

Preliminary results

In this section, we give some general properties of the algorithm that will be useful in the proofs.

Proposition 4.1 (General properties of the algorithm)

We have the following properties:

1. 0 ≤ t n -t n-1 ≤ ∆t 2.
For all K ∈ Z N and I ∈ U n (K), we have

u n I→K ≤ t n 3. N B n ∩ U n = ∅ 4. If I ∈ N A n , then u n I→K = t n if I ∈ U n (K) +∞ otherwise 5. If I ∈ N A n , then ũn-1 I ≤ t n . 6. If I ∈ U n-1 (K) ∩ U n (K), then u n I→K = u n-1 I→K . 7. If I ∈ U n (K)\U n-1 (K), then u n I→K = t n . 8. If t n > t n-1 then tn ≥ t n . 9. If t n = t n-1 , then tn ≤ t n .
Proof of Proposition 4.1

1. This is a straightforward consequence of Point 6 of the algorithm.

2. This is a straightforward consequence of Point 10 of the algorithm.

3. By contradiction, assume that there exists I and K ∈ V (I)\{I} such that I ∈ N B n ∩ U n (K). The fact that I ∈ N B n implies that (4.1)

θ n I ĉn I < 0.
The fact that I ∈ U n (K) implies that (4.2)

θ n I = -θ n K and θ n I ĉn K > 0.
Combining (4.1) and (4.2), we get ĉn I ĉn K < 0, which contradicts the definition of ĉ. [START_REF] Carlini | Convergence of a generalized fast marching method for a non-convex eikonal equation[END_REF]. By point 10 of the algorithm, we just have to prove that if

I ∈ N A n , then min(u n-1 I→K , t n ) = t n . But if I ∈ N A n , then I ∈ N B n-1
and so, by Property 3, we get that I ∈ U n-1 (K). This implies that u n-1 I→K = +∞. 5. By contradiction, assume that ũn-1

I > t n . Since I ∈ N A n , we get that ũn-1 I = tn > t n .
By Step 6 of the algorithm, we deduce that t n = t n-1 + ∆t < tn and so by Step 7, no point are accepted. Contradiction.

If

I ∈ U n-1 (K) ∩ U n (K), then by
Step 10 of the algorithm, we have

u n I→K = min(u n-1 I→K , t n ) = u n-1 I→K
where we have used Property 2 for the last equality.

7. If I ∈ U n (K)\U n-1 (K), then by Step 10 of the algorithm, we have

u n I→K = min(u n-1 I→K , t n ) = t n
where we have used that u n-1 I→K = +∞ since I ∈ U n-1 (K). 8. If t n > t n-1 , then by Step 6 of the algorithm, we get t n = min( tn , t n-1 + ∆t) ≤ tn . 9. If t n = t n-1 , then by Step 6 of the algorithm, we get

t n-1 ≥ min( tn , t n-1 + ∆t) and so t n = t n-1 ≥ tn . Proposition 4.2 (Monotonicity of c → ĉ) The application c → ĉ is monotone. More precisely, if c v ≥ c u then ĉv ≥ ĉu .
Proof of Proposition 4.2 Let c v ≥ c u . We will prove that for all I ∈ Z N , we have (4.3) ĉv,I ≥ ĉu,I .

The proof is distinguished in four cases: Since c v ≥ c u , this implies in particular that c u,I < 0. Since ĉu,I = c u,I , we also deduce that there exists J ∈ V (I) such that c u,J > 0 and |c u,I | ≤ |c u,J |. This implies that

|c v,I | ≤ |c u,I | ≤ |c u,J | = c u,J ≤ c v,J
and so ĉv,I = 0. This contradicts (4.4) and proves (4.3).

Case 4: ĉv,I = c v,I and ĉu,I = c u,I . This case can be treated in the same way as Case 3.

Proposition 4.3 (Symmetry of the algorithm)

Let us consider two velocities c u and c v . We denote by

(t u n ) n , (u n J→K ) n , (θ n u ) n (resp. (s v m ) m , (v m J→K ) m , (θ m v ) m
) the sequences of times , of useful times and of field associated to the velocity c u (resp c v ) and with the initial condition θ 0 u (resp. θ 0 v ). We also define

(s ū m ) m , (ū m J→K ) m , (θ m ū ) m (resp. (t v n ) n , (v n J→K ) n , (θ n v ) n ) the
θ m ū = -θ m v , θ n v = -θ n u , s ū m = s v m , t v n = t u n , ūm J→K = v m J→K , vn J→K = u n J→K
Let us assume that θ m v θ n u and let us prove that θ m ū θ n v (the other implication being similar). Case 1:

θ m v > θ n u Then θ m ū = -θ m v < -θ n u = θ n v . Case 2: θ m v = θ n u = σ This implies that θ m ū = θ n v = σ = -σ. Let J ∈ U m ū (K) ∩ U n v (K). This implies in particular that J ∈ U m v (K) ∩ U n u (K)
. Then, we have

σv n J→K = -σu n J→K ≤ -σv m J→K = σū m J→K
where we have used that θ m v θ n u . This implies that θ n v θ m ū .

5 Comparison principle

Comparison principle for θ ε

This subsection is devoted to the proof of Theorem 3.4.

To prove this theorem, we need the following comparison result for the t n time, whose proof is given in Subsection 5.3.

* = inf{t ≥ max(t 0 , s 0 ) s.t. θ ε v (x, t) < θ ε u (x, t) for some x ∈ R N } and x * s.t. θ ε v (x * , t * ) < θ ε u (x * , t * ). Let m, n and J s.t.    s m ≤ t * < s m+1 , t n ≤ t * < t n+1 , x * ∈ [x J , x J + ∆x).
Then

θ ε v (x * , t) = θ m v,J for t ∈ [s m , s m+1 ) and θ ε u (x * , t) = θ n u,J for t ∈ [t n , t n+1
). Therefore t * = s m or t * = t n and we can easily check that C(t n , s m ) is true. This implies by Theorem 5.1 that θ m v θ n u and then

θ m v,J ≥ θ n u,J
which is a contradiction.

Counter-example for GFMM of [4]

In this subsection, we give a counter-example in dimension one for the comparison principle for the GFMM of [START_REF] Carlini | Convergence of a generalized fast marching method for a non-convex eikonal equation[END_REF], which holds for all ∆x and ∆t small enough. We recall that in the GFMM of [START_REF] Carlini | Convergence of a generalized fast marching method for a non-convex eikonal equation[END_REF], we affect ,to u n (for points that are not accepted) the time when the point enter in the front while in the GFMM of Subsection 2.2, we affect the time when the point becomes useful.

The velocity for c u and c v are given by

c u (x, t) = max(0, 4 3 x) if t ≤ 1 min(0, -2x) if t ≥ 17 16 , c v (x, t) = max(0, x) if t ≤ 1 min(0, -3x) if t ≥ 17 16 and c u , c v ∈ Lip(R N × [0, T ]).
The initial conditions are given by

θ 0 u,i = θ 0 v,i = 1 if i ≤ 0 -1 if i ≥ 1
We begin to compute the evolution for u. The result are presented in Figure 2 on the left. A simple computation gives that the point i = 1 will be accepted at time t = 3 4 and we affect the value u 1 = u 2 = 3 4 . The point i = 2 will not be accepted before the velocity changes sign because ũ2 = 9 8 > 17 16 . When the velocity changes sign, the point i = 1 will be accepted again for ∆t small enough, with a time

u 1 = u 2 + ∆x 2∆x = 5 4 > 17 16
.

We now compute the evolution for v. The result are presented in Figure 2 on the right. As before, the point i = 1 will be accepted at time s = 1 and the point i = 2 will not be accepted before the velocity changes sign. Moreover, v 2 = 1. When the velocity changes sign, the point i = 1 will be again accepted with a time

v 1 = v 2 + ∆x 3∆x = 4 3 > 5 4 .
As we see, during the time interval [5/4, 4/3], we have

θ ε u (∆x, t) = -1 and θ ε v (∆x, t) = 1
which contradicts the comparison principle. Remark 5.2 In this counter-example, we see that the contradiction comes from the value we put for the node i = 2 which is the time when it enters in the front. This is the reason why, in our new GFFM (see Subsection 2.2), we put the time when the point become useful. Since the velocity are ordered, we then have u 2 ≤ v 2 and so the evolution preserves the inclusion (see Theorem 3.4).

x t t x 3 4 1 4 3 5 4 θ ε u = 1 θ ε u = -1 θ ε v = 1 θ ε v = -1

Comparison principle for the t n times

This subsection is devoted to the proof of Theorem 5.1. To perform the proof, we will need the following results

Lemma 5.3 (Two jumps, two arrivals)

Assume that θ m-1 v θ n-1 u . Then, if s m-1 ≤ t n < s m (resp. t n-1 ≤ s m < t n ) and t n , s m < T , then we have θ m-1 v θ n u (resp. θ m v θ n-1 u ).

Lemma 5.4 (Two jumps, one arrival)

Assume that θ m-1 v θ n-1 u , t n-1 < t n and s m-1 < s m . If s m = t n ≤ T , then θ m v θ n u .

Proposition 5.5 (Stationary case with the same arrival)

Let us assume that t n-p-1 < t n-p = ... = t n < t n+1 and s m-q-1 < s m-q = ... = s m < s m+1 with p, q ≥ 0 and

t n = s m ≤ T . If θ m-q v θ n-p u , then θ m v θ n u .
The proofs of Lemma 5.3 and 5.4 are given at the end of this subsection while the proof of Proposition 5.5 is given in Section 6. We define p ≥ 0 such that t n-p-1 < t n-p = ... = t n < t n+1 .

Proof of Theorem 5.1 By contradiction, let us define

s * = inf {min(t n , s m ) such that θ m v θ n u ,
Step 1 :

θ m v θ n-p-1 u To prove that θ m v θ n-p-1 u
is true, it suffices to show that C(t n-p-1 , s m ) is satisfied (because (n, m) is the minimal couple such that θ m v θ n u ). We recall that s m < t n-p = ... = t n < s m+1 , and t n-p+1 < t n-p .

If s m ≤ t n-p-1 , then s m ≤ t n-p-1 < s m+1 and t n-p-1 < t n-p , while if t n-p-1 < s m , then t n-p-1 < s m < t n-p and s m < s m+1 .

So, we always have that property C(t n-p-1 , s m ) is satisfied, which implies that θ m v θ n-p-1 u .

Step 2: Contradiction. Using Lemma 5.3 successively, we deduce that

θ m v θ n-p u ,..., θ m v θ n u . Contradiction.
Case 2: s m = t n Let us define p and q such that t n-p-1 < t n-p = ... = t n < t n+1 and s m-q-1 < s m-q = ... = s m < s m+1 .

We then have t n-p-1 ≤ s m-q-1 < s m-q = t n-p or s m-q-1 ≤ t n-p-1 < t n-p = s m-q and so C(t n-p-1 , s m-q-1 ) is satisfied. Therefore, this implies (by definition of (n, m)) that θ m-q-1 v θ n-p-1 u . Using Lemma 5.4, we deduce that θ m-q v θ n-p u . Using Proposition 5.5, we then deduce that θ m v θ n u . Contradiction.

Before to give the proofs of Lemma 5.3 and 5.4, we need some preliminary results (Lemma 5.6 and 5.7). The following lemma claims that if we compare

θ n-1 u and θ m-1 v (in the sense θ m-1 v θ n-1 u
), then we can compare the candidate time ũn-1 and ṽm-1 on the Narrow Band. This essentially comes from our definition of θ m-1 v θ n-1 u in which we compare not only the θ (and so the point that will play a role in the computation of the candidate time) but also the time on the useful points. The result then comes from the monotonicity of the computation of the candidate time (see Step 4 of the algorithm).

Lemma 5.6 (Comparison of the candidate time ũ)

Assume that θ m-1 v θ n-1 u , |t n-1 -s m-1 | ≤ ∆t, with t n-1 , s m-1 ≤ T . If θ m-1 v,I = θ n-1 u,I = -1 and I ∈ N B n-1 u,- resp. θ m-1 v,I = θ n-1 u,I = 1 and I ∈ N B m-1 v,+ , then I ∈ N B m-1 v,-
and ũn-1

I ≥ ṽm-1 I resp. I ∈ N B n-1 u,+
and ũn-1

I ≤ ṽm-1 I .
Proof of Lemma 5.6

We do the proof in the case

θ m-1 v,I = θ n-1 u,I = -1 and I ∈ N B n-1 u,-(the other case is similar). Since I ∈ N B n-1 u,-, we deduce that (5.1) ∃J ∈ V (I)\{I} s.t. θ n-1 u,J = 1 ĉn-1 u,I > 0
Step 1:

I ∈ N B m-1 v,- Since θ m-1 v θ n-1 u
, we deduce that θ m-1 v,J ≥ θ n-1 u,J = 1 and so θ m-1 v,J = 1. This implies that (5.2)

I ∈ F m-1 v,-. Moreover |t n-1 -s m-1 | ≤ ∆t and so c v (•, s m-1 ) ≥ c u (•, t n-1 ).
Using Proposition 4.2, yields (5.3) ĉm-1 v,I ≥ ĉn-1 u,I > 0 where the last inequality comes from (5.1).

Combining (5.2) and ( 5.3), we deduce that (5.4)

I ∈ N B m-1 v,-.
Step 2: Ordering u n-1

•→I ≥ v m-1 •→I Let J ∈ V (I)\ {I}. Case 1: θ m-1 v,J = -1 Since θ m-1 v θ n-1 u
, we get that θ m-1 v,J ≥ θ n-1 u,J and then θ n-1 u,J = -1. Therefore

u n-1 J→I = +∞ = v m-1 J→I Case 2: θ m-1 v,J = +1 Assume first that θ n-1 u,J = +1 which implies that J ∈ U n-1 u (I) ∩ U m-1 v (I). Then assumption θ m-1 v θ n-1 u implies that u n-1 J→I ≥ v m-1
J→I with σ J = +. In the case θ n-1 u,J = -1, we get that u n-1 J→I = +∞ which again implies u n-1 J→I ≥ v m-1 J→I .

We therefore deduce that in the general case, we always have

u n-1 J→I ≥ v m-1 J→I for any J ∈ V (I)\ {I} .
Step 3: ũn-1

I ≥ ṽm-1 I We know that N k=1 max 0, ũn-1 I -u n-1 I k,± →I 2 = (∆x) 2 |ĉ n-1 u,I | 2 and N k=1 max 0, ṽm-1 I -v m-1 I k,± →I 2 = (∆x) 2 |ĉ m-1 v,I | 2 with ĉm-1
v,I ≥ ĉn-1 u,I > 0 (see (5.3)), which implies, using also Step 2 that ũn-1

I ≥ ṽm-1 I
and ends the proof of the Lemma.

The following lemma claims that a point J with θ m v,J = θ n u,J = -1 is useful for u before to be useful for J. This essentially comes from the fact that the velocity are ordered.

Lemma 5.7 (Property of useful points)

Assume that J ∈ U m v (K) ∩ U n u (K), θ m v,J = θ n u,J = θ n-1 u,J = -1 and |t n-1 -s m | ≤ ∆t with t n , s m ≤ T . Then J ∈ U n-1 u (K).
Proof of Lemma 5.7 By contradiction, assume that J ∈ U n-1 u (K). Since J ∈ U m v (K) and θ m v,J = -1, we deduce that θ m v,K = 1 and ĉm v,K < 0. In the same way, we also have

θ n u,K = 1 and ĉn u,K < 0 Now because |t n-1 -s m | ≤ ∆t, we deduce that ĉn-1 u,K ≤ ĉm v,K < 0.
Using that θ n-1 u,J = -1, ĉn-1 u,K < 0 and J ∈ U n-1 u (K), we deduce that

θ n-1 u,J = θ n-1 u,K = -1
But we can not pass from θ n-1 u,K = -1 to θ n u,K = +1 with a negative velocity ĉn-1 u,K < 0. Contradiction.

Proof of Lemma 5.3

We make the proof in the case s m > t n , the other case being equivalent by symmetry (see Proposition 4.3). By contradiction, assume that θ m-1 v θ n u . Then, there exists J such that (5.5)

   θ m-1 v,J < θ n u,J or θ m-1 v,J = θ n u,J = σ J and ∃K : J ∈ U m-1 v (K) ∩ U n u (K) and σ J u n J→K < σ J v m-1

J→K

The proof is decomposed in two cases: in the first one, the value of θ n u changes while it do not change in the second one.

Case 1: J ∈ N A n u

There is only two non trivial sub-cases (but we treat all the cases below). The first one (Sub-case 1.1) is when the two θ were different and are now the same. In this case, we will contradicts the second line of (5.5) (on the time). This is rather easy because we know the value of u n J→K (which is in fact t n since J ∈ N A n u ). The second non trivial sub-case (Sub-case 1.2.2) is when the θ were the same and are now order in the bad sense (first line of (5.5)). In this case, we will prove that J should have been accepted for v before to be accepted for u.

Sub-case 1.1: θ m-1 v,J > θ n-1 u,J Then θ m-1 v,J = 1 and θ n-1 u,J = -1. Since J ∈ N A n u , we deduce that θ n u,J = 1 = θ m-1 v,J = σ J . We then have v m-1 J→K ≤ s m-1 ≤ t n = u n J→K
where we have used the fact that J ∈ U m-1 v (K) and Proposition 4.1 Point 2 for the first inequality and the fact that J ∈ N A n u ∩ U n u (K) joint to Proposition 4.1 Point 4 for the last equality. This contradicts (5.5). Sub-case 1.2:

θ m-1 v,J = θ n-1 u,J Sub-case 1.2.1: θ m-1 v,J = θ n-1 u,J = 1 Since J ∈ N A n u , we deduce that θ n u,J = -1. This contradicts (5.5). Sub-case 1.2.2: θ m-1 v,J = θ n-1 u,J = -1 Step 1: ũn-1 J ≥ ṽm-1 J and J ∈ N B m-1 v,-
We want to apply Lemma 5.6. We recall that θ m-1 v θ n-1 u and θ m-1 v,J = θ n-1 u,J = -1. Since J ∈ N A n u , we also deduce that J ∈ N B n-1 u,-. Moreover |t n-1s m-1 | ≤ ∆t (because s ms m-1 ≤ ∆t and t nt n-1 ≤ ∆t). We can then apply Lemma 5.6 to get ũn-1

J ≥ ṽm-1 J and J ∈ N B m-1 v,- Step 2: ṽm-1 J ≥ s m Recall that s m = max(s m-1 , min(s m-1 + ∆t, sm )). But s m > s m-1 and so s m = min(s m-1 + ∆t, sm ) ≤ sm .
Since, by definition of sm , we have sm ≤ ṽm-1

J with J ∈ N B m-1 v,-(Step 1), we deduce that ṽm-1 J ≥ s m .
Step 3: Contradiction By Step 1 and 2, we get ũn-1

J ≥ ṽm-1 J ≥ s m > t n
and then ũn-1

J > t n . This is impossible because J ∈ N A n u (see Proposition 4.1 Point 5). Sub-case 1.3: θ m-1 v,J < θ n-1 u,J This is impossible since θ m-1 v θ n-1 u . Sub-case 1.2: θ m-1 v,J = θ n-1 u,J Sub-case 1.2.1: θ m-1 v,J = θ n-1 u,J = 1 Since J ∈ N A n u \N A m v
, we deduce that θ n u,J = -1 and θ m v,J = 1. This contradicts (5.8). Sub-case 1.2.2:

θ m-1 v,J = θ n-1 u,J = -1 Step 1: ũn-1 J ≥ ṽm-1 J Since J ∈ N A n
u and θ n-1 u,J = -1, we deduce that J ∈ N B n-1 u,-. Moreover |t n-1s m-1 | ≤ ∆t, so we can apply Lemma 5.6 to get

J ∈ N B m-1 v,-
and ũn-1

J ≥ ṽm-1 J
Step 2: ṽm-1 J > s m Recall that s m = max(s m-1 , min(s m-1 + ∆t, sm )). But s m > s m-1 and so

s m = min(s m-1 + ∆t, sm ).
Recall that by definition of sm , we have sm ≤ ṽm-1

J with J ∈ N B m-1
v,-. We distinguish two cases:

1. ṽm-1 J > sm . Then s m ≤ sm < ṽm-1 J . 2. ṽm-1 J = sm . Since J ∈ N A m v ,
s m = s m-1 + ∆t < sm = ṽm-1 J .
Step 3: Contradiction By Step 1 and 2, we get ũn-1

J ≥ ṽm-1 J > s m = t n . This is impossible because J ∈ N A n u (see Proposition 4.1 Point 5). Sub-case 1.3: θ m-1 v,J < θ n-1 u,J This is impossible since θ m-1 v θ n-1 u . Case 2: J ∈ N A m v \N A n u
By symmetry (see Proposition 4.3), this case can be treated in the same way of Case 1.

Case 3:

J ∈ N A n u ∩ N A m v Sub-case 3.1: θ m-1 v,J > θ n-1 u,J
This implies that θ m-1 v,J = 1 and θ n-1 u,J = -1. Using also that J

∈ N A n u ∩ N A m v , we deduce that J ∈ N B n-1 u,-∩ N B m-1 v,+
This implies that ĉn-1 u,J > 0 and ĉm-1 v,J < 0. This is absurd since

|s m-1 -t n-1 | < ∆t. Sub-case 3.2: θ m-1 v,J = θ n-1 u,J Since J ∈ N A n u ∩N A m v , we deduce that θ n u,J = θ m v,J . Using that J ∈ U n u (K)∩U m v (K), we have by Proposition 4.1 point 4 v m J→K = s m = t n = u n J→K . This contradicts (5.8). Sub-case 3.3: θ m-1 v,J < θ n-1 u,J This is impossible since θ m-1 v θ n-1 u . Case 4: J ∈ N A n u ∪ N A m v Sub-case 4.1: θ m v,J < θ n u,J Since J ∈ N A n u ∪ N A m v , we have θ n-1 u,J = θ n u,J and θ m-1 v,J = θ m v,J . We then get θ m-1 v,J < θ n-1 u,J . Contradiction with θ m-1 v θ n-1 u . u,J Sub-case 1.2.1: θ m-l v,J = θ n-k u,J = 1 Since J ∈ N A n-k+1 u \N A m-l+1 v
, we deduce that θ n-k+1 u,J = -1 and θ m-l+1 v,J = 1. This contradicts (6.5). Let ϕ ∈ C 2 in a neighbourhood V of (x 0 , t 0 ) such that ϕ t (x 0 , t 0 ) > 0. There exist δ 0 > 0, r > 0, τ > 0

Sub

-case 1.2.2: θ m-l v,J = θ n-k u,J = -1 Step 1: ũn-k J ≥ ṽm-l J Since J ∈ N A n-k+1 u with θ n-k u,J = -1, we deduce that J ∈ N B n-k u,-. Moreover t n-k = s m-l joint
such that if max V ((θ ε ) * -ϕ) is reached at (x ε , t ε ) ∈ B δ0 (x 0 , t 0 ) ⊂ V with (θ ε ) * (x ε , t ε ) = 1, then there exists Ψ ε ∈ C 2 (B r (x 0 ), (t 0 -τ, t 0 + τ )) such that (i) For all (x J , t m ) ∈ Q r,τ (x 0 , t 0 ) = B r (x 0 ) × (t 0 -τ, t 0 + τ ) (7.2) θ ε (x J , t m ) = 1 =⇒ t m ≥ Ψ ε (x J ).
(ii) There exists (I,

n k ) ∈ Z N × N such that (x ε , t ε ) ∈ Sk I = [x I , x I + ∆x] × [t n k , t n k+1 ], (θ ε ) * (x I , t n k ) = 1, t n k = Ψ ε (x I ) and θ n I = 1, θ m I = -1 m 0 ≤ m ≤ n -1 where n = inf {n, n k ≤ n ≤ n k+1 -1, θ n I = 1} and m 0 = inf{m, t m ≥ t 0 -τ }.
(iii) The following Taylor expansion holds

Ψ ε (x J ) = Ψ ε (x I ) - Dϕ(x 0 , t 0 ) ϕ t (x 0 , t 0 ) (x J -x I ) + (∆x) O (∆x + |x I -x 0 | + |t n k -t 0 |) .
We now come back to the proof of Theorem 3.6.

For all J ∈ U n-1 (I) (with n defined in Lemma 7.3), we define

m J = sup{k ≤ n, J ∈ U k-1 (I)}
We distinguish two cases:

1. There exists J ∈ U n-1 (I) such that m J < m 0 .

In particular, we have that J ∈ U m (I) for m 0 ≤ m ≤ n -1, so by Proposition 4.1 Point 6 and Point 2, we have that u n-1 J→I = u m0 J→I ≤ t m0 . Moreover, since J ∈ U m (I) and θ m I = -1 for m 0 ≤ m ≤ n -1, we deduce that θ ε (x J , t m0 ) = 1. By (7.2), we then have t m0 ≥ Ψ ε (x J ).

We now assume that |Dϕ| = 0 (the case |Dϕ| = 0 can be treated in a similar way). Using Lemma 7.3 iii), we deduce that

t m0 ≥ Ψ ε (x J ) = t n k - 1 c n 0 • (x J -x I ) + (∆x) O(∆x + |x I -x 0 | + |t n k -t 0 |), where c = α |Dϕ(x 0 , t 0 )| > 0 and n 0 = Dϕ(x 0 , t 0 ) |Dϕ(x 0 , t 0 )| . We then get t n k -t m0 ≤ 1 c n 0 • (x J -x I ) + (∆x) O(∆x + |x I -x 0 | + |t n k -t 0 |) ≤ ∆x c + (∆x) O(∆x + |x I -x 0 | + |t n k -t 0 |)
Sending ∆x, ∆t to 0, we remark that t n k → t 0 (since t ε → t 0 , t ε ∈ [t n k , t n k+1 [ and t n k+1t n k ≤ ∆t) and t m0 → t 0τ (by definition of m 0 ). This implies that

t 0 -(t 0 -τ ) = τ ≤ 0.
This is absurd.

2. For all J ∈ U n-1 (I), m J ≥ m 0 .

Using the fact that J ∈ (U mJ (I) ∩ ... ∩ U n-1 (I))\U mJ -1 (I) joint to Proposition 4.1 Point 6 and 7, we get that u n-1 J→I = u mJ J→I = t mJ . Moreover (since J ∈ U m (I) and θ m I = -1 for m J ≤ m ≤ n -1), we have that θ ε (x J , t mJ ) = 1 and so by (7.2) we have u n-1 J→I = t mJ ≥ Ψ(x J ). We now assume that |Dϕ| = 0 (the case |Dϕ| = 0 can be treated in a similar way). Using Lemma 7.3 iii), we deduce that

u n-1 J→I ≥ Ψ(x J ) = t n k - 1 c n 0 • (x J -x I ) + (∆x) O(∆x + |x I -x 0 | + |t n k -t 0 |),
where c = α |Dϕ(x 0 , t 0 )| > 0 and n 0 = Dϕ(x 0 , t 0 ) |Dϕ(x 0 , t 0 )| . Since I ∈ N A n , we know by Proposition 4.1 Point 5 that ũn-1

I ≤ t n = t n k . This implies that ũn-1 I -u n-1 J→I ≤ t n k -u n-1 J→I ≤ 1 c n 0 • (x J -x I ) + (∆x) O(∆x + |x I -x 0 | + |t n k -t 0 |)
We first define u n-1 I i →I for all directions i ∈ C ⊂ {1, .., N } such that ũn-1

I -u n-1 I i →I := max(ũ n-1 I -u n-1 I i,+ →I , ũn-1 I -u n-1 I i,-→I ) ≥ 0. We deduce that ∆x c n-1 I 2 = i∈C ũn I -u n-1 I i →I 2 ≤ ∆x c 2 + (∆x) 2 O(∆x + |x I -x 0 | + |t n k -t 0 |). i.e. 1 | c n-1 I | 2 ≤ 1 c2 + O(∆x + |x I -x 0 | + |t n k -t 0 |)
Sending ∆x, ∆t to 0, yields a contradiction since c > c(x 0 , t 0 ) = 0.

This ends the proof of the theorem.

8 Appendix: heuristic error estimate for monotone evolution

We propose an error estimate in the case of the dynamics with signed speed. This is an heuristic computation, since we assume that the solution of the PDE (1.1) is a characteristic function of a smooth hyper-surface to allow us to do all the computations. This explain why we obtain an error estimate of order 1, while for this type of scheme the expected order of convergence is 1/2, see [START_REF] Crandall | Two approximations of solutions of Hamilton-Jacobi equations[END_REF].

In the proof we make use of a recent result by Vladimirsky, see [START_REF] Vladimirsky | Static pdes for time-dependent control problems[END_REF], where the propagation of a front evolving with signed speed depending on time is interpreted as a static PDE for a time-dependent control problem. We consider here the case of an isotropic dynamics, but in the cited paper the general anisotropic case is analysed.

Let Ω 0 be a bounded domain of R N and let u(x) be the minimum time to reach a point x ∈ Ω 0 starting from any point of ∂Ω 0 with the velocity c(x, t) : Ω 0 × [0, ∞) → (-∞, 0). If c is Lipschitz continuous and bounded, then the minimum time can be obtained solving the following stationary PDE: It is known, see for instance [START_REF] Falcone | The minimum time problem and its applications to front propagation[END_REF], that c(x, t) can be interpreted as a normal speed of a contracting front, whose position at time t is the level set u(x) = t. Then θ(x, t) = 1 {u(x)>t} -1 {u(x)≤t} solves the eikonal equation (1.1) with speed c(x, t).

Proof of Proposition 8.4

In fact, in the proof of Theorem 3.4, when the velocities are positive, the only point where we have to compare the velocities is in Lemma 5.6 and it is in fact sufficient to have an information on c v,I only when I ∈ N A m v (i.e. for ĉm-1 v,I )

Proof of Theorem 8.1 Let us denote by u the solution of (8.1) such that θ(x, t) = 1 {u(x)>t} -1 {u(x)≤t} . Given a mesh {x I = I∆x, I ∈ Z n }, we define a sequence of discrete increasing time t n in the following way t 1 = min{u(x I ), x I ∈ Ω 0 } t n = min{u(x I ) > t n-1 , x I ∈ Ω 0 } for n ≥ 2.

Then we consider θ ε,0 (x, t) the projection of θ on the mesh, defined by (8.5) θ ε,0 (x, t) = θ(x I , t n ) if x ∈ [x I , x I + ∆x) and t ∈ [t n , t n+1 ).

In particular, we have |θ ε,0 -θ| L ∞ ((0,T );L 1 (R N )) ≤ C(∆x + ∆t)

where C is a constant (depending on u C 2 ). Let us call θ ε the numerical solution obtained by the GFFM algorithm and extended in the continuous space by (3.1). For e > 0, we consider the discrete velocities ĉn-1,+e where K T is a positive constant. The last inequality follows by regularity property of equation (1.1) (see for instance [START_REF] Alvarez | Existence and uniqueness for dislocation dynamics with nonnegative velocity[END_REF]).

We now give the proof of Lemma 8.

Initialization 1 . 1 2. 3 .Loop 4 .

 1134 Set n = Initialize the field θ 0 as Initialize the time for pointsI u 0 I→K = t 0 if I ∈ U 0 (K) and K ∈ N B 0 +∞ otherwise Compute ũn-1 on N B n-1

Case 1 :

 1 ĉv,I = c v,I and ĉu,I = c u,I . In this case, we have ĉv,I = c v,I ≥ c u,I = c u,I and (4.3) is true. Case 2: ĉv,I = c v,I and ĉu,I = c u,I . In this case, we have ĉv,I = 0 = ĉu,I and so (4.3) is true. Case 3: ĉv,I = c v,I and ĉu,I = c u,I . This implies in particular that ĉu,I = 0. By contradiction, let us assume that (4.4) ĉv,I = c v,I < 0 = ĉu,I .

3 Following [ 4 ,

 34 sequences of times , of useful times and of field associated to the velocityc ū = -c v (resp c v = -c u ) and with the initial condition θ 0 ū = -θ 0 v (resp. θ 0 v = -θ 0 u ). Then, we have the following equivalence: Lemma 4.1], we have

Theorem 5 . 1 (

 51 Comparison principle for the t n times) Under the assumptions of Theorem 3.4, we denote by (t n ) n and (u n J→K ) n (resp. (s m ) m and (v m J→K ) m ) the sequences of times and of useful times associated to the velocity c u (resp. c v ). Then θ m v θ n u for every times satisfying (C(t n , s m )) and t n , s m ≤ T . Proof of Theorem 3.4 Let us define t

Figure 2 :

 2 Figure 2: Counter-example for the comparison principle.

J>.Lemma 7 . 3 (

 73 to the fact that by assumption in Lemma 6.5, we have θ m-Because s m-l+1 = s m-l and J ∈ N A m v , we deduce (see Point 8 of the algorithm) that sm-l+1 < ṽm-l sm-l+1 = tn-k+1 .This is impossible because J ∈ N A n-k+1 u (see Point 8 of the algorithm).Sub-case 1.3:θ m-l v,J < θ n-k u,JThis is impossible since θ m-l v θ n-k u Separation of the phases of θ ε by the level set of a test function)

(8. 1 )

 1 -c(x, u(x))|Du(x)| = 1 in Ω 0 , u(x) = 0 on ∂Ω 0 .

I

  and ĉn-1,-e I defined by Lemma 8.3 from Problem (8.2) with velocity c + e and ce respectively. From (8.4), we have, for e ≥ C(∆x + ∆t) and C large enough ĉn-1,+eI ≥ sup s∈[-∆t,∆t],tn-1+s≥0 c(x I , t n-1 + s), ĉn-1,-e I ≤ inf s∈[-∆t,∆t],tn-1+s≥0 c(x I , t n-1 + s)for (I, n) such that u e (x I ) = t e n . Using the comparison principle Proposition 8.4, we then get θ ε,+e ≥ θ ε and θ ε,-e ≤ θ ε .By the comparison principle for equation (1.1), we have θ -e ≤ θ ≤ θ e and then by Lemma 8.3, the following inequality holds θ ε,-e ≤ θ ε,0 ≤ θ ε,+e .Choosing e := C(∆x + ∆t) = O(|ε|), we can conclude that|θ ε (•, t)θ(•, t)| L ∞ ((0,T );L 1 (R N )) ≤|θ εθ ε,0 | L ∞ ((0,T );L 1 (R N )) + |θ ε,0 -θ| L ∞ ((0,T );L 1 (R N ))≤|θ ε,+e (•, t)θ ε,-e (•, t)| L ∞ ((0,T );L 1 (R N )) + C(∆x + ∆t)≤K T (∆x + ∆t).

3 :

 3 Proof of Lemma 8.3 We define ûn,e J = u e (x J ) if u e (x J ) ≤ t e n +∞ otherwise To construct the velocity ĉn-1,e I , we solve (2.1) (where the unknown is the velocity ĉn-1,e I ) for I such that u e (x I ) = t e n . In particular, we have ĉn-1,e I = c(x I , t e n ) + e + O(∆x) and by construction θ ε,e (x I , t e n ) = θ e (x I , t e n ).

  t n , s m ≤ T and C(t n , s m ) is true} Up to a symmetry (see Proposition 4.3), we can assume that s * = s m * for a certain index m * . Then let us define n

* = inf n ≥ 0 such that θ m * v θ n u , t n ≤ T and C(t n , s m * ) is true Therefore (t n * , s m * ) is the minimal couple such that θ m * v θ n * u , s m * ≤ t n * < s m * +1 and t n * < t n * +1 .

To simplify the notation, let us denote n * by n and m * by m. The proof is decomposed into two cases: Case 1: s m < t n

  we deduce that (see Step 7 and 8 of the algorithm)

Projet Commands, CMAP-INRIA Futurs, Ecole Polytechnique, 91128 Palaiseau and ENSTA, UMA, 32 Bd Victor, 75739 Paris Cedex 15, France.

CERMICS, Paris Est-ENPC, 6 & 8 avenue Blaise Pascal, Cité Descartes, Champs sur Marne, 77455 Marne la Vallée Cedex 2, France.

Acknowledgements

The author would like to thank E. Carlini and R. Monneau for fruitful discussions in the preparation of this paper. This work was supported by the ACI JC 1025 and the ANR MICA (2006)(2007)(2008)(2009).

Case 2: J ∈ N A n u In this case, the θ do not change and we essentially have to contradict the second line of (5.5). There is essentially two cases. The first one is when the value of u n J→K has changed and we will use that u n J→K = t n . The second one is when u n J→K = u n-1 J→K and we will use assumption θ m-1 v,J

θ n-1 u,J to get the contradiction. Sub-case 2.1: θ m-1 v,J < θ n u,J

Since J ∈ N A n u , we have θ n-1 u,J = θ n u,J and so θ m-1 v,J < θ n-1 u,J . Contradiction with θ m-1 v θ n-1 u .

Sub-case 2.2: θ m-1 v,J = θ n u,J

Since J ∈ N A n u , we have (5.6) θ n-1 u,J = θ n u,J = θ m-1 v,J = σ J = ±1.

From (5.5), there exists K such that (5.7)

J→K

We then distinguish several sub-cases: Sub-case 2.2.1: J ∈ U n-1 u (K) From (5.7), we have J ∈ U m-1 v (K) ∩ U n-1 u (K). Now the fact that θ m-1 v θ n-1 u and (5.6) imply that

K) imply, by Proposition 4.1 Point 6, that u n J→K = u n-1 J→K . Therefore

which contradicts (5.7).

Sub-case 2.2.2: J ∈ U n-1 u (K) and σ J = +1 Using the fact that J ∈ U n u (K)\U n-1 u (K) joint to Proposition 4.1 Point 7, we get that u n J→K = t n . This implies that

where we have used the fact that J ∈ U m-1 v (K) joint to Proposition 4.1 Point 2 for the last inequality. Contradiction with (5.7).

Sub-case 2.2.3: J ∈ U n-1 u (K) and σ J = -1 In this case, we have J ∈ U m-1 v (K) ∩ U n u (K) and θ n-1 u,J = θ n u,J = θ m-1 v,J = -1. So we can apply Lemma 5.7 and we get that J ∈ U n-1 u (K). Contradiction.

Proof of Lemma 5.4

The proof is very similar to the one of Lemma 5.3, but there are some additional cases. For the reader's convenience we give all the structure of the proof. By contradiction, assume that θ m v θ n u . Then, there exists J such that (5.8)

The proof is decomposed in several cases:

where we have used the fact that J ∈ U m v (K) and Proposition 4.1 Point 2 for the first inequality and the fact that J ∈ N A n u ∩ U n u (K) joint to Proposition 4.1 Point 4 for the last equality. This contradicts (5.8).

Sub-case 4.2:

From (5.8), there exists K such that J ∈ U m v (K) ∩ U n u (K) and

(5.10)

We then distinguish several sub-cases: Sub-case 4.2.1:

(K) From (5.9) and the fact that θ m-1 v θ n-1 u , we have

So we can apply Lemma 5.7 and we get that

By symmetry, this sub-case can be treated in the same way of sub-case 4.2.2.

Sub-case 4.2.4:

(K), we deduce by Proposition 4.1 Point 7 that

This contradicts (5.10).

6 Comparison principle for the tn times: proof of Proposition 5.5

This subsection is devoted to the proof of Proposition 5.5. We will prove a more general result (see Proposition 6.2). We recall that we consider two sequences t n-p-1 < t n-p = .... = t n < t n+1 and s m-q-1 < s m-q = ... = s m < s m+1 such that t n = s m ≤ T . For simplicity of notation, we redefine, only in this subsection, (6.1) tn-p = -∞ and sm-q = -∞.

We recall that by definition of comparable time Definition 3.1, that tn-k and sm-l are comparable for 0 ≤ k ≤ p and 0

Remark 6.1 Let us point out that for 0 ≤ k ≤ p (resp. 0 ≤ l ≤ q), we always have tn-k < tn-k+1 (resp. sm-l < sm-l+1 ).

This comes from the fact that the velocity c n-k u (resp. c m-l v

) is independent on k = 0, ..., p (resp. l = 0, ..., q) and from our definition (6.1).

To prove Proposition 5.5, we will prove the following more general result: Proposition 6.2 (Comparison principle for the tn times) 8 and9). This implies that C( tn , sm ) is true and then Proposition 6.2 implies that θ m v θ n u and so Proposition 5.5 is true.

The proof of Proposition 6.2 is similar to the one of Theorem 5.1 and we need the equivalent of Lemma 5.3 and 5.4 whose proofs are postponed:

Up to a symmetry (see Proposition 4.3), we can assume that s * = sm-l * for a certain index l * . Then let us define

Since C( tn-p , sm-q ) is true, we get that k * < p or l * < q and since sm-l * ≤ tn-k * , we get that k * < p.

To simplify the notation, let us denote k * by k and l * by l. The proof is decomposed into two cases:

Step 2: Contradiction. Using Lemma 6.4, we deduce that θ m-l v θ n-k u . Contradiction.

Case 2: sm-l = tn-k Since k < p, we deduce that sm-l = tn-k > -∞ and so l < q. Moreover, we have tn-k-1 ≤ sm-l-1 < sm-l = tn-k or sm-l-1 ≤ tn-k-1 < tn-k = sm-l and so C( tn-k-1 , sm-l-1 ) is satisfied. Therefore, this implies (by definition of (k, l)) that θ m-l-1 v θ n-k-1 u . Using Lemma 6.5, we deduce that θ m-l v θ n-k u . Contradiction.

We now give the proofs of Lemma 6.4 and 6.5.

Proof of Lemma 6.4

We make the proof in the case sm-l+1 > tn-k+1 , the other case being equivalent by symmetry (see Proposition 4.3). Since tn+1 ≥ t n+1 > t n = s m ≥ sm ≥ sm-l+1 for 1 ≤ l ≤ q + 1 (see Proposition 4.1 Point 8 for the first inequality and Point 9 for the last one), we deduce that 1 ≤ k ≤ p and t n-k+1 = t n .

By contradiction, assume that θ m-l v θ n-k+1 u . Then there exists J such that (6.2)

The proof is decomposed in several cases:

J→K where we have used the fact that J ∈ U m-l v (K) and Proposition 4.1 Point 2 for the first inequality and the fact that J ∈ N A n-k+1 u ∩ U n-k+1 u (K) joint to Proposition 4.1 Point 4 for the last equality. This contradicts (6.2). where we have used the definition of sm-l+1 (see point 5 of the algorithm) for the last inequality. This contradicts the fact that sm-l+1 > tn-k+1

From (6.2), there exists

We then distinguish several sub-cases: Sub-case 2.2.1: J ∈ U n-k u (K) From (6.3) and the fact that θ m-l v θ n-k u , we have

J→K ≥ σ J v m-l J→K , which contradicts (6.4). Sub-case 2.2.2: J ∈ U n-k u (K) and σ J = +1 Using the fact that J ∈ U n-k+1 u (K)\U n-k u (K), joint to Proposition 4.1 Point 7, we get that u n-k+1 J→K = t n-k+1 . This implies that

where we have used the fact that J ∈ U m-l v (K) joint to Proposition 4.1 Point 2 for the last inequality. Contradiction with (6.4).

Sub-case 2.2.3:

= θ m-l v,J = -1. So we apply Lemma 5.7 and we get that J ∈ U n-k u (K). Contradiction.

Proof of Lemma 6.5 By contradiction, assume that θ m-l+1 v θ n-k+1 u . Then, there exists J such that (6.5)

J→K

The proof is decomposed in several cases:

Then θ m-l v,J = 1 and θ n-k u,J = -1.

J→K where we have used the fact that J ∈ U m-l+1 v (K) and Proposition 4.1 Point 2 for the first inequality and the fact that J ∈ N A n-k+1 u ∩ U n-k+1 u (K) joint to Proposition 4.1 Point 4 for the last equality. This contradicts (6.5).

Sub-case 1.2: θ

By symmetry (see Proposition 4.3), this case can be treated in the same way of case 1.

Case 3: J

This implies that θ m-l v,J = 1 and θ n-k u,J = -1. Using also that J

This implies that ĉn-k u,J > 0 and ĉm-l v,J < 0. This is absurd since s m-l = t n-k .

This contradicts (6.5).

Sub-case 3.3:

From (6.5), there exists K such that J ∈ U m-l+1 v (K) ∩ U n-k+1 u (K) and (6.7)

J→K

We then distinguish several sub-cases: Sub-case 4.2.1:

J→K where we have used the fact that J ∈ U m-l+1 v (K) and Proposition 4.1 Point 2 for the last inequality. This contradicts (6.7).

Sub-case 4.2.2.2:

So we can apply Lemma 5.7 and we get that

By symmetry, this sub-case can be treated in the same way of sub-case 4.2.2.

Sub-case 4.2.4:

J→K . This contradicts (6.7).

7 Convergence result 7.1 Proof of convergence of the modified GFMM This subsection is devoted to the proof of Theorem 3.6.

Proof of Theorem 3.6

The proof is very similar to the one of [4, Theorem 2.5] and just needs some adaptations essentially due to the change in the point 10 of the algorithm. The only point to check is the sub-solution property of the limit [START_REF] Carlini | Convergence of a generalized fast marching method for a non-convex eikonal equation[END_REF]Proposition 6.1]. By contradiction, we assume that there are (x 0 , t 0 ) and ϕ ∈ C 2 such that θ 0ϕ reaches a strict maximum at (x 0 , t 0 ) with θ 0 (x 0 , t 0 ) = ϕ(x 0 , t 0 ) and (7.1) ϕ t (x 0 , t 0 ) = α + c(x 0 , t 0 )|Dϕ(x 0 , t 0 )| with α > 0. Now, the proof depends on the sign of the velocity. In the case c(x 0 , t 0 ) > 0 or c(x 0 , t 0 ) < 0, it suffices to replace [4, Lemma 5.1] by the following lemma (which proof is equivalent) and the proof is exactly the same.

, then for any J ∈ U n-1 (I), we have for ∆x ≤

with the convention that u n-1 J→I = t 0 if θ p J = -1 for 0 ≤ p ≤ n -1). Intuitively, this result comes from the fact that if the front reaches the point I at step n then (in the case where the velocity is positive) it has reached all the points J ∈ V (I) such that θ n-1 J = 1 at a time closed to t n . Moreover, the point J is useful for I as soon as J has been accepted. Remark 7.2 This lemma implies in particular that if the velocity is positive (or negative) then the algorithm presented in Subsection 2.2 is equivalent to the one of [START_REF] Carlini | Convergence of a generalized fast marching method for a non-convex eikonal equation[END_REF].

We now treat the case c(x 0 , t 0 ) = 0. In this case, we have

In particular, we have (θ ε ) * (x ε , t ε ) = 1 for ∆x, ∆t small enough. Indeed, by contradiction, suppose that (θ ε ) * (x ε , t ε ) = -1. Using the fact that (θ ε ) * is upper semi-continuous, we obtain (θ ε ) * = -1 a neighbourhood of (x ε , t ε ). We then deduce that ϕ t (x ε , t ε ) = |Dϕ(x ε , t ε )| = 0 and so

This is absurd.

We now recall the following Lemma which can be found in [4, Lemma 5.3]:

Theorem 8.1 (Heuristic error estimate for local monotone dynamics )

We assume that u ∈ C 2 (Ω 0 ) is a solution of the stationary equation (8.1) such that θ(x, t) = 1 {u(x)>t} -1 {u(x)≤t} is a solution of (1.1). Let us denote by θ ε (x, t), for (x, t) ∈ R N × (0, T ], the numerical solution of (1.1) obtained by the GFMM algorithm with ε = (∆x, ∆t).

Then, for T > 0, there exists a positive constant K T such that

Remark 8.2 In Theorem 8.1, it is possible to assume that u ∈ C 2 only on a neighbourhood of ∂Ω 0 , but for simplicity of presentation and since the proof is formal, we prefer to assume that u ∈ C 2 in all Ω 0 .

Before giving the proof, we need the following lemma whose proof is postponed:

We denote by θ e the solution of such that θ e (x, t) = 1 {u e (x)>t} -1 {u e (x)≤t} . Given a mesh {x I = I∆x, I ∈ Z n }, we define a sequence of discrete increasing time t e n by t e 1 = min{u e (x I ), x I ∈ Ω 0 } t e n = min{u e (x I ) > t e n-1 , x I ∈ Ω 0 } for n ≥ 2.

We assume that u e ∈ C 2 (Ω 0 ) uniformly in e for e small enough, then there exist a discrete velocity ĉn-1,e To prove Theorem 8.1, we also need another version of the comparison principle Theorem 3.4 with weak assumptions on the velocities: Proposition 8.4 (Comparison principle for the θ ε ) Let T > 0. Let two velocities c u ≥ 0 and c v ≥ 0. Given θ 0 u,J (resp. θ 0 v,J ) for all J ∈ Z N and u 0 J→K for all J ∈ U 0 u (K) (resp. v 0 J→K for all J ∈ U 0 v (K)), we assume that t 0 := sup

resp. s 0 := sup

for a given T > 0.

We also assume that the two velocities satisfy for all (x, t) ∈ R