M Jardino

K Smaïli

I Zitouni

M El-Beze

A FIRST EVALUATION CAMPAIGN FOR LANGUAGE MODELS

This article describes a comparative evaluation campaign for language models which has been set up by AUPELF-UREF 1 , an agency in charge of the promotion of the French language. Three laboratories have participated to the first part of this campaign. The language models have been compared with an original scheme derived from the Shannon game. The results of this evaluation as well as the description of the method and the evaluated language models are presented.

Introduction

In order to compare language models out of the site where they have been built, an original scheme has been drawn [START_REF] Bimbot | An alternative scheme for perplexity estimation[END_REF]. The method, depicted in the section 1 is derived from the Shannon game and based on a gambling approach : the system has to guess the next word to come. The corresponding protocole which have been adopted by each participant is written in the section 2. Three laboratories have participated to this campaign. Their language models are described in [START_REF] Cerf-Danon | Three different Probabilistic Language Models: Comparison and Combination[END_REF][START_REF] Jardino | Multilingual stochastic n-gram class language models[END_REF]Smaili et al, 1997). Results and comments are then given as well as the problems encountered.

Shannon guessing game and perplexity estimation

Usually, performances of language models are related to the perplexity of a test text but this approach is not appropriate for a comparative evaluation campaign. It would require either that each site compute itself the perplexity value or that the software of each participant be re-implemented within the site in charge of the evaluation. To overcome this difficulty, we have proposed to estimate the perplexity of a small word set, with a gambling scheme inspired by the Shannon game.

Consider the successsive sentence fragments, obtained by discovering progressively each word of the n-word sentence W : W =< s > w 1 w 2 :::w k :::w n < =s > 1 Association des Universités Partiellement ou Entièrement de Langue Française -Université des Réseaux d 'Expression Française For each truncated sentence W k 1 0 , < s > w 1 w 2 :::w k 1 , the probabilistic language model puts a bet (v j ) on each possible vocabulary entry v j such that :

(v j ) = p(v j =W k 1 0 )
where p(v j =W k 1 0 ) is the conditional likelihood to find v j knowing the truncated sentence W k 1 0 . Furthermore, the next condition has to be filfulled :

V X j=1 (v j ) = 1
where V is the size of the vocabulary.

The sentence perplexity P P (W) is then defined as the inverse of the geometrical mean of the bets :

P P (W) = 1 n s n Q k=1 (w k )
This scheme has been adapted in three aspects.

1 Randomization of the truncated sentences Instead of predicting successive words in a text, we have chosen the test data W as a set of distinct sentences which have been truncated at a random position. The participant has to predict the next word that comes immediately after each truncated sentence. With this approach, we can obtain a good representativity of the language with a relatively small sample.

2 List of hypotheses In order to limit again the volume of data to be handled, the number of hypotheses for each truncated sentence has been reduced relatively to the size of the vocabulary, V.

Only the most predictible words must be given by each participant with their corresponding bets. Assuming a uniform distribution for the words outside this set, their common bet is:

k = 1 P nhyp r=1 k (v r ) V nhyp (1)
where nhyp is the number of the most probable hypotheses which has been chosen.

Protocol

A set of truncated sentences is provided to every participant. For each sentence, the participants must give a list of candidate words. A capital of 1.0 is distributed between the words of the vocabulary and each participant must bet on the word coming just after the truncation. The perplexity is then evaluated outside of the participant's site as the inverse of the geometric mean of the bets placed on the correct words.

At this point, we had to find the best trade-off between perplexity evaluation reliability and the size of the participant's files. We have chosen to reduce the list of hypotheses to 5,000 and to use 10,000 randomly selected sentences in the test set defined below. This was done according to the results published in [START_REF] Bimbot | An alternative scheme for perplexity estimation[END_REF]. We will check later how much these choices are suitable for the three evaluated models which are more sophisticated than those described in [START_REF] Bimbot | An alternative scheme for perplexity estimation[END_REF].

The size of the vocabulary has been fixed to 20,000 words. An efficient language model is charaterized by its hability to reduce the branching ratio from the vocabulary size to a minimum value, the idealistic and smallest value being 1. So, this constraint seems a minimum condition to get fair evaluations.

Evaluation

In this preliminary phase, the different tasks have been dispatched among the participants.

The test set has been extracted from Le Monde Diplomatique (1990)(1991)(1992)(1993)(1994)(1995)(1996), a corpus that none of the participants has used to train its models. The word segmentation has been processed as explained in [START_REF] Adda | Text Normalization and Speech Recognition in French[END_REF]. The punctuation has been removed from the data, but the segmentation in sentences has been kept. It corresponds to a situation close to the one encountered in a speech recognition task. A subset of 10,000 truncated sentences has been randomly selected in the corpus and distributed to each participant.

In response, each participant had to give the 5,000 best candidates selected by his language model for each sentence, in all, 10,000 times 5,000 words with their respective bets.

Then, out of each participant site, the references have been searched among the proposed candidates. The observation rank and the bet put on the reference permit to compare the models in course.

Evaluated models

Language Model A (LM A)

LM A is a stochastic model expanded with a formal grammar which uses both n-classes and n-grams.

The n-class model is based on an interpolated tri-class model built with 233 syntactic classes (including punctuation) and adjusted by hand. This high number of classes has been chosen in order to build a model which is sufficiently predictive and highly selective. In this classification, each word can belong to several classes (up to 4 classes). This involves that some words have to be duplicated in the dictionary if they have more than one syntactic category. The original dictionary is made up of 41 000 entries from which the 20,000 most frequent words of Le Monde (1987)(1988) have been extracted. The stochastic model is trained over a corpus of 42M words. In a first step, a corpus of 0.5M words has been accurately labelled with this set of classes. Then, the model learned during this step has been used to label automatically each word of the entire corpus, with a modified Viterbi algorithm.

The n-gram component is an interpolated tri-gram computed from the same corpus. The formal grammar is a list of hand written French grammatical rules which are modelled with a unification grammar.

Prediction strategy To explain the different steps of predicting the n best words in this experiment, it has been assumed that the truncated sentence is w 1 :::w k 1 w k , the vocabulary classes are c 1 :::c 233 and the vocabulary words are v 1 :::v N . Each word v i be- longs to one or several syntactic classes. The prediction is conducted as follows:

Each word w i of the truncated sentence has been labelled. For doing that, a home-made labelling tool has been first used, but unfortunately, the results were very bad because this tool is efficient when it disposes of the whole sentence. Therefore, to deal with this problem, it has been decided to take into account only the last two words (w k 1 w k ) of the truncated sentence. That means that all the classes of the words w k 1 ; w k have been kept.

The 233 classes have been affected to the word to be discovered w k+1 . In other words, the word to be discovered can belong to each class. For each class of w k 1 , for each class of w k and for each word w i k+1

of the vocabulary classes, we compute the quantity:

Q = P (c k+1 =c k c k 1 ) P (w i k+1 =c k+1 )
In this step the n-gram model is used to rescore w i k+1 .

In fact, the positional word model has been used in order to give more weight to the word sequences.

In the fourth step and for each discovered word, the unification grammar has been used to examine the linguistic validity of each partial sentence w 1 V w k w i k+1 .

Thus, only the n best words, those which are not eliminated by the unification grammar, have been kept .

Language Model B (LM B)

LM B is a linear combination of statistical trigram and tri-class based models (respectively 40% and 60%).

The class-based model has been built with the Viterbi algorithm, applied on the tagged corpus of Le Monde (1992)(1993) and using the BDLEX dictionary (200,000 entries). The model has been built with 101 classes including the unknown word class, each vocabulary word can be tagged with at the most nine classes.

The trigram model has been trained on the newspaper Le Monde (1992)(1993) (about 35 million words), with the first version of the CMU toolkit, using the Katz back-off method to interpolate unseen events. It takes into account a reduction to 63,667 forms of the BDLEX vocabulary plus several Proper Nouns which have been added later. Finally, 555,942 bigrams and 786,299 trigrams occurring more than 4 times have been used to train the trigram model. The reduction of the size of the vocabulary to 20,000 words has been done dynamically for each truncated sentence through formula 1. The probabilities of the corresponding out-ofhypotheses words have been spread over the 20,000 most predictible words associated with the truncated sentence.

Language Model C (LM C)

This is a statistical tri-class-based model, built with untagged words. The mapping of these untagged words is realized through an iterative Monte-Carlo process, in order to reduce the distance between the distribution given by a word model and the distribution given by the class model.

The word model is supposed to be entirely described by the set of consecutive words observed in the training text, fw i w j g TT , and by the conditional probabilities : p(w j =w i ) = N w i ; w j ] N w i ] where N w i ; w j ] is the frequency of the sequence w i w j in the training text, and N w i ] the frequency of the word w i .

With the class model, these probabilities are averaged to: q(w j =w i ) = N w j ] N C(w j )]

N C(w i )C(w j )] N C(w i )] where C(w i ) and C(w j ) are the classes which respectively contain the words w i and w j . N C(w i )C(w j )] is the frequency of the sequence C(w i )C(w j ) in the training text and N C(w i )] the frequency of the class C(w i ) in this text.

The algorithm searchs which mapping leads to the smallest cross-entropy of the two distributions, defined as: D(pjjq) = X fwiwjgTT p(w j =w i ) log p(w j =w i )] log q(w j =w i )]

The training text contains about 300 million words and is composed of articles of Le Monde and of AFP wires, written between 1987 and 1996. The vocabulary is composed of the 20,000 most frequent words of Le Monde (1987)(1988). The number of classes is 1,000 and has been determined as the interpolation parameters on held-out data. Deleted interpolation has been used to predict events, unseen in the training text. Table 2: Comparative results in terms of observation ranks and perplexity for the reference words to be found, excluding the unknown words from the initial set of 10,000.

Results

Models

The results for the three models are given in tables 1 and 2. We have distinguished results with unknown words (table1) from the ones without unknown words (table 2). P P Sh is the perplexity calculated with the protocol defined above, with the bets (w r ) put on the N reference words, w r , and defined as:

P P Sh = 1 N q Q N r=1 (w r )
The tables include the number of words found in the 5,000 hypothesis lists, the mean rank of observation of the references in these lists, the number of words observed at the first rank and the number of words observed from the first rank to the fifth one. After the evaluation campaign, the complete reference sentences have been given to the participants. They have evaluated their models on this test (about 400,000 words) and the perplexities calculated in situ are written on line P P is .

In order to verify a posteriori the choice for the number of references and hypotheses, we have plot the variations of the perplexity, P P Sh , against the number of reference words on the figure 1 and the variations of the perplexity, P P Sh , against the number of hypotheses on the figure 2.

When the number of references grows, the perplexity tends to a relatively stable value, showing the efficiency of the randomized selection of the tested words on a relatively Figure 2: Variations of the perplexity, P P Sh , against the number of hypotheses small sample. When the number of hypotheses grows, we also observe that the perplexity tends to a constant value.

Evaluation's problems

This evaluation experiment has permitted us to figure out some uniformity problems in the training and test corpus. Every participant in this experiment has constructed his models using a corpus which has been treated long time before evaluation, leading to using his own criteria for rewriting compound words, apostrophes and numbers, etc. The text resources used in this evaluation campaign have been distributed by one of the participating laboratories with the description of formatting rules [START_REF] Adda | Text Normalization and Speech Recognition in French[END_REF]. They have been used without any modification in LM C. Nevertheless, some problems have been noticed due to the rewriting used in treating the test corpus. Some of which coming from the original text, the others coming from the preprocessing of this text. These problems have lead to the non-identification of some correct words especially for LM A and LM C.

Problems in the original text

Some words in the text were misspelled (fanastisme, EXPLICATIOB, ...), incorrectly segmented (MERESIN-DUSTRIES, PROJETSLIEUCAPITAL, URSScierie ...) or mistakenly written as in the sentence " pour le gouvernement de Mr William Clinton cela sign ifiait que les bénéfices ..." where the verb signifier has been truncated.

The non uniformity of putting accents for the same letter in the same word (specially for capital letters) gives misleading results when accented words are considered for prediction (Egypte instead of Égypte, Taiwan instead of Taïwan).

Long strings of foreign languages remain in the test, this arises every time one cites a foreign text.

Problems dues to the preprocessing

Words with capital letters

Rewritten rules for Mr, MR and M. are not the same in the training test and in the test.

Several words in the test have been uncorrectly written with their first letter as a capital.

One of us writes the words containing only one capital letter like Z., U., Q. while they are written Z, U, Q in the test.

Deletion of punctuation

The decision of removing the text punctuation in this campaign has also affected the evaluation. For instance, certain sentences have lost their syntactic validity after removing parenthesis and/or quotation marks. An example is given in the following sentence: " aux Etats-Unis, en mille neuf cent soixante-dix-huit puis mille neuf cent quatre-vingts, deux lois (deux) ont ouvert la période dite des " cieux ouverts " (open skies). " For which, removing the punctuation results in the incomprehensible sentence: " aux Etats-Unis en mille neuf cent soixante-dix-huit puis mille neuf cent quatre-vingts deux lois deux ont ouvert la période dite des cieux ouverts open skies."

Writing prefixes Prefixes like (agro, pro, ...) were in many cases separated from the root by a hyphen and a space. In other words, these prefixes became lexical entities. However, except for some of them, the prefixes which end with o are attached to the following word if it begins with a consonant. This rule has not been respected in the test corpus as in: autoréférentielle, auto-flagellation, ...

Writing expressions and compound words

Some expressions were separated into two or more units, for example : au fur et à mesure... Some of us usually considered these expressions as a single word. This problem can be taken into account either a priori, with the definition of a common vocabulary or a posteriori, during an adjustment phase in order that each participant adapts its programs to the treatment of this kind of expressions.

In summary, for evaluating language models according to the same criteria, we have to consider these points and to evaluate their relative importance. Some of them can be considered as noise, others can lead to misleading results. The work done by others in tokenization evaluation [START_REF] Habert | The need for tokenization evaluation[END_REF] would help us in this task.

Conclusions

In this paper we have described the efforts which are necessary to set up an evaluation campaign in a new domain. Tools for building the test data to be evaluated and tools for evaluating the models have been developed. The analysis of the results of this preliminary campaign with the detailed description of each system, shows the importance of the word segmentation and the necessity either to adapt the different models to a common vocabulary list or to take into account the discrepancies due to the different written forms, in particular to choose non misleading truncations in the sentences.

This work can be considered as a development phase in the evaluation of language models. It can be considered as the bases for a future complete comparative campaign.

  Figure 1: Variations of the perplexity, P P Sh , against the number of reference words

Out-of-vocabulary wordsIn order to deal with an open vocabulary, a certain part of the bets must be reserved for the probability that the word to be predicted is not in the vocabulary. This implies that a particular OOV-word is included in the vocabulary and that each participant must guess this word, in order to avoid a null term in the geometrical mean.


Miguel Angel Fernández

Mikel Landajuela

Jimmy Mullaert

Marina Vidrascu

Robin-Neumann schemes for incompressible fluid-structure interaction

come

Introduction

Mathematical problems involving the coupling of an incompressible viscous flow with an elastic structure appear in a large variety of engineering fields (see, e.g., [START_REF] Lombardi | Numerical simulation of sailing boats: Dynamics, FSI, and shape optimization[END_REF], [START_REF] Takizawa | Computational methods for parachute fluidstructure interactions[END_REF], [START_REF] Païdoussis | Fluid-structure interactions: cross-flow-induced instabilities[END_REF], [START_REF] Moireau | External tissue support and fluid-structure simulation in blood flows[END_REF], [START_REF] Heil | Fluid-structure interaction in internal physiological flows[END_REF]). This problem is considered here within a heterogenous domain decomposition framework, with the aim of using independent well-suited solvers for the fluid and the solid. One of the main difficulties that have to be faced under this approach is that the coupling can be very stiff. In particular, traditional Dirichlet-Neumann explicit coupling methods, which solve for the fluid (Dirichlet) and for the solid (Neumann) only once per time-step, are unconditionally unstable whenever the amount of added-mass effect in the system is large (see, e.g., [START_REF] Causin | Added-mass effect in the design of partitioned algorithms for fluid-structure problems[END_REF]. [START_REF] Förster | Artificial added mass instabilities in sequential staggered coupling of nonlinear structures and incompressible viscous flows[END_REF]). Typically this happens when the fluid and solid densities are close and the fluid domain is slender, as in hemodynamical applications. This explains, in part, the tremendous amount of work devoted over the last decade to the development of alternative coupling paradigms (see, e.g., [START_REF] Fernández | Coupling schemes for incompressible fluid-structure interaction: implicit, semi-implicit and explicit[END_REF] for a review).

In this paper we will review several explicit coupling procedures recently reported in the literature and present some new developments (Section 3.2). The common feature of these methods is that they are based on Robin-Neumann transmission conditions, whose nature depends on the thin-or thick-walled character of the structure (see Figure 1).

Problem formulation

For the sake of simplicity we consider a low Reynolds regime and assume that the interface undergoes infinitesimal displacements. The fluid is described by the Stokes equations, in a fixed domain Ω f ⊂ R d (d = 2, 3), and the structure by the linear (possibly damped) membrane equations written in the (d -1)-manifold Ω s ≡ Σ, which is also the fluid-structure interface (see Figure 1(left)).

The coupled model problem reads therefore as follows: find the fluid velocity u :

Ω f × R + → R d , the fluid pressure p : Ω f × R + → R, the solid displacement d : Σ × R + → R d and the solid velocity ḋ : Σ × R + → R d such that ρ f ∂ t u -∇ • σ(u, p) = 0 in Ω f , ∇ • u = 0 in Ω f , (1)
       u = ḋ on Σ, ρ s ∂ t ḋ + L e d + L v ḋ = -σ(u, p)n on Σ, ḋ = ∂ t d on Σ.
(2)

This system has to be complemented with appropriate initial and (external) boundary conditions, which will be omitted in the following since they are not relevant for the discussion. The symbols ρ f and ρ s denote, respectively, the fluid and solid densities, is the solid thickness and n stands for the unit normal vector on ∂Ω f . The fluid Cauchy-stress tensor is given by σ(u, p) def = -pI + 2µε(u), with ε(u) def = 1 2 ∇u + ∇u T and where µ denotes the fluid dynamic viscosity. Finally, the surface differential operators L e and L v describe the membrane elastic and viscous behavior, respectively.

Remark 1. In two spatial dimensions and for the geometrical configuration of Figure 1(left) an example of solid elastic operator is given by

L e d = [0, -c 1 ∂ xx d y + c 0 d y ] T , where d = [0, d y ]
T and c 0 , c 1 > 0 are material dependent parameters. A widely used form of the solid viscous operator is L v ḋ = αρ s ḋ + βL e ḋ, where α, β > 0 are given parameters. In artery wall modeling, the zeroth-order term, αρ s ḋ, describes the dissipative behavior of external tissues (see [START_REF] Moireau | External tissue support and fluid-structure simulation in blood flows[END_REF]), whereas the differential term, βL e ḋ, corresponds to the Kelvin-Voigt model (see, e.g., [START_REF] Kalita | Mechanical models of artery walls[END_REF]Schaefer [2008], Valdez-Jasso et al. [2009]).

Remark 2. Though simplified, problem (1)-(2) preserves some of the major numerical difficulties that arise in incompressible fluid-structure interaction.

Explicit coupling schemes

This section is devoted to the numerical approximation of the coupled problem (1)-(2). In the succeeding text, the symbol τ > 0 denotes the timestep size, t n def = nτ , for n ∈ N, and ∂ τ x n def = x n -x n-1 /τ the first order backward difference in time. In addition, the superscript is used to indicate zeroth-(i.e., without), first-order or second-order extrapolation from the previous time-steps, namely, x = 0 if r = 0, x = x n-1 if r = 1 and x = 2x n-1 -x n-2 if r = 2, where r denotes the extrapolation order.

The methods discussed in this review paper are explicit coupling schemes, in the sense that they enable a decoupled time-marching of the fluid and the solid. Traditional Dirichlet-Neumann explicit coupling procedures, as reported in Algorithm 1, are known to be unconditionally unstable, whenever Algorithm 1 Dirichet-Neumann explicit coupling scheme

For n ≥ 1: 1. Fluid step: find u n : Ω f × R + → R d and p n : Ω f × R + → R such that        ρ f ∂τ u n -∇ • σ(u n , p n ) = 0 in Ω f , ∇ • u n = 0 in Ω f , u n = ḋn-1 on Σ.
2. Solid step: find

d n : Σ × R + → R d such that ρ s ∂τ ḋn + L e d n + L v ḋn = -σ(u n , p n )n on Σ, ḋn = ∂τ d n on Σ.
the amount of added-mass effect in the system is large (see, e.g., [START_REF] Causin | Added-mass effect in the design of partitioned algorithms for fluid-structure problems[END_REF]). Stability in explicit coupling for incompressible fluid-structure interaction demands a different treatment of the interface coupling conditions (2) 1,2 . A stable explicit coupling alternative is given by the Robin-Robin methods introduced in Burman andFernández [2009, 2014], which build on a Nitsche treatment of the interface coupling. A salient feature of these methods is that they do not depend on the thin-or thick-walled nature of the solid. Unfortunately, the explicit treatment of the Nitsche's penalty induces a deterioration of the accuracy, which demands restrictive CFL constraints, unless correction iterations with suitable extrapolations are performed (see [START_REF] Burman | Explicit strategies for incompressible fluidstructure interaction problems: Nitsche type mortaring versus Robin-Robin coupling[END_REF]). Numerical evidence suggests that optimal first-order accuracy can be achieved by using a non-symmetric penalty-free formulation (see [Burman and Fernández, 2014, Section 4.3]). The rigorous stability analysis of the resulting schemes remains, however, an open problem.

Robin-Neumann schemes

The key difficulty is hence the derivation of alternative splitting methods which guarantee stability without compromising accuracy. The Robin-Neumann methods proposed in [START_REF] Fernández | Incremental displacement-correction schemes for incompressible fluid-structure interaction: stability and convergence analysis[END_REF], [START_REF] Fernández | Explicit Robin-Neumann schemes for the coupling of incompressible fluids with thin-walled structures[END_REF] achieve this purpose. The fundamental ingredient in the derivation of these schemes is the interface Robin consistency featured by the continuous problem ( 1)-( 2). Indeed, from (2) 1,2 it follows that

σ(u, p)n + ρ s ∂ t u = -L e d -L v ḋ on Σ, (3)
which can be viewed as a Robin-like boundary condition for the fluid. Hence, instead of performing the fluid solid time splitting in terms of (2) 1,2 as in Algorithm 1, we consider (3) and ( 2) 2 . The resulting schemes are detailed in Algorithm 2.

Algorithm 2 Robin-Neumann explicit coupling schemes (from [START_REF] Fernández | Explicit Robin-Neumann schemes for the coupling of incompressible fluids with thin-walled structures[END_REF]).

For n ≥ r + 1:

1. Fluid step: find u n :

Ω f × R + → R d and p n : Ω f × R + → R such that          ρ f ∂τ u n -∇ • σ(u n , p n ) = 0 in Ω f , ∇ • u n = 0 in Ω f , σ(u n , p n )n + ρ s τ u n = ρ s τ ḋn-1 -L e d -L v ḋ on Σ. (4)
2. Solid step: find

d n : Σ × R + → R d such that ρ s ∂τ ḋn + L e d n + L v ḋn = -σ(u n , p n )n on Σ, ḋ = ∂τ d n on Σ. ( 5
)
Algorithm 2 completely uncouples the fluid and solid time-marchings. This is achieved via the explicit Robin condition (4) 3 derived from (3). Note that only the solid inertial effects are implicitly treated in (4) 3 , this is enough to guarantee added-mass free stability. It is also worth noting that, from (5) 1 , the explicit Robin condition (4) 3 can be reformulated as

σ(u n , p n )n + ρ s τ u n = ρ s τ ḋn-1 + τ ∂ τ ḋ + σ(u , p )n on Σ.
The advantage of this new expression is its intrinsic character, in the sense that it avoids extrapolations of the solid viscoelastic terms within the fluid solver.

Remark 3. It should be noted that the implicit treatment of the solid-damping term L v in (4), as advocated in [START_REF] Guidoboni | Stable looselycoupled-type algorithm for fluid-structure interaction in blood flow[END_REF], Lukáčová-Medvid'ová et al. [2013], [START_REF] Bukač | Fluidstructure interaction in blood flow capturing non-zero longitudinal structure displacement[END_REF], yields a coupling scheme which is not explicit: it is semi-implicit. Moreover, the resulting solution procedure is not partitioned either, since the solid viscous contribution L v has to be integrated within the fluid solver.

Theoretical results on the stability and accuracy of Algorithm 2 have been reported in [START_REF] Fernández | Incremental displacement-correction schemes for incompressible fluid-structure interaction: stability and convergence analysis[END_REF] and [START_REF] Fernández | Explicit Robin-Neumann schemes for the coupling of incompressible fluids with thin-walled structures[END_REF]. A fundamental ingredient in the analysis is the fact that Algorithm 2 can be viewed as a fully implicit scheme with the following perturbed kinematic constraint

u n = ḋn + τ ρ s L e d n -d + L v ḋn -ḋ ) on Σ. (6)
The stability and the accuracy of Algorithm 2 are hence driven by the impact of this perturbation (i.e., the last term of ( 6)) on the stability and accuracy of the underlying implicit coupling scheme. Unconditional energy stability can be proved for r = 0 and r = 1. The scheme with r = 2 is energy stable under a CFL-like condition. As regards accuracy, the error analysis shows that the splitting error induced by the kinematic perturbation (6) scales as O(τ 2 r-1 ). Thus, Algorithm 2 with r = 1 or r = 2 yields an overall optimal first-order time-accuracy O(τ ) in the energy-norm, while a sub-optimal time convergence rate O(τ

2 ) is expected for the scheme with r = 0.

Remark 4. In the particular case of an undamped thin-walled solid (i.e., L v = 0), Algorithm 2 with r = 0 yields the splitting scheme reported in [START_REF] Guidoboni | Stable looselycoupled-type algorithm for fluid-structure interaction in blood flow[END_REF], which is known to deliver very poor accuracy (see [START_REF] Fernández | Incremental displacement-correction schemes for incompressible fluid-structure interaction: stability and convergence analysis[END_REF], [START_REF] Fernández | Explicit Robin-Neumann schemes for the coupling of incompressible fluids with thin-walled structures[END_REF] and the example below).

We conclude this section with a numerical illustration based on the balloon-like example proposed in [Küttler et al., 2006, Section 7.1] and using a non-linear version of (1)-( 2). This type of problems involving fully enclosed fluids cannot be solved using Algorithm 1 (or iterative variants) due to the constraint enforced by the fluid incompressibility on the interface solid velocity (unless it is directly prescribed in the solid solver, see [START_REF] Küttler | A solution for the incompressibility dilemma in partitioned fluid-structure interaction with pure Dirichlet fluid domains[END_REF]). Figure 2(left) presents some snapshots of the fluid velocity magnitude in the deformed configuration obtained with a non-linear version of Algorithm 2 (r = 1 and τ = 0.05). The fluid equations are discretized in space with Q 1 /Q 1 finite elements and a SUPG/PSPG stabilized formulation. Quadrilateral MITC4 (locking-free) shell elements are considered for the structure (see, e.g., [START_REF] Chapelle | The finite element analysis of shellsfundamentals[END_REF]). For comparison purposes, Figure 2(right) shows the maximal displacement magnitude on the interface obtained with Algorithm 2 and the implicit coupling scheme. Algorithm 2 with r = 1 or r = 2 provides numerical solutions close to the implicit scheme. The superior accuracy of the variant with r = 2, induced by the second-order extrapolation in (4), is clearly noticeable. On the contrary, Algorithm 2 with r = 0 (see Remark 4) yields an extremely poor approximation. This is a clear indication of the O(τ 1 2 )-loss in the accuracy of the scheme predicted by the error analysis.

Second-order accuracy

So far no explicit stable second-order time-accurate scheme is known for general fluid-structure interaction. For purely elastic thin-structures, some attempts have been presented in [START_REF] Lukáčová-Medvid'ová | Kinematic splitting algorithm for fluid-structure interaction in hemodynamics[END_REF] by combining a Strang operator splitting approach with the ideas reported in [START_REF] Guidoboni | Stable looselycoupled-type algorithm for fluid-structure interaction in blood flow[END_REF]. Though the accuracy of the splitting is improved, second-order time-accuracy is still not achieved.

In this section we show how the Robin-Neumann explicit coupling paradigm of Section 3.1 can be adapted to deliver second-order time-accuracy. This is achieved by combining a Crank-Nicholson time-stepping in both the fluid and the solid subproblems, with an enhanced time-discretization of (3) based on either second-order extrapolation or defect-correction iterations. It is worth noting that this strategy for enhancing accuracy might lead to stability prob-lems when applied to other explicit coupling paradigms (see, e.g., [START_REF] Burman | Explicit strategies for incompressible fluidstructure interaction problems: Nitsche type mortaring versus Robin-Robin coupling[END_REF]).

The resulting schemes are displayed in Algorithm 3, where K ≥ 0 denotes the number of correction iterations and x n-1 2 ,k def = x n,k + x n-1 /2 stands for the midpoint between the previous value x n-1 and the k-stage corrected one x n,k .

Algorithm 3 Second-order Robin-Neumann schemes

For n ≥ 0 if r = 0, 1 or for n ≥ 1 if r = 2: 1. Extrapolation: d n,0 = d , ḋn,0 = ḋ . 2. For k = 1, . . . , K + 1: a. Fluid step: Find u n,k : Ω f × R + → R d and p n-1 2 ,k : Ω f × R + → R such that            ρ f τ u n,k -u n-1 -∇ • σ(u n-1 2 ,k , p n-1 2 ,k ) = 0 in Ω f , ∇ • u n-1 2 ,k = 0 in Ω f , σ(u n-1 2 ,k , p n-1 2 ,k )n + ρ s τ u n,k = ρ s τ ḋn-1 + L e d n-1 2 ,k-1 + L v ḋn-1 2 ,k-1 on Σ. b. Solid step: Find d n,k : Σ × R + → R d such that      ρ s τ ḋn,k - ḋn-1 + L e d n-1 2 ,k + L v ḋn-1 2 ,k = -σ(u n-1 2 ,k , p n-1 2 ,k )n on Σ, ḋn-1 2 ,k = 1 τ d n,k -d n-1 on Σ.
3. Solution update:

u n = u n,K+1 , p n-1 2 = p n-1 2 ,K+1 , d n = d n,K+1 , ḋn = ḋn,K+1 .
Similarly to Algorithm 2, Algorithm 3 with K = 0 can be regarded as interface kinematic perturbations of an underlying second-order implicit scheme. Hence, in order to achieve overall second-order time-accuracy, two approaches are investigated:

1. r = 1 and K > 0: Recall that the consistency errors induced by the kinematic perturbations with r = 1 scale as O(τ ). Thus, after K > 0 defect-corrections the perturbation of the kinematic constraint scales as O(τ K+1 ). Hence, in order to retrieve second-order time-accuracy K = 1 will be enough. 2. r = 2 and K = 0 (genuine explicit scheme): Since the consistency error induced with r = 2 scales as O(τ 2 ), no defect-correction is needed.

To give some insight into the stability properties of Algorithm 3, we consider a simplification of the model problem (1)-(2) at hand (see, e.g., [START_REF] Causin | Added-mass effect in the design of partitioned algorithms for fluid-structure problems[END_REF], [START_REF] Badia | Fluid-structure partitioned procedures based on Robin transmission conditions[END_REF]). Specifically, we take . Under the problem setting described in the previous paragraph, we have:

Ω f = [0, L]×[0, R] ⊂ R 2 , Σ = {y = R},
1. If r = 0 or r = 1, |d n y,i | -→ n→+∞ 0 ∀ i ∈ {1, . . . , ∞}. 2. If r = 2, |d n y,i | -→ n→+∞ 0 with i ∈ {1, . . . , ∞} provided          4a i b i + 4b 2 i τ + 4d i b i τ 2 + d 2 i -2µ i ρ f + ρ s ρ s τ 3 ≥ 0, 4e i ρ s (b i + d i τ )(4a i + d i τ 2 + 4τ b i ) -4d i τ e 2 i -16 ρ s τ (b i + d i τ ) 2 (a i ρ s + 2b i µ i ρ f τ ) ≥ 0, (7)
where

a i = µ i ρ f + ρ s , b i = βc 1 λ i + α ρ s , d i = c 0 + c 1 λ i , e i = 4a i ρ s + τ (b i ρ s + 2d i µ i ρ f τ ) and µ i = L iπ tanh( iπR L ) , λ i = i 2 π 2
L 2 are the eigenvalues with respect to φ i of the Neumann-to-Dirichlet map and ∂ xx operators.

Proposition 1 establishes that whenever the Fourier series expansion of d n y is truncated (i.e., whenever the spatial discretization is fixed) the solution of Algorithm 3 with K = 0, under the above assumptions, is unconditionally stable with zeroth-and first-order extrapolations. For r = 2, the conditions (7) might be too restrictive since they do not explicitly take into account the effect of the spatial discretization step h.

In order to numerically illustrate the accuracy and stability of Algorithm 3, we consider the two-dimensional example of [START_REF] Fernández | Explicit Robin-Neumann schemes for the coupling of incompressible fluids with thin-walled structures[END_REF]. To pro- vide evidence on the O(h + τ 2 ) convergence behavior for the first and second order extrapolated variants, Figure 3 (left) reports the time-convergence history, with h = 10 -1 /4 fixed, of the solid displacement at time t = 0.015, in the relative elastic energy-norm, obtained with Algorithm 3 and a fully implicit second-order scheme. The reference solution has been generated using the implicit scheme with τ = 10 -6 and the same h. The h-uniformity is guaranteed by Figure 3 (right) were we have refined both in time and space according h = O(τ 2 ). The reference solution has been now obtained with τ = 10 -6 and h = 3 × 10 -3 .

Coupling with thick-walled structures

In this section we briefly describe the extension of the Robin-Neumann explicit coupling paradigm of Algorithm 2 to the case of the coupling with thick-walled structures (see Figure 1(right)). Thus, in the coupled problem (1)-( 2), the relations (2) are replaced by the linear elastodynamics equations

ρ s ∂ t ḋ + αρ s ḋ -∇ • Π(d, ḋ) = 0 in Ω s , ḋ = ∂ t d in Ω s , (8)
together with the kinematic and kinetic coupling conditions

u = ḋ on Σ, Π(d, ḋ)n s = -σ(u, p)n on Σ. (9)
Here, the symbol n s stands for the unit normal vector on ∂Ω s , the solid stress tensor is given by Π(d, ḋ) The fundamental ingredient in the derivation of the schemes described in the previous sections is the interface Robin consistency (3) featured by the continuous problem (1)-(2). Unfortunately, this property is not shared by the coupled problem (1), ( 8) and ( 9), since the inertial term in ( 8) is distributed on the whole solid domain Ω s and Σ = Ω s . The following generalized interface Robin consistency can however be recovered after discretization in space, using a lumped-mass approximation in the structure (see Fernández et al. [2015]):

σ(u, p)n + ρ s B h ∂ t u = ρ s B h ∂ t ḋ -Π(d, ḋ)n s on Σ. (10)
Note that, instead of the usual identity operator, the interface condition (10) involves the discrete interface operator B h , which consistently accounts for the solid inertial effects within the fluid. In fact, at the algebraic level, this operator is given by the interface entries of the solid lumped-mass matrix. Instead of formulating the time splitting in terms of (9), we consider (10) and ( 9) 2 . This yields the following Robin-Neumann splitting of (9): The analysis reported in Fernández et al. [2015] shows that the splitting (11) preserves the energy stability of the original Robin-Neumann explicit coupling paradimg (Algorithm 2). Numerical evidence indicates, however, that their optimal (first-order) accuracy is not preserved. Indeed, the order of the kinematic perturbation induced by the splitting ( 11) is expected to be O(τ 2 r-1 /h 1 2 ). Interestingly, the factor h -1 2 is intrinsically related to the thick-walled character of the structure, through the non-uniformity of the discrete viscoelastic operator, and not to the mass lumping approximation (see Fernández and Mullaert [2015]).

   σ(u n , p n )n + ρ s τ B h u n = ρ s τ B h ḋn-1 + τ ∂ τ ḋ -Π(d , ḋ )n s , Π(d n , ḋn )n s = -σ(u n , p n )n. ( 11
We conclude this section by considering the balloon-like example of Section 3.1 but, this time, involving a thick-walled structure. In Figure 4(left) we have reported some snapshots of the fluid velocity magnitude and of the deformed configurations obtained with the generalized Robin-Neumann splitting (11) with r = 1 and τ = 0.025. A comparison of the different variants with the implicit schemes is given in Figure 4(right). Note that spurious oscillations are visible for the explicit coupling with r = 2. This is consistent with the fact that stability conditions are expected to be more restrictive in the case of the coupling with thick-walled structures. Considering that the value of τ is twice smaller than in Section 3.1, the poor accuracy of the explicit scheme with r = 0 is even more striking. For r = 1 and r = 2 we obtain practically the same results as in Section 3.1. This is a clear indication of the h -1 2 perturbation introduced by the splitting: the time-step length must be reduced to achieve a similar level of accuracy as in the thin-walled case.

Conclusion

We have discussed a class of explicit coupling schemes for incompressible fluid-structure interaction. The key ingredient in the derivation of the methods is the notion of interface Robin consistency which depends on the thinor thick-walled character of the structure. In the case of the coupling with a thin-walled structure, energy stability and optimal first-order accuracy are retrieved without any restriction on the discretization parameters. Besides, under this structure regime, two promising extensions which deliver secondorder time-accuracy have been presented. The main issue regarding thickwalled structures is accuracy, since the perturbation induced by the splitting is not uniform with respect to the spatial discretization step h. It is worth noting, however, that the scheme with first-order extrapolation yields convergence under a standard hyperbolic-condition without the need of correction iterations.

Fig. 1

 1 Fig. 1 Fluid-structure configurations for a thin-(left) and a thick-walled structure (right).

Fig. 2

 2 Fig. 2 Left: Snapshots of the fluid velocity magnitude in the deformed configuration at t = 0.15, 7.5, 15 (Algorithm 2 with r = 1 and τ = 0.05). Right: Comparison of the solid displacements vs. time obtained with Algorithm 2 and the implicit scheme (τ = 0.05).

  the solid operators of Remark 1 and µ = 0 (potential fluid). In this framework the following proposition holds.Proposition 1. Take K = 0 (no defect-correction) in Algorithm 3 and write d n y = ∞ i=1 d n y,i φ i where we consider the orthonormal basis on L 2 0 (Σ) given by φ i (x) = 2/L sin (iπx/L) ∞ i=1

Fig. 3

 3 Fig. 3 Left: displacement convergence history in time with h = 10 -1 /4 fixed. Right: displacement convergence history in time with h = O(τ 2 ).

  def = π(d) + βπ( ḋ), where π(d) def = 2λ 1 ε(d) + λ 2 (∇ • d)I and λ 1 , λ 2 denote the Lamé coefficients. Damping effects in the solid are thus modeled via the Rayleigh-like term αρ s ḋ -β∇ • ḋ).

Fig. 4

 4 Fig. 4 Left: Snapshots of the fluid velocity magnitude in the deformed configurations at t = 0.15, 7.5, 15 (generalized Robin-Neumann explicit coupling (11) with r = 1 and τ = 0.025). Right: Comparison of the solid displacements vs. time obtained with the generalized Robin-Neumann explicit coupling (11) and the implicit scheme (τ = 0.025).

Acknowledgements This work was supported by the French National Research Agency (ANR) through the EXIFSI project (ANR-12-JS01-0004)