Laurent Gosse

Norbert J Mauser

Wolfgang Pauli

Multiphase semiclassical approximation of an electron in a one-dimensional crystalline lattice ⋆ III. From ab-initio models to WKB for Schrödinger-Poisson

Keywords: Hartree ansatz, semiclassical limit, periodic potential, homogenization, Vlasov-Poisson equation, moment method, nonstrictly hyperbolic systems. 1991 MSC: 81Q05, 81Q20, 35L65, 65M06

published or not. The documents may come

Multiphase semiclassical approximation of an electron in a one-dimensional crystalline lattice: III. From ab-initio models to WKB for Schrödinger-Poisson

Introduction

This article is the third and last part of a numerical study of semiclassical approximation of the motion of electrons in short-scale periodic potentials. We have now in mind to take into account also for the self-consistent interaction potential, which leads to a weak nonlinearity. More precisely, we are about to focus onto the following Schrödinger-Poisson equation in one space dimension,

i ∂ t ψ + 2 2m
∂ xx ψ = e V ions (x) + V ext (x) + eV P (t, x) ψ, -ǫ 0 ∂ xx V P = |ψ| 2 ;

x ∈ R [START_REF] Ambrosio | Transport equation and Cauchy problem for BV vector fields[END_REF] with the Planck's constant, ǫ 0 the dielectric permittivity of the medium (it will be set to ǫ 0 ≡ 1 throughout the whole paper), m and e the electronic mass and charge and V ion ∈ R the periodic potential modeling the interaction with a lattice of ionic cores. The smooth and slowly-varying external potential V ext stands usually for an applied electric field, a confining potential or a doping term.

In order to shed complete light on the derivation and the qualitative properties of the simplified model [START_REF] Ambrosio | Transport equation and Cauchy problem for BV vector fields[END_REF], we first start from the exact Hamiltonian for a neutral system constituted of N atoms with Z electrons each in R 3 :

H = N α=1    P 2 α 2M + Z i=1 p 2 αi 2m + N β( =α)=1   1 2 (Ze) 2 |X α -X β | + Z i=1   - Ze 2 |x βi -X α | + 1 2 Z j=1 e 2 |x αi -x βj |        . (2)
The notations have been chosen as follows: M, P α , X α stand for the mass, momentum and position of the nuclei while m, p αi , x αi refer to those of the electrons in the α th atom. All in all, this constitutes a system of N (Z + 1) charged particles interacting with each other via Coulombian forces (the atomic cores are lumped into a unique particle in this model). Ab initio computations will therefore refer to the ones involving this full Hamiltonian [START_REF] Ashcroft | Solid-state physics[END_REF] which can be considered as exact in nonrelativistic quantum mechanics. However, even for moderate values for N, Z, such ab initio computations become quickly almost impossible in terms of complexity. Hence several simplifications are usually in order:

• The Born-Oppenheimer assumption states that the nuclei's motion decouples adiabatically because M ≫ m; it can be neglected or at least treated classically. • One can safely restrict [START_REF] Ashcroft | Solid-state physics[END_REF] to vN valence and conduction electrons. All the others can generally be considered as tightly tied to the cores and confined inside the inner shells.

At this level, we have reduced our original system to a collection of N ions with v va-⋆ Support by the Wolfgang Pauli Institute (Wien) in the frame of the "Nanoscience"

Programme and the European network HYKE, funded by the EC as contract HPRN-CT-2002-00282 is acknowledged. Support from the FWF (Austrian Science Foundation) via the START Project of N. Mauser (Y-137-TEC) and the Wittgenstein project of P.A. Markowich is acknowledged. The first author is deeply grateful to Prof. Yann Brenier who knows why and to Dr. C. Sparber. Parts of this work have been carried out in the Lab. J.A. Dieudonné at University of Nice (France).

* Corresponding Author

Email addresses: l.gosse@area.ba.cnr.it (Laurent Gosse), mauser@univie.ac.at (Norbert J. Mauser).

lence/conduction electrons. So the Hamiltonian (2) boils down to H ions + H e -with

H ions = N α=1    P 2 α 2M + 1 2 N β( =α)=1 (ve) 2 |X α -X β |    , H e -= vN i=1    p 2 i 2m + V ions (x i ) + 1 2 vN j( =i)=1 e 2 |x i -x j |    .
(3) The ionic potential V ions (x) = N α=1 V ps (|x -X α |) where V ps is a smoothered "pseudopotential" originating from both Coulomb attraction and screening effects from inner shells electrons; it is referred to as the "effective core potential" in quantum chemistry. In the simplest Bohr-Oppenheimer framework, one assumes the X α to be constant and P α ≡ 0 thus remains only H e -(x, p) which can nonetheless constitute a delicate quantum many-body problem, especially in case N ∈ N is big.

A common way out lies in the mean-field approximation that we shall present in §2.1; roughly speaking, it consists in deriving self-consistently an average potential in place of the Coulomb interaction by letting N → ∞ with a convenient scaling. Within this framework, electrons move as independent particles submitted to an overall mean electric field. The Pauli exclusion for fermions can be included or not in the derivation; Hartree or Hartree-Fock models are obtained accordingly. We shall choose to ignore it; hence we somehow consider an electron cloud treated as a condensate, that is a system endowed with the property that all its components share the same one-particle state described by a unique wave function ψ solution of the Hartree equation 1 . This model as a "one-particle equation" is a somewhat crude approximation of the original many-body problem; since the wave function contributes to the effective potential only via its corresponding position density, this is the simplest realization of a time-dependent density functional theory (TDDFT). In the situation we consider in this article where (repulsive) Coulomb interaction is only to be taken into account, rigorous results have been obtained in case V ions ≡ 0 in [START_REF] Bardos | Derivation of the Schrödinger-Poisson equation from the quantum N-body system[END_REF][START_REF] Bardos | The weak coupling limit for systems of N → ∞ quantum particles: state of the art and applications[END_REF]. We shall indicate formally the changes that result from the inclusion of this potential. As the number of electrons is considered infinite, it is reasonable to assume that the number of corresponding ions diverges also; hence V ions can be seen as a smooth periodic potential admitting a Bravais lattice endowed with a Wigner-Seitz cell in R 3 . This matches the physical setting of the articles [START_REF] Gérard | Homogenization limits and Wigner transforms[END_REF][START_REF] Markowich | A Wigner-function approach to semiclassical limits: electrons in a periodic potential[END_REF][START_REF] Bechouche | Semiclassical limit for the Schrödinger-Poisson equation in a crystal[END_REF][START_REF] Bechouche | Semi-classical limit of a Schrödinger equation for a stratified material Monatsh[END_REF].

We have in mind to conduct semiclassical computations on this Hartree model by means of the "two-scale WKB method" originally presented in [START_REF] Guillot | Semiclassical asymptotics in solid-state physics[END_REF] (see also [START_REF] Carles | Semiclassical asymptotics for weakly nonlinear Bloch waves[END_REF][START_REF] Dimassi | Semiclassical asymptotics in magnetic Bloch bands[END_REF]) extensively used in the linear setting (no self-interactions) in [START_REF] Gosse | Multiphase semiclassical approximation of an electron in a one-dimensional crystalline lattice -I. Homogeneous problems[END_REF][START_REF] Gosse | Multiphase semiclassical approximation of an electron in a one-dimensional crystalline lattice -II. Impurities, confinement and Bloch oscillations[END_REF]. Relying on the well-known fact that the Hartree term is but the Green function of the Laplace operator in R 3 , we rewrite the mean-field equation as the weakly nonlinear Schrödinger-Poisson system. Then, assuming translational invariance in two independent space directions, [START_REF] Mauser | Semi)classical limits of Schrödinger-Poisson systems via Wigner transforms Journées[END_REF], we move forward to a one-dimensional model like [START_REF] Ambrosio | Transport equation and Cauchy problem for BV vector fields[END_REF] (see [START_REF] Kronig | Quantum mechanics of electrons in crystal lattices[END_REF][START_REF] Lu | Plastic lasers: stimulated emission from conjugated organic polymers[END_REF][START_REF] Takagaki | Transmission of interaction electrons through a one-dimensional periodic potential[END_REF] for examples of its physical realizations) to which it becomes possible to apply a variant of the linear WKB receipe. These derivations are presented in full detail within §2.2. Many (semi)classical limits have been carried out recently by means of the Wigner transform relying on the compactness lemma of [START_REF] Lions | Sur les mesures de Wigner[END_REF]. In the context of the Schrödinger-Poisson system, it leads to a Vlasov-Poisson like equation possibly including the energy bands corresponding to the last valence or the first conduction levels; consult §2.3 and e.g. [START_REF] Lions | Sur les mesures de Wigner[END_REF][START_REF] Bechouche | Semiclassical limit for the Schrödinger-Poisson equation in a crystal[END_REF][START_REF] Zhang | The limit from the Schrödinger-Poisson to the Vlasov-Poisson equations with general data in one dimension Comm[END_REF]. At a computational level, simulating measure solutions of this limit equation represents a heavy task even in one space dimension. Hence we chosed to stick to the recent framework proposed by Brenier [START_REF] Brenier | Derivation of the Euler equations from a caricature of Coulomb interaction[END_REF] (see also [START_REF] Ambrosio | Transport equation and Cauchy problem for BV vector fields[END_REF][START_REF] Bouchut | Renormalized solutions to the Vlasov equation with coefficients of bounded variation Arch[END_REF]) in § §3.1-2 for us to solve the Vlasov-Poisson problem in a mathematically simple but founded sense. It is then possible to use numerical techniques borrowed from [START_REF] Gosse | Identification of asymptotic decay to self-similarity for one-dimensional filtration equations[END_REF] in order to update the intensities and thus the electric field in a semi-Lagrangian framework, see [START_REF] Besse | Convergence of a semi-lagrangian scheme for the one-dimensional Vlasov-Poisson system[END_REF]. This is explained in detail in §3.3 assuming the reader familiar with the numerical techniques for K-branch solutions, [START_REF] Brenier | A kinetic formulation for multibranch entropy solutions of scalar conservation laws[END_REF][START_REF] Gosse | Using K-branch entropy solutions for multivalued geometric optics computations[END_REF][START_REF] Gosse | A case study on the reliability of multiphase WKB approximation for the one-dimensional Schrödinger equation, to appear[END_REF][START_REF] Gosse | Multiphase semiclassical approximation of an electron in a one-dimensional crystalline lattice -I. Homogeneous problems[END_REF][START_REF] Gosse | Multiphase semiclassical approximation of an electron in a one-dimensional crystalline lattice -II. Impurities, confinement and Bloch oscillations[END_REF][START_REF] Gosse | Two moment systems for computing multiphase semiclassical limits of the Schrödinger Equation[END_REF][START_REF] Runborg | Some new results in multiphase geometrical optics[END_REF]. Other methodologies have been proposed in e.g. [START_REF] Shi Jin | An Eulerian method for computing multi-valued solutions of the Euler-Poisson equations and applications to wave breaking in klystrons[END_REF][START_REF] Lisok | The evolution operator of a Hartree-type equation with a quadratic potential[END_REF]. §4 is devoted to computational results. The first one is a self-consistent free electrons cloud's 1 One speaks also about electrons (or mostly bosons) in coherence.

simulation; it corresponds somewhat to the simplest situation described by [START_REF] Ambrosio | Transport equation and Cauchy problem for BV vector fields[END_REF], namely V ′ ion ≡ 0 and V ′ ext ≡ 0, with initial data leading to a 5-branch solution thus asking for the inversion routines of [START_REF] Gosse | Finite moment problems and applications to multiphase computations in geometric optics[END_REF]. Next, we take V ion (x) = cos(x), the so-called Mathieu's potential already studied in [START_REF] Gosse | Multiphase semiclassical approximation of an electron in a one-dimensional crystalline lattice -I. Homogeneous problems[END_REF][START_REF] Gosse | Multiphase semiclassical approximation of an electron in a one-dimensional crystalline lattice -II. Impurities, confinement and Bloch oscillations[END_REF]. At last, we tried to simulate the screening effect for an impurity in the same periodic potential, but with V ext being a Coulomb term. For each of these, we expect to validate the proposed WKB algorithm against direct Schrödinger computations obtained via the Fourier schemes advocated in [START_REF] Bao | On time-splitting spectral approximations for the Schrödinger equation in the semiclassical regime[END_REF].

2 Hartree equation: mean-field assumption, WKB ansatz and Wigner analysis 2.1 Derivation of the Schrödinger-Poisson system via density functions

In this section, we aim at deriving the Hartree equation emanating from (3) within the strongest Born-Oppenheimer assumption, i.e. considering the ions steady. More precisely, we shall write down a "vN -body Schrödinger equation" (recall v as the number of valence/conduction electrons per atom) for the wave function Ψ : R + × R 3vN → C satisfying i ∂ t Ψ = H e -Ψ. It would perhaps be more natural to consider a Hartree-Fock derivation instead, taking into account for the Pauli exclusion principle. However, recent numerical experiments suggest that for many physical situations, the parameters' size and the density are such that "exchange effects" can acutally be neglected, see [START_REF] Bao | Effective one particle quantum dynamics of electrons: a numerical study of the Schrödinger-Poisson-Xα model[END_REF][START_REF] Mauser | Schrödinger-Poisson-Xα model[END_REF]. Thus we first change to "atomic units" for which = m = e = 1 and without any loss of generality, we assume v = 1. Making explicit the dependence on N ∈ N of the wave function, there holds

i∂ t Ψ N (t, x 1 , ...x N ) = - 1 2 N i=1 ∆ xi + V ion (x i ) Ψ N + 1 N 1≤i<j≤N V Cou (|x j -x i |)Ψ N , (4)
with x i ∈ R 3 and V Cou standing for the Coulomb term, already studied in the semiclassical context in [START_REF] Gosse | Multiphase semiclassical approximation of an electron in a one-dimensional crystalline lattice -II. Impurities, confinement and Bloch oscillations[END_REF], §5. We also introduce the density, D

N (t, X N , Y N ) = Ψ N (t, X N )Ψ N (t, Y N ) ∈ C
, where X N = (x 1 , x 2 , ..., x N ) and Y N = (y 1 , y 2 , ..., y N ) ∈ R 3N . At this level, it is convenient to define another important object, namely its n th marginal for any N ∋ n < N :

D N :n (t, x 1 , ..., x n , y 1 , ..., y n ) = R 3(N -n)
D N (t, x 1 , ..., x n , z n+1 , ..., z N , y 1 , ..., y n , z n+1 , ..., z N )dz n+1 ...dz N .

One observes at once that the local position density ̺(t, x) reads: ̺(t, x) = D N :1 (t, x, x) for any x ∈ R 3 . All these quantities can be deduced from equation [START_REF] Bao | Effective one particle quantum dynamics of electrons: a numerical study of the Schrödinger-Poisson-Xα model[END_REF]. It is now that the "coherence assumption" comes into play since we must complete (4) with peculiar initial data like,

Ψ N (t = 0, x 1 , ..., x N ) = N i=1 ψ 0 (x i ), (5)
which expresses the fact that initially, all the N electrons located in x i=1,...,N are in the same quantum state ψ 0 , an assumption which violates Pauli's exclusion principle2 . Nevertheless, the idea is to prove, at least formally, that this "ansatz" propagates in time t ∈ R + asymptotically in N → ∞.

It is well-known that densities satisfy the Von-Neumann equation,

i∂ t D N (t, X N , Y N ) = - 1 2 [∆ XN -∆ YN ]D N (t, X N , Y N ) + N i=1 [V ion (x i ) -V ion (y i )]D N (t, X N , Y N ) + 1 N 1≤i<j≤N [V Cou (|x j -x i |) -V Cou (|y j -y i |)]D N (t, X N , Y N ),
from where one deduces the BBGYK 3 hierarchy for each of the n th marginals, [START_REF] Bardos | The weak coupling limit for systems of N → ∞ quantum particles: state of the art and applications[END_REF]:

i∂ t D N :n (t, X n , Y n ) = - 1 2 [∆ Xn -∆ Yn ]D N :n (t, X n , Y n ) + n i=1 R 3(N -n) [V Cou (|x i -z|) -V Cou (|y i -z|)]D N :n+1 (t, X n , z, Y n , z).dz +e(n, N ) + n i=1 [V ion (x i ) -V ion (y i )]D N :n (t, X n , Y n ), (6)
since the last integral term coming from V ion vanishes identically; e(n, N ) stands for an error term going to zero as N → +∞. Now, it is tempting to consider the "self-consistent one-particle equation":

i∂ t ψ = - 1 2 ∆ x ψ + V ion (x)ψ + R 3 V Cou (|x -z|)|ψ(t, z)| 2 .dz ψ, (7)
for which the density reads simply ρ(t, x, y) = ψ(t, x)ψ(t, y) for x, y in R 3 . The same way, it can be shown to solve a "one-particle Von-Neumann equation",

i∂ t ρ(t, x, y) = - 1 2 [∆ x -∆ y ]ρ(t, x, y) + [V ion (x) -V ion (y)]ρ(t, x, y) +ρ(t, x, y) R 3 [V Cou (|x -z|) -V Cou (|y -z|)]ρ(t, z, z).dz , from which we infer that ρ n (t, X n , Y n ) def = n i=1 ρ(t, x i , y i
) is solution of an infinite hierarchy similar to (6):

i∂ t ρ n (t, X n , Y n ) = - 1 2 [∆ Xn -∆ Yn ]ρ n (t, X n , Y n ) + n i=1 [V ion (x i ) -V ion (y i )]ρ n (t, X n , Y n ) + n i=1 R 3(N -n) [V Cou (|x i -z|) -V Cou (|y i -z|)]ρ n+1 (t, X n , z, Y n , z).dz.
Hence it is reasonable to expect that under the same hypotheses as in [START_REF] Bardos | Derivation of the Schrödinger-Poisson equation from the quantum N-body system[END_REF], i.e. ψ 0 ∈ H 2 (R 3 ) and ( 5), the following convergence holds:

∀t ∈ R + , (x, y) ∈ R 6 , D N :1 (t, x, y) N →∞ -→ ρ(t, x, y).
By a uniqueness result for the Cauchy problem on the infinite hierarchies, [START_REF] Bardos | Derivation of the Schrödinger-Poisson equation from the quantum N-body system[END_REF], this implies that ψ solution of ( 7) is related to (4) via Ψ N (t, x 1 , ..., x N ) = coherence as time increases. All in all, mean-field provides a convenient way to compute approximately a global wave function Ψ N solution of (4) from the knowledge of a simpler one ψ solving the self-consistent problem [START_REF] Bechouche | Semiclassical limit for the Schrödinger-Poisson equation in a crystal[END_REF]; this shortcut is only meant to be relevant for large values of N ∈ N. The final step is to rewrite [START_REF] Bechouche | Semiclassical limit for the Schrödinger-Poisson equation in a crystal[END_REF] as

i∂ t ψ(t, x) = - 1 2 ∆ x ψ(t, x) + V ion ψ(t, x) + V P (t, x)ψ(t, x), (8)
where the self-consistent potential V P = V Cou * x |ψ| 2 , which is equivalent to say that V P solves the Poisson equation:

-∆ x V P (t, x) = |ψ| 2 (t, x), x ∈ R 3 . (9)
If we restrict ourselves to models endowed with translational invariance in 2 space dimensions [START_REF] Mauser | Semi)classical limits of Schrödinger-Poisson systems via Wigner transforms Journées[END_REF], a one-dimensional problem like (1) arises. The preceding derivation seems to indicate that only smooth initial data ψ(t = 0, .) = ψ 0 ∈ H 2 (R 3 ) are relevant, like in [START_REF] Bardos | Derivation of the Schrödinger-Poisson equation from the quantum N-body system[END_REF].

Bloch spectrum and the one-dimensional (linear) WKB ansatz

From the former section, one can notice that the mean-field model ( 7) is mostly concerned with a "large system" containing an infinite number of strongly delocalized valence/conduction electrons which wander inside the material. A concrete example of such a system is given by a metal cluster, see [START_REF] Brack | The physics of simple metal clusters: self-consistent jellium model and semiclassical approaches[END_REF], where N can grow from 1000 up to the Avogadro's number (which may be considered as "infinite" in practice). Typically, mean-field is too much of a rough approximation for quantum chemistry. Relying on these considerations, it is quite natural to switch to the characteristic scales of the bulk system under consideration; thus a dimensionless parameter ε is introduced, which measures the microscopicmacroscopic ratio. We can assume it small in order to look for "wave-packet solutions" of ( 7) with a spatial spreading of the order of 1/ε. Physically speaking, this means exactly that only strongly delocalized electrons wandering inside the crystal are sought.

Sticking hereafter to our one-dimensional model, we recast (1) in macroscopic variables x → x/ε, t → t/ε and taking into account for the slowly-varying exterior potential V ext , we obtain a scaled problem as in [START_REF] Gosse | Multiphase semiclassical approximation of an electron in a one-dimensional crystalline lattice -I. Homogeneous problems[END_REF][START_REF] Gosse | Multiphase semiclassical approximation of an electron in a one-dimensional crystalline lattice -II. Impurities, confinement and Bloch oscillations[END_REF],

iε∂ t ψ + ε 2 2 ∂ xx ψ = V ion x ε ψ + (V P ψ) + V ext (x)ψ, V ion (x + 2π) = V ion (x), (10)
for which V P stands for the self-consistent potential and V ext is smooth and independent of time. From now on, we assume the lattice period to be 2π on the atomic lengthscale for the sake of simplicity only.

The naive "WKB plane-wave" ansatz A(t, x) exp(iϕ(t, x)/ε) doesn't have the correct structure hence following [START_REF] Carles | Semiclassical asymptotics for weakly nonlinear Bloch waves[END_REF][START_REF] Dimassi | Semiclassical asymptotics in magnetic Bloch bands[END_REF][START_REF] Guillot | Semiclassical asymptotics in solid-state physics[END_REF], we shall consider instead a two-scale amplitude A(t, x, x/ε) exp(iϕ(t, x)/ε) as follows:

A t, x, y = x ε = A 0 (t, x, y) + εA 1 (t, x, y) + • • • ; A t, x, y + 2π = A(t, x, y) ∈ C. ( 11
)
Since we are interested in arbitrary small values of ε ≥ 0, the x ∈ R and y ∈ R variables must be uncorrelated. Taking this new dependence into account inside (10) yields the expression:

-A∂ t ϕ + 1 2 ∂ yy A -A(∂ x ϕ) 2 + 2i(∂ x ϕ)(∂ y A) -V ion (y) + V ext (x) + V P (t, x) A + iε 2 2∂ t A + A∂ xx ϕ + 2∂ x A ∂ x ϕ -2i∂ xy A + ε 2 2 ∂ xx A = 0. ( 12
)
• The O(1) terms inside [START_REF] Bouchut | Renormalized solutions to the Vlasov equation with coefficients of bounded variation Arch[END_REF] rewrite

- ∂ t ϕ + V ext (x) + V P (t, x) - 1 2 (∂ y + i(∂ x ϕ)) 2 -V ion (y) A,
thus they cancel if and only if y → A 0 (t, x, y) exp(iκy) is an eigenstate of H(p, y) = -1 2 ∂ yy + V ion (y), p = i∂ y , written in Bloch wave form, see [START_REF] Bloch | Über die Quantenmechanik der Electronen in Kristallgittern[END_REF][START_REF] Pratt | Generalization of band-theory to include self-energy corrections[END_REF] and associated to the eigenvalue

E(∂ x ϕ) = -∂ t ϕ -V ext (x) -V P (t, x): H(y, p)(A 0 exp(iκy)) = -∂ t ϕ + V ext (x) + V P (t, x) (A 0 exp(iκy)), κ = ∂ x ϕ.
That is to say, we want y → Ψ κ (y) = exp(iκy)A 0 (t, x, y) to satisfy for all (t, x) ∈ R + × R:

∀y ∈ R, H(p, y)Ψ κ = - 1 2 ∂ yy Ψ κ + V ion (y)Ψ κ = E(κ)Ψ κ . (13)
Note that the slow variable x shows up only as a parameter; thus an Hamilton-Jacobi equation has been derived from this cell problem,

∂ t ϕ + E(∂ x ϕ) + V ext (x) + V P (t, x) = 0. ( 14
)
However, it isn't clear at this level why the Poisson potential doesn't depend on the fast scale y = x/ε as A 0 does. • The second step consists in writing A 0 (t, x, y) = a 0 (t, x)z κ (y) with stationary 2π-periodic orthonormal modulations: z κ L 2 (0,2π) = 1. Then following [START_REF] Carles | Semiclassical asymptotics for weakly nonlinear Bloch waves[END_REF], the solvability condition to make O(ε) remainder terms in ( 12) vanish leads to the modified transport equation:

∂ t a 0 + E ′ (∂ x ϕ)∂ x a 0 + a 0 2 ∂ x E ′ (∂ x ϕ) + β(t, x)a 0 = 0. ( 15
)
The phase-shift term is purely imaginary; β(t, x) = iℑβ(t, x) (ℑ. standing for the imaginary part of a complex number). It is sometimes referred to as the Berry phase which stems from the interaction between the periodic lattice and the exterior potentials. However, one can always multiply (15) by 2ā 0 and take its real part in order to derive the more usual continuity equation for the intensity |a 0 | 2 :

∂ t |a 0 | 2 + ∂ x |a 0 | 2 E ′ (∂ x ϕ) = 0. ( 16
)
• We must at last indicate how to extract the Poisson potential V P from ϕ, Ψ κ and the principal amplitude a 0 . The computation is shown for the pre-caustic region, and for a smooth wave-function ψ (we recall from §2.1 that presumably,

ψ 0 ∈ H 2 (R)). Let us start from -∂ xx V P (t, x) = |ψ| 2 (t, x) = |a 0 (t, x)| 2 |z κ (x/ε)| 2 , κ = ∂ x ϕ.
Since y → z κ (y) is 2π-periodic and C ∞ (energy bands are isolated in 1d, see e.g. the introduction of [START_REF] Bechouche | Semi-classical limit of a Schrödinger equation for a stratified material Monatsh[END_REF]), it can be written as its Fourier series:

-V P (t, x) = x x ′ |a 0 (t, s)| 2 |z κ(t,s) (s/ε)| 2 .ds.dx ′ = j,j ′ ∈Z x x ′ (a 0 .a 0 )(t, s)ẑ j κ .ẑ j ′ κ exp(i(j -j ′ )s/ε).ds.dx ′ .
This self-consistent potential is defined up to 2 constants coming from boundary/decay conditions for the Poisson equation. We now integrate by parts making use of exp(i(j -

j ′ )s/ε) = -iε j-j ′ ∂ s exp(i(j -j ′ )s/ε
) and the smoothness of a 0 and z κ . The terms j = j ′ yield an adiabatic decoupling:

-V P (t, x) = x x ′ |a 0 (t, s)| 2 z κ(t,s) (.) 2 L 2 (0,2π) j∈Z |ẑ j κ | 2 =1 .ds.dx ′ + O(ε m ), (17)
where m ∈ N is the smoothness of a 0 , i.e. x → a 0 (t, x) is of class C m for t in some time interval. This is somewhat a homogenization process for the Poisson equation arising in this 1d context. In a 3-D case, a stationary phase argument on the Hartree term would (formally) give a similar result with m = 1 (see also [START_REF] Carles | Semi)classical limit of the Hartree equation with harmonic potential[END_REF][START_REF] Liu | Semiclassical limit of the non-linear Schrödinger-Poisson equation with subcritical initial data[END_REF]).

All in all, starting from the Schrödinger equation [START_REF] Besse | Convergence of a semi-lagrangian scheme for the one-dimensional Vlasov-Poisson system[END_REF], one has to consider the Bloch spectral decomposition (13) producing a countable set of distorted plane waves Ψ n κ , n ∈ N, associated to the energy bands E n (κ); consult [START_REF] Ashcroft | Solid-state physics[END_REF][START_REF] Bechouche | Semiclassical limit for the Schrödinger-Poisson equation in a crystal[END_REF][START_REF] Bloch | Über die Quantenmechanik der Electronen in Kristallgittern[END_REF][START_REF] Carles | Semiclassical asymptotics for weakly nonlinear Bloch waves[END_REF][START_REF] Dimassi | Semiclassical asymptotics in magnetic Bloch bands[END_REF][START_REF] Guillot | Semiclassical asymptotics in solid-state physics[END_REF][START_REF] Gosse | Multiphase semiclassical approximation of an electron in a one-dimensional crystalline lattice -I. Homogeneous problems[END_REF][START_REF] Gosse | Multiphase semiclassical approximation of an electron in a one-dimensional crystalline lattice -II. Impurities, confinement and Bloch oscillations[END_REF][START_REF] Markowich | A Wigner-function approach to semiclassical limits: electrons in a periodic potential[END_REF] for more details. Thus a convenient n th band ansatz reads (as in the linear case) at least before breakup,

ψ ε n (t, x) = a 0 (t, x) exp iϕ(t, x) ε z n κ (x/ε), κ = ∂ x ϕ(t, x), (18)
where the unknowns evolve according to the n th band weakly nonlinear WKB system:

∂ t ϕ+E n (∂ x ϕ)+V ext (x)+V P (t, x) = 0, ∂ t µ+∂ x E ′ n (∂ x ϕ) µ = 0, -∂ xx V P (t, x) = µ = |a 0 | 2 . ( 19
) Equations ( 18)-( 19) mean in particular that an initial datum in the n th band E n (κ), z n κ always leads to an approximate solution in the same band; hence the Poisson nonlinearity induces a behaviour not so different compared to the linear cases in [START_REF] Gosse | Multiphase semiclassical approximation of an electron in a one-dimensional crystalline lattice -II. Impurities, confinement and Bloch oscillations[END_REF]. This is one of the reasons why it is possible to extend K-branch solutions to cover the present situation.

Remark 1 The post-caustic region is more delicate to handle as we expect ϕ and µ to become multivalued as in [START_REF] Gosse | Multiphase semiclassical approximation of an electron in a one-dimensional crystalline lattice -I. Homogeneous problems[END_REF][START_REF] Gosse | Multiphase semiclassical approximation of an electron in a one-dimensional crystalline lattice -II. Impurities, confinement and Bloch oscillations[END_REF]. So, in order to remain consistent, the Poisson equation will involve µ 1,2,... plus many cross-terms which go weakly to zero (as formally shown in [START_REF] Gosse | Multiphase semiclassical approximation of an electron in a one-dimensional crystalline lattice -I. Homogeneous problems[END_REF] §3.2) except on caustics and at the edges of the Brillouin zone. Hence another O(ε) error term comes into play when neglecting them. We shall go back to that in §4.

Rigorous semiclassical limit: the Wigner-Bloch series

In this section, we shall recall briefly the main result from [START_REF] Bechouche | Semiclassical limit for the Schrödinger-Poisson equation in a crystal[END_REF] concerning the semiclassical behaviour of mixed-states for (8)-( 9), in our 1D context [START_REF] Besse | Convergence of a semi-lagrangian scheme for the one-dimensional Vlasov-Poisson system[END_REF] though. More precisely, we consider a scaled system of equations in R + × R,

iε∂ t ψ ε j + ε 2 2 ∂ xx ψ ε j = V ion x ε ψ ε j + (V ε P ψ ε j ), V ion (x + 2π) = V ion (x), ψ ε j (t = 0, x) = ψ ε j,0 (x), j ∈ N, ̺ ε (t, x) = j∈N λ ε j |ψ ε j (t, x)| 2 ; -∂ xx V ε P = ̺ ε . ( 20
)
The infinite vector (ψ ε j ) j∈N represents the quantum mixed state of the system under consideration. Furthermore, it is assumed:

λ ε j ≥ 0, j∈N λ ε j = 1, j∈N (λ ε j ) 2 ≤ O(1)ε 3 .
Then, from the Bloch decomposition recalled in §2.2, one defines the Wigner-Bloch series as follows,

w ε n (t, x, ξ) = γ∈2πZ ζ ε n,n x + ε 2 γ, x - ε 2 γ exp(-iγξ),
with ζ ε n,p standing for the Bloch density matrix built from the projectors I ε n onto the wavepacket subspaces S ε n (notation borowed from [START_REF] Gosse | Multiphase semiclassical approximation of an electron in a one-dimensional crystalline lattice -I. Homogeneous problems[END_REF], §2.3 is used here),

∀x, y ∈ R 2 , ζ ε n,p (t, x, y) = j∈N λ ε j I ε n ψ ε j (t, x)I ε p ψ ε j (t, y).
Now, let the initial data concentrate inside an isolated energy band E n (κ), like e.g. [START_REF] Carles | Semiclassical asymptotics for weakly nonlinear Bloch waves[END_REF], then it follows that, in convenient topologies,

w ε n (t, x, ξ) ε→0 ⇀ f (t, x, ξ) ≥ 0, ̺ ε (t, x) ε→0 ⇀ ̺(t, x) := 1 2 -1 2 f (t, x, ξ).dξ, V ε P → V P .
Moreover, the kinetic distribution f satisfies the semiclassical (n th band) Vlasov-Poisson equation,

∂ t f + E ′ n (ξ)∂ x f -∂ x V P (t, x)∂ ξ f = 0, -∂ xx V P = ̺, (21)
in the sense of distributions. One sees here one big advantage in using WKB methods in the present context when compared to Wigner techniques. Indeed, WKB construction delivers a rather simple expression [START_REF] Carles | Semiclassical asymptotics for weakly nonlinear Bloch waves[END_REF] for a wave function belonging to the n th energy band and approximately satisfying (1) for t ≥ 0 and ε positive but small enough through the solving of [START_REF] Carles | Semi)classical limit of the Hartree equation with harmonic potential[END_REF]. In sharp constrast, Wigner techniques furnish only information on the ideal ε = 0 case discarding fine-scale modulations z n κ (./ε); it would therefore be more difficult to study numerically the weak consistency of physical observables relying on this approach, left apart the more singular moment systems admitting measure-valued solutions, see [START_REF] Gosse | Two moment systems for computing multiphase semiclassical limits of the Schrödinger Equation[END_REF][START_REF] Shi Jin | Multi-phase computations of the semiclassical limit of the Schrödinger equation and related problems: Whitham vs[END_REF][START_REF] Runborg | Some new results in multiphase geometrical optics[END_REF][START_REF] Talenti | Recovering a function from a finite number of moments[END_REF]. However, results of this type do provide a guideline as we shall see in the forthcoming section.

3 K-branch solutions with a weak nonlinearity K-branch solutions, see e.g. [START_REF] Brenier | A kinetic formulation for multibranch entropy solutions of scalar conservation laws[END_REF][START_REF] Gosse | Using K-branch entropy solutions for multivalued geometric optics computations[END_REF][START_REF] Gosse | A case study on the reliability of multiphase WKB approximation for the one-dimensional Schrödinger equation, to appear[END_REF][START_REF] Runborg | Some new results in multiphase geometrical optics[END_REF], have been used up to now exclusively in the context of linear dispersive equations. Hence we must show now how to adapt this tool in order to tackle the weakly nonlinear problem [START_REF] Carles | Semi)classical limit of the Hartree equation with harmonic potential[END_REF].

Lagrangian solutions for Vlasov-Poisson in 1D with V ′

ext ≡ 0

The Hamilton-Jacobi equation in ( 19) must be considered in a "geometric sense", i.e. relying on the method of characteristics. We also want our framework to be fully consistent with the "ideal case" ε = 0 studied in [START_REF] Bechouche | Semiclassical limit for the Schrödinger-Poisson equation in a crystal[END_REF][START_REF] Mauser | Semi)classical limits of Schrödinger-Poisson systems via Wigner transforms Journées[END_REF][START_REF] Zhang | The limit from the Schrödinger-Poisson to the Vlasov-Poisson equations with general data in one dimension Comm[END_REF] by means of Bloch-Wigner series where a (n th band) Vlasov-Poisson equation is derived,

∂ t f + ∂ x (E ′ n (ξ)f ) + ∂ ξ (F (t, x)f ) = 0, f (t = 0, x, ξ) = f 0 (x, ξ), (22)
and where F (t, x) stands for the electric field F = -∂ x V P . We aim at building solutions by means of a method which can easily be implemented on a computer. So, following a recent paper by Brenier, [START_REF] Brenier | Derivation of the Euler equations from a caricature of Coulomb interaction[END_REF], we start with a N -particle density function,

f N (t, x, ξ) = 1 N N α=1 δ(x -X α (t))δ(ξ -U α (t)), t ≥ 0, δ (
.) the Dirac measure in 0, which evolves according to the differential system:

Ẋα (t) = E ′ n (U α )(t), Uα (t) = F (t, X α (t)). ( 23
)
The trick is based on the fact that the Laplacian's Green function in 1d is but the Heaviside function H; accordingly,

∂ x F (t, x) = R f N (t, x, ξ).dξ = 1 N N α=1 δ(x -X α (t)),
which yields:

F (t, x) = 1 N N α=1 H(x -X α (t)), H(0) = 1 2 . ( 24
)
From [START_REF] Bouchut | Renormalized solutions to the Vlasov equation with coefficients of bounded variation Arch[END_REF][START_REF] Brenier | Derivation of the Euler equations from a caricature of Coulomb interaction[END_REF], we know that the nonlinear differential system ( 23)-( 24) is well-posed in phase-space for any value N ∈ N thus we get:

Ẋα (t) = E ′ n (U α )(t), Uα (t) = 1 N N β=1 H(X α (t) -X β (t)).
We stress that, since N ∈ N is finite, this is but a 2N ×2N autonomous first-order differential system with a BV right-hand side. So the associated Liouville equation is linear and the renormalization property of [START_REF] Bouchut | Renormalized solutions to the Vlasov equation with coefficients of bounded variation Arch[END_REF] fully applies hence ensures well-posedness. However, we now intend to pass formally to the continuous limit N → ∞ hence f (t, x, ξ) = R δ(x -X(t, α))δ(ξ -U (t, α)).dα for which ( 23)-( 24) boils down to:

∂ t X(t, α) = E ′ n (U (t, α)), ∂ t U (t, α) = R 0 H(X(t, α) -X(t, α ′ )).dα ′ , (25)
where R = a 0 (t = 0, .) 2 L 2 (R) . This is a one-dimensional bicharacteristics system for the semiclassical Vlasov-Poisson equation and we shall interpret [START_REF] Carles | Semi)classical limit of the Hartree equation with harmonic potential[END_REF] in this "geometric sense" hereafter, see also Remark IV.6 in [START_REF] Lions | Sur les mesures de Wigner[END_REF]. Of course, the symbol α which refers to the Lagrangian mass variable has here a completely different meaning compared to [START_REF] Mauser | Schrödinger-Poisson-Xα model[END_REF].

Let us now show that this (Lagrangian) construction is consistent with [START_REF] Engquist | Computational high frequency wave propagation[END_REF]:

d dt R f (t, x, ξ)φ(x, ξ).dx.dξ = d dt R φ(X(t, α), U (t, α)).dα = R {∂ x φ(X, U )∂ t X + ∂ ξ φ(X, U )∂ t U }(t, α).dα = R {∂ x φ(X, U )E ′ n (U (t, α)) + ∂ ξ φ(X, U )F (t, X(t, α))}.dα = R f (t, x, ξ){∂ x φ(x, ξ)E ′ n (ξ) + ∂ ξ φ(x, ξ)F (t, x)}.dx.dξ.
The third step uses the definition of the differential system (25) and the last one is just a consequence of the definition of f by means of Dirac masses. So clearly we have derived a weak formulation of ( 22) for any test function φ ∈ C 1 (R 2 ). At last, the case V ′ ext = 0 can be handled by replacing 23) and so on.

F (t, X α (t)) by F (t, X α (t)) -V ′ ext (X α (t)) in (

Consistency of bicharacteristics' system (25) before breakup

We shall consider monokinetic initial data, like in [START_REF] Zhang | The limit from the Schrödinger-Poisson to the Vlasov-Poisson equations with general data in one dimension Comm[END_REF],

f (t = 0, x, ξ) = ̺ 0 (x)δ(ξ -u 0 (x)), ̺ 0 = a 2 0 ≥ 0,
which leads to a monokinetic solution ̺(t, x)δ(ξ -u(t, x)) at least for some time if ̺ 0 , u 0 are smooth, [START_REF] Liu | Semiclassical limit of the non-linear Schrödinger-Poisson equation with subcritical initial data[END_REF]. Indeed we can initialize [START_REF] Gosse | A case study on the reliability of multiphase WKB approximation for the one-dimensional Schrödinger equation, to appear[END_REF] as follows:

X(t = 0, α) = X 0 (α), U (t = 0, α) = u 0 (X 0 (α)), ( 26
)
with X 0 the reciprocal mapping of ̺ 0 (i.e. the pseudo-inverse of the antiderivative of ̺ 0 ) in the sense of [START_REF] Gosse | Identification of asymptotic decay to self-similarity for one-dimensional filtration equations[END_REF]. That is to say, we consider r 0 (x) =

x -∞ ̺ 0 (s).ds, an increasing function. There obviously holds lim x→+∞ r 0 (x) = a 0 (t = 0, .) 2 L 2 (R) = R; usually R = 1 because of the probabilistic interpretation of the kinetic distribution. The reciprocal mapping X 0 is defined as a pseudo-inverse of r 0 , i.e.,

X 0 : [0, 1] → R α → X 0 (α) := inf sup{y ∈ R such that r 0 (y) = α}. ( 27
)
Now, by definition ( 27), X 0 is a solution at time t = 0 of the Jacobian equation:

̺(t, X(t, α)) ∂X ∂α (t, α) = 1. ( 28
)
Pushing further, one observes from ( 19) that r(t, x), any antiderivative of µ, solves the transport equation ∂ t r + E ′ (u)∂ x r = 0; hence α = r(t, X(t, α)) = r 0 (α) holds before breakup. Moreover, assuming the solution of ( 25)-( 26) being given (by a suitable extension of the recent theorems in [START_REF] Ambrosio | Transport equation and Cauchy problem for BV vector fields[END_REF][START_REF] Bouchut | Renormalized solutions to the Vlasov equation with coefficients of bounded variation Arch[END_REF][START_REF] Zhang | The limit from the Schrödinger-Poisson to the Vlasov-Poisson equations with general data in one dimension Comm[END_REF]), let us consider any function σ(t, x) satisfying ( 28) with σ(t = 0, x) = ̺ 0 (x). This means that for any continuous test-function

φ ∈ C 0 (R), R φ(X(t, α)).dα = R φ(x)σ(t, x).dx.
Then, differentiating on both sides with respect to time and using ( 25) leads to:

R φ(x)∂ t σ(t, x) = R ∂ x φ(X(t, α))E ′ n (U (t, α)).dα = R ∂ x φ(x)E ′ n (u)(t, x).σ(t, x).dx,
which is but a weak formulation of the continuity equation ∂ t σ + ∂ x (σE ′ n (u)) = 0 holding for t → σ(t, .) smooth enough. Hence by a uniqueness result 4 , we have σ(t, .) = ̺(t, .) since intial data coincide.

A consequence is that for any φ ∈ C 0 (R 2 ) and X, U solution of ( 25)-( 26), there holds: R δ(x-X(t, α))δ(ξ-U (t, α))φ(x, ξ).dx.dξ = R φ(X, U )(t, α).dα = R φ(x, u(t, x))̺(t, x).dx, with u(t, .) implicitly defined by u(t, X(t, α)) = U (t, α) as long as α → X(t, α) remains a diffeomorphism (an admissible change of variables!). This precisely means that the density built out of ( 25)-( 26) reads f (t, x, ξ) = ̺(t, x)δ(ξ -u(t, x)) on this time interval.

Updating the intensities within a time-marching scheme

We have presented in the former section a Lagrangian framework to solve the Vlasov-Poisson equation [START_REF] Engquist | Computational high frequency wave propagation[END_REF]. Following [START_REF] Keller | Semiclassical mechanics[END_REF], the WKB strategy can be seen as a mean to manufacture

4 A simple energy estimate gives d dt R σ 2 2 .dx = -R σ(∂ x σ)E ′ n (u).dx = R σ 2 2 ∂ x E ′ n (u)
.dx which makes sense for Lipschitz u's.

a quantum wave function starting from the knowledge of the classical motion in phase space. The theory of "K-branch solutions" [START_REF] Brenier | A kinetic formulation for multibranch entropy solutions of scalar conservation laws[END_REF][START_REF] Gosse | Using K-branch entropy solutions for multivalued geometric optics computations[END_REF][START_REF] Runborg | Some new results in multiphase geometrical optics[END_REF] is well-suited5 to compute efficiently multivalued velocities u = ∂ x ϕ (or crystal momentum); it is moreover easier to handle when compared to the processing of the full moment systems emanating from a Wigner analysis, see [START_REF] Sparber | Multivalued geometrical optics: Wigner functions vs. WKB methods[END_REF][START_REF] Shi Jin | Multi-phase computations of the semiclassical limit of the Schrödinger equation and related problems: Whitham vs[END_REF][START_REF] Gosse | Multiphase semiclassical approximation of an electron in a one-dimensional crystalline lattice -I. Homogeneous problems[END_REF][START_REF] Gosse | Two moment systems for computing multiphase semiclassical limits of the Schrödinger Equation[END_REF][START_REF] Gosse | A case study on the reliability of multiphase WKB approximation for the one-dimensional Schrödinger equation, to appear[END_REF]. Indeed, as the treatment of the corresponding (possibly multivalued) intensities µ is decoupled, moment systems become less singular hence less demanding at a computational level. In return, original algorithms have to be devised in order to update µ at each time-step: in [START_REF] Gosse | Multiphase semiclassical approximation of an electron in a one-dimensional crystalline lattice -I. Homogeneous problems[END_REF][START_REF] Gosse | A case study on the reliability of multiphase WKB approximation for the one-dimensional Schrödinger equation, to appear[END_REF], some sort of "backwards ray-tracing" has been introduced (because the bicharacteristics are straight lines for homogeneous problems) whereas the conservation of the Hamiltonian along trajectories in phase space has been used in [START_REF] Gosse | Multiphase semiclassical approximation of an electron in a one-dimensional crystalline lattice -II. Impurities, confinement and Bloch oscillations[END_REF].

Both techniques fail when considering the Poisson coupling here; however, an algorithm consistent with the analysis of §3.1 can be easily deduced. Indeed, the right-hand side of the second equation in [START_REF] Gosse | A case study on the reliability of multiphase WKB approximation for the one-dimensional Schrödinger equation, to appear[END_REF] corresponds to the field created by all the electrons located on the left of the one at X(t, α); this is what is needed in order to set up a semi-lagrangian scheme.

From now on, ∆x and ∆t will stand for the usual parameters of a cartesian grid in the t, x-plane and we assume the reader familiar with the numerical schemes of [START_REF] Gosse | Multiphase semiclassical approximation of an electron in a one-dimensional crystalline lattice -I. Homogeneous problems[END_REF][START_REF] Gosse | Multiphase semiclassical approximation of an electron in a one-dimensional crystalline lattice -II. Impurities, confinement and Bloch oscillations[END_REF] which generate u n j = (u k=1,...,K ) n j , an approximation of u(t n = n∆t, x j = j∆x) ∈ R K for j, n ∈ Z × N. Then let us consider an auxiliary quantity F k (t, x) at each time-step; at time t = 0, it is defined as follows:

F k (t = 0, x j ) = xj µ k (t = 0, s).ds = xj |a 0 | 2 (t = 0, s).ds, k = 1, ..., K.
Once again, this quantity is defined up to a constant coming from the Poisson equation. Then, as an antiderivative of µ k , each F k solves a transport equation

∂ t . + u k ∂ x . = 0 (see §3.
2), so from ( 18), ( 25) and [START_REF] Gosse | Multiphase semiclassical approximation of an electron in a one-dimensional crystalline lattice -II. Impurities, confinement and Bloch oscillations[END_REF] §3.1, we update it at every time-step like

F k t n+1 , x j + E ′ (u k (t n , x j ))∆t = F k (t n , x j ), k = 1, ..., K,
for some energy band κ → E(κ) corresponding to the initial data [START_REF] Carles | Semiclassical asymptotics for weakly nonlinear Bloch waves[END_REF]. It is easy to interpolate the values F k (t n+1 , .) on the original Eulerian grid x j = j∆x for instance by means of quadratic splines just solving a 3 × 3 Vandermonde system in every computational cell (see [START_REF] Besse | Convergence of a semi-lagrangian scheme for the one-dimensional Vlasov-Poisson system[END_REF] for some mathematical properties of interpolation operators in a related context). Intensities µ k (t n+1 , x j ) := ∂ x F k (t n+1 , x j ) can be recovered by means of e.g. centered differences, as in [START_REF] Gosse | Identification of asymptotic decay to self-similarity for one-dimensional filtration equations[END_REF]. Now, in order to compute an approximation of u(t n+1 , x j ), a value for the electric field independent of k can be deduced:

R ∋ F (t n+1 , x j ) = k s.t. |F k (t n+1 ,xj )-F k-1 (t n+1 ,xj )|>∆x F k (t n+1 , x j ),
where we chosed arbitrarily ∆x to be the threshold value (this can be seen as the correct answer to the issue raised in [START_REF] Gosse | Multiphase semiclassical approximation of an electron in a one-dimensional crystalline lattice -II. Impurities, confinement and Bloch oscillations[END_REF], Appendix A). This means that, in case several electrons with different momenta u k show up at x j , the total electric field is given by summing the fields F k produced by each electron, as written in [START_REF] Gosse | A case study on the reliability of multiphase WKB approximation for the one-dimensional Schrödinger equation, to appear[END_REF]. At last, the velocities can be updated by e.g. a simple extension of the "Riemann split-schemes" of [START_REF] Gosse | Multiphase semiclassical approximation of an electron in a one-dimensional crystalline lattice -II. Impurities, confinement and Bloch oscillations[END_REF], §2.3. Of course, the aforementioned algorithm can be used for simpler cases, like for instance the ones presented in [START_REF] Gosse | Multiphase semiclassical approximation of an electron in a one-dimensional crystalline lattice -II. Impurities, confinement and Bloch oscillations[END_REF]. At last, in case V ′ ext = 0, one has to include the corresponding terms in the moment system's right-hand side, see again [START_REF] Gosse | Multiphase semiclassical approximation of an electron in a one-dimensional crystalline lattice -II. Impurities, confinement and Bloch oscillations[END_REF].

Remark 2 (Consistency with the δ-closure, [START_REF] Shi Jin | An Eulerian method for computing multi-valued solutions of the Euler-Poisson equations and applications to wave breaking in klystrons[END_REF]) It isn't easy at this level to state whether or not the approximate solutions [START_REF] Carles | Semiclassical asymptotics for weakly nonlinear Bloch waves[END_REF] built out of the aforementioned algorithm are consistent with the ones obtained in [START_REF] Shi Jin | An Eulerian method for computing multi-valued solutions of the Euler-Poisson equations and applications to wave breaking in klystrons[END_REF]. First, in case K is chosen too low, they will surely be different as they already are in the linear case, as seen in [START_REF] Gosse | Two moment systems for computing multiphase semiclassical limits of the Schrödinger Equation[END_REF]. Now, even if K is big enough, one should need a genuine comparison with Schrödinger computations since there is no uniqueness result for the Vlasov-Poisson equation with measure-data, [START_REF] Zhang | The limit from the Schrödinger-Poisson to the Vlasov-Poisson equations with general data in one dimension Comm[END_REF].

Numerical experiments

We want now to check numerically the outcome of our WKB approach by a systematic comparison with the quadratic observables coming out of a Fourier scheme [START_REF] Bao | On time-splitting spectral approximations for the Schrödinger equation in the semiclassical regime[END_REF] for the Schrödinger-Poisson equation [START_REF] Besse | Convergence of a semi-lagrangian scheme for the one-dimensional Vlasov-Poisson system[END_REF] as done in [START_REF] Gosse | Multiphase semiclassical approximation of an electron in a one-dimensional crystalline lattice -I. Homogeneous problems[END_REF][START_REF] Gosse | Multiphase semiclassical approximation of an electron in a one-dimensional crystalline lattice -II. Impurities, confinement and Bloch oscillations[END_REF] for the linear case. We shall use the same parameter, namely δt = 0.01 6 . Following [START_REF] Brenier | Sticky particles and scalar conservation laws[END_REF], we tried to check on right column a weak convergence as ε → 0 by looking at the antiderivative of the difference of the position densities (the first quadratic observable); thus we shall study the function

x → x 0 ̺ ε W KB (T, s) -|ψ ε (T, s)| 2 .ds, (29)
which can be expected to flatten as ε is decreased. ̺ ε W KB stands for the position density obtained from the WKB ansatz [START_REF] Carles | Semiclassical asymptotics for weakly nonlinear Bloch waves[END_REF] as done in [START_REF] Gosse | Multiphase semiclassical approximation of an electron in a one-dimensional crystalline lattice -I. Homogeneous problems[END_REF][START_REF] Gosse | Multiphase semiclassical approximation of an electron in a one-dimensional crystalline lattice -II. Impurities, confinement and Bloch oscillations[END_REF]. Lemma 2.1 in [START_REF] Brenier | Sticky particles and scalar conservation laws[END_REF] ensures that the L 1 norm of ( 29) going to zero is equivalent to the weak convergence of ρ ε W KB . It appeared absolutely necessary to filter numerically the input or the outcome of the Fourier schemes; here we used a standard convolution receipe involving a Gaussian kernel exp(-aξ 2 ), a ∈ R + . Different values of a have been used, from 0.01 to 0.1. More precisely, to initialize the Fourier time-split schemes, we shall always use

1 √ 2π √ πa R ψ ε n (0, s) exp(-(x -s) 2 /4a).ds ⇔ ψε n (0, ξ) exp(-aξ 2 ),
instead of (18); of course, letting a → 0, one recovers the correct initial signal.

Free self-consistent electron cloud

This first test-case corresponds to [START_REF] Besse | Convergence of a semi-lagrangian scheme for the one-dimensional Vlasov-Poisson system[END_REF] with constant ionic and exterior potentials; of course this leads to a trivial Bloch decomposition with a unique energy band E(κ) = κ 2 2 , an infinite Brillouin zone and constant modulations involved. The WKB system [START_REF] Carles | Semi)classical limit of the Hartree equation with harmonic potential[END_REF] is just made of the classical Eikonal/continuity equations (as in [START_REF] Gosse | Using K-branch entropy solutions for multivalued geometric optics computations[END_REF][START_REF] Gosse | A case study on the reliability of multiphase WKB approximation for the one-dimensional Schrödinger equation, to appear[END_REF]) coupled by the Poisson potential. We selected the following initial data, inspired by [START_REF] Gosse | Two moment systems for computing multiphase semiclassical limits of the Schrödinger Equation[END_REF][START_REF] Gosse | Finite moment problems and applications to multiphase computations in geometric optics[END_REF]:

u 0 (x) = sin(x)| sin(x)|, µ 0 (x) = exp(-(x -π) 2 )/2π, (30)
which leads to a 5-branch solution after some time. The inversion routines of [START_REF] Gosse | Finite moment problems and applications to multiphase computations in geometric optics[END_REF] have been used to generate the results of Figs.1 (T = 0.5), 2 and 3 (T = 2.5), pre-and postbreakup respectively. 512 points of discretization have been used for both methods; the CFL number has been chosen to be 0.95. Beyond caustic onset, one observes the appearance of the double cusp on Fig. 2; there is a quite good agreement between the WKB approximation and the direct Schrödinger computation in both logarithmic and normal scales away from caustics. One can observe the nice convergence in log-scale as ε is decreased on Figs. 1 and3; interestingly, the two curves look similar despite bigger errors in the 5-valued context. Notingly, the 5-valued region x ∈ [2.5, 3.5] seems to produce the right values for the position density. Finally, it seems that the error terms coming from multivaluations are indeed of little influence when carrying out practical computations: this (partially) answers the question raised in Remark 1.

Self-consistent electron cloud within Mathieu's potential

This test-case corresponds to [START_REF] Besse | Convergence of a semi-lagrangian scheme for the one-dimensional Vlasov-Poisson system[END_REF] with V ion (x) = cos(x) and V ′ ext ≡ 0. The main novelty with respect to the former one lies in the handling of the Bloch decomposition and the energy bands when computing the moment systems which govern the evolution of the K-branch solutions; this has been done according to the routines proposed in [START_REF] Gosse | Multiphase semiclassical approximation of an electron in a one-dimensional crystalline lattice -I. Homogeneous problems[END_REF][START_REF] Gosse | Multiphase semiclassical approximation of an electron in a one-dimensional crystalline lattice -II. Impurities, confinement and Bloch oscillations[END_REF]. We selected an initial datum leading only to a 3-branch solution,

u 0 (x) = 0.3 sin(x), µ 0 (x) = 0.3 exp(-(x -π) 2 )/π. ( 31
)
Since the Poisson term is repulsive, a strong initial position density prevents numerous multivaluations to develop in the solution. The 3-branch solutions are displayed on Fig. 4 where the dispersive effect of the repulsive Poisson term is clearly seeable. We compared with a direct Schrödinger computation at time T = 2, see Fig. 5. The agreement looks satisfying away from caustics; even the central spike is produced by both schemes. A decay of the L 1 norm of (29) in T = 2 (and even a harsh strong L 1 convergence) has also been observed 7 , see Fig. 6. The error coming from the spurious blowup on the caustics seems to decrease and the results in the multivalued region contribute at most up to 10% of the overall (as seen on the antiderivatives of the postion densities' difference, right of Fig. 6). We believe that the slight increase of the L 1 norm of (29) as ε ≃ 1/40 comes from a shortage of Fourier modes; 512 points of discretization have been used here.

It is interesting to notice that one main difference with §4.1 is the number of multivaluations; hence part of the error reported on Fig. 3 with respect to Fig. 6 comes from the algorithm used to invert Markov's moment problem as proposed in [START_REF] Gosse | Finite moment problems and applications to multiphase computations in geometric optics[END_REF]. Also the simulation of a bigger hyperbolic moment system is likely to produce slightly higher truncation errors.

A smoothered model for screening

The situation described now is still given by V ion (x) = cos(x) supplemented by an exterior Coulomb term V ext (x) = -1 |x-x0| ; i.e. a potential induced by an impurity inside the periodic lattice. It has already been studied in [START_REF] Gosse | Multiphase semiclassical approximation of an electron in a one-dimensional crystalline lattice -II. Impurities, confinement and Bloch oscillations[END_REF] in a linear context, that is to say, without considering any self-interaction among the electrons. Roughly speaking, V ext creates a potential well around x 0 , but the repulsive Poisson term has the opposite effect and both mechanisms should balance after some transient regime. However, it hasn't been possible to work with the normal Coulomb term because it is too singular; hence we turned back to a smoother potential,

V ext (x) = -cos(0.5(π -x)) 2 . The initial data are rather simple: Results at time T = 2 are shown in Fig. 7. The validation is done by means of a comparison with a direct Schrödinger computation with 1024 Fourier modes in Fig. 8. It's been more difficult to obtain a reliable outcome while decreasing the parameter ε thus we show a decay of the L 1 norm of (29) only for moderate values, see Fig. 9. We notice that for ε ∈ [1/25, 1/5], the weak consistency is quite satisfying.

u 0 ≡ 0, µ 0 (x) = exp(-(x -π) 2 )/2π.

Conclusion and outlook

An extension of the Homogenization/WKB techniques to the weakly nonlinear Schrödinger-Poisson equation has been introduced, in the spirit of [START_REF] Bechouche | Semiclassical limit for the Schrödinger-Poisson equation in a crystal[END_REF][START_REF] Zhang | The limit from the Schrödinger-Poisson to the Vlasov-Poisson equations with general data in one dimension Comm[END_REF]. It somehow "closes a loop" initiated in the joint work [START_REF] Gosse | Multiphase semiclassical approximation of an electron in a one-dimensional crystalline lattice -I. Homogeneous problems[END_REF] and the earlier ones [START_REF] Gosse | Using K-branch entropy solutions for multivalued geometric optics computations[END_REF][START_REF] Runborg | Some new results in multiphase geometrical optics[END_REF]. The validation of our numerical algorithms has been entirely done by systematic comparisons of quadratic observables with the ones obtained from direct computations on Schrödinger-Poisson models with timesplitting Fourier schemes. A clean convergence of the position densities has been observed for problems of increasing difficulty. This confirms the results from [START_REF] Gosse | A case study on the reliability of multiphase WKB approximation for the one-dimensional Schrödinger equation, to appear[END_REF] concerning the validity of these 1D WKB techniques with K-branch solutions, [START_REF] Brenier | A kinetic formulation for multibranch entropy solutions of scalar conservation laws[END_REF][START_REF] Gosse | Using K-branch entropy solutions for multivalued geometric optics computations[END_REF][START_REF] Gosse | Finite moment problems and applications to multiphase computations in geometric optics[END_REF][START_REF] Runborg | Some new results in multiphase geometrical optics[END_REF], even for weakly nonlinear problems of the type [START_REF] Ambrosio | Transport equation and Cauchy problem for BV vector fields[END_REF]. Indeed one could be tempted to go down this track and study the semi-classical limit of the so-called Xα equation heuristically derived in [START_REF] Mauser | Schrödinger-Poisson-Xα model[END_REF] which reads:

i ∂ t ψ + 2 2m ∂ xx ψ = e V ion (x) + V ext (x) + V P (t, x) -α|ψ| 2 3 ψ, -ǫ 0 ∂ xx V P = e|ψ| 2 . ( 32
)
The strong focusing nonlinearity emanating from Pauli's exclusion principle forbids to apply any known technique to obtain rigorously the semiclassical behaviour of ψ, see [START_REF] Carles | Semi)classical limit of the Hartree equation with harmonic potential[END_REF]. However, the local exchange term -αρ = α( ǫ0 e ∂ xx V P ) might be treated as a small perturbation (for α below a critical threshold, [START_REF] Bao | Effective one particle quantum dynamics of electrons: a numerical study of the Schrödinger-Poisson-Xα model[END_REF]) inside the present approach. At best, this equation is likely to describe ballistic transport of electron ensembles inside solid-state materials. These basic concepts don't address the issue of collisions (phonons, impurities, see [START_REF] Ashcroft | Solid-state physics[END_REF]); they are incorporated by linking the ballistic quantum transport picture to a classical Boltzmanntype equation and by assuming that quantum effects and collisions aren't relevant in the same computational subdomains, see [START_REF] Benabdallah | Coupling one-dimensional time-dependent classical and quantum transport models[END_REF].

Fig. 1 .

 1 Fig. 1. Comparison of position densities in T = 0.5 with ε = 1/25 (left) and decay of (29) as ε → 0 (right).

Fig. 2 . 5 -

 25 Fig. 2. 5-branch velocity (left) and corresponding intensities (right) at time T = 2.5.

Fig. 3 .

 3 Fig. 3. Comparison of position densities in T = 2.5 with ε = 1/10, 1/25, 1/40 and decay of (29) as ε → 0 (left to right, top to bottom).

Fig. 4 . 3 -

 43 Fig. 4. 3-branch velocities (left) and corresponding intensities for Mathieu's potential at times T = 0.5, 1.5, 2, 2.5, 3.5 (top to bottom).

Fig. 5 .

 5 Fig. 5. Comparison of position densities in T = 2.5 with ε = 1/10 (left) and ε = 1/40 (right) in logarithmic (top) and normal (bottom) scales.

6 .Fig. 7 . 3 -Fig. 8 .Fig. 9 .

 67389 Fig. 7. 3-branch velocity (left) and corresponding intensities (right) at time T = 2.

7

  Compare especially with Figures 11 and 12 in [26].

A Slater determinant,[START_REF] Ashcroft | Solid-state physics[END_REF], could be considered instead

N i=1 ψ(t, x i ), up to an error that goes eventually to zero as N → ∞. This expresses the fact that electrons remain in[START_REF] Bao | On time-splitting spectral approximations for the Schrödinger equation in the semiclassical regime[END_REF] after Born, Bogolyubov, Green, Yvon and Kirkwood.

Namely, this "interpolation between geometric and viscosity solutions" essentially leads to K × K moment systems from which f (t, x, ξ) can be exactly recovered as long as K is big enough; otherwise entropy is produced through compressive Lax shocks and irreversibility appears.

The notation ∆t refers to the time-step used to compute the solution of hyperbolic moment systems. δt stands for the one used in the time-splitting Fourier schemes.


Stéphane Weiss
email: weiss@loria.fr

Pascal Urso
email: urso@loria.fr

Pascal Molli
email: molli@loria.fr

Wooki: a P2P Wiki-based Collaborative Writing Tool

Wiki systems are becoming an important part of the information system of many organisations and communities. This introduce the issue of the data availability in case of failure, heavy load or off-line access. We propose to replicate wiki pages across a P2P network of wiki engines. We address the problem of consistency of replicated wiki pages in the context of a P2P wiki system. In this paper, we present the architecture and the underlying algorithms of the wooki system. Compared to traditional wikis, Wooki is P2P wiki which scales, delivers better performances and allows off-line access.

Introduction

Currently, wikis are the most popular collaborative editing systems. They allow people to easily create and modify content on the web. This ease of interaction and operation makes a wiki an effective tool for collaborative writing. Collaborative writing is becoming increasingly common; often compulsory in academic and corporate work. Writing scientific articles, technical manuals and planning presentations are a few examples of common collaborative writing activities.

A lot of critical data are now under the control of wiki systems. Wikis are now used within enterprises or organizations. For example, United States intelligence community uses Intellipedia for managing national security informations. Wikis are now an important piece in the information system of many large organizations and communities. This introduces the issue of data availability in case of failure, heavy load or off-line access.

Current wiki systems are intrinsically centralized. Consequently, in case of failure or off-line work, data are unavailable. In case of heavy load, the system scales poorly and the cost linked to underlying hardware cannot be shared. Our objective is to replace the centralized architecture of a wiki server by a P2P network of wiki servers. This makes the whole wiki system fault tolerant, this allows to balance the load on the network and finally costs of the underlying hardware can be shared between different organizations.

This approach supposes that wiki data are replicated on a P2P network of wiki sites. Consequently, the main problem is how to manage replicate consistency between wiki sites. Traditional pessimistic replication approaches (Distributed Database, ...) ensure consistency but are not adapted to this context. They scale poorly and do not support off-line work. Optimistic replication approaches suppose to know how to safely merge concurrent updates. Some previous work tried to build a P2P wiki [START_REF]Reliable Software[END_REF][START_REF] Kang | Repliwiki: A next generation architecture for wikipedia[END_REF] relying on distributed version control system (DVCS) approaches. The main problem with DVCS approach is correctness. An optimistic replicated system is considered as correct if it eventually converges i.e., when the system is idle all sites contain identical data. This is called eventual consistency [START_REF] Saito | Optimistic replication[END_REF]. DVCS have never ensured this property. Consequently, building a P2P system with a DVCS will not ensure eventual consistency. Other approaches ensure convergence [START_REF] Ellis | Concurrency control in groupware systems[END_REF][START_REF] O'brien | An application framework for nomadic, collaborative applications[END_REF] but are not compatible with P2P networks constraints. Finally, other approaches converge and are adequate with P2P constraints but do not support collaborative editing constraints.

We developed the woot [START_REF] Oster | Data consistency for P2P collaborative editing[END_REF] algorithm to manage consistency of a replicated linear structure in a P2P environment. This algorithm ensures convergence without managing versions. In this paper, we describe how we built Wooki. Wooki is a fully functional P2P wiki system based on this algorithm. We refined the original algorithm to achieve a better time complexity. We combined this new algorithm with a probabilistic dissemination algorithm for managing updates propagation on the overlay network and with an anti-entropy algorithm for managing failures and disconnected sites. Wooki is currently available under GPL license.

The Wooki approach

A wooki network is a dynamic p2p network where any site can join or leave at any time. Each site has a unique identifier named siteid. Site identifiers are totally ordered. Each site replicates wiki pages of other sites. Each site only requires a partial knowledge of the whole network. There is three main components in a wooki site (figure 1). The core component wooto which is in charge of generating and integrating operations affecting the documents. Another component is in charge of user interface. The last component is in charge of disseminating local operations and retrieving remote operations.

Wooto Approach

Wooto is an optimized version of woot [START_REF] Oster | Data consistency for P2P collaborative editing[END_REF]. A wooki page is identified by a unique identifier pageid. This identifier is set when the page is created. This identifier is the name of the created wiki page. If some sites create concurrently pages with the same name, their content will be directly merged by the wooto algorithm. A wooki page contains a sequence of four-tuples < idl, content, degree, visibility >, where each tuple represents a line of the wooki page.

idl is the unique identifier of the line. This id is a pair (siteid, logicalclock). Each site maintains a logical clock [START_REF] Lamport | Time, clocks, and the ordering of events in a distributed system[END_REF]. Each time an operation is generated, the logical clock is incremented. The line identifiers are strictly totally ordered. Let idl1 and idl2 be two line identifiers with their respective values (s1, l1) and (s1, l2). We get idl1 < id idl2 if and only if (1) s1 < s2 or (2) s1 = s2 and l1 < l2. content is a string representing the content of the wiki-readable line. degree is an integer used by the wooto algorithm. The degree of a line is fixed when the line is generated. We will describe how the degree is computed when we will describe the generation of an operation. visibility is a boolean representing if a line is visible or not. It means that in the wooki approach, we do not delete lines, we mark them as invisible.

By applying this storage model, if we have the following wiki page:

=== Three p i g s === * [ [ Image : p i g . png | thumb | l e f t | 1 0 0 px | r i r i ] ] f i f i and l o u l o u
Assuming these three lines were generated on site number 1 in this order and assuming there is no invisible lines, the wiki page will be internally stored as:

((1 ,1) ,=== Three p i g s ===,0, t r u e ) ( ( 1 , 2 ) , * [ [ Image : p i g . png | thumb | l e f t | 1 0 0 px | r i r i ] ] , 1 , t r u e ) ( ( 1 , 3 ) , f i f i and l o u l o u , 2 , t r u e )
To manage the storage model, the Wooki handles two operations: the insertion and the deletion of a line. As in traditional version control systems, there is no operation of line update.

1. Insert(pageid, line, l P , l N ) where pageid is the page where to insert the line line =< idl, content, degree, visibility >. l P and l N are the id of the previous and the next lines.

2. Delete(pageid, idl) sets visibility of the line identified by idl as false in the page identified by pageid. Optionally, the content of the deleted line can be garbaged. However, to maintain consistency, the deleted line identifier must be kept as tombstones. Tombstones, also known as "death certificate", are heavily used in optimistic replication, especially in Usenet [START_REF] Spencer | Managing Usenet[END_REF] or replicated databases [START_REF] Demers | Epidemic algorithms for replicated database maintenance[END_REF].

When wooto creates a new page, the page is initialized as : L B , L E . L B and L E are special lines indicating the beginning and the ending of a page. When site x generates an insert operation on page p, between lineA and lineB, it generates Insert(p, < (x, + + clock x ), content, d, true >, idl(lineA), idl(lineB)) where d = max(degree(lineA), degree(lineB)) + 1. The lines L B and L E have a degree of 0. The degree represents a kind of loose hierarchical relation between lines. Lines with a lower degree are more likely generated earlier than lines with a higher degree.

Every generated insert operation must be integrated on every wooki site (including the generation one). The wooto algorithm is able to integrate insert operations and to compute the same result whatever the integration order of insert operations. In the following algorithm, S represents, on the local site, the lines sequence of the page where a line have to be inserted. This algorithm selects the sub-sequence of lines present between the previous line and the next line. If this sequence is empty, the line l is inserted in the model just before the next line. Elsewhere, wooto filters the sub-sequence keeping only lines with the minimum degree. The remaining lines are sorted according the < id order [START_REF] Oster | Data consistency for P2P collaborative editing[END_REF]. Thus, l must be integrated at its place according < id between remaining lines. We then make a recursive call to place l among lines with higher degree.

However, since wooki sites can receive operations in any order, the operations have pre-conditions. When a site receives an operation, if its pre-conditions are verified, the operation can be integrated immediately by executing the wooto algorithm. If pre-conditions are false, the operation is placed on a waiting queue until its pre-conditions are verified. Pre-conditions are: a line can only be inserted on a site if its previous and next lines are already present in the model of this site. Similarly, only an existing line can be deleted.

Let's now illustrate wooto algorithm through an example (see figure 2). On this scenario, line L 1 and line L 2 were concurrently inserted when the page was empty, and line L 3 was inserted before line L 1 . Without woot or

L3 l N B B B B B B B B LB l P = = | | | | | | | | l P / / l P ( ( Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q L1 l N / / LE L2 l N Fig. 2. Example
wooto, such a scenario can lead to three different line orders

L B , L 2 , L 3 , L 1 , L E , L B , L 3 , L 2 , L 1 , L E or L B , L 3 , L 1 , L 2
, L E each of them respecting the previous and next relationship. Wooto computes the unique order

L B , L 3 , L 1 , L 2 , L E .
According to definition, we have degree(L 1 ) = degree(L 2 ) = 1 and degree(L 3 ) = 2. Due to pre-conditions, there is no site where line L 3 is present and not line

L 1 . Now, let's assume that L 1 < id L 2 < id L 3 .
Imagine a site, where line L 2 arrives when line L 1 and line L 3 are present. The wooto algorithm first selects the lines present between L B and L E and filters them to keep only line L 1 . The reason of such a filtering is above. Indeed, since line L 3 is dependent to another line -here line L 1 -, it has a higher degree. Moreover, there could exist a site where line L 1 is present and not line L 3 . Thus, line L 2 must be placed according to line L 1 earlier to line L 3 . We obtain L B , L 3 , L 1 , L 2 , L E . The wooto algorithm computes the same order L B , L 3 , L 1 , L 2 , L E whichever the integration order respecting pre-conditions.

Finally, compared to woot original integration algorithm, the filtering is done on degree instead of the previous and next relationship of each line. Thus, wooto has a better time complexity : O(n 2 ) instead of O(n 3 ). This also allows to reduce the space required to store lines: an integer replacing two line identifiers. As woot, we have formally verified the eventual consistency of wooto with the Lamport's model-checker TLC [START_REF] Yu | Model checking TLA+ specifications[END_REF].

User's operation

Users do not directly edit the model. When a user opens a page for editing, he sees a view of the model which presents only the content of the visible lines. As in traditional wiki, the user makes all the modifications he wants and saves.

To detect operations, we use a diff algorithm [START_REF] Myers | An o(nd) difference algorithm and its variations[END_REF] between the page the user requested at edition time and the page the user saves. We translate the operations given by the diff algorithm in terms of wooto operations. A delete of the line number n is translated into a delete of the n th visible line. An insert at position n is translated into an insert between the (n -1) th and the n th visible lines. These operations are integrated locally and broadcasted to the other wooki sites.

Wooki Broadcast

For operation dissemination, we use a broadcast protocol in the spirit of [START_REF] Birman | Bimodal multicast[END_REF]. We combine a probabilistic broadcast algorithm with an anti-entropy algorithm [START_REF] Demers | Epidemic algorithms for replicated database maintenance[END_REF]. The probabilistic broadcast quickly disseminates updates on the P2P network and to manage membership. The anti-entropy algorithm has the responsibility to recover missing updates for sites that were off-line or crashed.

In order to be deployed on a P2P network, the broadcast protocol must be scalable, reliable and must also support the churn of the network. Indeed, in a P2P network, nodes join and leave the network dynamically. Thus, we replace the standard probabilistic broadcast of [START_REF] Birman | Bimodal multicast[END_REF] by the lightweight probabilistic broadcast (lpbcast) [START_REF] Eugster | Lightweight probabilistic broadcast[END_REF]. This algorithm gives probabilist warranties that sent operations will be delivered to all connected nodes.

In order to ensure a reliable dissemination of messages, each site must manage a table of neighbors. This table has a fixed size and contains only a partial nodes list of the entire P2P network. Lpbcast updates this table during messages propagation. Lpbcast gives probabilistic warranties that there is no clusters within P2P network. Moreover, since wooto does not require an ordering on message reception, the lpbcast can be unordered for higher efficiency.

The lpbcast algorithm ensures a reliable and scalable dissemination of operations on connected nodes. For managing off-line work, we combine it with an anti-entropy algorithm. We use the original anti-entropy algorithm of [START_REF] Demers | Epidemic algorithms for replicated database maintenance[END_REF]. When a site starts an anti-entropy, it selects a neighbor at random in the local table of neighbors and send to him a digest of his own received messages. The selected site returns missing messages to caller. Using anti-entropy implies that each site keeps received messages in a log. As this log should not grow infinitely, we purge this log from time to time. Purging the log is an intrinsic problem of anti-entropy approach. If a site purges its log and then starts an anti-entropy with another site, it can receive previously purged messages. In the traditional approach, tombstones or death certificates are used to avoid this problem. Fortunately, Wooki supports re-integration of already integrated operations. Indeed, we drop an insert operation of a line which identifier is already present in the model. Also, reapplying deletion of a line causes no modification. Thus, we can purge the anti-entropy log without using operation tombstones. This is an interesting property of combining wooto and anti-entropy approach.

Finally, if a site is off-line for a long period of time, anti-entropy may not find missing messages i.e., missing messages which have been purged on all sites of the P2P network. In this case, this site cannot be synchronized. The only way to recover this site is to make a state transfer with a site. It is important to notice that, even in this case, off-line work is not lost since local operations are still applicable. The site can send its local operations and then make the state transfer.

Implementation

The wooki prototype has been implemented in Java as servlets in a Tomcat Server. Wooki pages are just stored in regular files. All network messages are transported by the http protocol.

In figure 3, we can see the same page entitled "wooki1" loaded from 2 different wooki sites: http://wooki.loria.fr/wooki1 and http://wooki.loria.fr/wooki2. In this example, the same server "wooki.loria.fr" hosts 3 wooki sites. We can also see on figure 3 that both sites are connected and each site has two neighbors. We can observe the table of neighbors in figure 4. This interface lets the administrator manage manually this table. In the normal case, no administration is required except when starting wooki for the first time. The administrator has to connect the new wooki site to an existing wooki network by typing the http address of a wooki node. Once bootstrapped, the routing table is updated when messages from other sites are received. This interface also allows the administrator to start an anti-entropy mechanism or a state transfer. In the normal case, anti-entropy is activated at a regular interval of time. Administrator can force anti-entropy when he restarts the wooki system or when an off-line session is ended.

The wooki prototype is available with a GPL license at http://p2pwiki.loria.fr.

Pessimistic replication (database [START_REF] Bernstein | Concurrency Control and Recovery in Database Systems[END_REF] or consensus [START_REF] Lynch | Distributed Algorithms[END_REF]) ensures that, at anytime, all replicas host the same content. Pessimistic replication is widely used and recognized for its safety. Unfortunately, pessimistic replication is also well-known for its poor scalability [START_REF] Saito | Optimistic replication[END_REF] and its incapacity to provide an off-line work.

Virtual Synchrony [START_REF] Birman | Exploiting virtual synchrony in distributed systems[END_REF] is a middleware which allows sharing data among programs running on multiple machines. Virtual Synchrony provides a pessimistic replication with some optimizations to improve global performance. Consistency is ensured by enforcing a total ordered reception of modifications. Unfortunately, this ordering is costly and do not scale to a huge number of sites. In addition, Virtual Synchrony does not allow disconnected work.

Icecube [START_REF] Kermarrec | The IceCube approach to the reconciliation of divergent replicas[END_REF] is an optimistic reconciliation algorithm. Using static or dynamic reconciliation constraints, some semantic relations can be defined between users' operations. The Icecube algorithm aimed to obtain the best operations' schedule satisfying all constraints. Therefore, Icecube requires a central site which have to choose this schedule. Unfortunately, a central site is a serious bottleneck, hence, Icecube is not well-fit to provide a scalable wiki. In addition, due to concurrency, some constraints may not be satisfiable, hence, some operations have to be dropped. On the contrary, in the wooto approach, operations never conflict and, consequently, they are all integrated.

Joyce [START_REF] O'brien | An application framework for nomadic, collaborative applications[END_REF] is a programing framework based on the Icecube approach. In Joyce, the schedule is incrementally determined. Using Joyce, the authors proposed a collaborative text editor called Babbles which supports selective undo/redo mechanism. Thanks to the constraints, babbles can detect insertion conflicts. On the contrary, we consider that two insertions never conflict. The main drawback of Babbles is the requirement of a primary site which have to resolve conflicts. This primary limits the scalability, and is a single point of failure.

The operational transformation (OT) approach [START_REF] Ellis | Concurrency control in groupware systems[END_REF] is composed by operations which express modifications, and the transformation functions used to modify concurrent operations toward local operations. A state vector is associated to each operations. The state vector size grows linearly with the number of sites and consequently, limits the scalability of this approach. The wooto approach depends only of the number of operations and not of the number of sites.

Distributed version control systems (DVCS) allow many users to edit the same documents concurrently. They provide the same features as CVS [START_REF] Berliner | CVS II: Parallelizing software development[END_REF] or Subversion [START_REF] Collabnet | Subversion[END_REF] without requiring a central site. DVCS do not express the notion of consistency. In addition, a well-known scenario from the OT approach [START_REF] Oster | Tombstone transformation functions for ensuring consistency in collaborative editing systems[END_REF] leads most of DVCS (Darcs, Mercurial, Git, Bazaar, ...) to the document inconsistency. Code Co-op [START_REF]Reliable Software[END_REF] is a DVCS which allows to add a wiki to a replicated folder. Hence, we obtain a p2p wiki. As many DVCS, Code Co-op cannot ensure the wiki's pages consistency. Repliwiki is a P2P wiki based on the SHH-sync which is a DVCS. Unfortunately, as claimed before, DVCS algorithms failed to ensure consistency.

Wooki is a P2P wiki system. Compared to traditional centralized wikis, a P2P wiki system is fault-tolerant, improves global performances and allows user to work off-line. Wooki uses the wooto algorithm to manage consistency of copies. Wooto is an optimized version of the woot algorithm and ensures eventual consistency. Compared to other optimistic replication approaches, wooto is designed for P2P networks and is fully compatible with P2P network constraints.

In this paper, we described how to combine the wooto algorithm with an epidemic dissemination algorithm. This combination provides a reliable P2P wiki system that scales and tolerates the "churn" of P2P networks. It supports long-term disconnections without ever loosing off-line work. It also does not require any permanent sites, and the P2P network can be unstructured.

The wooki system has several open issues:

-We clearly make the choice to keep all tombstones in the wooto page model. It implies that wooki pages will grow infinitely. Nevertheless, keeping a tombstone has a very small space overhead. In the context of a wiki system, this choice is reasonable. In another context, it is interesting to design a distributed tombstone garbage collector that is compatible with P2P constraints. -A P2P wiki system changes interactions between humans and the system.

In a central wiki system, a user is aware about concurrent changes when he saves its page. If the wiki page has changed during the edition, the user have to resolve conflicts before committing his changes. In a P2P wiki system, a user can save its changes before concurrent ones arrive for integration. Wooto will solve the conflicts but the final page available on the site is a page computed by the system but not reviewed by a human. We need to add to Wooki an awareness engine that is responsible to warn about concurrent changes. -Replicating a wiki site is not completely transparent. If a wiki page contains some macros that computes some statistics, the visible result will not be the same on all sites. Suppose a counter that counts the read number of a page. If the page is replicated, this counter can have different values on different sites. This does not violate eventual consistency. The source page is still the same on all sites, but the rendering of the page can be different. -In collaborative editing, it is important to undo some operations. In traditional wikis, it is possible to revert to a previous version of the wiki. In the general case, it must be possible to undo any operations (not always the last one), anytime [START_REF] Sun | Undo as concurrent inverse in group editors[END_REF]. We have not yet provided such features in wooto. However, as we keep all informations within pages, it should be possible to undo an operation. We still need to design such an algorithm and prove eventual consistency in case of undo. -In Wooki, we built a new P2P wiki system. We are working on integration of the wooki engine with existing wiki systems. The general approach is to manage optimistic replication by only using the web service interface of existing wiki systems.

Fig. 1 .

 1 Fig. 1. Wooki architecture

  I n t e g r a t e I n s ( l , lp , ln ) :l e t S ′ := subseq(S, lp, ln) ; i f S ′ := ∅ t h e n insert(S, l, position(ln)) ; e l s e l e t i := 0 , dmin := min(degree, S ′ ) ; l e t F := f ilter(S ′ , λli . degree(li) = dmin) ; w h i l e (i < |F | -1) and (F |i| < id l) do i := i + 1 ; I n t e g r a t e I n s ( l , F [i -1] , F [i] ) ; e n d i f ;

Fig. 3 .

 3 Fig. 3. Wooki Interface