Florent Benaych-Georges
email: florent.benaych@upmc.fr

RECTANGULAR R-TRANSFORM AS THE LIMIT OF RECTANGULAR SPHERICAL INTEGRALS

Keywords: 2000 Mathematics Subject Classification. 15A52, 46L54, 60B15. Key words and phrases. Random Matrices, Free Probability, Rectangular R-transform, Haar Measure, Spherical Integrals

. More specifically, we study the limit, as n, m tend to infinity, of

is a certain n × m deterministic matrix and U n , V m are independent Haar-distributed orthogonal or unitary matrices with respective sizes n×n, m×m. We prove that when the singular law of M n converges to a probability measure µ, for θ small enough, this limit actually exists and can be expressed with the rectangular R-transform of µ. This gives an interpretation of this transform, which linearizes the rectangular free convolution, as the limit of a sequence of log-Laplace transforms.

Introduction

In this article, we study the limit, as n, m tend to infinity in such a way that n/m tends to a limit λ ∈ [0, 1], of

1 n log E{exp[ √ nmθ ℜ(Tr(E n U n M n V m ))]},
where θ ∈ R, M n is a certain n × m deterministic matrix, U n , V m are independent Haardistributed orthogonal or unitary matrices with respective sizes n × n, m × m, E n is an m × n elementary matrix (i.e. a matrix which entries are all zero, except one of them, which is equal to one) and ℜ(•) denotes the real part.

The departure point of this study is the work of Collins, Zinn-Justin, Zuber, Guionnet, Maïda, Śniady, Mingo and Speicher who proved, in the papers [START_REF] Zinn-Justin | On some integrals over the U(N ) unitary group and their large N limit[END_REF][START_REF] Collins | Moments and cumulants of polynomial random variables on unitary groups, the Itzykson-Zuber integral and free probability[END_REF][START_REF] Guionnet | Maïda A Fourier view on the R-transform and related asymptotics of spherical integrals[END_REF][START_REF] Collins | Śniady Integration with respect to the Haar measure on unitary, orthogonal and symplectic group[END_REF][START_REF] Collins | Śniady New scaling of Itzykson-Zuber integrals[END_REF][START_REF] Collins | Speicher Second order freeness and fluctuations of random matrices. III. Higher order freeness and free cumulants[END_REF], that under various hypotheses on some n × n matrices A n and B n and a positive exponent α, the asymptotics of 1 n α log E{exp[nθ Tr(B n U n A n U * n )]} are related to free probability theory. For example, it has been proved [START_REF] Guionnet | Maïda A Fourier view on the R-transform and related asymptotics of spherical integrals[END_REF]Th. 2] that if the spectral law (i.e. uniform distributions on eigenvalues) of the self-adjoint matrix A n converges to a compactly supported probability measure µ and F n = diag(1, 0, . . . , 0), then for θ small enough, [START_REF] Anderson | An Introduction to Random Matrices[END_REF] 1

n log E{exp[nθ Tr(F n U n A n U * n )]} -→ n→∞ β 2 2θ β 0 R µ (t)dt,
where R µ is the so-called R-transform of µ and β = 1 or 2 according to wether we consider real or complex matrices. The R-transform is an integral transform of probability measures on R. Its main property is that it linearizes the additive free convolution ⊞, the binary operation on probability measures on R which can be defined by the fact that for A, B large self-adjoint random matrices with spectral laws tending to µ A , µ B (as the dimension goes to infinity) and U a Haar-distributed orthogonal or unitary matrix independent of A and B, the spectral law of A + UBU * tends to µ A ⊞ µ B : the free convolution ⊞ can be thought as the analogue, for the spectral laws of certain large random matrices, of the classical convolution for real random variables. For all probability measures µ, ν on R, we have

(2) R µ⊞ν (t) = R µ (t) + R ν (t) (for t in a neighborhood of zero).

Hence in the analogy between the free convolution and the classical one, the R-transform plays the role of the log-Laplace transform, and (1) gives a concrete sense to this: the R-transform (more specifically its primitive, which also satisfies (2)), is the limit of a certain sequence of log-Laplace transforms.

Let us now describe the content of our paper. For each λ ∈ [0, 1], another free convolution, denoted by ⊞ λ and called the rectangular free convolution with ratio λ, does the same job as ⊞ for the singular laws (i.e. uniform distributions on singular values) of rectangular n × m random matrices which dimensions n, m tend to infinity in such a way that n/m tends to λ: for n, m large integers such that n/m ≃ λ, for A, B some n × m real or complex matrices with singular laws ν A , ν B and U, V Haar-distributed orthogonal or unitary matrices independent of A and B, the singular law of A + UBV is approximately ν A ⊞ λ ν B (see [START_REF]Benaych-Georges Rectangular random matrices, related convolution[END_REF] or the introduction of [START_REF]Benaych-Georges On a surprising relation between the Marchenko-Pastur law, rectangular and square free convolutions[END_REF] for a more precise definition of ⊞ λ ). Like the R-transform for ⊞ and the log-Laplace transform for the classical convolution, an integral transform linearizes ⊞ λ . It is called the rectangular R-transform with ratio λ and is denoted by C (λ) : for all probability measures µ, ν on [0, +∞), we have

(3) C (λ) µ⊞ λ ν (t) = C (λ) µ (t) + C (λ) ν (t) (for t in a neighborhood of zero).
The main result of the paper gives an interpretation of the rectangular R-transform (more specifically its primitive, which also satisfies (3)) as the limit of a sequence of log-Laplace transforms: we prove that if the singular law of M n tends to a probability measure µ and n/m tends to a limit λ ∈ [0, 1] as n, m tend to infinity, then for θ small enough, for E n a sequence of m n × n elementary matrices, (4)

1 n log E{exp[ √ nmθ ℜ(Tr(E n U n M n V m ))]} -→ n,m→∞ β θ β 0 C (λ) µ (t 2 ) t dt.
Let us mention that free probability theory has initially been built in the area of operator algebras and that concrete relations between free and classical probability theory, like the ones of ( 1) and (4), are not that common.

Let us also mention that expectations of the exponential of traces of polynomials of constant matrices and uniform orthogonal random matrices, which have been extensively studied in physics and also other areas, like information theory, are often called spherical integrals. See e.g. [START_REF] Zvonkin | Matrix integrals and map enumeration: an accessible introduction[END_REF][START_REF] Guionnet | Large deviations asymptotics for spherical integrals[END_REF][START_REF] Guionnet | Large random matrices: lectures on macroscopic asymptotics École d' Été de probabilités de Saint-Flour XXXVI-2006[END_REF] and the references above for the case of square matrices. Spherical integrals involving rectangular matrices are considered in the papers [START_REF] Schlittgen | Generalizations of some integrals over the unitary group[END_REF][START_REF] Ghaderipoor | Tellambura Generalization of some integrals over unitary matrices by character expansion of groups[END_REF][START_REF] Kabashima | Inference from correlated patterns: a unified theory for perceptron learning and linear vector channels[END_REF]. The quantities studied in the paper [START_REF] Kabashima | Inference from correlated patterns: a unified theory for perceptron learning and linear vector channels[END_REF] of Kabashima are closely related to the spherical integral we study here: in Equation ( 8), Kabashima considers exactly the same spherical integral as ours, with the same hypotheses (he supposes the singular law of X to have a limit and p/N to stay bounded), except that he supposes θ to be on the imaginary line, whereas in our paper, θ is real. He is not giving an argument that qualifies as a mathematical proof, but he gives an asymptotic formula in Equation [START_REF] Collins | Speicher Second order freeness and fluctuations of random matrices. III. Higher order freeness and free cumulants[END_REF]. With our vocabulary, this formula expresses

lim n→∞ 1 n log E{exp i Tr(E n U n M n V m )}
as a saddle point value of a certain function. The actual computation of this saddle point is not easy, but his Equation ( 9) has a structure which is quite close to our Equation (29).

The paper is organized as follows. In Section 1, we state the main result of the paper, Theorem 1.2, and discuss it. In Section 2, we recall the precise definition of the rectangular R-transform and prove a result of continuity of the map (λ, µ) -→ C 1. Main result 1.1. Statement. Let us consider, for all n ≥ 1, an integer m n ≥ n such that, as n tends to infinity, n/m n tends to a limit λ ∈ [0, 1] and an n × m n real or complex nonrandom matrix M n whose singular values are strictly bounded, uniformly in n, by a constant K and such that, as n tends to infinity, the singular law of M n converges weakly to a probability measure that we shall denote by µ. Let us define, for θ ∈ R, (5)

I n (θ) = 1 n log E{exp[ √ nm n θ ℜ(Tr(E n U n M n V n ))]},
where U n , V n are independent Haar-distributed orthogonal or unitary (according to whether M n is real or complex) matrices with respective sizes n × n, m n × m n and E n denotes an m n × n elementary matrix (i.e. a matrix which entries are all zero, except one of them, which is equal to one).

In the case where λ = 0, we also suppose that there is α < 2 such that [START_REF] Collins | Moments and cumulants of polynomial random variables on unitary groups, the Itzykson-Zuber integral and free probability[END_REF] for n large enough, m n ≤ n α .

Remark 1.1. Let K be either R or C according to wether we consider real or complex matrices. I n (θ) can also be considered as the Laplace transform of a certain scalar product estimated at a pair of independent random vectors, one of them being a uniform random vector of the unit sphere of K n and the other one being the projection, on K n , of a uniform random vector of the unit sphere of K mn . Indeed, let us denote the singular values of M n by µ n,1 , . . . , µ n,n and introduce (see [START_REF] Horn | Matrix analysis[END_REF]) some orthogonal or unitary matrices P n , Q n with respective sizes n × n, m n × m n such that

M n = P n   µ n,1 0 • • • 0 . . . . . . . . . µ n,n 0 • • • 0   Q n .
Let also, for each n, (i n , j n ) be the index of the non-null entry of E n . Then the j n th row (resp. i n th column)

u n = (u n,1 , . . . , u n,n ) (resp. v n = (v n,1 , . . . , v n,mn ) t ) of U n P n (resp. Q n V n
) is uniformly distributed on the unit sphere of K n (resp. K mn ) and one has (7)

I n (θ) = 1 n log E{exp[ √ nm n θ ℜ( n k=1 u n,k µ n,k v n,k )]}.
The main result of the article is the following one.

Theorem 1.2. Set β = 1 or β = 2 according to wether we consider real or complex matrices. The function I n converges uniformly on every compact subset of (-βK -1 , βK -1 ) to the function

I(θ) = β θ β 0 C (λ) µ (t 2 ) t dt,
where C

µ denotes the rectangular R-transform of µ with ratio λ (its definition is recalled in Section 2 below).

Remark 1.3. Note that the function C (λ) µ is analytic on (-K -2 , K -2
) and vanishes at zero, so I is actually well defined and analytic on (-K -1 , K -1 ).

1.2. Particular cases where the matrices M n are square (λ = 1) or asymptotically flat (λ = 0). Let us recall that the R-transform of a probability measure ν is the function

R ν (z) = G -1 ν (z) - 1 z , for G µ (z) = dµ(t)
z -t (the convention we use is the one of the analytic approach to freeness [START_REF] Hiai | Petz The semicircle law, free random variables, and entropy[END_REF][START_REF] Anderson | An Introduction to Random Matrices[END_REF], which is not exactly the one of the combinatorial approach [START_REF] Nica | Lectures on the combinatorics of free probability[END_REF]: R combinatorics

ν (z) = zR analysis ν (z)).
Let µ s be the symmetrization of µ, defined by µ s (A) = µ(A)+µ(-A) 2 for all Borel subset A of R, and µ 2 be the push-forward of µ by the function t → t 2 .

Corollary 1.4. In the particular case where λ = 1 (resp. λ = 0), the limit I of I n can be expressed via the R-transform of µ s (resp. µ 2 ) in the following way

I(θ) = β θ 2 0 R µs (t)dt, (resp. I(θ) = β θ 2 0 tR µ 2 (t 2 )dt.)
Proof. It suffices to prove that C

1.3.1.

Cumulants point of view. For λ ∈ [0, 1], the rectangular free cumulants with ratio λ of µ have been defined in [START_REF]Benaych-Georges Rectangular random matrices, related convolution[END_REF]Sect. 3.4] (see also [START_REF]Benaych-Georges Rectangular random matrices, related free entropy and free Fisher's information[END_REF]Sect. 2.2]): this is the sequence (c 2k (µ)) k≥1 linked to the moments of µ by [START_REF] Benaych | Georges Infinitely divisible distributions for rectangular free convolution: classification and matricial interpretation[END_REF]Eq. (4.1)]. Recall also that for X a bounded real random variable, the classical cumulants of X are the numbers Cl k (X) defined by the formula

log E(e zX ) = k≥1 Cl k (X) k! z k .
Differentiating formally the convergence I n (θ) -→ I(θ), one would get the following "classical cumulants interpretation" of the rectangular free cumulants with ratio λ: for all positive integers k,

(8) c 2k (µ) = lim n→∞ (nm n ) k n β 2k-1 (2k -1)! Cl 2k (ℜ(Tr(E n U n M n V n ))).
This formula can be considered as a "rectangular analogue" of [START_REF] Collins | Moments and cumulants of polynomial random variables on unitary groups, the Itzykson-Zuber integral and free probability[END_REF]Th. 4.7]. The author believes that ( 8) can be proved rigorously with one of the following two methods. One of them would be to use the Weingarten calculus, developed by Collins and Śniady, for the computation of the expectation of moments of the entries of the matrices U n , V n (as in the proof of [START_REF] Collins | Moments and cumulants of polynomial random variables on unitary groups, the Itzykson-Zuber integral and free probability[END_REF]Th. 4.7]). The other one would rely on the extension of Theorem 1.2 to complex values of θ and notice that the functions in question there are analytic in θ (so that their convergence implies the one of their derivatives).

1.3.2.

Case where M is chosen at random. If M n is also chosen at random, independently of U n and V n , and the expectation, in [START_REF]Benaych-Georges On a surprising relation between the Marchenko-Pastur law, rectangular and square free convolutions[END_REF], is taken with respect to the randomness of U n , V n and M n , then Theorem 1.2 stays true in certain cases (for example if M n is a standard Gaussian matrix divided by √ m n ), but it can easily be seen that Theorem 1.2 is not true in general anymore. However, if the expectation, in [START_REF]Benaych-Georges On a surprising relation between the Marchenko-Pastur law, rectangular and square free convolutions[END_REF], only concerns the randomness of U n and V n , then I n (θ) is a random variable, and for certain sequences of random matrices M n , more than Theorem 1.2 can be said about its convergence. An important example is given by the case where

M n = A n + P n B n Q n with A n ,

Preliminaries about the rectangular R-transform

Let µ be a probability measure on the real line which support is contained in [-K, K], with K > 0 (we do not suppose µ to be symmetric, how it was the case in the initial definition of the rectangular R-transform). Let us define the generating function of the moments of µ 2

M µ 2 (z) = t∈R t 2 z 1 -t 2 z dµ(t) = t∈R 1 1 -t 2 z dµ(t) -1 (z ∈ [0, K -2 )).
It can easily be proved that M µ 2 is nonnegative and non decreasing on [0, K -2 ). Let us define, for λ ∈ [0, 1], T (λ) (z) = (λz + 1)(z + 1), and

H (λ) µ (z) = zT (λ) (M µ 2 (z)).
Then

H (λ)
µ defines an increasing analytic diffeomorphism (in this paper, for I an interval, we shall call an analytic function on I a function on I which extends analytically to an open subset of

C containing I) from [0, K -2 ) onto the (possibly unbounded) interval [0, lim z↑K -2 H (λ) µ (z)) such that H (λ) µ (0) = 0, ∂ z H (λ) µ (0) = 1, H (λ) µ (z) ≥ z, lim z↑K -2 H (λ) µ (z) ≥ K -2 .
We denote its inverse by

H (λ) µ -1
. Moreover, T (λ) defines an analytic increasing diffeomorphism from [-1, +∞) to [0, +∞), thus one can define the rectangular R-transform with ratio λ of µ:

(9) C (λ) µ (z) = T (λ) -1 z H (λ) µ -1 (z)
for z = 0, and C (λ) µ (0) = 0, which is analytic and non negative on the interval [0, lim z↑K -2 H (λ)

µ (z)) (which always contains [0, K -2 )).
By Theorems 3.8 and 3.12 of [START_REF]Benaych-Georges Rectangular random matrices, related convolution[END_REF], the rectangular R-transform characterizes symmetric measures, and for all pair µ 1 , µ 2 of compactly supported symmetric probability measures, µ 1 ⊞ λ µ 2 is characterized by the fact that in a neighborhood of zero,

C (λ) µ 1 ⊞ λ µ 2 (z) = C (λ) µ 1 (z) + C (λ) µ 2 (z).
The following theorem states the continuity of the mapping (λ, µ) -→ C (λ) µ in a way which is quite different from the one of Theorem 3.11 of [START_REF]Benaych-Georges Rectangular random matrices, related convolution[END_REF] (where λ was fixed).

Theorem 2.1. Fix K > 0, let µ n be a sequence of probability measures on [-K, K] which converges weakly to a limit µ, and let λ n be a sequence of elements of [0, 1] which converges Proof. Recall that C (λ) µ is defined by [START_REF] Collins | Speicher Second order freeness and fluctuations of random matrices. III. Higher order freeness and free cumulants[END_REF]. Since, by Heine's Theorem, (λ, z) → T (λ) -1 (z) is uniformly continuous on every compact subset of [0, 1] × [0, +∞), it suffices to prove that

z H (λn) µn -1 (z) converges to z H (λ) µ -1 (z)
uniformly on every compact subset of [0, K -2 ).

Claim a : For each compact subset E of C\[K -2 , +∞), there is a constant k E such that for any law ν on [-K, K], for any c ∈ [0, 1], for any z ∈ E,

|T (c) (M ν 2 (z))| ≤ k E . Indeed, for z ∈ C\[K -2 , +∞), for any law ν on [-K, K], for any c ∈ [0, 1], T (c) (M ν 2 (z)) = (t,t ′ )∈[-K,K] 2 1 (1 -zt 2 )(1 -zt ′ 2 ) dν(t)d(cν + (1 -c)δ 0 )(t ′ ), thus k E = max{|1 -zt 2 | -2 ; |t| ≤ K, z ∈ E} is convenient.
Claim b : As ν varies in the set of laws on [-K, K] and c varies in [0, 1], the set of functions

z ∈ [0, K -2 ) -→ z H (c) ν -1
(z) is relatively compact for the topology of uniform convergence on every compact subset of [0, K -2 ). By Ascoli's Theorem, to prove Claim b, it suffices to prove that this family is uniformly bounded and uniformly Lipschitz on every compact subset of [0, K -2 ). Let us fix ν a law on [-K, K] and c ∈ [0, 1]. Note that we have

z H (c) ν -1 (z) = H (c) ν (z) z • H (c) ν -1 (z), ∂ z z H (c) ν -1 (z) = zH (c) ′ ν (z) -H (c) ν (z) z 2 H (c) ′ ν (z) • H (c) ν -1 (z).
Since, moreover, for all z ∈ [0, K -2 ), H

(c) ν -1 (z) ≤ z (indeed, for all z ∈ [0, K -2 ), H (c)
ν (z) ≥ z), it suffices to verify that the sets of functions

{z -→ H (c) ν (z) z ; ν law on [-K, K], c ∈ [0, 1]} and {z -→ zH (c) ′ ν (z)-H (c) ν (z) z 2 H (c) ′ ν (z) ; ν law on [-K, K], c ∈ [0, 1]}
are uniformly bounded on every compact subset of [0, K -2 ). The family of functions

H (c) ν (z) z = T (c) (M ν 2 (z)), indexed by ν, c
, is a family of analytic functions on C\[K -2 , +∞) which is uniformly bounded on every compact subset of C\[K -2 , +∞) (by Claim a). As a consequence, the family of the derivatives ∂ z

H (c) ν (z) z
is also uniformly bounded on every compact subset of C\[K -2 , +∞). Since

zH (c) ′ ν (z) -H (c) ν (z) z 2 H (c) ′ ν (z) = 1 H (c) ′ ν (z) ∂ z H (c) ν (z) z and H (c) ′ ν (z) ≥ 1 on [0, K -2 ), Claim b is proved. Hence one can suppose that z H (λn) µn -1 (z)
converges to a function f uniformly on every compact of [0, K -2 ). Let us fix z ∈ [0, K -2 ) and let us prove that f

(z) = z H (λ) µ -1 (z)
. If z = 0, it is clear (since all these functions are implicitly defined to map 0 to 1). Suppose that z > 0. Note that f (z) = 0, because for all n, It suffices to prove that l = H (λ) µ -1 (z), i.e. that H (λ)

µ (l) = z. Since H (λ) µ (l) = lim n→∞ H (λ) µ (H (λn) µn -1 (z)),
it suffices to prove that H uniformly on every compact subset of [0, K -2 ). But it is easy to see, using [1, Th. C.11], that M µ 2 n converges to M µ 2 uniformly on every compact subset of [0, K -2 ) and then that H 3. Proof of Theorem 1.2 3.1. Preliminaries. We shall use the following lemmas several times in the paper. Let

• denote the canonical euclidian norm on each R d .

Lemma 3.1. Let (G i ) i≥1 be a family of independent real random variables with standard Gaussian law. Let T be fixed and let, for each n, (σ n,1 , . . . , σ n,n ) ∈ [0, T ] n be such that

(10) 1 n n i=1 σ 2 n,i = 1.
Let us define, for each n, X n = (σ n,1 G 1 , . . . , σ n,n G n ). Then for all κ ∈ (0, 1 2 ), for n large enough,

P{| X n - √ n| ≥ n 1 2 -κ } ≤ 2T 4 n 2κ-1 .
Proof. Note that by [START_REF] Ghaderipoor | Tellambura Generalization of some integrals over unitary matrices by character expansion of groups[END_REF], the random variable

N n := Xn 2 n -1 is centered. Moreover, Var(N n ) = Var(G 2 1 ) n 2 n i=1 σ 4 n,i ≤ 2T 4 n .
It follows, by Tchebichev's inequality, that for all κ ∈ (0, 1 2 ),

P{|N n | ≥ n -κ } ≤ 2T 4 n 2κ-1 .
To deduce that for n large enough,

P X n √ n -1 ≥ n -κ ≤ 2T 4 n 2κ-1 ,
it suffices to notice that the function √ • is 1-Lipschitz on [1/4, +∞) and that n -κ ≤ 3/4

for n large enough.

Lemma 3.2. Let µ be a probability measure whose support is contained in

[-K, K], fix λ ∈ [0, 1], θ ∈ [0, K -1 ) and define γ = C (λ) µ (θ 2 ). Then (11) M µ 2 θ 2 T (λ) (γ) = γ.
Proof. By the definition of C (λ) µ

given in ( 9),

θ 2 H (λ) µ -1 (θ 2 ) = T (λ) (γ), hence θ 2 T (λ) (γ) = H (λ) µ -1 (θ 2 ). Since γ ≥ 0, θ 2 T (λ) (γ) ∈ [0, K -2
) and one can apply the function H (λ) µ on both sides. We get

H (λ) µ θ 2 T (λ) (γ) = θ 2 , i.e. θ 2 T (λ) (γ) T (λ) M µ 2 θ 2 T (λ) (γ) = θ 2 .
It follows that

T (λ) M µ 2 θ 2 T (λ) (γ) = T (λ) (γ). Since both M µ 2 θ 2 T (λ) (γ)
and γ are nonnegative real numbers, one gets [START_REF] Guionnet | Large deviations asymptotics for spherical integrals[END_REF].

Lemma 3.3. Let X n be a sequence of nonnegative random variables, with positive expectations. Let Z n be a sequence of real random variables such that there exists deterministic constants C, η > 0 such that for all n, |Z n | ≤ Cn 1-η . Then as n tends to infinity,

1 n log E(X n e Zn ) = 1 n log E(X n ) + o(1).
Proof. It suffices to notice that we have X n e -Cn 1-η ≤ X n e Zn ≤ X n e Cn 1-η .

3.2.

Notation for the proof of Theorem 1.2. In the next sections, o(1) shall denote any sequence of functions on (-K -1 , K -1 ) which converges to zero as n tends to infinity, uniformly on every compact subset of (-K -1 , K -1 ). Also, we shall work with the notation introduced in Remark 1.1 and handle I n (θ) via Formula (7).

3.3.

Reduction to the case where all singular values of M n are positive. Let us suppose the result to be proved in the particular case where for all n, k, µ n,k > 0, and let us prove it in the general case. We set, for each n, k, μn,k = µ n,k + min{m -2 n , (K -µ n,k )/2} and define the perturbation of I n (θ)

Ĩn (θ) = 1 n log E{exp[ √ nm n θ n k=1 ℜ(u n,k μn,k v n,k )]}.
The uniform law on the μn,k 's converges weakly to µ as n tends to infinity and we have 0 < μn,k < K, so by hypothesis, if follows that lim n→∞ Ĩn (θ) = I(θ). Note moreover that

Ĩn (θ) = 1 n log E{exp[ √ nm n θ n k=1 ℜ(u n,k µ n,k v n,k )]e Zn }, with
Z n = √ nm n θ n k=1 ℜ(u n,k v n,k ) min{m -2 n , (K -µ n,k )/2}.
Since |Z n | ≤ K -1 , Lemma 3.3 allows us to claim that lim n→∞ I n (θ) = I(θ).

3.4. Deducing the complex case from the real one. Let us explain how one can deduce the complex case from the real one. Let us use, in this paragraph, the notation

I (β)
n,mn (θ, M n ) to emphasize on the value of each of the parameters defining I n (θ). We have

I (2) n,mn (θ, M n ) = 1 n log E{exp[ √ nm n θ n k=1 ℜ(u n,k µ n,k v n,k )]} = 1 n log E{exp[ √ nm n θ n k=1 µ n,k (ℜ(u n,k )ℜ(v n,k ) -ℑ(u n,k )ℑ(v n,k ))]} = 2I (1) 2n,2mn θ 2 , M n 0 0 -M n (12)
Indeed, for (z n,1 , . . . , z n,n ) a vector with uniform distribution on the unit sphere of C n the vector (ℜ(z 1 ), ℑ(z 1 ), . . . , ℜ(z n ), ℑ(z n )) has uniform distribution on the unit sphere of R 2n (use the realization of such vectors as the projection of standard Gaussian vectors on the sphere to see it).

Since the singular values of M n 0 0 -M n are the one of M n with multiplicity multiplied by two, (12) allows to deduce the complex case from the real one.

Let us now prove Theorem 1.2 in the case where all µ n,k 's are positive and where β = 1.

3.5. Proof of Theorem 1.2: a) Expression of I n (θ) with a Gaussian integral. As written above, we suppose from now on that all µ n,k 's are positive and that β = 1. In this section, we shall first explain how to replace, in Formula (7), √ nu n,k and √ m n v n,k by independent standard Gaussian variables (Formula ( 17)) and then inject (quite artificially first) C

µ (θ 2 ) in the formula of I n (θ) (Equation ( 21)). For each n, let us define the function

f n : ((x 1 , . . . , x n ), (y 1 , . . . , y mn )) ∈ R n × R mn -→ n k=1 µ n,k x k y k .
By [12, Sect. 1.2.1], up to a change of the probability space which does not change the expectation, one can suppose that there are independent standard Gaussian vectors x n , y n of R n , respectively R mn , such that

u n = x n x n , v n = y n y n . Let us fix κ ∈ (0, 1/2). If λ > 0, the precise choice of κ ∈ (0, 1/2) is irrelevant, but if λ = 0, we choose κ ∈ ( α-1 2 , 1
2 ) (α is the one of ( 6)). Let us now define the set

A n := (x, y) ∈ R n × R mn ; x - √ n ≤ n 1 2 -κ , | y - √ m n | ≤ m 1 2 -κ n .
The event {(x n , y n ) ∈ A n } is independent of (u n , v n ) (because the density of the law of a standard Gaussian vector is a radial function), thus

I n (θ) = 1 n log E ½ (xn,yn)∈An exp( √ nm n θf n (u n , v n )) - 1 n log P(A n ). Moreover, by Lemma 3.1, P{(x n , y n ) ∈ A n } -→ 1 as n → ∞, thus (13)
I n (θ) = 1 n log E ½ (xn,yn)∈An exp( √ nm n θf n (u n , v n )) + o(1).
Moreover, note that on the event

{(x n , y n ) ∈ A n }, √ n -n 1 2 -κ ≤ x n ≤ √ n + n 1 2 -κ √ m n -m 1 2 -κ n ≤ y n ≤ √ m n + m 1 2 -κ n , thus, since m n ≥ n, (14)
√ nm n -3 √ m n n 1 2 -κ ≤ x n y n ≤ √ nm n + 3 √ m n n 1 2 -κ . If λ > 0, since m n /n is bounded, it follows that there is a deterministic constant C independent of n such that on on the event {(x n , y n ) ∈ A n }, (15) | x n y n - √ nm n | ≤ Cn 1-κ .
If λ = 0, it follows from ( 14) and ( 6) that for η = 1-α 2 + κ (which is positive by definition of κ), for n large enough, ( 16)

| x n y n - √ nm n | ≤ 3n 1-η .
Note that by [START_REF] Guionnet | Large random matrices: lectures on macroscopic asymptotics École d' Été de probabilités de Saint-Flour XXXVI-2006[END_REF], Note that on the event {(x n , y n ) ∈ A n }, we have

I n (θ) = 1 n log E[½ (
n -2n 1-κ ≤ n -2n 1-κ + n 1-2κ ≤ x n 2 ≤ n + 2n 1-κ + n 1-2κ ≤ n + 3n 1-κ n -2n 1-κ ≤ n -2nm -κ n + nm -2κ n ≤ n mn y n 2 ≤ n + 2nm -κ n + nm -2κ n ≤ n + 3n 1-κ .
thus for all n, on the event

{(x n , y n ) ∈ A n }, (18)
x n 2 -n + n m n y n 2 -n ≤ 6n 1-κ .
Now, let us define, for each n,

(19) γ n (θ) = C ( n mn ) µn (θ 2 ) for µ n = 1 n n k=1 δ µ n,k .
Note that µ n is the singular law of M n , which tends to µ. Hence by Theorem 2.1, we have

(20) γ n (θ) -→ n→∞ C (λ) µ (θ 2 )
uniformly on every compact subset of (-K -1 , K -1 ), so by [START_REF] Nica | Lectures on the combinatorics of free probability[END_REF], for every such compact set E, there is a constant Q E such that for all n, for all θ ∈ E, on the event {(x n , y n ) ∈ A n }, we have

|γ n (θ)( 1 2 x n 2 + n 2m n y n 2 -n)| ≤ Q E n 1-κ .
Hence, by [START_REF] Maïda | Large deviations for the largest eigenvalue of rank one deformation of Gaussian ensembles[END_REF] and Lemma 3.3,

I n (θ)= 1 n log E ½ (xn,yn)∈An exp θf n (x n , y n ) -γ n (θ) 1 2 x n 2 + n 2m n y n 2 -n + o(1) =γ n (θ) + 1 n log E ½ (xn,yn)∈An exp θf n (x n , y n ) -γ n (θ) 1 2 x n 2 + n 2m n y n 2 :=Jn(θ)
+o [START_REF] Anderson | An Introduction to Random Matrices[END_REF].

Thus, by ( 20), ( 21)

I n (θ) = C (λ) µ (θ 2 ) + 1 n log J n (θ) + o(1).
3.6. Proof of Theorem 1.2: b) Convergence of the Gaussian integral. We have, assimilating the vectors of R n and R mn with column-matrices, Notation: In this section, in order to lighten the notation, we shall write J n for J n (θ), a n for a n (θ), etc. We shall also use the notation of the matricial functional calculus (thus assimilate a and aI n , etc.).

(22) J n (θ) = (2π) -n+mn 2 x∈R n ,y∈R mn ½ An (x, y) exp -
∆ = (b -a) 2 + 4Λ 2 , r ± = a + b ± √ ∆ 2 , f ± = 1 2∆ ± 2(b -a) √ ∆ and T = a Λ Λ b , D = r + 0 0 r -, P = 2Λf + 2Λf - (b -a)f + + √ ∆f + (b -a)f -- √ ∆f -.
Then P is an orthogonal matrix and we have T = P DP t .

Proof. One can easily verify that P is orthogonal. Let us define

Q = 2Λ 2Λ (b -a) + √ ∆ (b -a) - √ ∆ , H = f + 0 0 f -.
Then P = QH. One can easily verify that T Q = QD. If follows that T QH = QDH.

Since HD = DH, T QH = QHD, i.e. T P = P D, thus T = P DP t .

For θ = 0, let us define ∆ n , r ± n , f ± n as in the lemma, using Λ n instead of Λ, a n instead of a and b n instead of b. Let us define P n in the same way, extended to an (n+m n )×(n+m n ) matrix by adding I mn-n on the lower-right corner, i.e.

P n =   2Λ n f + n 2Λ n f - n 0 (b n -a n )f + n + √ ∆ n f + n (b n -a n )f - n - √ ∆ n f - 0 0 0 I mn-n   ,
and D n extended to an (n + m n ) × (n + m n ) matrix by adding b n I mn-n on the lower-right corner, i.e.

D n =   r + n 0 0 0 r - n 0 0 0 b n I mn-n   . For θ = 0, we set r ± n = 1, P n = D n = I n+mn . Let us denote, for X an (n + m n ) × (n + m n ) matrix, X(A n ) = {X x y ; (x, y) ∈ A n }.
Let us also introduce a standard Gaussian random column vector in R n+mn , that we shall denote by

Z n = (Z + n,1 , . . . , Z + n,n :=Z + n , Z - n,1 , . . . , Z - n,n :=Z - n , Z 0 n,1 , . . . , Z 0 n,mn-n :=Z 0 n ) t .
We have, by (22) and Lemma 3.4,

J n = (2π) -n+mn 2 An exp{- 1 2
x t y t P n D n P t n x y }dxdy.

Thus, since P n is an orthogonal matrix,

J n = (2π) -n+mn 2 P t n (An) exp{- 1 2 x t y t D n x y }dxdy.
Hence, by definition of D n , we have

J n = (2π) -n+mn 2 [b mn-n n n i=1 r + n,i r - n,i ] -1/2 √ DnP t n (An) exp{- 1 2 ( x 2 + y 2 )}dxdy,
which, by definition of Z n , can be written

(23) J n = [b mn-n n n i=1 (a n b n -λ 2 n,i )] -1/2 P{Z n ∈ D n P t n (A n )} =P{PnD -1/2 n

Zn∈An}

Let X n = (X n,1 , . . . , X n,n ) t be the vector of the first n coordinates of P n D -1/2 n Z n and Y n = (Y n,1 , . . . , Y n,mn ) t be the one of the m n last ones. By definition of the set A n , we have (24)

P n D -1/2 n Z n ∈ A n ⇐⇒ X n - √ n ≤ n -κ and | Y n - √ m n | ≤ m -κ n . Claim : Both events {| X n - √ n| ≤ n -κ } and Y n - √ m n ≤ m -κ n
have probabilities tending to one as n tends to infinity, uniformly on every compact subset of (-K -1 , K -1 ) (the random vectors X n and Y n depend indeed on θ).

For θ = 0, X n (resp. Y n ) is a standard Gaussian random vector of R n (resp. R mn ). For θ = 0, by the definitions of P n and D n ,

X n = 2Λ n (f + n (r + n ) -1/2 Z + n + f - n (r - n ) -1/2 Z - n ), Y n = (b n -a n + √ ∆ n )f + n (r + n ) -1/2 Z + n + (b n -a n - √ ∆ n )f - n (r - n ) -1/2 Z - n b -1/2 n Z 0 n .
Thus for each n, X n (resp. Y n ) has the law of (σ n,1 G 1 , . . . , σ n,n G n ) (resp. (σ ′ n,1 G 1 , . . . , σ ′ n,mn G mn )), for (G i ) i≥1 a family of independent real random variables with standard Gaussian law and where if θ = 0, all σ n,i 's and σ ′ n,i 's are equal to 1, whereas if θ = 0, for each i = 1, . . . , n,

a n + √ ∆ n ) 2 (a n + b n + √ ∆ n )[2(b n -a n ) √ ∆ n + 2∆ n ] + 2( √ ∆ n -(b n -a n )) 2 (a n + b n - √ ∆ n )[-2(b n -a n ) √ ∆ n + 2∆ n ] .
Hence by Lemma 3.1, to prove the claim, it suffices to prove: ∀ε > 0, sup A straightforward computation leads, for θ = 0, to the formula

σ 2 n,i = -16b n λ 2 n,i (b 2 n + ∆ n,i -a 2 n ) 2 -4b 2 n ∆ n,i
.

By hypothesis, µ n , which is defined in [START_REF] Schlittgen | Generalizations of some integrals over the unitary group[END_REF], converges weakly to µ. Using [START_REF] Zinn-Justin | On some integrals over the U(N ) unitary group and their large N limit[END_REF] where in the case where λ = 0, 1 2λ log(1 + λγ) has to be understood as γ 2 . By [START_REF] Zvonkin | Matrix integrals and map enumeration: an accessible introduction[END_REF], one gets, still writing γ for C (λ) µ (θ 2 ), (29)

I n (θ) = γ - 1 2λ log(1 + λγ) - log(1 + γ) 2 - 1 2 t∈[-K,K] log{1 - θ 2 T (λ) (γ)
t 2 }dµ(t)

:=f (θ)

+o [START_REF] Anderson | An Introduction to Random Matrices[END_REF].

I(0) = f (0) = 0 (indeed, by [START_REF] Collins | Speicher Second order freeness and fluctuations of random matrices. III. Higher order freeness and free cumulants[END_REF], C

µ (0) = 0). So to conclude the proof of Theorem 1.2, it suffices to verify that I and f have the same derivatives on (-K -1 , K -1 ). Using [START_REF] Guionnet | Large deviations asymptotics for spherical integrals[END_REF], it can easily be proved that both derivatives are equal to γ/θ.

Aknowledgements:

The author would like to thank Mylène Maïda for her comments on a draft of this paper and also both referees for their careful reading of the paper and their remarks.

  last, Section 3 is devoted to the proof of Theorem 1.2, following the ideas of the proof of [12, Th. 2].

( 1 )

 1 µ (t 2 ) = tR µs (t) and that C (0) µ (t) = tR µ 2 (t). The second equation can be found in [4, Lem. 3.2 or Sect. 3.6]. The first equation follows from the fact that for all λ, C (λ) µ = C (λ) µs and from the fact that for all symmetric probability measure ν, by [4, Sect. 3.6], C(1)ν (z 2 ) = zR ν (z).

1. 3 .

 3 Possible extensions of Theorem 1.2.

  to a limit λ ∈ [0, 1]. Then the sequence of functions C (λn) µn converges to C (λ) µ uniformly on every compact subset of [0, K -2 ).

≥ 1 .

 1 Let us denote l = z f (z) .

  every compact subset of [0, K -2 ).

  xn,yn)∈An e θfn(xn,yn)+ θfn(xn,yn) xn yn ( √ nmn-xn yn ) ] + o(1), and that for all n, k, 0 ≤ µ k,n ≤ K, which implies that fn(xn,yn) xn yn ≤ K. Hence by Lemma 3.3 and (15) (or (16) if λ = 0), (17) I n (θ) = 1 n log E ½ (xn,yn)∈An e θfn(xn,yn) + o(1).

  θ)I n Λ n (θ) 0 n,mn-n Λ n (θ) b n (θ)I n 0 n,mn-n 0 mn-n,n 0 mn-n,n b n (θ)I mn-n   , where a n (θ) = 1 + γ n (θ), b n (θ) = 1 + n mn γ n (θ) and Λ n (θ) is the diagonal n × n matrix with diagonal entries λ n,1 (θ) := -θµ n,1 , . . . , λ n,n (θ) := -θµ n,n .

Lemma 3 . 4 .

 34 Let us fix n ≥ 1 and let a, b be real numbers and Λ an invertible diagonal real n × n matrix. Let us define

σ 2 n,i = 4λ 2 n,i 2 ( 2 n,i 2 (

 2222 2∆ n,i + 2(b n -a n ) ∆ n,i )(a n + b n + ∆ n,i ) +4λ 2∆ n,i -2(b n -a n ) ∆ n,i )(a n + b n -∆ n,i ),for each i = n + 1, . . . , m n , σ ′ n,i 2 = b -1n and for each i = 1, . . . , n,

|θ|≤K - 1

 1 first that (25) and (26) both hold when θ = 0.

  Strong continuity property for the rectangular spherical integrals. One other way to extend this work, suggested to us by a referee, would be to use (28) to prove a strong continuity property for the rectangular spherical integrals. in the spirit of Proposition 2.1 or Lemma 2.3 of[START_REF] Maïda | Large deviations for the largest eigenvalue of rank one deformation of Gaussian ensembles[END_REF].

	To prove it, the ideas are the same as the ones of [12, Sect. 6.1 and 6.2]: first prove that
	the random variable	1 n	log e √ nmnθ ℜ(Tr(EnUnMnVn)) dU n dV n
	concentrates around its mean (to do it, use [1, Cor. 4.4.30] instead of [12, Lem. 24] in
	order to be allowed to consider the complex case) and then the ideas of [12, Sect. 6.2].
	Since the singular law of M

B n deterministic matrices having limit singular laws µ A , µ B and P n , Q n Haar-distributed orthogonal or unitary matrices with respective sizes n and m n . In this case, one can prove (with technical additional hypotheses), that almost surely, lim n→∞ 1 n log e √ nmnθ ℜ(Tr(EnUnMnVn)) dU n dV n = lim n→∞ 1 n log e √ nmnθ ℜ(Tr(EnUnAnVn)) dU n dV n + 1 n log e √ nmnθ ℜ(Tr(EnUnBnVn)) dU n dV n . n converges almost surely to µ A ⊞ λ µ B , this gives a new proof of (3). 1.3.3.

  and[START_REF] Anderson | An Introduction to Random Matrices[END_REF] Th. C.11], one easily sees that, writing γ for C

							(λ) µ (θ 2 ), we have
	1 n	log(J n (θ)) = -	1 2λ	log(1 + λγ) -	log(1 + γ) 2	-	1 2 t∈[-K,K]	log{1 -	θ 2 T (λ) (γ)	t 2 }dµ(t) + o(1),

This work was partially supported by the Agence Nationale de la Recherche grant ANR-08-BLAN-0311-03.

But (removing the indices)

It follows, writing γ n for γ n (θ), that

.

By definition of γ n (θ), we have γ n (θ) ≥ 0, hence T ( n mn ) (γ n (θ)) ≥ 1. Since for all n, i, |µ n,i | ≤ K, it follows that the first part of (25) holds. Moreover, by the definition of µ n given in [START_REF] Schlittgen | Generalizations of some integrals over the unitary group[END_REF], we have

.

By [START_REF] Guionnet | Large deviations asymptotics for spherical integrals[END_REF], it follows that the second part of (25) also holds.

Let us now prove (26). A straightforward computation leads, for θ = 0 and i ≤ n, to the formula

,

. The first part of (26) holds for the same reasons as the first part of (25) above. Moreover, writing γ n for γ n (θ), we have

.

By [START_REF] Guionnet | Large deviations asymptotics for spherical integrals[END_REF], it follows that the second part of (26) also holds.

The proof of the claim is complete. As a consequence, by (24), the probability of the event {P n D -1/2 n Z n ∈ A n } tends to one as n tends to infinity, uniformly on every compact subset of (-K -1 , K -1 ) (remember indeed that the matrices P n and D n depend on θ). So by (23), we have, still writing γ n for γ n (θ), (28)

T ( n mn ) (γ n ) t 2 }dµ n (t) + o(1).


Angelo Luiz

Jean-Charles Steffenel

Chantal Boisson

Stéphane Barberot

Eric Gérard

Christophe Hénon

Olivier Jaillet

Michaël Flauzac

Krajecki

Luiz-Angelo Steffenel

Jean-Charles Boisson

Chantal Barberot

Stéphane Gérard

Eric Hénon

Christophe Jaillet

Olivier Flauzac

Michael Krajecki

Deploying a fault-tolerant computing middleware over Grid'5000: performance analysis of CONFIIT and its integration with a quantum molecular docking application

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

CONFIIT is a purely decentralized peer-to-peer middleware. It was designed to cope with joining the computation resources to be used on a local area network or on the Internet, all while providing fault tolerance and autonomy to the peers. This paper presents recent results on the deployment of CONFIIT over Grid'5000. In the first experiment we evaluate the impact of nodes placement on the communication performance when using the distributed mode of CONFIIT. Indeed, CONFIIT relies on a virtual ring for the node management and tasks distribution, so it is essential to evaluate how the token passing mechanism is dependent on the network speed and the ring circumference. Using the well-known Langford's combinatorial problem as a test benchmark, we try to verify the impact of nodes placement in the overall system performance when deploying CONFIIT over a countrywide grid environment. In the second experiment we describe how existing applications can be easily integrated with CONFIIT and deployed on a grid. We selected a quantum molecular docking application that is quite resource consuming but has serious applications on the field of drugs research and enzyme-interaction analysis. Preliminary results with the PDE4-Zardaverine protein demonstrate the feasibility of this approach, obtaining fine results in a reasonable amount of time.

The rest of this paper is organized as follows: Section 2 describes the CONFIIT framework. We detail how the topology management is used to improve robustness, and how tasks are locally and globally scheduled on processors. Section 3 observe the overall performance of CONFIIT as we explore different node placements over Grid'5000. Section 4 details how CONFIIT can be interfaced with an existing algorithm for solving the quantum molecular docking. Finally, Section 5 presents our conclusions. [START_REF] Dewdney | A computer microscope zooms in for a close look at the most complicated object in mathematics[END_REF] The CONFIIT Middleware

CONFIIT outline

The notion of FIIT applications was defined in [START_REF] Krajecki | An object oriented environment to manage the parallelism of the FIIT applications[END_REF], and they are composed by a Finite number of Independent and Irregular Tasks (FIIT). The well-known Mandelbrot's set [START_REF] Dewdney | A computer microscope zooms in for a close look at the most complicated object in mathematics[END_REF] can be seen as a FIIT application: each pixel (or set of pixels) can be computed independently from the others, and its computation time is unpredictable since it depends on the corresponding region. In such a framework, the programmer needs to decide on how to divide the problem into a finite number of independent tasks, and how to compute each individual task. CONFIIT (Computation Over Network for FIIT) [START_REF] Flauzac | Confiit: a middleware for peer-to-peer computing[END_REF], is a middleware for peer-to-peer computing. Each computer collaborating in a CONFIIT computation is called a node. A node is set up with three main basic thread components: a topology and communication manager, a tasks manager and one or several task solvers. The nodes are connected according to a logical oriented ring, set up and maintained by the topological layer of the system. Basically, each node knows its predecessor and successor. Communication between nodes is achieved using a token, which carries the state of computation around the ring and ensures load balancing between nodes. Task status are exchanged to broadcast local knowledge on all nodes, and thus, to compute an accurate global view of the calculus. At the end of the computation, the ring spreads termination on nodes.

Typically, one tasks solver should be launched for each processor on the node. A task manager can cope with several tasks solvers. Over and above the main thread elements, each node owns a set of data representing the local known state of the global computation. A node owns the different parameters of the current computations (a list of tasks and associated results). It is able to set up its local parameters of tasks to be computed. At the beginning of a computation, all tasks are marked as uncomputed. When a task is completed (locally), its result is stored and will be propagated to the whole ring with the token. To prevent loss of time, the task manager schedules a new task without waiting for the token. But the task could have already been scheduled by another node, and will be replicated in the ring. So, the local list of tasks owned by a node is randomly rearranged. Thus, when the task manager picks up the n th task, it probably will be different from the n th task on another node [START_REF] Krajecki | An object oriented environment to manage the parallelism of the FIIT applications[END_REF]. This strategy also guarantees the termination of the computation regardless node faults.

Programming models

Since constraints of a given application could be different and sometimes in contradiction (fault tolerance, efficiency. . . ), CONFIIT offers two main programming models: distributed and centralized mode.

The distributed mode allows an accurate fault tolerance in the computation since task results are locally stored on each node in the community. Thus, a broken computation can be re-launched using already computed tasks. Fig. 1(a) shows information exchanges in the community for a distributed application. At first, the launcher sends the computing request to a node. The request is propagated along the community by the token (dotted arrows). During computation, results of individual tasks are propagated across the community (thick dashed arrows) such that each node could locally store all individual results (data blocks). Concurrently to the computations, information on the global computation is exchanged according to the thin arrows. Another interesting point from this mode is that the launcher only needs to be connected during the initiation phase. At the end of the computation, the global result can be retrieved from any node in the community. The centralized mode reduces the global load of storage space and network communication, with the drawback of reducing fault tolerance. This mode is especially suited for the integration of external applications, which manage themselves the data storage. Fig. 1(b) shows information exchanges in the community for a centralized application. At first, the launcher sends the computing request to a node. The request is propagated along the community by a specific token (dotted arrows) as in the distributed mode, but the launcher must remain connected. During computation, results of individual tasks are sent to the initial launcher (thick dashed arrows), which has the storage in charge (data blocks). As in the distributed mode, information on the global computation evolution is updated through the token (thin arrows). A crash on a computing node is not a problem for the computation since the main community ring is fault tolerant, but a crash on the launcher will stop the computation because the gathering of information cannot be achieved.

Deployment of CONFIIT over Grid'5000

CONFIIT is available as a Java .jar package to simplify the launching of the daemon, the application and the administration tools. To deploy a CONFIIT community over Grid'5000 nodes, we must initially launch the daemons on each site: one "first" daemon that expects the initial connections (launched with the -wait option) and the subsequent nodes that join the community through one existing daemon (using the -node option). Please note that when one daemon contacts the community, it will be inserted in the virtual ring just after that daemon. This way we can control the initial node placement used in the next section. A daemon will launch as many computing threads as cores/processors a machine can hold, unless we explicitly limit this number (with option -thread).

Launch the first daemon on machine-01 user@machine-01$$ java -cp Confiit-0.6.jar CDaemon -init -clean & Launch the daemon on the other nodes (they try to join the community via machine-01) user@machine-02$ java -cp Confiit-0.6.jar CDaemon -clean -node machine-01 ... Back to machine-01 (or any other machine holding the application classes), we can launch the application. CONFIIT will copy the application classes in all nodes, launch the application and manage the tasks completion. user@machine-01$ cd Applications/Langford user@machine-01$ java -cp ../../Confiit-0.6.jar:. Langford 19 6

The CONFIIT community is fault tolerant so it supports both node joining, leaving and even the complete stop of all daemons (in the Distributed mode). Indeed, partial results and tasks completion list are saved in each node (at the ~/.confiit directory) so that an application instance can be continued later (it is enough to restart a CDaemon without the option -clean). This behaviour is especially interesting for the best-effort submission mode in Grid'5000 and to conduct experiences that exceed the maximum reservation limits imposed by the usage agreement.

3 Scalability on a grid: impact of node placement This first experiment analyses the impact of nodes placement on the communication performance when using the distributed mode of CONFIIT. In the case of the distributed mode, the virtual ring not only distributes tasks and informs nodes about their completion, but also replicates the results among the nodes. Hence, the token must also ensure that all nodes receive the results from different tasks. According to the amount of data exchanged, the underlying network performance and the ring round-trip speed may impact the computing performance.

From these aspects, the placement of nodes becomes an important factor to be evaluated. Contrarily to traditional grid applications, which follow a structured hierarchy, dynamic P2P platforms are subjected to node volatility that may reorder the topology in a small amount of time. In the aspects that concern a virtual ring based topology, this means that nodes can be structured according to a geographic distribution (Fig. 2(a)) but also may face worst scenarios, like when the token hops from cluster to cluster (Fig. 2(b)). This diversity of scenarios makes the token round trip time vary by several orders of magnitude, potentially compromising the performance of a platform that is not prepared to face such variations.

Experiment scenarios

In order to evaluate the impact of nodes placement on the performance of CONFIIT, we designed a progressive scenario where we scale-up the number of clusters from 1 to 5, while keeping the same number of computing threads. Our objective is to evaluate how CONFIIT performance behaves with the increment on the ring circumference, on both best case (geographically distributed or geo, as in Fig. 2(a)) and worst case (Fig. 2(b)). Indeed, if we consider the average network latency measured with the ping command, a ring with 60 machines in 5 clusters would take around 46.805ms to do a roundtrip in the best case (geo: Nancy → Bordeaux → Nice → Lille → Toulouse) and 535.788ms to do the same roundtrip in the worst case. Please note that these estimations can be under-evaluated as they do not take into account the communication throughput that is much more dependent on the application communication stack (for instance the Java network stack, in the case of CONFIIT). From this evidence, it is clear that if communication and computation do not overlap efficiently, this roundtrip time may represent a serious performance concern.

In our experiments, we also evaluate the performance of CONFIIT with different task sizes when solving the wellknown Langford combinatorial problem, which consists in a permutation of the sequence of 2n numbers 1, 1, 2, 2, ..., n, n in which the two ones are one unit apart, the two twos are two units apart, and more generally the two copies of each number k are k units apart. For example, a Langford pairing for n = 3 is given by the sequence 2,3,1,2,1,3. Langford's problem is the task of finding Langford pairings for a given value of n. This problem can be modelized as a tree search problem, and a parallel version can be derived by splitting the search tree at depth level d, generating a set of 2 d tasks. In the tests, we varied d from 9 (512 tasks) to 13 (8184 tasks).

Analysis

Table 1 represents the average of 3 runs for each combination of clusters, topology and number of tasks. The ring topology is constructed in the order Nancy → Bordeaux → Nice → Lille → Toulouse for both geo and worst scenarios (the worst scenario alternates machines from each cluster, in the same order). For the matter of comparison, we also indicate the execution time in a single machine. From the analysis of these data, we obtain the following insights:

Impact of nodes placement In spite of the difference between the placement policies geo and worst, the computation times are barely affected by the ring circumference. While the geo strategy generally benefits from a small advantage in comparison with the worst strategy, this difference seems to vanish (or event to invert) when the problem is subdivided in smaller tasks. This can be explained by the task selection mechanism from CONFIIT. Because CONFIIT nodes randomly select unsolved tasks, nodes are allowed to start new tasks even if the token has not yet returned. With more small tasks, computation of tasks can continue with a small probability of "double work", while waiting for the token update. These results are valid for the 10Gbit/s interconnection on Grid'5000, and we cannot exclude performance problems if the inter-cluster networks become too slow in comparison with the local-area network (like the traversing of a PSTN or ADSL link).

Number of clusters

In spite of the increment in the number of clusters, no slowdown could be observed in the experiments. Also, the ratios between the performances of Langford's algorithm in one or several clusters remain stable, which is an interesting fact. Although these results are encouraging, especially when considering grid environments, we believe that further scalability tests should be necessary to determine the limits of the platform if we plan to deploy experiments in open networks.

Impact of task size

We finish the analysis of the experiments by looking on the impact of task sizes on the overall computation time. Table 1 shows that a small number of tasks does not parallelizes as well as when a larger number of tasks is deployed. Actually it is not easy to determine if a task will have a long or small duration, as FIIT tasks are independent and their computation time depends on the evaluation algorithms. Nevertheless, we can estimate that in a combinatorial tree search the more we subdivide the tree, the shorter will be the average computational time of each branch, up to the point where computation/communication overlap reaches its limits.

While CONFIIT proposes a rich API 4 for the development of FIIT applications directly in Java, it also supports the integration of existing external applications, acting this way as a deployment middleware. This section presents the preliminary results obtained in a collaboration with chemistry researchers.

Case Study: quantum molecular docking

Molecular modeling tools are widely used to search for new drugs in medicinal and pharmaceutical fields. Drugs are usually (relatively) small organic molecules called "ligand" and mostly produced their effect by interacting with a biological macromolecule such as protein. Among several molecular modeling techniques, molecular docking is employed to describe the best orientation of a ligand that binds to a particular protein of interest.

In the present work, several computational techniques are combined to carry out molecular docking of a known PDE4 inhibitor (zardaverine) in view of tackling the design of new inhibitors derived from pyridazinone. PDE4 inhibitors act by increasing intracellular concentrations of cyclic AMP, which has a broad range of anti-inflammatory effects on various key effector cells involved in asthma and chronic obstructive pulmonary disease (COPD). The very recent AlgoGen-DivCon [START_REF] Thiriot | Combining a genetic algorithm with a linear scaling semiempirical method for protein-ligand docking[END_REF] code combining a genetic algorithm for conformational search and the Divide and Conquer linear semiempirical quantum method for energy evaluation is applied to the PDE4-zardaverine complex.

Because genetic algorithms are inherently parallel and the evaluation of one chromosome does not affect the evaluation of another chromosome, several evaluations can be carried out simultaneously. Deploying the AlgoGen-DivCon code over a distributed grid environment with the help of CONFIIT allows an improvement of the results without increase the time needed to evaluate each generation. For instance, with a relatively small complex (1000 atoms), one solution can require more than 10 minutes to be evaluated. By distributing the evaluation of all a population of solutions on grid with different level of granularity, we allow a better exploration of the search space and avoid a premature convergence of the algorithm (if the number of processing cores is sufficient).

To assess the relative performance of the deployment of our problem over CONFIIT [START_REF] Flauzac | Confiit: a middleware for peer-to-peer computing[END_REF], we have chosen a test system consisting of the docking of the PDE4-zardaverine complex. The aim of this investigation is to obtain a reliable molecular dockings of PDE4-ligand complexes using a quantum description of the interaction energy obtained with AlgoGen-DivCon in a reasonable amount of time. Thus, we verify whether the program can correctly reproduce the binding mode of the zardaverine co-crystallized with PDE4.

Interfacing AlgoGen-DivCon and CONFIIT

In order to be deployed on grid, the original code combining a python genetic algorithm (GA) with a Fortran executable as evaluation function had to be interfaced with CONFIIT (in Centralized mode). In one hand, the GA does not need to know how the individuals are evaluated (sequentially, on a cluster or a grid). In the other hand, CONFIIT can be used with any algorithms and not only GAs. Therefore, to deploy the application, we use a script generator that relies on two other scripts: the first in Python for configuring the genetic algorithm and the second in shell script to prepare the system and launch CONFIIT. During the evolution of the genetic algorithm, each time an evaluation is required, a query is given to CONFIIT for the current population. CONFIIT distributes the evaluation of the different individuals on the available task solvers of the community. Finally, when the genetic algorithm terminates, an archive of all the results is made and put in the home directory of the user. The implementation of a script generator has been motived by several facts:

the final user (chemists here) does not need (and does not want to know) how all the application works but wants only the results. Consequently, proposing an automation of the generation of the input files is essential. using an application to prepare the experiments allows to verify the parameters and optimize the configuration according to these parameters. For instance, if the user wants to launch the calculus on a simple multi-core machine, the script generator does not enable the use of CONFIIT and configures the genetic algorithm to make a multi-core experimentation. generally, using a grid generally means to use a submission server (OAR or PBS Pro, for example). So, the script generator helps the user to submit its experiment: the scripts prepare the data, send it to the grid, launch the experiment and gather the results from the grid to the user account.

DivconEval class according to the configuration, the genetic algorithm can make the evaluation of the population:

sequentially on a mono-core processor: each individual is written on the file system and the command divcon is called for each respective individual. in parallel on a N -cores processor or N -processors node: N individuals are written on the file system and N instances of divcon are launched. The file system is regularly checked in order to know which individuals were already evaluated. If M individuals were already evaluated, N -M evaluations are launched. The aim is to keep the cores/processors fully charged.

in parallel on a grid: the genetic algorithm writes all the individuals on a N F S location and an instance of the DivconEval class is provided.

In the last case, the CONFIIT community is contacted for evaluating a set of individuals. The DivconEval class contains all the information useful for the community in centralized mode, such as the size of the population and the location of the individuals on the file system. Each task in CONFIIT is identified by a number and, in our case, the task number corresponds to the rank of an individual in the population. The task 1 is the evaluation of the first individual of the population, the task 2 the second, etc. Each task solver of the community evaluates an individual by launching a script indicating the evaluation method (DivCon, in our case).

Preliminary results

As a result of this very preliminary study, the best conformation obtained by the docking is found to be relatively closed to the experimentally observed position indicated by an rmsd of 3,45 Å. As can be seen from Figure 3, the orientation of the zardaverine ligand is properly reproduced. However, it is very likely that the geometry optimization of the ligand we had performed before docking prevents the zaradaverine to be perfectly positioned in the active site of the PDE4 structure. The main interactions distances are reported in Table 2. The best solution emphasizes the key feature of the binding mode that is the interaction between the catechol ether moieties and the Gln284 (see Fig 4). For the matter of comparison, the run time needed for this first calculation in a single processor (12 cores) is about 167 hours for a population of 32 individuals and 500 generations. A total number of 12 008 evaluations has been performed. It is to be noted that no adjustments of the parameters for the docking program has been required to achieve this result and that no other conformations cluster is obtained. This preparatory study reveals that the Algogen-Divcon molecular docking approach is able to sample the conformational space of the zardaverine inhibitor into the PDE4 protein in the presence of metal ions in a reasonable amount of time. Increasing the grid size should allow for exploring a new ligand in less than one day, as well as improving the population size. Of course, further calculations are needed to compare the influence of the parameters set during docking (population size, generations number, size of protein model, etc.). CONFIIT scheduling mechanism proved to be adapted to such problems, which can also take advantage of CONFIIT's fault-tolerance aspects to deploy long-run experiments.

Discussions

This preparatory study reveals that the Algogen-Divcon molecular docking approach is able to sample the conformational space of the zardaverine inhibitor into the PDE4 protein in the presence of metal ions in a reasonable amount of time. Increasing the grid size will reduce the computing time as well as allowing the improvement of the population size. Of course, further calculations are needed to compare the influence of the parameters set during docking (population size, generations number, size of protein model, etc). CONFIIT scheduling mechanism proved to be adapted to such problems, which can also take advantage of CONFIIT's fault-tolerance aspects to deploy long-run experiments. In addition, attempt to include the free energy of solvation into the binding interaction model as well as the change in entropy ∆S between bound and unbound state should be considered for molecular docking investigations. Concerning the quantum method for energy evaluation, some other Hamiltonians should be used such as the PM3-PIF method [START_REF] Bernal-Uruchurtu | Improving description of hydrogen bonds at the semiempirical level: water-water interactions as test case[END_REF], which has been carefully parametrized to improve the description of intermolecular interactions, more precisely, hydrogen bonds.

The next step in the grid deployment of the algorithm is to be able to evaluate the population at two levels: individual and sub-system. Currently the granularity of the deployment is limited to the individual evaluation i.e. an individual is fully evaluated by a single processor. But it can be possible to evaluate an individual in parallel. A MPI version of the evaluation function exists and shall be tested to speed-up the execution time. Nevertheless, in order to have an important population evaluated in parallel, the number of resources required is important. For instance, for evaluating 100 individuals with a 10-nodes individual paralleling evaluation, the ideal case (evaluation in one iteration) needs 1000 computing cores.

Conclusions

This paper aims to present CONFIIT and illustrate its integration on the Grid'5000 network through two recent experiments. The first experiment is a traditional scalability performance analysis where we observe how the geographical disposition of nodes in a grid environment impact on the performance of an application. Using a distributed solver for the Langford's problem as the evaluation subject, we were able to observe the main factors that influence the computation performance, resulting in the fact that CONFIIT is little sensitive to the performances of the network. As tasks computation is almost independent of the token mechanism, the nodes keep selecting uncomputed tasks even without new updates. The experiments show a trade-off between computation and communication overlap that limits the speed-up in some cases.

As CONFIIT proved to be efficient with well-known benchmarks, we tried to demonstrate how real life problems that need a lot of computational resources could also be adapted and deployed in a grid. For instance, we associate with chemistry researchers to develop a solution for a quantum molecular docking problem, which is a very resource expensive problem. CONFIIT allowed us to obtain an efficient grid version for the resolution of this problem, allowing the chemistry researchers to discovery new drugs and/or reach a better understanding of the secondary effects of existing drugs.

Fig. 1 .

 1 Fig. 1. Programming modes

Fig. 2 .

 2 Fig. 2. Node distribution scenarios (a) and (b), and Grid'5000 sites used in the first experiment (c)

Fig. 3 .

 3 Fig. 3. Zardaverine conformations before docking; successive best solutions; individuals of the last generation.

Fig. 4 .

 4 Fig. 4. Selected geometrical parameters from the best docking solution

Table 1 .

 1 Computation times when varying the number of clusters and tasks

		512 tasks 1024 tasks 2048 tasks 4092 tasks 8184 tasks
	Single machine 16425.32s 17242.13s 16675.48s 17545.15s 17361.09s
	1 cluster	676.263s	524.347s	405.81s	381.576s	386,414s
	2 clusters (geo) 663.646s	567.54s	447.152s	418,517s	417,009s
	2 clusters (worst) 677.29s	587.003s	533.274s	422.769s	420.739s
	3 clusters (geo) 697.262s	492.119s	422.628s	423.568s	415.886s
	3 clusters (worst) 717.504s	538.026s	434.973s	412.001s	413.61s
	4 clusters (geo) 673.082s	528.628s	456.385s	421.053s	404.126s
	4 clusters (worst) 609.69s	534.328s	439.901s	405.943s	411.397s
	5 clusters (geo) 654.827s	478.253s	412.802s	389.592s	413.817s
	5 clusters (worst) 656.894s	499.64s	408.056s	402.154s	397.587s

Table 2 .

 2 Comparison of geometrical distances from the best docking solution, in Å.

	R1 R2 R3 R4
	Crystal structure 3.36 3.05 4.32 4.01
	AlgoGen-DivCon 4.80 3.38 3.60 4.71

https://www.grid5000.fr

http://cosy.univ-reims.fr/~lsteffenel/CONFIIT

Acknowledgement

Experiments presented in this paper were carried out using the Grid'5000 experimental testbed, being developed under the INRIA ALADDIN development action with support from CNRS, RENATER and several Universities as well as other funding bodies (see https://www.grid5000.fr ). This work is partially supported by ANR (Agence National de Recherche), project reference ANR 08 SEGI 022.