Gabriel R Barrenechea
email: gabriel.barrenechea@strath.ac.uk

AND Lyonell Boulton
email: l.boulton@hw.ac.uk

Nabile Boussa Ïd

FINITE ELEMENT EIGENVALUE ENCLOSURES FOR THE MAXWELL OPERATOR

Keywords: eigenvalue enclosures, Maxwell equation, spectral pollution, finite element method

We propose employing the extension of the Lehmann-Maehly-Goerisch method developed by Zimmermann and Mertins, as a highly effective tool for the pollution-free finite element computation of the eigenfrequencies of the resonant cavity problem on a bounded region. This method gives complementary bounds for the eigenfrequencies which are adjacent to a given parameter t ∈ R. We present a concrete numerical scheme which provides certified enclosures in a suitable asymptotic regime. We illustrate the applicability of this scheme by means of some numerical experiments on benchmark data using Lagrange elements and unstructured meshes.

The framework developed by Zimmermann and Mertins [START_REF] Zimmermann | Variational bounds to eigenvalues of self-adjoint eigenvalue problems with arbitrary spectrum[END_REF] which generalizes the Lehmann-Maehly-Goerisch method [START_REF] Goerisch | Eigenwertschranken für Eigenwertaufgaben mit partiellen Differentialgleichungen[END_REF][START_REF] Goerisch | Eine Verallgemeinerung eines Verfahrens von N. J. Lehmann zur Einschließung von Eigenwerten[END_REF][START_REF] Lehmann | Beiträge zur numerischen Lösung linearer Eigenwertprobleme[END_REF][START_REF] Lehmann | Beiträge zur numerischen Lösung linearer Eigenwertprobleme[END_REF][START_REF] Maehly | Ein neues Verfahren zur gendherten Berechnung der Eigenwerte hermitescher Operatoren[END_REF] (also [START_REF] Weinberger | Variational Methos for Eigenvalue Approximation[END_REF]Chapter 4.11]), is a reliable tool for the numerical computation of bounds for the eigenvalues of linear operators in the spectral pollution regime [START_REF] Behnke | Lower and upper bounds for sloshing frequencies[END_REF][START_REF] Boulton | Eigenvalue enclosures for the MHD operator[END_REF][START_REF] Barrenechea | Eigenvalue Enclosures[END_REF]. In its most basic formulation [START_REF] Davies | Spectral pollution[END_REF][START_REF] Barrenechea | Eigenvalue Enclosures[END_REF][START_REF] Boulton | On the quality of complementary bounds for eigenvalues[END_REF], this framework relies on fixing a parameter t ∈ R and then characterizing the spectrum which is adjacent to t by means of a combination of the Variational Principle with the Spectral Mapping Theorem. In the present paper we show that this formulation can be effectively implemented for computing sharp estimates for the angular frequencies and electromagnetic field phasors of the resonant cavity problem by means of the finite element method.

Let Ω ⊂ R 3 be a polyhedron. Denote by ∂Ω the boundary of this region and by n its outer normal vector. Consider the anisotropic Maxwell eigenvalue problem: find ω ∈ R and (E, H) = 0 such that (1)

     curl E = iωµH curl H = -iω E in Ω E × n = 0 on ∂Ω.
The physical phenomenon of electromagnetic oscillations in a resonator is described by [START_REF] Amrouche | Vector potentials in three-dimensional non-smooth domains[END_REF], assuming that the field phasor satisfies Gauss's law [START_REF] Arnold | Finite element exterior calculus: from hodge theory to numerical stability[END_REF] div( E) = 0 = div(µH) in Ω.

Here and µ, respectively, are the given electric permittivity and magnetic permeability at each point of the resonator. The orthogonal complement in a suitable inner product [START_REF] Birman | The self-adjoint Maxwell operator in arbitrary domains[END_REF] of the solenoidal space (2) is the gradient space. This gradient space has infinite dimension and is part of the kernel of the densely defined linear self-adjoint operator M : D(M) -→ L 2 (Ω) 6 associated to [START_REF] Amrouche | Vector potentials in three-dimensional non-smooth domains[END_REF]. In turns, this means that (1)- [START_REF] Arnold | Finite element exterior calculus: from hodge theory to numerical stability[END_REF] and the unrestricted problem [START_REF] Amrouche | Vector potentials in three-dimensional non-smooth domains[END_REF], have exactly the same non-zero spectrum and exactly the same eigenvectors orthogonal to the kernel. For general data, the numerical computation of ω by means of the finite element method is extremely challenging, due to a combination of variational collapse (M is strongly indefinite) and the fact that finite element bases seldom satisfy the ansatz [START_REF] Arnold | Finite element exterior calculus: from hodge theory to numerical stability[END_REF].

Several ingenious methods for the finite element treatment of the eigenproblem (1)-( 2) have been developed in the recent past. Perhaps the most effective among these methods [START_REF] Boffi | Computational models of electromagnetic resonators: analysis of edge element approximation[END_REF][START_REF] Boffi | Finite element approximation of eigenvalue problems[END_REF] consists in re-writing the spectral problem associated to M 2 in a mixed form and employing edge elements. This turns out to be linked to deep mathematical ideas on the rigorous treatment of finite elements [START_REF] Arnold | Finite element exterior calculus: from hodge theory to numerical stability[END_REF] and it is at the core of an elegant geometrical framework. Other approaches include, [START_REF] Bramble | The approximation of the Maxwell eigenvalue problem using a least-squares method[END_REF] combining nodal elements with a least squares formulation of (1)-(2) re-written in weak form, [START_REF] Buffa | Solving electromagnetic eigenvalue problems in polyhedral domains[END_REF] employing continuous finite element spaces of Taylor-Hood-type by coupling (1) with (2) via a Lagrange multiplier, and [START_REF] Bonito | Approximation of the eigenvalue problem for the time harmonic Maxwell system by continuous Lagrange finite elements[END_REF] enhancing the divergence of the electric field in a fractional order negative Sobolev norm.

In spite of the fact that some of these techniques are convergent, unfortunately, none of them provides a priori guaranteed one-sided bounds for the exact eigenfrequencies. In turns, detecting the presence of a spectral cluster (or even detecting multiplicities) is extremely difficult. Below we argue that the most basic formulation of the pollution-free technique described in [START_REF] Zimmermann | Variational bounds to eigenvalues of self-adjoint eigenvalue problems with arbitrary spectrum[END_REF] can be successfully implemented for determining certified upper and lower bounds for the eigenfrequencies and corresponding approximated field phasors of [START_REF] Amrouche | Vector potentials in three-dimensional non-smooth domains[END_REF]. Remarkably the classical family of nodal finite elements renders sharp numerical approximations.

In Section 2 we fix the rigorous setting of the self-adjoint operator M and set our concrete assumptions on the data of the problem. For these concrete assumptions we consider both a region Ω with and without cylindrical symmetries, generally non-convex and not even Lipschitz. In Section 3 we describe the finite element realization of the computation of complementary eigenvalue bounds. Based on this realization, in Section 4 an algorithm providing certified eigenvalue enclosures in a given interval is presented and analyzed. This algorithm is then implemented and its results are reported in Sections 5-7.

Abstract setting of the Maxwell eigenvalue problem

2.1. Concrete assumptions on the data. The concrete assumptions on the data of equation ( 1) made below are as follows. The polyhedron Ω ⊂ R 3 will always be open, bounded and simply connected. The permittivities will always be such that

(3) , 1 , µ, 1 µ ∈ L ∞ (Ω).
Without further mention, the non-zero spectrum of M will be assumed to be purely discrete and it does not accumulate at ω = 0. This hypothesis is verified, for example, whenever Ω is a polyhedron with a Lipschitz boundary, [START_REF] Monk | Finite element methods for Maxwell's equations[END_REF]Corollary 3.49] and [START_REF] Birman | The self-adjoint Maxwell operator in arbitrary domains[END_REF]Lemma 1.3]. A more systematic analysis of the spectral properties of M on more general regions Ω is being carried out elsewhere [START_REF] Barrenechea | Some remarks on the spectral properties of the maxwell operator on rough domains and domains with symmetries[END_REF].

2.2.

The self-adjoint Maxwell operator. We follow closely [START_REF] Birman | The self-adjoint Maxwell operator in arbitrary domains[END_REF]. Let

H(curl; Ω) = u ∈ L 2 (Ω) 3 : curl u ∈ L 2 (Ω) 3 H 0 (curl; Ω) = {u ∈ H(curl; Ω) : Ω curl u • v = Ω u • curl v ∀v ∈ H(curl; Ω)}.
The linear space H(curl; Ω) becomes a Hilbert space for the norm

u curl,Ω = u 2 0,Ω + curl u 2 0,Ω 1/2 ,
where

v 0,Ω = Ω |v| 2 1/2
is the corresponding norm of L 2 (Ω) 3 , where the closure is in the norm • curl,Ω .

H 0 (curl; Ω) 3 = C ∞ 0 (Ω)
A domain of self-adjointness of the operator associated to (1) for = µ = 1 is

D 1 = H 0 (curl; Ω) × H(curl; Ω) ⊂ L 2 (Ω) 6
and its action is given by

M 1 = 0 i curl -i curl 0 : D 1 -→ L 2 (Ω) 6 . Let P = 1/2 I 3×3 0 0 µ 1/2 I 3×3 .
Condition (3) ensures that P : L 2 (Ω) 6 -→ L 2 (Ω) 6 is bounded and invertible. Moreover,

ω, E H ∈ R × D 1
is a solution of (1), if and only if

Ẽ H = P E H
is a solution of

P -1 M 1 P -1 Ẽ H = ω Ẽ H .
Therefore M = P -1 M 1 P -1 on D(M) = PD 1 is the self-adjoint operator associated to [START_REF] Amrouche | Vector potentials in three-dimensional non-smooth domains[END_REF].

As M anticommutes with complex conjugation, the spectrum is symmetric with respect to 0. Moreover, ker(M) is infinite dimensional, because it always contains the gradient space, see [START_REF] Birman | The self-adjoint Maxwell operator in arbitrary domains[END_REF].

Isotropic cylindrical symmetries.

If Ω = Ω × (0, π) for Ω ⊂ R 2 an open simply connected polygon, then (1) decouples by separating the variables for = µ = 1. In turns, a non-zero ω is an eigenvalue of M 1 , if and only if either ω 2 = λ 2 where λ 2 is a Dirichlet eigenvalue of the Laplacian in Ω, or ω 2 = ν 2 + ρ 2 where ν 2 is a non-zero Neumann eigenvalue of the Laplacian in Ω and ρ ∈ N.

The Neumann problem can be re-written as (ν = ω)

     curl E = iωH curl H = -iωE in Ω E • t = 0 on ∂ Ω , for ω, E H ∈ R × ( D1 \ {0}). (5)
Here

E = E 1 E 2 , curl E = ∂ x E 2 -∂ y E 1 , curl H = ∂ y H -∂ x H , t is the unit tangent to ∂ Ω and D1 = u ∈ L 2 (Ω) 2 : curl u ∈ L 2 (Ω) and u • t = 0 × u ∈ L 2 (Ω) : curl u ∈ L 2 (Ω) 2 .
This two-dimensional Maxwell problem exhibits all the complications concerning spectral pollution as its three-dimensional counterpart.

We denote by M : D -→ L 2 ( Ω) 3 the self-adjoint operator associated to [START_REF] Behnke | Lower and upper bounds for sloshing frequencies[END_REF]. This operator has often been employed for tests which can then be validated against numerical calculations for the original Neumann Laplacian via the Galerkin method, [START_REF] Dauge | Computations for Maxwell equations for the approximation of highly singular solutions[END_REF]. Note that the latter is a semi-definite operator with a compact resolvent, so it does not exhibit spectral pollution.

Finite element computation of the eigenvalue bounds

The basic setting of the general method proposed in [START_REF] Zimmermann | Variational bounds to eigenvalues of self-adjoint eigenvalue problems with arbitrary spectrum[END_REF] is achieved by deriving eigenvalue bounds directly from [32, Theorem 1.1], as described in [START_REF] Davies | Spectral pollution[END_REF]Section 6] and [START_REF] Barrenechea | Eigenvalue Enclosures[END_REF]. We will see next that, from this setting, a general finite element scheme for computing guaranteed bounds for the eigenvalues of M which are in the vicinity of a given non-zero t ∈ R can be established.

3.1. Formulation of the weak problem and eigenvalue bounds. Let {T h } h>0 be a family of shape-regular [START_REF] Ern | Theory and practice of finite elements[END_REF] triangulations of Ω, where the elements K ∈ T h are simplexes with diameter h K and h = max K∈T h h K . For r ≥ 1, let

V r h = {v h ∈ C 0 (Ω) 3 : v h | K ∈ P r (K) 3 ∀K ∈ T h } V r h,0 = {v h ∈ V r h : v h × n = 0 on ∂Ω}. Then (6) L ≡ L h = V r h,0 × V r h ⊂ D 1 . For t ∈ R, let m p t : D 1 × D 1 -→ C be given by m 1 t E H , F G = Ω (M 1 -tP 2 ) E H • F G m 2 t E H , F G = Ω (P -1 M 1 -tP) E H • (P -1 M 1 -tP) F G
The following weak eigenvalue problem [START_REF] Zimmermann | Variational bounds to eigenvalues of self-adjoint eigenvalue problems with arbitrary spectrum[END_REF][START_REF] Davies | Spectral pollution[END_REF][START_REF] Barrenechea | Eigenvalue Enclosures[END_REF] plays a central role below:

(7) find τ, E H ∈ R × (L \ {0}) such that m 1 t E H , F G = τ m 2 t E H , F G ∀ F G ∈ L.
Let m ± (t) ≡ m ± (t, h) be the number of negative and positive eigenvalues of (7), respectively. Let τ

± j (t) ≡ τ ± j (t, h), τ - 1 (t) ≤ . . . ≤ τ -(t) m -(t)
be the negative eigenvalues of ( 7) and

τ + m + (t) (t) ≤ . . . ≤ τ + 1 (t) be the positive eigenvalues of (7), if they exist at all. Let ρ ± j (t, h) = t + 1 τ ± j (t)
.

As we will see next, the latter quantities provide bounds for the spectrum of M in the vicinity of t. By counting multiplicities, let

. . . ≤ ν - 2 (t) ≤ ν - 1 (t) < t < ν + 1 (t) ≤ ν + 2 (t) ≤ .
. . be the eigenvalues of M which are adjacent to t. That is ν - j (t) is the j-th eigenvalue strictly to the left of t and ν + j (t) is the j-th eigenvalue strictly to the right of t.

The following crucial statement is a direct consequence of [START_REF] Zimmermann | Variational bounds to eigenvalues of self-adjoint eigenvalue problems with arbitrary spectrum[END_REF]Theorem 2.4] or [4, Corollary 7] (see also [START_REF] Davies | Spectral pollution[END_REF]Theorem 11]).

Theorem 1. Let t ∈ R. Then ρ - j (t, h) ≤ ν - j (t) ∀j = 1, . . . , m -(t) and ν + j (t) ≤ ρ + j (t, h) ∀j = 1, . . . , m + (t).
Remark 1. In the case of the lower-dimensional Maxwell operator M1 , the finite element spaces on a corresponding triangulation T h of Ω are chosen as

L h = u h v h ∈ C 0 Ω 2+1 : u h v h K ∈ P r (K) 2+1 ∀K ∈ T h and u h • t = 0 on ∂ Ω .
The weak problem analogous to [START_REF] Bernhard | On a theorem of Danskin with an application to a theorem of von Neumann-Sion[END_REF] and a corresponding version of Theorem 1 (and further statements below) are formulated by substituting m p t with the corresponding lower-dimensional forms.

Convergence of the eigenvalue bounds.

According to [START_REF] Barrenechea | Eigenvalue Enclosures[END_REF]Theorem 12], if L captures an eigenspace of M within a certain order of precision O(ε) for small ε, then the eigenvalue bounds found in Theorem 1 are within O(ε 2 ). We now show a consequence of this statement in the present setting.

Consider an open bounded segment J ⊂ R, such that 0 ∈ J. Denote by E J the eigenspace associated to this segment and assume that t ∈ J. Here and elsewhere the relevant set where the indices j move is

F ± J (t) = {j ∈ N : ν ± j (t) ∈ J}. Theorem 2. Let r ∈ N be fixed. Then lim h→0 ρ ± j (t, h) -ν ± j (t) = 0 ∀j ∈ F ± J (t).
If in addition P -1 E J ⊆ H r+1 (Ω) 6 , then there exist

C ± t ≡ C ± t (r) > 0 such that (8) ρ ± j (t, h) -ν ± j (t) ≤ C ± t h 2r ∀j ∈ F ± J (t) for h sufficiently small.
Proof. By combining [START_REF] Monk | Finite element methods for Maxwell's equations[END_REF]Theorem 3.26] with (4) and standard interpolation estimates (cf. [START_REF] Ern | Theory and practice of finite elements[END_REF]), it follows that for any

F G ∈ D 1 there exists F h G h ∈ L h such that (9) lim h→0 F -F h curl,Ω + G -G h curl,Ω = 0 .
Since P is a bounded operator, then for any

F G = P F G ∈ D(M),
we have

(10) lim h→0 M F -F h G -Gh 0,Ω + F -F h G -Gh 0,Ω = 0 where F h Gh = P F h G h ∈ D(M).
In turns, this is exactly the hypothesis required in [4, Theorem 12] which ensures the claimed statement. Let I r,h denote the interpolation operator associated to the finite element spaces V r h (cf. [START_REF] Ern | Theory and practice of finite elements[END_REF]) and let

F h G h = I r,h F G . If F G ∈ E J ⊂ H r+1 (Ω) 6 , then (11)
F -F h G -G h curl,Ω ≤ c(r)h r F G r+1,Ω , so that (12) M F -F h G -Gh 0,Ω + F -F h G -Gh 0,Ω ≤ Ch r
where C > 0 is a constant independent of h. This is precisely the condition [4, (35)]. Thus, [4, Theorem 12] ensures the claimed statement.

3.3.

Eigenfunctions. The statement established in [4, Corollary 13], provides an insight on how the eigenspace E J in the framework of Theorem 2 is also captured by the trial subspaces L as h → 0. Let

dist 1 [(F , G), E] = inf   X Y   ∈E F -X G -Y curl,Ω
be the Hausdorff distance between a given vector

F G ∈ D 1 and E ⊆ D 1 .
Denote by

F ± j (t, h) G ± j (t, h) ∈ L h
the eigenvectors of (7) associated to τ ± j (t) respectively and assume that

F ± j (t, h) G ± j (t, h) 0,Ω = 1.
Then, the following result concerning approximation of eigenspaces can be stated.

Theorem 3. Let r ∈ N be fixed. Then,

lim h→0 dist 1 [(F ± j (t, h), G ± j (t, h)), E J ] = 0.
If in addition P -1 E J ⊆ H r+1 (Ω) 6 , then there exist

C ± t (r) > 0 such that dist 1 [(F ± j (t, h), G ± j (t, h)), E J ] ≤ C ± t (r)h r for h sufficiently small.
Proof. Proceed as in the proof of Theorem 2 in order to verify the hypotheses of [4, Corollary 13].

Convergence of the eigenvalue bounds in Theorem 1 are therefore ensured, in spite of the fact that L are spaces of nodal finite elements with no particular mesh structure. Note that this is guaranteed, even in the case where and µ are rough, however, since P -1 E J ⊆ H r+1 (Ω) 6 unless these coefficients are smooth themselves, an estimate on the convergence rate in this situation is beyond the scope of Theorem 3. For a highly heterogeneous medium, a deterioration of the convergence speed is to be expected.

We remark that the above analysis relies on the regularity of the eigenspaces associated to the interval J only. Thus, for non-convex Ω, this allows the possibility of approximating eigenvalues associated to regular eigenfunctions with high accuracy, if some a priori information about their location is at hand.

A certified numerical strategy

Let us now describe a procedure which, in an asymptotic regime, renders small intervals which are guaranteed to contain spectral points. Convergence will be derived from Theorem 2.

Denote by 0 < t up < t low the corresponding parameters t in the weak problem [START_REF] Bernhard | On a theorem of Danskin with an application to a theorem of von Neumann-Sion[END_REF], which are set for computing ρ - j (t low , h) (lower bounds) and ρ + j (t up , h) (upper bounds) in the segment (t up , t low ). The scheme described next aims at finding intervals of enclosure for the eigenvalues of M which lie in this segment, for a prescribed tolerance set by the parameter δ > 0. According to Lemma 4 below, these intervals will be certified in the regime δ → 0.

Procedure 1.

Input.

-Initial t up > 0.

-Initial t low > t up such that t low -t up is fairly large.

-A sub-family F of finite element spaces L h as in [START_REF] Behnke | Bounds for eigenvalues with the use of finite elements[END_REF], dense as h → 0.

-A tolerance δ > 0 fairly small compared with t low -t up . Output.

-A prediction m(δ) ∈ N of Tr 1 (tup,t low ) (M).

-Predictions ω ± j,δ of the endpoints of enclosures for the eigenvalues in σ(M) ∩ (t up , t low ), such that 0 < ω + j,δ -ω - j,δ < δ for j = 1, . . . , m(δ).

Steps. a) Set initial L h ∈ F. b) While ρ + j,h -ρ - j,h ≥ δ or ρ - j,h > ρ + j,h for some j = 1, . . . , m, do c) -e). c) Compute ρ + j,h = ρ + j (t up , h) for j = 1, . . . , mup
where mup is such that ρ + mup,h < t low and

ρ + mup+1 (t up , h) ≥ t low . d) Compute ρ - mlow -k+1,h = ρ - k (t low , h) for k = 1, . . . , mlow
where mlow is such that ρ - mlow ,h > t up and ρ - mlow +1 (t low , h) ≤ t up . e) If mlow = mup , decrease h, set new L h ∈ F and go back to c). Otherwise set m = mlow = mup , decrease h, set new L h ∈ F and continue from b). f ) Exit with m(δ) = m and ω ± j,δ = ρ ± j,h for j = 1, . . . , m. Assume that (t up , t low ) ∩ σ(M) = {ω k+1 , . . . , ω k+m } where m = Tr 1 (tup,t low ) (M) > 0 and k ≥ 0.

A priori, an interval (ω - j,δ , ω + j,δ ) obtained as the output of Procedure 1 is not guaranteed to have a non-empty intersection with the spectrum of M or in fact include precisely the eigenvalue ω k+j . However, as it is established by the following lemma, the latter is certainly true for δ small enough. Lemma 4. There exist t 0 > 0 and δ 0 > 0, ensuring all the next items for all t low ≥ t 0 and δ < δ 0 .

a) The conditional loop in Procedure 1 always exits in the regime

h → 0. b) m(δ) = m. c) ω - j,δ ≤ ω k+j ≤ ω + j,δ for all j = 1, . . . , m.
Proof. Set t 0 > ω + 1 (t up ) sufficiently large, ensuring m = 0 for any t low ≥ t 0 . Since ν + j (t up ) = ω k+j = ν - m-j+1 (t low ) for all j = 1, . . . , m, Theorem 2 alongside with the assumption on F, ensures the existence of ρ ± j,h in Procedure 1-c) and d), for all j = 1, . . . , m whenever h is small enough. Moreover ρ + j,h ↓ ω k+j and ρ - j,h ↑ ω k+j as h → 0 as needed.

If the eigenfunctions of M lie in H r+1 (Ω) 6 , then

ρ + j,h -ρ - j,h = O(h 2r
). This means that the exit rate of the conditional loop in Procedure 1 is also O(h 2r ) as h → 0.

Observe that in the above procedure, a good choice of t up and t low has a noticeable impact in performance. See Section 6.3. The results of the recent manuscript [START_REF] Boulton | On the quality of complementary bounds for eigenvalues[END_REF], suggest 1 that the constants involved in the estimates of Theorem 2 are of order |t -ν ± 1 (t)| -1 . Table 6 strongly suggest that the accuracy improves significantly, as t up ↓ ν - 1 (t up ) and t low ↑ ν + 1 (t low ). In the subsequent sections we proceed to illustrate the practical applicability of the ideas discussed above by means of several examples. Two canonical references for benchmarks on the Maxwell eigenvalue problem are [START_REF] Dauge | Computations for Maxwell equations for the approximation of highly singular solutions[END_REF] and [START_REF] Boffi | Computational models of electromagnetic resonators: analysis of edge element approximation[END_REF]. We validate some of our numerical bounds against these benchmarks. Everywhere below we will write ω ± j ≡ ω ± j,δ (see Procedure 1) where δ might or might not be specified. In the latter case, we have taken its value small enough to ensure the reported accuracy. 1 An upper bound is provided in [4, Corollary 11] and the value -1 seems to be the right exponent.

ω + k -ω - k .
Horizontal axis: eigenvalue index k (not counting multiplicity). Here we consider elements of order r = 1, 3, 5 on unstructured uniform meshes rendering roughly the same number of degrees of freedom. For each r, we have used exactly the same trial subspace L h for all the eigenvalues.

We consider constant = µ = 1 in sections 5 and 6, and = 1 with jumps in Section 7.

Convex domains

The eigenfunctions of (1) and ( 5) are regular in the interior of a convex domain, see [START_REF] Monk | Finite element methods for Maxwell's equations[END_REF][START_REF] Amrouche | Vector potentials in three-dimensional non-smooth domains[END_REF]. In this, the best possible case scenario, the method of sections 3 and 4 achieves an optimal order of convergence for finite elements.

Without further mention, the following convention will be in place here and everywhere below. The index k for eigenvalues and eigenvalue bounds will be used, whenever multiplicities are not counted. Otherwise the index j (as in previous sections) will be used.

The square. Let

Ω ≡ Ωsqr = (0, π) 2 ⊂ R 2 . The eigenvalues of M are ω = ± √ l 2 + m 2 for l, m ∈ N ∪ {0}. Pick t up = 1 4 ω k-1 + 3 4 ω k and t low = 3 4 ω k + 1 4 ω k+1
to machine precision. In our first experiment we have computed enclosure widths ω + k -ω - k for k = 1, . . . , 100 and r = 1, 3, 5. We have chosen h = h(r) such that the corresponding trial subspaces have roughly the same dimension ≈ 61K. We have then found all the eigenvalue bounds for a fixed r, from exactly the same trial subspace. Figure 1 shows the outcomes of this experiment. In the graph, we have excluded enclosures with size above 10 -1 .

As it is natural to expect, for a fixed L h , the accuracy deteriorates as the eigenvalue counting number increases: high energy eigenfunctions have more oscillations, so their approximation requires a higher number of degrees of freedom. The accuracy increases with the polynomial order. The first 100 eigenvalues are approximated fairly accurately (note that ω (k=100) = √ 261 with polynomial order r = 5).

The slashed cube.

Let Ω ≡ Ω sla = (0, π) 3 \ T ⊂ R 3 , where T is the closed tetrahedron with vertices (0, 0, 0), (π/2, 0, 0), (0, π/2, 0) and (0, 0, π/2). This domain does not have symmetries allowing a reduction into two-dimensions.

In our first experiment on this region, we determine benchmark eigenvalue enclosures for [START_REF] Amrouche | Vector potentials in three-dimensional non-smooth domains[END_REF]. The table in Figure 2 shows the outcomes of implementing a numerical scheme based on Procedure 1. We have iterated our algorithm for three fixed choices of t up and t low (third and fourth columns), with δ = 10 -2 . We have picked the family of meshes so that no more than five iterations were required to achieve the needed accuracy. We have chosen trial spaces made out of Lagrange elements of order r = 3. All the final eigenvalue enclosures have a length of at most 2 × 10 -3 . The mesh used in the last iteration is depicted on the left of Figure 2. The parameter l in this table counts the number of eigenvalues to the right of t up or to the left of t low , respectively.

From the table, it is natural to conjecture that there is a cluster of eigenvalues at the bottom of the positive spectrum near √ 2. The latter is the first positive eigenvalue for Ω ≡ Ω cbe = (0, π) 3 , which is of multiplicity 3 for that region. See [4, Section 5.1]. As we deform Ω cbe into Ω sla , it appears that this eigenvalue splits into a single eigenvalue at the bottom of the spectrum and a seemingly double eigenvalue slightly above it. Another cluster occurs at ω 4 and ω 5 with strong indication that this is a double eigenvalue. This pair is near √ 3, the second eigenvalue for Ω cbe , which is indeed double. The next eigenvalues for Ω cbe are 2 and √ 5 with total multiplicity 5. We conjecture that ω j for j = 6, . . . , 10 are indeed perturbations of these eigenvalues.

For our second experiment on the region Ω sla , we have estimated numerically the electromagnetic fields corresponding to index up to j = 6. The purpose of the experiment is to set benchmarks for the eigenfunctions on Ω sla and simultaneously illustrate Theorem 3. In Figure 8 we depict the density of electric and magnetic fields, |E| and |H| both re-scaled to having maximum equal to 1. We also show arrows pointing towards the direction of these fields on ∂Ω sla . The mesh employed for these calculations is the one shown in Figure 2.

It is remarkable that for both experiments on Ω sla , a reasonable accuracy has been achieved even for the fairly coarse mesh depicted.

Non-convex domains

The numerical approximation of the eigenfrequencies and electromagnetic fields in the resonant cavity is known to be extremely challenging when the domain is not convex. The main reason for this is the fact that the electromagnetic field might have a singularity and a low degree of regularity at re-entrant corners. See for example the discussion after [29, Lemma 3.56] and references therein.

In some of the examples of this section we consider a mesh adapted to the geometry of the region. However, we do not pursue any specialized mesh refinement strategy. We show below that, even in the case where there is poor approximation due to low regularity of the eigenspace, the scheme in Procedure 1 provides a stable approximation.

6.1.

A re-entrant corner in two dimensions. The region

Ω ≡ ΩL = (0, π) 2 \ [0, π/2] 2 ⊂ R 2
is a classical benchmark domain both for the Maxwell and the Helmholtz problems, and it has been extensively examined in the past. Numerical computations for the eigenvalues of M, via an implementation based on a mixed formulation of ( 5) and edge finite elements, were reported in [10, Table 5]. See also [START_REF] Dauge | Computations for Maxwell equations for the approximation of highly singular solutions[END_REF]. We now show estimation of sharp enclosures for these eigenvalues by means of the method described in sections 5 and 6.

For the next set of experiments we consider unstructured triangulations of the domain, refined around the re-entrant corner (π/2, π/2) ∈ ∂ ΩL . The polynomial order is set to r = 3. Figures 3,4 and 9 summarize our findings.

We produced the table in Figure 3 by implementing Procedure 1 in the same fashion as for the case of Ω sla described previously. For comparison, in the second column of this table we have included the benchmark eigenvalue estimations found in [START_REF] Boffi | Computational models of electromagnetic resonators: analysis of edge element approximation[END_REF] and [START_REF] Dauge | Computations for Maxwell equations for the approximation of highly singular solutions[END_REF]. Note that some of the approximations made by means of the mixed formulation are lower bounds of the true eigenvalues, and some (see the row for j = 9 in the table) are upper bounds. This confirms that the latter approach is in general un-hierarchical as previously suggested in the literature.

From the third column of the table, it is clear that the accuracy depends on the regularity of the corresponding eigenspaces. The eigenfunctions associated to ω = 2 and ω = √ 8 are found by the translation and gluing in an appropriate fashion, of eigenfunctions in the sub-region Ω = (0, π/2) 2 ⊂ ΩL . These eigenfunctions are smooth in the interior of ΩL and they achieve a maximum order of convergence. Here Procedure 1 has been implemented on Lagrange elements of order 3. The final mesh shown on the right has a number of DOF=56055. The mesh has a maximum element size h = 0.1 and has been refined at (π/2, π/2) ∈ ∂ ΩL . For comparison on the second column we include the eigenvalue estimations found in [START_REF] Boffi | Computational models of electromagnetic resonators: analysis of edge element approximation[END_REF] and [START_REF] Dauge | Computations for Maxwell equations for the approximation of highly singular solutions[END_REF].

The eigenfunctions associated to ω 1 and ω 2 , on the other hand, are singular at the re-entrant corner. Moreover, the electric field component for index j = 1 is known to be outside H 1 (Ω L ) 2 while that for index j = 2 is in H 1 ( ΩL ) 2 . This explains the significant gain in accuracy in the calculation of ω 2 with respect to the one for ω 1 .

Here the computation of the eigenvalues with smooth eigenspace (j = 3, 4 or 7) is less accurate than that for the index j = 2, because of the mesh chosen.

Figure 4 depicts in log-log scale residuals versus maximum element size. We have considered here Lagrange elements of order r = 3 and r = 5. The hierarchy of meshes (not shown) was chosen unstructured, but with an uniform distribution of nodes. Since the eigenfunctions associated to ω 1 and ω 2 have a limited regularity, then there is no noticeable improvement on the convergence order as r changes from 3 to 5. Since the third eigenfunction is smooth, it does obey the estimate [START_REF] Birman | The self-adjoint Maxwell operator in arbitrary domains[END_REF].

Benchmark approximated eigenfunctions are depicted in Figure 9. The mesh employed to produce these graphs is the one shown on the right of Figure 3. As some of the electric fields have a singularity at (π/2, π/2) ∈ ∂ ΩL we have re-scaled each individual plot to a range in the interval [0, 1]. 6.2. The Fichera domain. In this next experiment we consider the region

Ω ≡ Ω F = (0, π) 3 \ [0, π/2] 3 ⊂ R 3 .
See also [4, §5.2] for related results.

The table on right of Figure 5 shows numerical estimation of the first 15 positive eigenvalues. Here we have fixed t up = 0.1 and t low = 2.8. We have considered meshes refined along the re-entrant edges. The final mesh is shown on the left side of Figure 5. We have stopped the algorithm when the tolerance δ = 0.03 has been achieved. However, note that the accuracy is much higher for the indices j = 2, 3, 9, 10, 11, 13, 14, 15. Figure 10 includes the corresponding approximated eigenfunctions. The mesh employed for this calculation is the same as that of Figure 5.

6.3.

A non-Lipschitz domain. As mentioned earlier, for a single trial space L, the accuracy of the eigenvalue bounds established in Theorem 1 depends on the position of t relative to adjacent components of the spectrum. In this experiment we demonstrate that this dependence might vary significantly with t. The numerical evidence below suggests that a good choice of t up and t low plays a major role in the design of efficient algorithms for eigenvalue calculation based on this method.

Let Ω ≡ Ωcut = (0, π) 2 \ S for S = [π/2, π] × {π/2}. Benchmarks [START_REF] Dauge | Computations for Maxwell equations for the approximation of highly singular solutions[END_REF] on the eigenvalues of [START_REF] Behnke | Lower and upper bounds for sloshing frequencies[END_REF] The eigenfunctions associated to ω 2 , ω 4 and ω 5 are smooth, as they are also eigenfunctions on Ωsqr . On the other hand, ω 1 and ω 3 correspond to singular eigenfunctions. Standard nodal elements are completely unsuitable for the computation of these eigenvalues, even with a significant refinement of the mesh on S. The table in Figure 6 shows computation of ω ± 3 on a mesh that is increasingly refined at S with a factor RF for two pairs of choices of t up and t low . Here h = 0.1 and we consider Lagrange elements of order r = 1. The choice of t up and t low further from ω 3 , even with the very coarse mesh, provides a sharper estimate of ω ± 3 than the other choices even with a finer mesh.

(l = 1 ω - 3 ) (l = 3 ω - 3 ) (l = 1 ω + 3 ) (l = 3 ω + 3 ) 1

The transmission problem

In this final example, we consider a non-constant electric permittivity. Let 7. Enclosures for the first 10 positive eigenvalues of M for the transmission problem (Section 7). For comparison, on the second column we include the upper bounds found in [START_REF] Dauge | Computations for Maxwell equations for the approximation of highly singular solutions[END_REF]. Here the trial subspace is made out of Lagrange elements of order 1, t up = 10 -9 and t low = 11.74. The mesh employed was constructed in an unstructured fashion in the four sub-domains Ωsqr,l . The maximum element size is set to h = .01 and the total number of DOF=399720. x ∈ Ω sqr,3 ∪ Ω sqr,4 .

Ω sqr,1 = 0, π 2 × 0, π 2 Ω sqr,2 = π 2 , π × π 2 , π Ω sqr,3 = π 2 , π × 0, π 2
Numerical estimations of the eigenvalues of M on Ω ≡ Ωsqr for this data were found in [START_REF] Dauge | Computations for Maxwell equations for the approximation of highly singular solutions[END_REF].

We have set the experiment reported in Figure 7, on a family of meshes (not shown), which is unstructured but of equal maximum element sizes in each one of the subdomains Ωsqr,l . We implemented Procedure 1 as discussed previously, with fix t up = 10 -9 and t low = 11.74. For comparison, in the second column of the table we have included the benchmark upper bounds from [START_REF] Dauge | Computations for Maxwell equations for the approximation of highly singular solutions[END_REF].

As we pointed out in sections 5 and 6, accuracy depends on the regularity of the corresponding eigenspace. Moreover, finding conclusive lower bounds for the ninth and tenth eigenvalues turns out to be extremely expensive, if t low ≈ 3.5. Observe that, from the reproduced values in the second column of the table, these two eigenvalues form a cluster of multiplicity 2. It seems that in fact they are part of a larger cluster. The resulting narrow gap from this cluster seems to be the cause of the dramatic deterioration in accuracy. Recall the observations made in Section 6.3.

The data has a natural symmetry with respect to the diagonals of Ωsqr . Four types of eigenvectors arise from these symmetries, and the analytical problem reduces to four different eigen-problems which give rise to degenerate eigenspaces. As we are not considering a mesh that completely respects these symmetries, the multiplicities arising from them are not shown completely in the numerics.

In order to find reasonable bounds for ω 9 and ω 10 , we had to resource to exploiting the fact that ρ - j (t, h) is locally non-increasing in t, and it respects ordering in j. An analytical proof of this property is achieved by extending to the indefinite case the results of [12, §3], but in the present context we have examined them only from a numerical perspective. Note that, when t low is near to cross an eigenvalue, ρ - j (t low , h) jumps. These jumps appear to be small (respecting the order of the j) as long as the subspace captures well the eigenvectors. This effect will disappear eventually as we increase t low further, due to the fact that L is finite-dimensional.

In our experiments, we have determined that t = t low ≈ 11.74 is near to optimal for the trial subspaces employed. Note that t low = 11.74 gives 85 eigenvalues in the segment (10 -9 , 11.74) for these trial subspaces.

Figure 1 .

 1 Figure 1. Semi-log graph associated to Ωsqr . Vertical axis:ω + k -ω - k .Horizontal axis: eigenvalue index k (not counting multiplicity). Here we consider elements of order r = 1, 3, 5 on unstructured uniform meshes rendering roughly the same number of degrees of freedom. For each r, we have used exactly the same trial subspace L h for all the eigenvalues.

Figure 2 .

 2 Figure 2. Benchmark spectral approximation for Ω sla . In the table we compute interval of enclosure for the first 10 eigenvalues, by means of an implementation of Procedure 1. The trial spaces are made of Lagrange elements of order r = 3. The final mesh is the one shown on the right side. Total number of DOF=117102.

Figure 3 .

 3 Figure 3. Enclosures for the first 10 positive eigenvalues of M on ΩL . The next eigenvalue is above 3.7. Here Procedure 1 has been implemented on Lagrange elements of order 3. The final mesh shown on the right has a number of DOF=56055. The mesh has a maximum element size h = 0.1 and has been refined at (π/2, π/2) ∈ ∂ ΩL .For comparison on the second column we include the eigenvalue estimations found in[START_REF] Boffi | Computational models of electromagnetic resonators: analysis of edge element approximation[END_REF] and[START_REF] Dauge | Computations for Maxwell equations for the approximation of highly singular solutions[END_REF].

Figure 4 .

 4 Figure 4. Compared order of approximation for different eigenvalues in the region ΩL . The log-log plot shows residual versus maximum element size h for the calculation of enclosures for ω j where j = 1, 2, 3 and L is generated by Lagrange elements of order r = 3 and r = 5. Note that (E, H) ∈ H s (Ω L ) 3 for j = 1 and s = 1, and for j = 2 and s = 1.5. On the other hand, for j = 3 we have (E, H) smooth, as the eigenfunction is also solution of (1) on a square of side π/2.

Figure 5 .

 5 Figure 5. Spectral enclosures for the Fichera domain Ω F . Here we have fixed t up = 0.1 and t low = 2.8. The final mesh in the iteration is shown on the left side. Its number of DOF=347460. RF DOF t low = 1.95 t low = 2.05 t up = 1.05 t up = 0.7(l = 1 ω - 3 ) (l = 3 ω - 3 ) (l = 1 ω + 3 ) (l = 3 ω + 3 )1 4143 1.24764 1.26640 1.50395 1.3436 0.1 9648 1.25029 1.26830 1.49282 1.3336 0.01 74226 1.25063 1.26846 1.48899 1.3274

Figure 8 .

 8 Figure 8. The first six eigenfunctions on Ω sla for the first six positive eigenvalues. Densities |E| (top) and |H| (bottom). Corresponding arrow fields E (red) and H (blue) on ∂Ω sla .

Figure 9 .

 9 Figure 9. Eigenfunctions on ΩL associated to the first eight positive eigenvalues. Densities |E| (top) and |H| (bottom). Corresponding arrow fields E. We have re-scaled each individual density to have as maximum the value 1.

Figure 10 .

 10 Figure 10. The first six eigenfunctions on Ω F for the first six positive eigenvalues. Densities |E| (top) and |H| (bottom). Corresponding arrow fields E (red) and H (blue) on ∂Ω F .

  are found by means of solving numerically the corresponding Neumann Laplacian problem.The first seven positive eigenvalues are

	j	ω j	+ -
	1	1.1 441 298
	2 1.54 391 228 3 1.54 392 233
	4 5 6	2.0 815 690 2.0 820 796 2.0 820 796
	7 8	2.2 348 180 2.2 348 187
	9 2.32 679 547
	10 2.33 250 044 11 2.33 255 066
	12	2. 400 375
	13 2.60 366 023 14 2.605 98 62 15 2.605 97 65

ω 1 ≈ 0.647375015, ω 2 = 1, ω 3 ≈ 1.280686161, ω 4 = ω 5 = 2, ω 6 ≈ 2.

096486081 and ω 7 ≈ 2.229523505.

  Dependence of the accuracy of the bounds from Theorem 1 on the choice of t for the region Ωcut . It is preferable to pick t up and t low as far as possible from ω, than to increase the dimension of the trial subspace.

	4143	1.24764	1.26640	1.50395	1.3436
	0.1 9648	1.25029	1.26830	1.49282	1.3336
	0.01 74226	1.25063	1.26846	1.48899	1.3274
	Figure 6.

Acknowledgements References

Acknowledgements

We kindly thank Université de Franche-Comté, University College London and the Isaac Newton Institute for Mathematical Sciences, for their hospitality. Funding was provided by the British-French project PHC Alliance (22817YA), the British Engineering and Physical Sciences Research Council (EP/I00761X/1 and EP/G036136/1) and the French Ministry of Research (ANR-10-BLAN-0101).


R El Haddad
email: rami.haddad@fs.usj.edu.lb

C Lécot

P L'ecuyer
email: lecuyer@iro.umontreal.ca

N Nassif

Quasi-Monte Carlo methods for Markov chains with continuous multi-dimensional state space

Keywords: Markov chain, discrepancy, quasi-Monte Carlo method, simulation

We describe a quasi-Monte Carlo method for the simulation of discrete time Markov chains with continuous multi-dimensional state space. The method simulates copies of the chain in parallel. At each step the copies are reordered according to their successive coordinates. We prove the convergence of the method when the number of copies increases. We illustrate the method with numerical examples where the simulation accuracy is improved by large factors compared with Monte Carlo simulation.

Introduction

Many real-life systems can be modeled using Markov chains. Fields of application are queueing theory, telecommunications, option pricing, etc. In most interesting situations, analytic formulas are not available and the state space of the chain is so large that classical numerical methods would require a considerable computational time and huge memory capacity. So Monte Carlo (MC) simulation becomes the standard way of estimating performance measures for these systems. A drawback of MC methods is their slow convergence. One approach to improve the accuracy of the method is to change the random numbers used. Quasi-Monte Carlo (QMC) methods use quasirandom numbers instead of pseudo-random numbers. Pseudo-random numbers aim to simulate a sequence of independent and identically distributed (i.i.d.) random variables with a given distribution (we only consider the uniform distribution). In the example of MC integration, it is not so much the randomness of the samples that is relevant, but rather that the samples should be spread in a uniform manner over the integration domain. Quasirandom numbers are sample points for which the empirical distribution is close to the uniform distribution; unlike for random sampling, quasi-random points are not required to be independent and may be completely deterministic.

The efficiency of a QMC method depends on the quality of the quasirandom points that are used. Broadly speaking, these points should form a low-discrepancy point set. We recall from [START_REF] Niederreiter | Random Number Generation and Quasi-Monte Carlo Methods[END_REF] some basic notations and concepts. We first denote I := [0, 1). Let s ≥ 1 be a fixed dimension and denote by λ s the s-dimensional Lebesgue measure. For a set U = {u 0 , . . . , u N -1 } of points in the s-dimensional unit cube I s and for a Borel set B ⊂ I s we define the local discrepancy by

D(B, U ) := 1 N 0≤k<N 1 B (u k ) -λ s (B), (1)
where 1 B denotes the indicator function of B. The discrepancy of U is defined by

D(U ) := sup Q |D(Q, U )|, the supremum being taken over all subintervals Q ⊂ I s . The star discrepancy of U is D (U ) := sup Q |D(Q , U )|
, where Q runs through all subintervals of I s of the form s i=1 [0, a i ). A low-discrepancy point set in I s is a set of N points for which the discrepancy is of size O((log N ) s-1 /N ), which is the minimum size possible. The most powerful current methods of constructing low-discrepancy point sets are based on the theory of (t, m, s)-nets. For an integer b ≥ 2, an elementary interval in base b is an interval of the form s

i=1 [a i b -d i , (a i + 1)b -d i ), with integers d i ≥ 0 and 0 ≤ a i < b d i for 1 ≤ i ≤ s. If 0 ≤ t ≤ m are integers, a (t, m, s)-net in base b is a point set U consisting of b m points in I s such that D(Q, U ) = 0 for every elementary interval Q in base b with measure b t-m . If b ≥ 2 and t ≥ 0
are integers, a sequence u 0 , u 1 , . . . of points in I s is a (t, s)-sequence in base b if, for all integers j ≥ 0 and m > t, the points u with jb m ≤ < (j + 1)b m form a (t, m, s)-net in base b.

In the example of numerical integration, the QMC method achieves a significantly higher accuracy than the MC method, with the same computational effort. It may be hoped that the improvement obtained by using quasi-random points in place of random samples can also be attained in problems of numerical analysis that can be reduced to numerical integration. QMC simulations can outperform MC simulations in some applications: we refer to the IMACS Seminars on Monte Carlo Methods [START_REF]Selection of papers presented at the IMACS Seminar on Monte Carlo Methods[END_REF][START_REF]IMACS Sponsored Special Issue: The Second IMACS Seminar on Monte Carlo Methods[END_REF][START_REF]Special Issue: 3rd IMACS Seminar on Monte Carlo Methods[END_REF][START_REF] Sabelfeld | Selection of papers presented at the international conference: 4th IMACS Seminar on Monte Carlo Methods[END_REF].

In previous communications, we first proposed QMC schemes to simulate Markov chains with a discrete state space, either one-dimensional [START_REF] Lécot | Quasi-Monte Carlo methods for estimating transient measures of discrete time Markov chains[END_REF][START_REF] Lécot | Comparison of quasi-Monte Carlo-based methods for simulation of Markov chains[END_REF] or multi-dimensional [START_REF] Haddad | Quasi-Monte Carlo simulation of discrete-time Markov chains on multidimensional state spaces[END_REF]. We next applied the method to one-dimensional continuous state spaces [START_REF] L'ecuyer | Randomized quasi-Monte Carlo simulation of Markov chains with an ordered state space[END_REF][START_REF] L'ecuyer | A randomized quasi-Monte Carlo simulation method for Markov chains[END_REF]. In the present work, we extend the QMC algorithm to Markov chains with continuous multi-dimensional state spaces.

The method

Our setting is an homogeneous Markov chain {X j , j ∈ N} whose state space E is a subspace of R s for some s ∈ N * . The distribution P 0 of X 0 is known, and we assume that the chain evolves according to the stochastic recurrence:

X j+1 = ϕ j+1 (X j , U j+1 ), j ≥ 0, (2)
where {U j , j ≥ 1} is a sequence of i.i.d. uniform random variables over I d for some d ∈ N * , and ϕ j+1 : E × I d → E is a measurable map for each j.

To approximate the Markov chain by ordinary MC, we proceed as follows. Given a large integer N , we draw N samples x 0 k , 0 ≤ k < N from the initial distribution P 0 . Then for each k, we generate a sample path of the chain via

x j+1 k = ϕ j+1 (x j k , u j+1 k ), j ≥ 0, (3)
where u 1 k , u 2 k , . . . are pseudo-random numbers which simulate independent and uniformly distributed random variables over I d . In order to construct a QMC algorithm for the approximation of the Markov chain, we reduce the simulation to numerical integration.

We denote by M + the set of all nonnegative measurable functions on E. If P j denotes the distribution of X j , then

∀f ∈ M + E f dP j+1 = I d E f • ϕ j+1 (x, u)dP j (x)du. (4)
For x ∈ E, let us write δ x for the unit mass at x. We are looking for an approximation of P j of the form

P j := 1 N 0≤k<N δ x j k , (5)
for some integer N and a judiciously chosen set X j := {x j 0 , . . . ,

x j N -1 } ⊂ E. Let b ≥ 2, d 1 , . . . , d s be integers and put N := b m where m = s i=1 d i .
We shall use a low-discrepancy sequence Y = {y 0 , y 1 , . . .} ⊂ I s+d for QMC approximation. If Y j is the point set {y : jN ≤ < (j + 1)N } and if π and π are the projections defined by π (u 1 , . . . , u s+d ) := (u 1 , . . . , u s ) and π (u 1 , . . . , u s+d ) := (u s+1 , . . . , u s+d ), we assume that

∀j ∈ N π Y j is a (0, m, s)-net in base b and π (Y j ) ⊂ Id , (6)
where I := (0, 1). For u ∈ I s+d , we denote u := π (u) and u := π (u). We now explain our algorithm in which N copies of the chain are simulated simultaneously.

Generating the initial states

A sample X 0 is chosen such that P 0 ≈ P 0 .This means that X 0 has a small star P 0 -discrepancy (see section 3).

Transition

Supposing that we have calculated a set X j of N states such that P j ≈ P j , we compute X j+1 and P j+1 in two steps.

Relabeling the states

The states are labeled x j a using a multi-dimensional index in ). This type of sorting was first introduced in [START_REF] Lécot | A direct simulation Monte Carlo scheme and uniformly distributed sequences for solving the Boltzmann equation[END_REF]. It provides a good description of the distribution of the states in the state space and will guarantee theoretical convergence: since each transition can be described by a numerical integration (see Section 2.2.2 below), the sorting reverts to minimizing the amplitude of the jumps of the function to be integrated.

A := {a = (a 1 , . . . , a s ), 0 ≤ a i < b d i , 1 ≤ i ≤ s}, such that: if a 1 < a 1 then x j a,1 ≤ x j a ,1 , if a 1 = a 1 , a 2 < a 2 then x j a,2 ≤ x j a ,2 , • • • if a 1 = a 1 , ..., a s-1 = a s-1 , a s < a s then x j a,s ≤ x j a ,s .

QMC integration

If we replace P j by P j in the right-hand-side of (4), we define a probability measure P j+1 on E:

E f d P j+1 := I d E f • ϕ j+1 (x, u)d P j (x)du, f ∈ M + . ( 7
)
This measure certainly approximates P j+1 , but it is not a sum of unit masses, like P j . We recover this kind of approximation if we use a QMC quadrature rule. For a = (a 1 , . . . , a s ) ∈ A, let

I a := s i=1 [a i b -d i , (a i + 1)b -d i
) and 1 a be the indicator function of I a . For f ∈ M + , define

C j f (u) := a∈A 1 a (u )f • ϕ j+1 (x j a , u ), u = (u , u ) ∈ I s+d . (8)
Then we have

∀f ∈ M + E f d P j+1 = I s+d C j f (u)du. ( 9
)
We retrieve P j+1 if we perform a QMC approximation:

E f d P j+1 := 1 N jN ≤ <(j+1)N C j f (y ), f ∈ M + . ( 10
)
The last step of the algorithm may be summarized as follows. For each u ∈ I s , we associate the index a(u ) := ( b d 1 u 1 , . . . , b ds u s ). From ( 6), the mapping k ∈ {jN, jN + 1, . . . , (j + 1)N -1} → a(y k ) ∈ A is one-to-one.

The N states x j+1 0 , . . . , x j+1 N -1 are computed according to:

x j+1 a(y ) = ϕ j+1 (x j a(y ) , y ), for jN ≤ < (j + 1)N, (11)
which must be compared with [START_REF] Haddad | Quasi-Monte Carlo simulation of discrete-time Markov chains on multidimensional state spaces[END_REF]. This means that the projection π (y ) of each point y of the low discrepancy sequence is used to select the state of the chain which will advance, while the remaining components π (y ) are used to determine the next state.

Convergence

First we adapt the basic concepts of QMC methods to the present study. If U = {u 0 , . . . , u N -1 } ⊂ I s and if c : I s → R is a non-negative measurable and bounded function, we put

D(c, U ) := 1 N 0≤k<N c(u k ) - I s c(u)du. (12)
Let now P be a probability measure on E and X := {x 0 , . . . , x N -1 } ⊂ E. For a measurable subset A of E we define the local P -discrepancy by

D(A, X; P ) := 1 N 0≤k<N χ A (x k ) -P (A), (13)
where χ A denotes the characteristic function of A. The star P -discrepancy of the point set X is defined by D (X; P ) := sup z∈E |D(A z , X; P )|, where A z := {x ∈ E : x < z} and x < z means ∀i x i < z i . We shall also use the following notation: if f ∈ M + , then

D(f, X; P ) := 1 N 0≤k<N f (x k ) - E f dP. ( 14
)
The next Lemma is a version of the classical Koksma inequality [START_REF] Niederreiter | Random Number Generation and Quasi-Monte Carlo Methods[END_REF].

Lemma 1. Let P be a probability measure on E, with a Riemann-integrable density function ρ. Let f : E → R be a function such that f and |f | are of bounded variation in the sense of Hardy and Krause. If f or ρ is continuous and if X is a point set consisting of N points in E, then

|D(f, X; P )| ≤ V (f )D (X; P ). (15)
We now go back to the convergence analysis of the QMC algorithm. We restrict ourselves to the case s = d and we assume that E = s i=1 E i and every ϕ j has the form: ϕ j (x, u ) = (ϕ j,1 (x 1 , u 1 ), . . . , ϕ j,s (x s , u s )). In addition, we assume that every P j has a continuous density function ρ j .

Proposition 1. Suppose that

(i) ∀j ≥ 1 ∀z ∈ E ∀u ∈ I s V (χ Az • ϕ j (•, u )) ≤ 1,
and for every j ≥ 1 and 1 ≤ i ≤ s:

(ii) for any x i ∈ E i , the map ϕ j,i (x i , •) : I → E i is strictly increasing, (iii) for any z i ∈ E i , the map x i → (ϕ j,i (x i , •)) -1 (z i ) is monotone. Then D (X J ; P J ) ≤ D (X 0 ; P 0 ) + b d 1 +•••+d s-1 + ds/2 J-1 j=0 D(Y j ) + 1 b d 1 + • • • + 1 b d s-1 + 1 b ds/2 J. ( 16
)
Proof. For j ≥ 1, f ∈ M + and x ∈ E, denote Ψ j f (x) := I s f • ϕ j (x, u )du . For z ∈ E we have:

D(A z , X j+1 ; P j+1 ) = D(Ψ j+1 χ Az , X j ; P j ) + D(C j χ Az , Y j ). ( 17
)
By Lemma 1 and assumption (i), we get |D(Ψ j+1 χ Az , X j ; P j )| ≤ D (X j ; P j ).

The function C j χ Az is the indicator function of

R j z := a∈A I a × {u ∈ I s : ϕ j+1 (x j a , u ) < z}, (18)
hence D(C j χ Az , Y j ) = D(R j z , Y j ). From ( 6) and (ii) we have

D(R j z , Y j ) = D( R j z , Y j ),
where

R j z := a∈A I a × s i=1 0, (ϕ j+1,i (x j a,i , •)) -1 (z i ) . ( 19
)
Let δ s ≤ d s be an integer. Denote for z ∈ E:

Φ j+1 a (z) = (ϕ j+1,1 (x j a,1 , •)) -1 (z 1 ), . . . , (ϕ j+1,s (x j a,s , •)) -1 (z s ) . (20)
Because the states are sorted and by (iii), there exist s partitions of [0, 1]:

0 = w j 0,1 (z) ≤ w j 1,1 (z) ≤ • • • ≤ w j b d 1 ,1 (z) = 1, • • • 0 = w j α 1 ,...,α s-1 ,0,s (z) ≤ w j α 1 ,...,α s-1 ,1,s (z) ≤ • • • ≤ w j α 1 ,...,α s-1 ,b δs ,s (z) = 1, for 0 ≤ α 1 < b d 1 , . . . , 0 ≤ α s-1 < b d s-1 , such that, for 0 ≤ α 1 < b d 1 , . . . , 0 ≤ α s-1 < b d s-1 , 0 ≤ α s < b δs and α s b ds-δs ≤ a s < (α s + 1)b ds-δs , we have Φ j+1 α 1 ,...,α s-1 ,as (z) ∈ [w j α 1 ,1 (z), w j α 1 +1,1 (z)] × • • • ×[w j α 1 ,...,αs,s (z), w j α 1 ,...,αs+1,s (z)]. (21)
If we put

J α := s-1 i=1 [α i b -d i , (α i + 1)b -d i ) × [α s b -δs , (α s + 1)b -δs ) and Q j z := α J α × [0, w j α 1 ,1 (z)) × • • • × [0, w j α 1 ,...,αs,s (z)), (22)
Q j z := α J α × [0, w j α 1 +1,1 (z)) × • • • × [0, w j α 1 ,...,αs+1,s (z)), (23)
∂Q j z := α J α × [w j α 1 ,1 (z), w j α 1 +1,1 (z)) × I s-1 ∪ • • • ∪[0, w j α 1 ,1 (z)) × • • • × [w j α 1 ,.
..,αs,s (z), w j α 1 ,...,αs+1,s (z)) , (24

) then D(Q j z , Y j ) -λ 2s (∂Q j z ) ≤ D( R j z , Y j ) ≤ D(Q j z , Y j ) + λ 2s (∂Q j z ). The subsets Q j z and Q j z are disjoint unions of b d 1 +•••+d s-1 +δs subintervals of I 2s , hence max |D(Q j z , Y j )|, |D(Q j z , Y j )| ≤ b d 1 +•••+d s-1 +δs D(Y j ). On the other hand, λ 2s (∂Q j z ) ≤ b -d 1 + • • • + b -d s-1 + b -δs . By choosing δ s = d s /2 , we get |D( R j z , Y j )| ≤ b d 1 +•••+d s-1 + ds/2 D(Y j ) + 1 b d 1 + • • • + 1 b d s-1 + 1 b ds/2 . (25)
The desired result follows by taking the supremum over z ∈ E and by induction on j.

Numerical examples

In this section, we present the results of numerical experiments which show the kind of improvement that our method can bring with respect to MC, even when the restrictive assumptions of Proposition 1 are not fulfilled. The examples we choose are artificial since the exact solutions are known and can be analytically calculated, but we use them as a benchmark to evaluate the viability of our method. The MC computations are done using the pseudorandom points generated by MRG32k3a of [START_REF] Ecuyer | Good parameters and implementations for combined multiple recursive random number generators[END_REF]. The QMC computations use Niederreiter's sequences in base b = 2 [START_REF] Niederreiter | Random Number Generation and Quasi-Monte Carlo Methods[END_REF].

Asian option

We consider the pricing of an Asian option on a single asset whose value S(t) obeys: dS(t) = rS(t)dt + σS(t)dB(t), where r is the risk-free interest rate, σ the volatility parameter and B is a standard Brownian motion (BM). Consider discrete observation times 0 = t 0 < t 1 < • • • < t J = T and write:

S(t j ) = S(t j-1 ) exp (r -σ 2 /2)δt j + σ δt j Z j , (26)
where δt j := t j -t j-1 and {Z j : j ≥ 1} is a sequence of i.i.d. standard normal variables. The value of the call option at maturity can be written as C A = e -rT E[max(( J j=1 S(t j )) 1/J -K, 0)] where the constant K is the strike price. We want to estimate C A by our QMC algorithm and compare the results with those given by a classical MC scheme. Thus, we define a bi-dimensional Markov chain by: X 0 := (S(t 0 ), 1) and X j := (S(t j ), ( j h=1 S(t h )) 1/j ), for j ≥ 1. Here s = 2, d = 1 and we consider the following parameters: S(0) = 100, r = 0.037, σ = 0.2, T = 240/365, K = 90. We estimate the error for J = 120 as a function of N , say Err MC (N ) for MC and Err QMC (N ) for the QMC method. The value of N varies from 2 7 to 2 20 . Figure 2 shows the errors, in log-log scale. A linear regression analysis estimates the empirical convergence rate of the QMC method to be of the order of O(N -0.84 ). Clearly, the QMC algorithm enjoys a much faster convergence than the MC scheme, whose convergence rate is known to be O(N -0.50 ).

European option on the maximum of two risky assets

For our second example, we consider the pricing of an European call option on the maximum of two risky assets. The model is a bivariate geometric Brownian S(t) = (S 1 (t), S 2 (t)) with interest rate r and volatility parameters σ 1 and σ 2 . Thus, for i = 1, 2: dS i (t) = rS i (t)dt + σ i S i (t)dB i (t), where B 1 and B 2 are two standard BM with correlation parameter ρ. For a strike price K > 0, the option has discounted payoff e -rT max(max(S 1 (T ), S 2 (T )) -K, 0) at maturity date T > 0. The expected value C M of this payoff can be computed by formulas given in [START_REF] Johnson | Options on the maximum or the minimum of several assets[END_REF]. To estimate C M , we discretize the problem using a set of observation times S 1 (t j ) = S 1 (t j-1 ) exp (r -σ 2 1 /2)δt j + δt j (σ 1 Z j,1 )

S 2 (t j ) = S 2 (t j-1 )

• exp (r -σ 2 2 /2)δt j + δt j (σ 2 ρZ j,1 + σ 2 1 -ρ 2 Z j,2 ) , (28)

where {Z j : j ≥ 1} are i.i.d. random variables such that Z j ∼ N (0, I 2 ) (here I 2 is the identity matrix). We define the Markov chain by X j = (S 1 (t j ), S 2 (t j )). Here s = d = 2; for numerical illustration, let S 1 (0) = S 2 (0) = 40, r = 0.048, σ 1 = 0.2, σ 2 = 0.3, ρ = 0.5, T = 7/12, K = 35 and J = 100. The number N of paths varies from 2 7 to 2 20 . The values of the errors are shown on Figure 3. Here again, regression analysis estimates the convergence speed to be Err QMC = O(N -0.84 ) for QMC, showing a strong improvement over MC.

Conclusion

We have presented a QMC algorithm for the simulation of Markov chains with continuous and multi-dimensional state space. The method simulates several copies of the chain in parallel and reduces the error by sorting the states used in the simulation according to their successive coordinates at each step. Under certain assumptions, we have proved a convergence result as the number of simulated paths increases. The results of some numerical examples have shown that our QMC method is clearly superior to standard MC simulation in magnitude of error and in convergence rate. In the future, we shall analyze the convergence in more general settings and we shall provide some experiments with larger and more complicated models.

Figure 1 :

 1 Figure 1: Relabeling the states (b = 2, s = 2, d 1 = 2, d 2 = 3)

Figure 2 :

 2 Figure 2: Asian option : the error as a function of N for MC (thin line) and QMC (thick line)

Figure 3 :

 3 Figure 3: European option on the maximum of two risky assets : the error as a function of N for MC (thin line) and QMC (thick line)


Alessandra Speciale

Abderrahmane Sissako

Subjectivités en mouvement et déplacements identitaires dans les « cinémas africains » contemporains

Faire un film c'est une quête. On se cherche avec des astuces comme si l'on maitrisait tout, mais en réalité, on se retrouve à affronter tous les doutes et toutes les incertitudes d'une recherche intérieure.

Abderrahmane Sissako 1

Les cinématographies africaines, peu diffusées dans les circuits commerciaux, sont encore regardées quelquefois, moins comme des formes d'expressions artistiques que comme des témoignages ethnographiques. Cela étant, face à un film tel qu'Un homme qui crie (Mahamat Saleh Haroun, Tchad/Belgique/France, 2010) les commentaires portent moins sur les aspects proprement cinématographiques du film que sur la situation au Tchad.

En effet, les cinéastes africains sont longtemps restés enfermés dans la définition de leur propre origine, contraints parfois de répondre aux exigences étrangères.

Aujourd'hui beaucoup de réalisateurs représentent dans leurs films les enjeux de leur subjectivité, leurs déplacements identitaires, partie intégrante de leur vécu et de leurs expériences. Ils mettent en jeu leur existence culturellement métissée, riche et complexe, miroir de sociétés qu'on ne peut plus éviter d'affronter désormais.

Cet article voudrait tenter de démontrer en quoi la thématique de la quête identitaire, d'identités en perpétuels mouvement et construction, occupe une place centrale, non seulement dans les existences, mais aussi dans les oeuvres de ces cinéastes, lesquels se placent ainsi dans une forme d'humanité plus universelle.

African films, still poorly circulated within commercial cinema circuits, are sometimes mostly looked at in an anthropologic and ethnographic perspective, rather than as artistic expressions. It is for this reason that reviews of movies such as Un homme qui crie (Mahamat Saleh Haroun, Chad, Belgium, France, 2010), mainly deal with the situation in Chad rather than with cinematographic aspects. Likewise, for a long time, African filmmakers were prisoners of their origins, compelled to answer to the foreign expectations.

Today, many directors openly deal with their subjectivities, their complex and shifting identities that are an integral component of their lives and experiences. They put into play their hybrid existence, complex and yet enriching, mirroring the complexity of realities.

The present article deals with the central role that the theme of the search for identity, in constant movement and definition, plays in the lives and notably in the works of these African filmmakers that are thus placed within a wider, universal context.

« Cinémas africains » ?

La notion de « Cinéma africain » est relativement vaste, et ses contours restent flous, car elle réfère à un grand nombre de productions très diverses. On pourrait éclaircir le concept en spécifiant : des cinémas « faits par des réalisateurs africains »; mais, comme on le verra plus loin, la définition n'en est ni simple, ni univoque. « L'Afrique est plurielle. Son cinéma aussi. » précise Olivier Barlet 2 .

Dans ce travail, nous nous attacherons principalement à des longs métrages de fiction de réalisateurs originaires de l'Afrique Sub-saharienne.

Tenter d'élaborer une définition reste toujours une tâche ardue. Aussi, n'est-il pas très opérant d'enfermer les « cinémas africains » dans une classification réductrice, d'autant qu'il faut aussi considérer, pour ce faire, le concept d'« africanité », en se gardant des préjugés et des mythifications qui le cernent. Pourtant est-il possible aujourd'hui d'évoquer une « authenticité africaine », ou bien a-t-on besoin de « réponses nouvelles à la question de savoir "qui est Africain" et qui ne l'est pas »? 3 . Encore y a-t-il lieu de se demander si l'adjectif « africain » reste pertinent. Ne peut-on le penser réducteur, dans la mesure où il pourrait mener à une marginalisation culturelle, et que, par ce biais, les cinéastes africains risqueraient de se trouver confinés dans le « ghetto » de leurs origines ? Effectivement beaucoup de réalisateurs le refusent, déclarant : « Je ne suis pas un réalisateur africain, je suis un réalisateur qui est Africain ».

Quelques exemples, parmi d'autres, peuvent aider à saisir la complexité de cette question.

Le burkinabé Dani Kouyaté, griot descendant d'une ancienne tradition familiale, aujourd'hui installé en Suède, réalise un documentaire entre Paris et la Guadeloupe : Souvenirs encombrants d'une femme de ménage (2008), qui raconte les confessions intimes et les questionnements d'une femme originaire de la Guadeloupe, vivant en France.

Peut-on le définir comme un « film africain » ?

Pourtant dans la variété des oeuvres de Kouyaté, on peut saisir une recherche de synthèse entre les racines et un présent pluriforme, entre tradition et devenir. C'est tout cela qui l'a amené à faire du cinéma, cet « instrument merveilleux pour un griot », comme il le dit lui-même. Ses films relèvent de la nécessité pour chacun de trouver son propre équilibre dans la complexité de l'existence. biologique que culturel, le menant à avouer : « La plupart de mes personnages sont des métis, presque à mon insu. » 4 . Sa subjectivité est fondée sur des déplacements identitaires et culturels. Il raconte, par exemple, avoir retrouvé ses racines africaines pendant le tournage au Sénégal du film Le fleuve, une réadaptation du scénario que lui avait confié le cinéaste David Achkar. 5 Les déplacements identitaires, l'étonnement face à la rencontre du divers, de l'inconnu, contribuent à la redéfinition de soi. On reconnait sa propre spécificité dans la confrontation avec l'altérité, qui est aussi la source d'une véritable conscience de soi. « L'altérité se niche au coeur de l'identité » affirme l'anthropologue italien Remotti. 6 Il est par exemple très étonnant de constater à quel point peut-être différente la perception que l'on a de soi-même, quand, par le seul franchissement de la frontière, on devient l'autre, l'étranger.

Mama

La quête identitaire caractérise le cinéma de Mama Keita, un cinéma tout imprégné de la sensation d'être toujours absent à quelqu'un ou à quelque chose, comme le suggère son long-métrage L'absence (2009). D'ailleurs, ses oeuvres n'ont pas d'ancrage géographique, son dernier courtmétrage, One more vote for Obama, (2010), par exemple, a été tourné aux Etats-Unis et financé par l'Algérie. 7

Comment doit-on considérer Mama Keita ? L'enfermer dans une catégorie serait réducteur ; il a l'habitude d'affirmer : « Si l'on me catalogue simplement comme réalisateur Guinéen -comme on peut le voir quelquefois -on risque de passer à coté de moi ».

John Akomfrah, originaire du Ghana, est défini sur Wikipédia, l'encyclopédie contributive en ligne, comme « réalisateur britannique ». En revanche, Rémi Mazet, français et blanc, gagne le prix du meilleur court-métrage au Festival du film Black de Montréal, avec son film Siggil (2010).

Ou bien encore, dans beaucoup de livres de référence sur les cinémas africains, on trouve fréquemment citée, parmi les pionniers, Sarah Maldoror, Franco-Guadeloupéenne, une des premières femmes à réaliser des films en Afrique noire (quelques années avant Lettre paysanne de Safi Faye). De surcroît, on voit souvent classé parmi les réalisateurs africains, Raoul Peck, Haïtien, et actuel Président de La fémis, qui a tourné des films importants en Afrique.

Ce ne sont là que quelques exemples qui témoignent de réalités complexes, et révèlent des êtres habités par des appartenances plurielles et multiples, que l'on aurait du mal à enfermer dans les contours étroits d'une définition.

La complexité et les déplacements identitaires, individuels et collectifs, sont en effet aujourd'hui parmi les principales sources d'inspiration des oeuvres de réalisateurs africains de la diaspora, cette dimension existentielle formée conjointement d'une vocation à l'errance et à l'enracinement.

4

Entretien avec Mama Keita, Paris, juillet 2010. Tous les entretiens cités dans cet article ont été réalisés par nous dans le cadre d'un doctorat à l'Université Lyon 3, sous la direction de J.P. Esquenazi. 5 David Achkar est décédé en 1998. Il était en train de travailler au film Un fleuve comme fracture depuis six ans. Mama Keita lui a aussi consacré le documentaire Une étoile filante. 6 Francesco Remotti, Contro l'identità, Editori Laterza, 2008(première édition 1996, Gius. Laterza e Figli), 112 pages. Notre traduction de l'italien.

7

Ce court-métrage fait partie de « L'Afrique vue par… », projet de l'État algérien, produit par Laith Media : dix cinéastes de dix pays réalisent chacun un court-métrage pour donner une image plus juste du continent. Le projet a été présenté au cours de la deuxième édition du PANAF à Alger (2009).

Milieux socioculturels et «milieux du cinéma 8 »,

Pour mieux comprendre le contexte, il serait utile de s'attarder aussi sur les milieux socioculturels et historiques d'où surgissent les cinématographies d'Afrique noire. Nous sommes alors dans les années 60, à l'époque des indépendances politiques 9 .

Ainsi, les premiers films répondaient-ils à une exigence d'auto-représentation, après l'époque coloniale, qui a mis en cause les points de référence identitaires. Les réalisateurs africains ont pris la parole, comme une voix qui se libère de l'intérieur, après avoir vécu l'enfermement de leurs propres images, espaces et territoires 10 -physiques et mentaux -dans un regard exogène, parfois méprisant. L'enjeux de la représentation est central, car on sait bien la force du rapport entre l'autonomie identitaire, la légitimité de ses propres images, représentations et imaginaires, et l'affirmation d'une dignité.

Aujourd'hui dans de nombreux films de cinéastes exilés, qui se sont établis « ailleurs », on observe comment l'expérience subjective et collective du déplacement influence leur existence et leurs oeuvres.

« Aujourd'hui, le mouvement va vers une multiplicité de voix et de styles cinématographiques qui sont influencés et modulés par la résidence géographique des cinéastes en Afrique, Europe, ou Etats-Unis »11 Dans cette multiplicité des voix, les réalisateurs prennent en charge, chacun à sa manière, l'expérience de la migration et de la confrontation à l'altérité, à la fois comme vécu personnel, et comme phénomène social.

Toutefois, vu que le cinéma est aussi une industrie, on ne peut analyser les oeuvres sans tenir compte des « directives » et des « contraintes »12 .

Ce n'est pas ici le lieu d'aborder des problématiques complexes comme celles de la production, de la distribution, des financements, -souvent étrangers, et qui parfois s'avèrent provenir des expuissances coloniales -des multiples casquettes que les cinéastes se trouvent obligés de porter, des langues utilisées, et surtout des publics.

Il est toutefois légitime de se demander si l'on peut vraiment parler de « cinémas africains », étant donnée la pénurie d'institutions cinématographiques dans la plus part des pays du continent.

8 On emprunte l'expression à Pierre Sorlin. 9 Il est opportun de préciser politique car, bien qu'en France l'on vienne de fêter le cinquantenaire des indépendances, il est lieu de se demander si certains pays africains sont à l'heure actuelle véritablement indépendants. On peut en douter sur le plan économique, et tout particulièrement pour ce qui concerne les productions cinématographiques. 10 Voir à ce propos, l'intéressant analyse de André Gardies, dans son livre Cinémas d'Afrique noire francophone. L'espace miroir, L'Harmattan, paris, 1989, 199 pages. Il explique comment la monstration devient affirmation d'existence et d'identité et comment « au lieu de montrer pour raconter, le cinéma négro-africain tendait à raconter pour montrer ».

Hybridité et déplacements identitaires : quelques exemples de subjectivités indirectes

Pourtant, les films finissent par exister, et ils surgissent aussi des existences complexes de ces cinéastes qui ne vivent plus « entre deux », mais « entre plusieurs ». Nombre d'entre eux sont aussi des métis biologiques 13 ; cependant le métissage culturel est désormais une caractéristique intrinsèque des individus et des communautés humaines.

On peut trouver des exemples de subjectivités indirectes dans les films suivants qui abordent la complexité des réalités et la quête identitaire et personnelle, suite à des déplacements culturels : des fictions comme possibles paraphrases des réalités, au sens ou l'entend Esquenazi 14 et qui peuvent participer à la construction de l'imaginaire collectif. (Mweze Ngangura, RDC 1998), montre le dépaysement d'un roi congolais confronté à la société belge, à l'occasion d'un voyage à la recherche de sa fille. Le titre au pluriel, joue avec la plurivocité des termes (identité / carte de séjour), mais suggère également des « identités en pièces ». Ce film est aussi le fruit de l'expérience du réalisateur congolais, installé à Bruxelles. Emblématique, est la scène qui se déroule à la frontière pour entrer en Belgique. La séquence commence par un gros plan sur un passeport européen, de couleur bordeaux, tandis que le douanier déclare en souriant « C'est bon, vous pouvez passer ». Par contre, quand Mani Kongo, roi de Bakongo, se place dans la file, peu nombreuse, et majoritairement constituée de blancs, il s'aperçoit aussitôt que sa place n'est pas là. « Pour le passeport avec visa prenez plutôt l'autre file ». Un travelling parcourt une longue file, et la caméra s'arrête sur certains visages, aux origines multiples, par contraste avec l'autre file. Une sorte de division entre êtres humains est déjà établie par les panneaux dans l'aéroport, qui séparent les citoyens de l'Union Européenne des autres. L'effroi du roi augmente lorsqu'il se trouve en face du douanier, lequel exige de lui qu'il déclare et s'acquitte des taxes pour les trois objets -son chapeau, son bâton et ses colliers -héritages de la tradition, et qui «sont [s]es pièces d'identité ». Quand une douanière surgit pour les confisquer, le roi congolais se résout à payer, afin d'empêcher le sacrilège que des mains de femme puissent toucher ces objets sacrés.

Pièces d'identités

Pourtant lorsqu'il y a une vraie rencontre, c'est dans l'échange avec l'autre que l'on se reconnaît : se reconnaître dans le regard de l'autre, sans se perdre, comme une sorte de processus de réaffirmation de soi, permet de sortir en même temps du camouflage et du piège de l'autochtonie. Cet échange est possible quand on accepte de regarder l'autre en face et de prendre en charge la complexité. La rencontre se nourrit de la connaissance, de l'écoute, de l'échange, pour arriver à être soi même, « poreux à tous les souffles du monde » (A. Césaire).

C'est aussi l'idée de l'« identité rhizome » que Glissant 15 conçoit, à partir de la distinction opérée par Deleuze et Guattari entre la notion de racine unique et de rhizome : une «racine, mais allant à la rencontre des autres racines, alors ce qui devient important n'est pas tellement un prétendu absolu de chaque racine, mais le mode, la manière dont elle entre en contact avec d'autres racines : la 13 Le thème de la recherche des origines est très commun parmi ces cinéastes-métisse. Par exemple, dans sa fiction Notre étrangère (2010) -dont le titre en anglais The place in between est emblématique -Sara Bouyain, métisse franco-burkinabée, raconte sa propre histoire de déplacements subjectifs. 14 Voir Jean-Pierre Esquenazi, La vérité de la fiction. Comment peut-on croire que les récits de fiction nous parlent sérieusement de la réalité ?, Lavoisier, 2009. 15 Edouard Glissant, Introduction à une poétique du divers, Gallimard, 1996. 148 pages Relation ». Relation qui se révèle vitale pour l'« animal social » qu'est l'être humain, et qui se construit et se nourrit aussi de l'enrichissement de la rencontre avec l'autre.

Cette complexité, on la saisit dans les oeuvres, les intuitions et les réflexions personnelles que les réalisateurs veulent partager avec les spectateurs comme questions ouvertes, dans la tentative d'appréhender des réalités sociales et humaines. Durant tout le film, il semble que la caméra veuille pénétrer le corps du protagoniste, pour percer ses pensées et ses émotions les plus intimes, face à l'écart entre monde rêvé et monde réel.

Dans L'Afrance, après une scène d'amour, El Hadj sort dans la rue, où il se sent moins à l'aise. Il rejoint ensuite un copain dans une cantine dépouillée où tous deux abordent l'atavique refrain du retour au pays. Devant une caméra fixe, l'ami avoue : « Moi j'ai essayé de rentrer et je me suis fait bouffer. Pour moi le Sénégal c'était l'hospitalité, l'Afrique, quoi, mais, écoute, une fois là-bas, on m'a traité comme un étranger. Avec gentillesse, on m'a emménagé comme un malade, parce que, soit disant, je venais de France, je ne savais plus comment cela se passait, je ne comprenais pas.[…] J'ai passé tout mon temps à me demander quand est-ce que j'allais retrouver les sentiments, le naturel. Et à qui tu voulais que je raconte ça ? Même ma mère ne pouvait pas comprendre. » Ils entreprennent alors une discussion sur les valeurs de l'enfance et le pays où l'on s'est formé. « Mais c'est ton enfance aussi qui te forme, si on n'est plus ça, on est quoi ? » demande El Hadji. Ses réflexions continuent sous la douche, lieu privilégié de l'espace personnel dans le film, lieu de défoulement : « Je ne vais pas rester un étranger toute ma vie ».

Gomis, né en France d'une mère française et d'un père sénégalais, s'est toujours interrogé sur son identité métisse. Il raconte : « La douche c'est un espace particulier, très personnel. Pour moi c'était l'espace du personnage par rapport à lui-même. Il y avait ses études, ce qu'il raconte, ses espoirs, le Sénégal, et puis lui sous la douche. Un espace très confortable, où tout est possible. Et dehors il y avait la réalité qui fait exploser les choses : lui, il vivait dans une sorte d'afrance (avec le a s'arrête ; la musique et la bande son, particulièrement travaillées comme dans tous ses films 20 , mènent les spectateurs jusqu'à l'introspection.

Les traits d'autobiographies sont perceptibles, bien au-delà de la passion du réalisateur pour la musique et du souvenir d'une aventure de jeunesse, l'enregistrement d'un album. Il partage avec les spectateurs ses inquiétudes personnelles et intimes relativement au sort des enfants métis, souvent grandis dans une famille monoparentale, dans le Londres d'aujourd'hui.

Dans une des séquences vers la fin du film, on assiste au paroxysme des questionnements identitaires. Lorsque la mère rejoint Jamie (Rage pour les amis) en larmes dans sa chambre, le croyant éprouvé par un problème de travail, devant une caméra immobile, le jeune métis l'agresse ainsi : «Ca n'a rien à voir avec le taf ! [...] Pourquoi t'a épousé papa ? Pourquoi t'es pas restée avec les tiens ?» Devant une femme perplexe qui le rassure sur l'amour sincère qui l'a uni à son mari, la colère de Rage explose : « On est blancs ou noirs ? » « Ni l'un. Ni l'autre, vous êtes les deux à la fois, vous êtes vous-mêmes, vous êtes mes enfants. J'ai épousé ton père parce que j'étais amoureuse de lui, la couleur de peau n'a rien à voir. » « Je suis noir ! Mais c'est pas à moi de le dire, ce sont les noirs qui décident si je le suis ou pas. Je dois sans arrêt le prouver » « Tu n'es pas noir, Jamie ». Le jeune ne cesse ainsi de s'interroger : « Qui je suis ? » A l'époque de l'écriture de Rage, Aduaka, qui envisageait avoir des enfants avec sa compagne italienne de l'époque, s'interrogeait : « Je me demandais tout simplement comment des enfants métis grandissent dans la société dans laquelle on vit, et où l'on parle de multiculturalisme ; mais à la fin, on comprend qu'il n'existe pas vraiment, que c'est plutôt une idée. Je suis maintenant le père de deux enfants métisses et j'espère pouvoir répondre à leurs questionnements. J'aimerais qu'advienne un temps où ils n'auront plus à se poser ce genre de questions, mais je suis conscient qu'ils seront toujours confrontés à tout ça.» 21 Rage, comme La Haine (Kassovitz, 1995) 22 en France, aussi bien que les cinématographies de John Akomfrah, Isaac Julien, Horace Ové, parmi d'autres, en Grande Bretagne, nourrissent des résonnances avec un certain cinéma américain indépendant, tel celui de Spike Lee. Un black cinema 23 qui parle des sociétés, des nouveaux espaces urbains, des cultures de la jeunesse. Aduaka ne cache pas son intérêt pour les cinémas indépendants en général : « C'était le temps où l'on vendait sa propre voiture et tout ce qu'on avait, on louait une caméra, et on faisait un film.» 24 20 Aduaka a commencé comme ingénieur du son dans nombreux documentaires britanniques ; il a aussi travailler dans Quartier Mozart de Jean Pierre Bekolo (1992).

21

Entretien avec Newton Aduaka, Paris, Janvier 2011. Notre traduction de l'anglais.

22

Le scénario de Rage a été écrit en 1994, avant la sortie de La Haine 23 Il est intéressant de noter que John Akomfrah voit le père du black cinema en Sembène Ousmane. (Entretien, Londres, janvier 2011). Ces cinématographies impliquent la black diaspora et la communauté noire qui, selon Paul Gilroy, est aussi rapprochée par le partage de la mémoire commune de l'esclavage, en surcroît des difficultés de la vie quotidienne.

Enjeux de vie et enjeux de représentation

Il est intéressant de remarquer comment les différents contextes et milieux socioculturels, ainsi que le vécu et les expériences personnelles, inspirent ces fictions, où chaque réalisateur met en jeu sa subjectivité et ses déplacements identitaires.

Pourtant on pourrait parler plutôt de « cinémas du monde » que de « cinémas africains » : les réalisateurs en question vivent dans un univers sans frontières culturelles, (pas toujours sans frontières géopolitiques), en relation avec des intellectuels de divers pays, qui habitent la complexité du monde post-postcolonial.

Ce sont des artistes qui peuvent s'exprimer dans plusieurs langues, qui font expérience de divers contextes, ce qui fait la richesse de leur regard et de leur sensibilité.

Les spectateurs sont aussi impliqués dans différents milieux, et l'on peut dire de chaque film qu'il résonne différemment selon les publics. En effet, à la suite d'Esquenazi 25 , on peut envisager un récit fictionnel : «comme une « structure signifiable », plutôt que comme une « structure signifiante » : la signification n'est pas une donnée immanente du récit mais une valeur qui lui est attribuée par le destinataire ». Le spectateur devient alors un inventeur de sens et de formes, se fait auteur à son tour.

On peut imaginer que nous appartenons à la même « élite » que ceux que Zygmunt Baumann appelle «globalisés pour choix », et que nous préférons désigner comme des « êtres dans le monde ». C'est bien pour cela que ces films ont en nous des résonances familières, ils nous parlent et nous permettent de nous y reconnaître. En évitant un regard préconçu envers ces fictions, on peut alors percevoir comment des « réalités » multiformes, jamais figées, sont librement transposées à l'écran.

Ces réalisateurs « nomades », qui trouvent l'inspiration surtout dans leurs déplacements identitaires, dévoilent à la fois, le métissage et la complexité des sociétés contemporaines, et la richesse culturelle qui en découle.

Daniela Ricci 25

Jean-Pierre Esquenazi, La vérité de la fiction. Comment peut-on croire que les récits de fiction nous parlent sérieusement de la réalité ?, Lavoisier, 2009.

  Keita, né au Sénégal d'un père guinéen et d'une mère vietnamienne, a vécu, enfant, dans divers pays, son père officiant comme militaire de l'armée française, puis a finalement grandi en France. Le mélange culturel auquel il a été confronté dès son enfance marque son existence et ses films et l'on sait bien à quel point la subjectivité d'un artiste s'exprime aussi par ce qui échappe à son contrôle dans ses oeuvres. Tout cela fait de Keita un emblème du métissage, aussi bien 2 Olivier Barlet, Les cinémas d'Afrique noire, le regard en question, L'Harmattan, Paris 1997, 351 pages 3 Afropolitanisme de Achille Mbembe, pubblié sur www.africultures.com, le 26/12/2005, consulté le 7/02/2011

  La tentative de compréhension et de partage passe à travers les personnages, intermédiaires entre monde réel et univers fictionnel, -comme le propose Kate Hamburger 16 -menant les spectateurs à percevoir les subjectivités en mouvement mises en jeu par les réalisateurs.« Sortir de l'autochtonie. Cela suppose laisser son personnage exister librement, pour lui-même, dans sa singularité. Ne pas en faire le symbole emblématique d'une cause. Ce sera le parcours d'El Hadj dans L'Afrance (Alain Gomis, France/Sénégal 2001) : cet étudiant sénégalais avait construit sa solidité à Paris autour du projet de rentrer au pays, pour y servir l'indépendance prêchée par les héros de la décolonisation mais, face à l'exclusion, se trouve complètement déstabilisé et, comme le Samba Diallo de L'Aventure ambiguë de Cheik Hamidou Kane, au bord du suicide 17 ».L'Afrance, dès son titre, imbrique France et Afrique, comme on le voit aussi dans l'incipit du film, où les images de Paris et de Dakar sont mêlées et entrelacées. Les confessions des personnages dévoilent leur étrangeté partout, dans la société où ils vivent, aussi bien que dans leur pays d'origine, où -à leur retour -ils sont perçus comme des étrangers.

Manthia Diawara, African films. New forms f aesthetics and politics, Prestel, 2010. Notre traduction de l'anglais.

Voir Jean-Pierre Esquenazi, Eléments de sociologie du film, dansCinémas 17,2, 2007, pages 117-141

Kate Hamburger, Logiques des genres littéraires, Le Seuil,Paris, 1986

Olivier Barlet, Les nouvelles stratégies des cinéastes africains, www.africultures.com, publié le 1/10/2001, consulté le 27/12/2010

Entretien avec Newton Aduaka, Paris, Janvier 2011. Notre traduction de l'anglais.