S Dumont

F Lebon

REPRESENTATION OF PLANE ELASTOSTATICS OPERATORS IN DAUBECHIES WAVELETS

This paper is devoted to describing representations of the plane elastostatics operators in orthonormal bases of compactly supported wavelets. We are interested in giving an alternative numerical model to the finite element method and Fourier analysis, because wavelets bases are well-suited to adaptivity and discontinuities. The discretization of the elastostatics operators leads to matrices where elementary terms are easily computed from integrals of two or three wavelets and their derivatives. These integrals are performed as eigenvectors of low order matrices and given in filter banks. Mathematical results are worked out in details. A numerical example is presented which demonstrates the efficiency of the representation and shows it being consistent with analytical solutions.

I. INTRODUCTION

Daubechies [I] has introduced compactly supported wavelets. In Refs [2], [3], Beylkin et a!. find exact and explicit representations of several basic operators as derivatives, in orthonormal bases of compactly supported wavelets. In Ref. [START_REF] Beylkin | On the representation of operators in bases of compactly supported wavelets[END_REF], Beylkin and Torresani consider the implementation of these operators via filter banks in the framework of the multiresolution analysis. These representations need some regularity concerning the functions transformed by these operators. In elastostatics, displacements are often in Sobolev spaces of low order. We present two examples.

Example I: periodic homogenization (local problem). such that divCgrad,u = -divCE. (I)

Y is a representative part of a given bidimensional domain f.l (see Fig. 1). H~(Y) is the Sobolev space of first order with periodic conditions on Y (see Section 2). C = C(x) is a fourth order tensor depending on the materials.

Example 2: linear elasticity (see Fig. 2 for the notations).

Cgrad,u • n = g on olf.l, (3) u = 0 on o 0 f.l. (4) This paper is devoted to the representation of plane elastostatics operators [eqns (I) and (2)] in Daubechies bases. This representation is based on a wavelet-Galerkin method. The difficulties arise from the eventual heterogeneities of the materials and to the nature of the differential operator (coupling of the derivatives, two-dimensional operators, second and fourth order tensors, etc).

Mathematical results show that the representation of the elastostatics operators leads to the computation of elementary terms which are integrals of two or three wavelets or scale functions and their derivatives. These wavelets could have different orders (for example Haar basis and Daubechies wavelet of order 3).

These terms are performed via filter banks which are the eigenvectors of matrices or eigenmatrices of a fourth order tensor. Usually, these matrices have a low order and the eigenvectors can be estimated by symbolic computational software.

The paper is organized as follows: in Section 2, generalities concerning bases of compactly supported wavelets are given; Section 3 is devoted to the discretization of the operators using the wavelet-Galerkin method and to the matrix coefficients computations; Section 4 contains a numerical example to validate the algorithm. Filter banks are such that -divCgrad, u = f in f.l, (2) given in the Appendices.

BASES OF COMPACTLY SUPPORTED WAVELETS

One -dimensional Daubechies wavelets

In this section, we present a brief summary of one-dimensional Daubechies wavelets [I]. Let M be a positive integer. There exists a sequence of real numberS I h(n)h(n+2k)=Oob Vke7L, [START_REF] Dumont | Ondelettes et equations aux derivees partielles. I. Le cas unidimensionnel[END_REF] n=O where b; 1 = I if i = j, bu = 0 otherwise. This sequence defines two compactly supported functions cp (scale function) and tjJ (the associated wavelet). The function cp is defined by: [START_REF] Cohen | Ondelettes et traitement numerique du signal[END_REF] 11=0 and verifies:

{ h (n)} n ~ 0 •. 2M_ 1 SUCh that n =2M -1 I h(n) = j2,
n~ 2M-I cp(x)=j2 I h(n)cp(2x-n), Vxe!R1,
t cp(x)dx =I, (8) JR cp(x)cp(x-k) dx = Oob Vk E7L, (9) Icp(x-k)=J, VxER (10)
keZ

The function tjJ is defined by

n~2M -I t/J(x)=j2 I g(n)cp(2x-n), Vxe!R1, ( 11
)
n=O where g(n) = ( -l)"h(2M-n-1), n = 0, ... , 2M-I.

(12)

The compact support of cp and tjJ is included in the closed interval [0, 2M -1].

The function tjJ has M vanishing moments:

JUlt/J(x)x'"dx=O form=O, ... ,M-1, (13) and verifies (14

)
A representation of the functions cp and tjJ is given in Fig. 3 for different order of M. Let

cp 1 k(x)=1!f2cp(2ix-k), VxEIR1, Vj,ke7L, (15)
and

tjJ 1 k(x)=1PtjJ(zlx -k), VxEIR1, Vj,kE7L. (16)
The compact support of cp 1 k and tjJ 1 k is included in the closed interval [k /21, (k +2M -I )/21].

We define V 1 as the closure of the space generated by { cp 1 k, k E 7L} and rtj, its orthogonal complementary in Vj + 1, aS the clOSUre Of the Space generated by {t/1 1 k>ke7L}.

The sub-spaces V; and W; verify the following conditions:

(17) 0. 00 -------------------------------------------------________ ,.._ =------0. 00 0. 0121 2.5121 5.00 -2. 00 -1-----,---,-------,---,-------r--,-----r---r---r------, 0. 00 2. 50 5. 00 The set of spaces V 1 is called a multiresolution analysis of L 2 (1R). These spaces will be used to approximate the solutions of the elastostatics equations using a Galerkin method. The functions cp and ljt give us bases of L 2 (1R) and, for certain values of M, bases of H 1 (1R).

(18) L 2 (1R1) = V 1 EB Wk = EB Wk, k ~ i kEZ (19) n V;= {o}
Note that the polynomials of degree lower than M-I are exactly included in the space rj. For example, for numerical applications we usually use wavelets of order 3, and so, polynomials of degree 2 are included in the discretization spaces.

Periodic one-dimensional wavelets

It is easy to define periodic wavelets (see Example I) and a multiresolution analysis of L~(Y). First, we define L~(O, I) and H~(O, I) by:

L~(O, I)= {v E Lfoc(IR), v(x) = v(x +I) a.e.} (22)
¢ 1 k(x) = 2i 12 L cp(2i(x + r)-k).
(24) rEZ One can show [START_REF] Liandrat | Numerical resolution of non-linear partial differential equations using the wavelet approach[END_REF] that the closure of { ¢ 1 k, k E Z}, noted V), defines a multiresolution analysis of L~(O, 1).

Periodic two-dimensional wavelets

If Y is the square (0, 1]2, we define L~( Y) and H~(Y) by

= v(x 1 , x 2 +I) a.e.}, (25)
and Furthermore, we can determine the orthonormal basis of L~ ( Y). L ~ ( Y) = U 1 \!) where Vf is the closure of the space generated by {<P{,k 2 ,k 1 ,k 2 E&'}, where

It is clear that { <P{,k,, k 1 , k 2 E &'}
is an orthonormal basis of vy. With these notations, we obtain

(L~(Y)) 2 = (U 1 \1)) 2 • If we denote {V 1 ,j E &'} the mul- tiresolution analysis of (L~(Y)) 2 , an element of V; is thus written: with u;(X 1 , x 2 ) = I u7'k'<P{,k,(x 1 , x 2 ), (k,,kz)EA 1 with N 1 = 2!-I and A 1 = [0, N 1 f (28) (29)
For simplicity, we have merely chosen to perform the representation on one given level j. Note that the dimension of the space vy is equal to 2! and so the dimension Of a Space \1 1 is equaJ to 2 2 1 + I,

ELASTOST A TICS DISCRETIZATION

General form

The operator which we represent on Y is divegrad,. A variational formulation, using Green's formulae, leads to the term Jra(u):£(v)dy. £ is the second order strain tensor,£ = grad,u. t1 is the second order Cauchy stress tensor, t1 = C£. Let U;,j =au;/ ax} for i,j = 1, 2. The projection of u and v in wavelets' bases corresponds to the representation of the plane elastostatics operators in compactly supported bases. In this case, Proposition 1 is obtained.

Proposition l: the projection of the plane elasticity operators into the wavelet basis with scale equal to j, is given by a matrix K of order 2 21 + 1 : K = (Ku 1 ,; 2 J,(kl.kZl), where K(; 1 ,; 2 J.(kl.k 2 l) = K 1 k is an elementary matrix of order 2:

[F " + Fn F'2 + Fz'] K _ " 33 12 33 u.-Fz' + F'2 F22 + F" ' 21 33 22 33 ( 30
)
where with A= (rx, {3), rx, f3 = l, 2 or 3 and n = ('7, 0, '7, ~ = 1 or 2.

Proof: to verify this proposition, we need to define the plane strain tensor. For bi-dimensional problems, the strain tensor £ is defined by £ 11 = u 1 , 1 , £ 22 = u 2 , 2 and £ 12 = l/2(u 1 _ 2 + u 2 , 1 ), (32) and the symmetric elasticity tensor C = ( C;;) by Ci3 = 0 for i ~ 3. In order to discretize the problem, we need to express the term a(u):£(v):

This expression is discretized in the wavelet basis with u given by eqns (28,29) and with v equal to the vectors of the wavelet basis. It follows directly that a(u):l(V)= I ((C 11 u\<P~. 1 + C, 2 u~<P{, 2 )<P 1 p. 1 ) i,keA 1 if and a(u):£(v)= I ((C;zU;;<P~.;+Cnu~<P-tz)<P~. [START_REF] Beylkin | Fast wavelet transforms and numerical algorithms I[END_REF] i.ke~1

if By integration on Y, the proof of Proposition l is obtained. Q.E.D. It is clear, from the form of the elementary matrix, that the matrix K is symmetric.

Matrix coefficients

In this section, we propose a technique to compute the terms of the matrix K. C is usually a piecewise constant function (a given constant for each material). Two cases appear. C is either a constant function on the intersection of the supports of <P~ and <P{ or not.

The first case is more easily tractable. Equation (31) gives us Using a simple change of variables, we obtain and f'l is the derivative of order s.

We note that eqn (38) is a translation of the derivation with respect to the first or second variable. The algorithm to compute the terms A;k and B;k is given in Section 3.3.

On the other hand, if C is not constant on the intersection of the supports of the two wavelets, this function is decomposed into a wavelet basis which is not necessarily the same as in Section 2.3. Due to the form of C, 11 , the best choice seems to be the Haar basis.

Let() be the wavelet basis of decomposition of C,p, () is a wavelet basis of L~(O, 1). We obtain the following formula: c,,,(x,, x2) = I C~)i" 2 0J,,,(x,)OJp,(x2), (41)

(Pl•P2)EA;
with NJ = 2 1 -I and A 1 = [0, Nlf J is not necessarily equal to j, but usually J?: j is chosen to have 2J-; in N. Proof: using eqn (41), the different terms F~ of the matrix K have the following form:

with r = i -2 1 -ik and s = k-i. Q.E.D.

Thus, we have to compute elementary terms which can be seen as the "product of three wavelets". The algorithm to compute these terms is given in Section 3.4.

Evaluation of two wavelets' products

The evaluation of the integral JA ¢)7 1 (x )¢j;;' 1 (x) dx is a particular case of a theorem given by Beylkin (3]. The coefficients h(i) are defined in eqns (5, 6). This theorem corresponds to the evaluation of tors of a simple matrix with eigenvalues equal to 2-".

Usually, due to the low dimension of the matrix, this evaluation can be done by a symbolic computational software. Using eqn (24), the evaluation of the terms H 4> JJl(x )¢ J2l(x) dx is given by the theorem with n = I and the evaluation of the terms H 4>JJl(x)¢)2(x) dx by the theorem with n = 2.

Evaluation of the three wavelets' products

To perform the terms r~;k it is necessary to introduce the coefficients yr. where where I} is a Daubechies wavelet of order M and cp a Daubechies wavelet of order M. These wavelets are chosen without periodic conditions.

The two wavelets verify the following conditions:

r=2M-I IJ(x)=J2 I H(r)IJ(2x-r), \fxE~, ( 53
) r=O r=ZM-1 cp(x)=J2 I h(r)cp(2x-r), VxE~. (54) r=G
The following theorem is introduced. T-=::. 0 X (ex-2i + r)h({J-2k + r)X[o. 2 M-IJ X (ex-2i + r)X[o. 2 M-IJ({J-2k + r), (56) and

X[a.bJ (x) = I if x E [a, b ],
XJa.bJ(x) = 0 in all other cases. (57)

Proof: due to eqns (53, 54), with q = 2i + r I -rands= 2k + r2-r. The change of variables i I = 2i + r I -r and k I = 2k + r2 -r and the equality yr.= 0 for i, k ¢[2-2M, 2M-2], complete the proof. Q.E.D. IB is a fourth order tensor. The coefficients y can then be seen as eigenmatrices of the tensor lB. The evaluation of these terms is obtained using a wellchosen numbering. The tensor IB is transformed into a matrix and the matrix y into a vector. Then, eqn (55) is a problem of the determination of eigenvectors with the eigenvalue 2"+"'. Note that this problem is solved only once and written in filter banks. Details and tables concerning the computations of the coefficients are given in the Appendix I.

The evaluation of the coefficients r is obtained using the following formula, obtained using a simple change of variables in eqn (52) and for J sufficiently larger than 0: Then, the coefficients r~ik (j < J) are performed from eqn (59) by a pyramidal algorithm described for example in Refs [2, 6 and 7] (see Appendix 2).

VALIDATION TEST

The aim of this paragraph is to validate the representation from an academic example. We consider an elementary composite (see Fig. 4). Let the displacement u be u 1 (x 1 , x 2 ) = sin(2nx 1 )cos(2nxJ, (60)

u 2 (x 1 , xJ = 10cos(2nx 1 )sin(2nx 2 ). ( 61
)
The forces applied on the domain are given on each sub-domain by the following formulae:

The displacement given by eqns (60, 61) is projected into the wavelet basis (M = 3) and transformed by the representation of the plane strain elastostatics operator. The forces obtained are compared with the analytical solution given by eqns (62, 63) and with the direct decomposition of this solution into the wavelet basis. Figures 5 and6 show the accuracy between the numerical and analytical results. Figure 5 represents the displacement u = (u 1 , u 2 ) and Fig. 6, the force f, (x 1 , x 2 ) for x 2 = 0.5.

CONCLUSION

The numerical model presented in this paper turns out to be a good alternative to the finite element methods and Fourier analysis. Several applications can be made: periodic homogenization [8], linear elasticity using fictitious domains [9], inverse problems using experimental data, linear and non-linear properties of a composite from images of its complex microstructure, etc. On the other hand, the first improvements to give are the use of adaptivity properties and the implementation of wavelets with Dirichlet and Neumann boundary conditions.

Computation of y~

To perform the coefficients y?J! it is necessary to determine an eigenvector of the matrix IE! with the eigenvalue equal to one. Another condition has to be introduced to satisfy the uniqueness of this vector. The functions 0 and tp verify:

IO(x-k)=l, 'v'xE~, (AI) keZ Then (A3)
Table AI gives the values of the vector y?J!.

Computation of Y~k 1

The coefficients y~( correspond to the determination of an eigenvector of the matrix IE! with the eigenvalue equal to 0. -0.535714856 X JO-l -0.122693167 X 10° 0.677531606 X 10° -0.225189020 X ]0 1 0.17024089] X 10 1 0.840745335 x 10-' 0.203438334 X 10° -0.J0JJ8J720 X ]0 1 0.305186162 X ]0 1 -0.225189020 X ]0 1 -0. Table A2 gives the values of the vector y~).

Computation of y J)

The coefficients y i( correspond to the determination of an eigenvector of the matrix IE! with the eigenvalue equal to 0.25. Let

  Fig. I. Heterogeneous bi-dimensional domain and a local represen ta ti ve part.

Fig. 2 .

 2 Fig.2. Two-dimensional elasticity problem.

Fig. 3 .

 3 Fig. 3. Scale function and wavelet: (a) M = I; (b) M = 3.

  Hp(O, I)= v ELr(O, 1), ox 1 EL (0, I) . (23) We define the function ¢ 1 k such that

F~

  I then n I =I and n2 = 0, if 11 = 2 then n I = 0 and n 2 = I , if¢ = I then m I = I and m2 = 0, and if¢= 2 then m I= 0 and m2 =I,

Proposition 2 :

 2 the evaluation of the terms FZ needs to compute the elementary terms rtik• p = (n, m), where (42) More precisely, FZ = I qi•P2rt;,, rr;,,,, (43) (PJ.P:¥AJ with r, = i,-k, and s, = p,-2J-ik,. The same nota- tions are used as in eqn (31 ).

  Theorem I : let rZ = L q>(x-k)q>(" 1 (x) dx, n EN. (48) Then, and l:k"r% = ( -l)"n', (50) k with 2M-Ik ak=2 I h(i)h(i+k),k=l,2M-l. (51) i=O

2 Fig. 4 .

 24 Fig. 4. Elementary composite (I) Young's modulus: 410000 MPa, Poisson's ratio: 0.19. (2) Young's modulus: 72 000 MPa, Poisson's ratio: 0.32.

Theorem 2 :

 2 the coefficients yr., verify the relation (55) with 2M-I IB;k•P = J8 I H(r)h

  Yr.= 2" + "'J2 I H(r )h(r l)h(r2)y~, (58) r=O r1,r2=0

Fig. 5 .Fig. 6 .

 56 Fig.5. Displacement u(x 1 , x 2 ), M = 3, j = 5.

  y~ (M =I and M = 3) 568478777 x w-z 0.189275244 X 10 1 -0.441328283 X 1()-1 0.147791132 X 10 5 0.324935170 X I 0 4 -0.134388718 x w-1 0.441328283 x w-) 0 9. S. Dumont, F. Lebon and P. Alart, Elasticite et ondelettes: formulations mathematiques et mise en oeuvre numerique. In: Proc. 2nd French National Congress on Computational Structural Mechanics, Giens, France pp. 827-832 Hermes, Paris (1995) (in press).APPENDIX I

  5. Letijik = t Olll(x)tp(X-i)tp(X -k)dx. (A4) Then, y?( and i5,k are two non-colinear eigenvectors of IE!. Due to the definition of y~{ and i5,ko then 0 Coefficients y~( (M = I and M = 3) x 10-1o.ISOS3970I x Jo-1 -0.124283163 X 10° 0.567892841 X 10° 0.827328955 X 10° -0.442097978 X 10-l -0.2IIII06II x 10-1 0.166483459 X 10° -0.752893875 X 10° -0.106420845 X 10 1 0.188744849 X 10-l 0.109093267 x 10-1 -0.698971276 X 10-\ 0.293074414 X 10° 0.246829!48 X 10° -0.801477819 X 10-4 -0.452898781 x 10-2 0.262518093 X 10-l -0.!03068691 X 10° -0.960718286 x 10-2 -0.896484317 X 10-5 -0.323247933 X J0-3 0.144502219 X J0-2 -0.500468928 X JO-l -0.342465753 X JO-l TableA3. Coefficients y~( (M =I and M = 3

k =2M- 2 k = 2M - 2 I

 22 477946449 X ]0 2 -0.!28299571 X 10° 0.467364635 X 10° -0.10JJ8J720 X 10 1 0.677531606 X 10° o.IS3079476 x 10-2 0.460236098 X 10-I -0.!28299571 X 10° 0.203438334 X 10° -0.]22693167 X JOG 0.198359243 x 10-3 0.153079476 x 10-2 -0.477946449 X 10 2 0.840745335 x 10-2 -0.535714856 X 10 2 kyO:.pk-p=i, I ki5_pk-p=O.

2 II

 2 Y2~ = 0, 'v'kE l. and I ky2~ =!. technique to perform the coefficients consists of obtaining two non-colinear eigenvectors A and B, and to determine tx and {3, such that: kApk-p+/3 I kB_pk-p=l. (A7)

  and f;k = t O(xi)tp(x -k)tp 121 (x) dx. (A10)

Table AI .

 AI Coefficients

Table A3 gives the values of the vector y )) . The one-dimensional pyramidal algorithm

Let J = 0 and SZ be given. SZ = tfcpOk dy.

(Al2)

Then the coefficients at level j are obtained from the coefficients at level)+ I using eqn (AI4). This algorithm is presented on an elementary example, with j = -2, on Fig.


S Dumont

F Lebon

WAVELET -GALERKIN METHOD FOR PERIODIC HETEROGENEOUS MEDIA

This paper is devoted to a new algorithm to compute the local and overall response of a composite. The local elastic problem is discretized by a Galerkin-wavelet method. Details are given to compute the terms of the matrix and of the right hand side. The local solution is selected by a viscosity method. The solution with average equal to zero is chosen. Due to the form of the wavelet bases, the macroscopic coefficients are computed directly from the wavelet coefficients of the solution. Numerical examples are presented. Comparisons are made with analytic solutions and with finite element computations.

I. INTRODUCTION

Many structural analysis problems are concerned with heterogeneous media. Different approaches have been explored by many authors [1-5] to determine the elastic behaviour of composite materials. A large class of material could be considered as periodic. Theoretical and numerical results have been given in several previous papers [START_REF] Suquet | Plasticite et homogeneisation[END_REF][START_REF] Licht | Frottement, viscoplasticite et homogeneisation[END_REF][START_REF] Lene | Contribution a !'etude des materiaux composites et de leur endommagement[END_REF][START_REF] Moulinec | A fast numerical method for computing the linear and nonlinear mechanical properties of composites[END_REF][START_REF] Bensoussan | Asymptotic Analysis for Periodic Structures[END_REF][START_REF] Sanchez-Palencia | Non Homogeous Materials and Vibration Theory[END_REF][11]. The idea is to consider the material being a juxtaposition of identical cells, with the same geometrical and mechanical properties. In elastostatics, it is possible to obtain the macroscopic properties by the knowledge of these microstructures. From a numerical point of view, the classical method to solve this kind of problem, is the finite element method [START_REF] Lene | Contribution a !'etude des materiaux composites et de leur endommagement[END_REF][START_REF] Peyroux | Homogenization in thermoelasticity: application to composite materials[END_REF]. Another approach has been proposed using Fourier transform [START_REF] Moulinec | A fast numerical method for computing the linear and nonlinear mechanical properties of composites[END_REF][START_REF] Peyroux | Homogenization in thermoelasticity: application to composite materials[END_REF][START_REF] Dumontet | Homogeneisation par developpement en series de Fourier[END_REF]. The difficulty is to eliminate Gibbs phenomena near the heterogeneities; these problematic phenomena could vanish using Fejer series.

In this paper, an original wavelet-Galerkin method is proposed to solve the problem on the microscopic structure. The advantages of the wavelet transform are, in particular, localization and adaptivity [START_REF] Daubechies | Orthonormal bases of compactly supported wavelets[END_REF]. In this case, using a viscosity method [START_REF] Attouch | Viscosity solutions of minimization problems[END_REF], it is possible to obtain the displacement solution with the average equal to zero. The coefficients of the matrix are computed using a fast original algorithm based on the product of three wavelets [START_REF] Dumont | Representation of plane elastostatics operators in Daubechies wavelets[END_REF]. The evaluation of the right hand side is obtained by the generalization of a method given by Beylkin [START_REF] Beylkin | Fast wavelet transforms and numerical algorithms I[END_REF][START_REF] Beylkin | On the representation of operators in bases of compactly supported wavelets[END_REF].

The paper is organized as follows: in Section 2, we introduce some aspects of the periodic homogenization and we give precise definitions of macroscopic and microscopic variables: we then provide in Section 3 an introduction to viscosity methods, we justify their use for our problem and we review the necessary mathematical background; Section 4 is devoted to the discretization of the problem using wavelet-Galerkin method and to the matrix and the right-hand side coefficients' computations; Section 5 contains some numerical examples: validity is shown comparing results with analytical solutions and with finite element solutions given in literature [START_REF] Lene | Contribution a !'etude des materiaux composites et de leur endommagement[END_REF][START_REF] Peyroux | Homogenization in thermoelasticity: application to composite materials[END_REF].

PERIODIC HOMOGENIZATION SUMMARY

Microscopic and macroscopic variables, notations

A two phase isotropic elastic composite is considered. We intend to study the behaviour of this heterogeneous media. In this paper, the notion of "equivalent" material is used. By equivalent, we mean that under the same loadings, this equivalent material has globally the same response. In a celebrated paper, Hashin and Strickman [START_REF] Hashin | A variational approach to the theory of the elastic behaviour of multiphase materials[END_REF] have computed optimal bounds for the bulk and shear moduli of a two phase composite. Without going into further detail, these bounds depend on the shear and bulk moduli of the two phases and on the volumic fraction of the two phases in the composite. One could loosely categorize our work in the same framework.

The theory of periodic homogenization focuses on an idealized composite consisting of the juxtaposition of identical heterogeneities. To begin with, then, we give some precisions about notations.

Let !l be a given bi-dimensional domain (with Cartesian coordinates x1, x 2 ) containing the different materials with a periodic representation (see Fig. 1). Let Y be a (periodic) representative part of !l. We distinguish two scales: the macroscopic scale (x e Q) and the microscopic one (y e Y). [START_REF] Attouch | Viscosity solutions of minimization problems[END_REF] The displacement U is decomposed into two parts: or U(x, y) = Ex+ u(y) and the deformation tensor e is written: e(U(x, y)) = E + e(u(y)), where E is constant and given in Y.

We denote (using Einstein's notations):

e,1 (u) = ~ (uu + uu)

or in other terms e(u) = Du = grad, u with:

(I) (2)
(3) e(U) = AE.

(13)

Under these hypotheses, we infer that:

I:= <CA)r E. ( 14
)
We give in the next sections of this paper a new approach to compute the macroscopic stress tensor.

Equilibrium equation in the representative elementary volume

A fundamental question in heterogeneous media (4) mechanics concerns what happens when a deformation is applied. Merely, the determination of I: corresponding to a given deformation E needs the resolution of the equilibrium equations (EQ) on Y We denote I: the macroscopic stress tensor and (J the stress tensor in Y.

The macroscopic stress tensor is given by: I:= <(J)r. The material being elastic, we have:

or

(J = C(Du +E), ( 11
)
where C = C(y) is the elasticity tensor on Y.

We denote A, the localization tensor such that:

divCDu = -divCE (16)
or [START_REF] Liandrat | Numerical resolution of non linear partial differential equations using the wavelet approach[END_REF] with L~(Y)={veLfoc(Y), v(x,+k,,x,+k,)= v(x,, x, )a.e., k,, k, e £:} and

H~ ( Y) = {v E L~ ( Y), aav E L'( Y), aav E ( Y)}. X1 X2 (18)
H'(Y) is the Sobolev space of order one. Details about the periodic conditions on the boundary of the domain Y are given in Section 4. The macroscopic stress tensor I: is determined by conditions ( 9), ( 10), ( 11) and (14).

It is clear that the solution u of problem EQ is defined to within a rigid field. In the next section, a mathematical method is introduced to select one, and only one, solution. In particular, it is easy to select a solution with the average equal to zero. Using the fast wavelet transform, it is easier to compute this kind of solution than to impose a given displacement on the boundary of the domain.

THE VISCOSITY METHOD

Asymptotic results

In this section, we focus on a theorem due to Attouch [START_REF] Attouch | Viscosity solutions of minimization problems[END_REF]. The aim of this theorem consists of replacing a minimization problem, the solution of which is not unique, by approached problems, called viscous problems, where the solutions are unique and converge toward a particular solution of the initial problem: commonly called the selection principle.

Theorem 1. Let f: X-+ IR u { + oo} be an extended real-valued function and

(P) min {f(x): x EX} (19)
the associated minimization problem.

Let us assume that infx f is a finite real number.

Let g: X -+!R+ be a nonnegative real-valued function and, for any £ > 0, let us consider the approximate minimization problem (PJ min {f(x) + £g(x): x EX}. (20) Let us assume that there exists a topology on X such that the following topological properties (i) and (ii) are satisfied:

(i) for every £ > 0, there exists a solution u, to (P,) and the sequence min{u, £-+0} is relatively compact;

(ii) f and g are lower semicontinuous.

Then, every limit point u of the sequence { u, £ -+0}, minimizes the function f on X and satisfies the viscosity selection principle gives

{ g(u) ~ g(v) Vv E argminf ( 2 l) u E argminf.
The problem (EM) is the elastic energy minimization problem associated to the problem (EQ). These problems are equivalent to the virtual work principle (VW).

Problem VW. Find u E (H~ (Y)) 2 such that a(u, v) = l(v) Vv E (H~ (Y)f (26)
The following corollary is introduced: with The solution of problems (VEQ), (VEM) and

(VVM) converges towards the solution of problem (EQ) such that 1 udy = 0.

To summarize, the process chosen to solve the equilibrium equation (EQ) could be described concisely as the following: the problem (EQ) is replaced by the problem (VEQ) which is discretized using a wavelet-Galerkin method; the solution of this problem selected by the viscosity selection principle converges toward the solution of problem (EQ) with average equal to zero.

In the following section, we present the discretization of the problem by a Galerkin-wavelet method using Daubechies wavelets, which are compactly supported wavelet bases.

THE W A VELET-GALERKIN METHOD

One-dimensional Daubechies wavelets

In this section, we present a brief summary of one-dimensional Daubechies wavelets [START_REF] Daubechies | Orthonormal bases of compactly supported wavelets[END_REF]. Let M be a positive integer. There exists a sequence of real numbers {h(n)}n:o . . zM-1 such that (39) l cp(x) dx =I and LCfJ(X-k)=l, VxEIR. The compact support of q> and 'l' is included in the closed interval [0, 2M-1].

n =2M-I L h(n) = j2 (33) n=O and n =2M-I l 'l'(x)'l'(x-k) dx = boh Vk E 7L
Let

cp 1 k (x) = 2! 12 cp(2'x-k), Vx E R Vj, k E 71., (41) and 'l';k (x) = 2! 12 'l'(21x-k), Vx E IR, Vj, k E 71., (42)
These functions are obtained from q> and 'l' using dilatation and translation. The compact support of CfJJk and 'l' 1 k is included in the closed interval

[k/2!, (k +2M-1)/2!].
We define ~the closure of the space generated by

{ CfJJh k E 71.}.
The sub-spaces ~ verify the following conditions: and

V(IR) = U V 1 • (45) }E Z. L h(n)h(n + 2k) = bok, Vk E Z. ( 34
)
The set of spaces ~ is called a multiresolution n=O This sequence defines two compactly supported functions q>, called the scale function and 'l', called the associated wavelet. These functions verify

n=2M-I q>(x) = j2 L h(n)cp(2x-n), Vx E IR (35) n=O n =2M-I 'l'(x) = j2 L g(n)cp(2x-n), Vx E IR (36)
n=D where g(n) = (l)"h(2M-n-1), n = 0, ... , 2M-I.

(37)

i cp(x)cp(x-k) dx = bok. Vk E 7L (38)
analysis of V(IR).

Periodic wavelets

Due to the form of the problem, it is necessary to define periodic wavelets and a multiresolution analysis of L~ ( Y).

We define the periodic function c/J;k such that

cP;k (x) = 21i 2 L cp(2!(x + r)-k).
(46) ,.z One can show [START_REF] Liandrat | Numerical resolution of non linear partial differential equations using the wavelet approach[END_REF] that the closure of { c/J;k, k E 7L}, noted V]' defines a multiresolution analysis of L~ (0, 1).

Furthermore, we can determine orthonormal bases of L~ (Y).

where vy is the closure of the space generated by {<PC k,, k~, k2 E 71.}, where (47)

Proof

The proof of this theorem is an elementary development of the eqn ( 68) using eqns ( 69) and ( 70 Tables for n = 1 are given in Appendix A. Note that Then, the coefficients for j < J are given using the pyramidal algorithm presented for example in Refs [START_REF] Liandrat | Numerical resolution of non linear partial differential equations using the wavelet approach[END_REF][START_REF] Dumont | Representation of plane elastostatics operators in Daubechies wavelets[END_REF][START_REF] Cohen | Ondelettes et traitement numerique du signal[END_REF].

Evaluation of the macroscopic coefficients

The aim of this paragraph is to compute, using the wavelet coefficients of the microscopic displacement u, the macroscopic stress tensor :E and the homogenized matrix < CA) r.

Due to the definition of :E in eqn [START_REF] Dumont | Representation of plane elastostatics operators in Daubechies wavelets[END_REF],

:E = (Ce(U))r = (Ce(u))r + (CE)r. (73)
The term (CE)r is a given constant, we need to compute the term < Ce(u)) r.

Let A" = [0, N"L for J1 = J or j. Equations For example (77) with s, = k,-2J-jp,.

Then, it is possible to deduce :E and the symmetric tensor Chom = (CA )r. For example, if E = (1, 0, 0) is chosen, then: The previous algorithms are validated on an academic homogeneous medium. This test is very useful to give us the parameters to introduce in the method: viscosity coefficient, orders of the wavelets, dimension of the approximation space, numerical method to inverse the linear system.

The right-hand side f is given by x (14y 2 -14y + 3)-4CII x 2 (1x)ly 4

x (1 -y) 4 (14x 2 -14x + 3)-16

x (1y) 3 (1 -2x) (1 -2y)

(79) Figure 2 shows the accuracy between the numerical results and the analytical solution given by eqns (81 ), (82). Figure 3 shows the fluctuation of the error during the variations of the viscosity parameter. For this example the value 0.01 is optimal.

Figure 4 shows the solutions for different order of wavelets. It is not necessary to choose a wavelet with too large an order. In this case, the order equal to three gives us a very good approximation of the solution. On the other hand, the level of approximation is chosen equal to 5, then the number of "nodes" is equal to 1024. The improvement is not very important for a larger number of nodes.

The linear system is solved by a conjugate gradient method without preconditioner. A sparse matrix storage is used. An important remark concerns the fluctuations of the residuum along the iterative process (see Fig. 5). These fluctuations are very slow and the number of iterations is not too large, so the matrices are not ill-conditioned ones.

Two layer composite

We test the previous approaches on a two layer composite (see Fig. 6) which has the advantage of being elementary with an analytical solution.

For the first layer, the Young's modulus is equal to 410,000 MPa and the Poisson's ratio to 0.19 (Silicium). For the second layer, the Young's modulus is equal to 72,000 MPa and the Poisson's ratio to 0.32 (Aluminium).

The numerical results are given in Table 1 and give us a good accuracy between the analytical solution (no more than 0.1% ). Table 2 shows results given by a finite element method.

The optimal value of the viscosity coefficient is equal to O.Ol. The fluctuations of the residuum are given in Fig. 7. Without preconditioner, the number of iterations is not too large and the fluctuations are due to the difference of elasticity coefficients.

Fiber-matrix composite

The second example concerns a fiber-matrix composite (see Fig. 8). The numerical results are compared with a finite element method [START_REF] Peyroux | Homogenization in thermoelasticity: application to composite materials[END_REF].

The materials are the same as for paragraph 5.2.: silicium for the fiber and aluminium for the matrix. Table 3 shows the numerical results and gives us a good accuracy relative to the finite element solution (see Table 4).

The fluctuations of the residuum are given in Fig. 9. The optimal value of the viscosity coefficient is equal to 0,0 l.

An important remark is that the computation times are comparable for the two methods. The wavelet-Galerkin is more efficient because it is not necessary to generate a mesh. Without meshing, the finite element method (Pl element) is more efficient, but, because of the choice of the order of the wavelet (M = 3), it could be necessary to compare with P2 elements. In this case, the number of computations for each element is four times larger.

CONCLUSION

Wavelet-Galerkin methods have been introduced for solving periodic homogenization problems. The numerical model presented in this paper turns out to be a good alternative to the finite element method.

An improvement to give to this work concerns the use of adaptivity properties. Then, it is necessary to introduce the wavelet function and not only the scale function. The computations are done too in the orthogonal complementary of the basis. The implementation is obviously more complicated.

( 5 )

 5 Problem EQ. E e (L'(YW be given, find u e <m (Y))' such that Ex is the part of the displacement slowly oscillant and u(y) is the (periodic) part quickly oscillant. Ex represents the displacement in Y if the material is homogeneous. e(u) represents a fluctuation of the or local deformation, then: divCDU = 0

  is the average on Y: <f)r = _!_(Y) r f(y) dy with mes(Y) = r dy.

FigFig. 2 .

 2 Fig. I. Periodic heterogeneous media and its representative cell.

3

 3

3. 2 .

 2 Application to heterogeneous mediaIn this section the former theorem is applied in order to solve the problem on the representative part Yof!l.Let us consider the following problem of energy minimization (EM) (EM) minH 1 a(v): e(v) dy: v E (H~ (Y))'}• (22) Let us consider the approximate problem (VEM) (VEM) minH 1 a(v): e(v) dy Proof The viscosity selection principle lluiiL 1 (1') ~ llvlkm Vv E em (Y)) 2 • Then, lluiiL'm ~ llu + CiiL'II') VC E IR'. In other words, C'l Yl + 2C i u, dy ~ 0 VC E IR. Thus, i u dy = 0. Q.E.D.

  Corollary l. Every limit point u of the sequence {u, £-+0}, minimizes the function a(u, v) = 1 a(u): e(v) dy = i CD(u): D(v) dy ~ i a(v): e(v) dy on (H~ ( Y)f and satisfies the viscosity selection principle { II u IIL'm ~ II v IIL'm Vv E argminH 1 cr(•): e(•) dy} u E argminH 1 crO: eO dy} . (24) Proof This result is an elementary application of theorem l, with X= (H~ (Y)) 2 ,f(v) = ~ i a(v): e(v) dy and g(v) = ~ llv lli'm• An important result gives Proposition 1. The solution selected by the viscosity selection principle verifies (25) (27) and l(v) = -L CE: D(v) dy. (28) On the other hand, the viscous energy minimization (VEM) is equivalent to the viscous equilibrium equation (VEQ) and to the viscous virtual work principle (VVW). Problem VEQ. E E (V( Y)) 3 given, find u E(H~ ( Y)f and a E (L;P (Y)) 9 such that diva+ £U = 0 (29) with a = C(Du + £).

  Problem VVM. Find u E (H~ (Y)) 2 such that a, (u, v) = l(v) Vv E (H~ ( Y)) 2 (31) with a, (u, v) = L a(u): e(v) dy + £ L u • v dy. (32)

  ) and a change of variable in h. The term x appears because r, = 0 for i~[O, 2M-2]. Q.E.D.

(

  48), (49) give us Then, by a simple derivation, we obtain e(u). e" (u) = L u7'.k'I/>}Z: (xi)I/J)ti (x2), tk1.k2l E A. 1 i = 1 or 2, n = oil and m = 02; (75) and So, the term (Ce(u))r is deduced by a decomposition of C, if necessary, into the wavelet basis.

Fig. 3 .

 3 Fig. 3. Fluctuation of the error during the variations of the viscosity (validation test M = 5,} = 5).

Fig. 4 .Fig. 5 .Fig. 6 .

 456 Fig. 4. (a) Error (log). (b) CPU time (Sun Spare server 630 mp). Error and CPU time for different order of wavelets (validation test j = 5,£ = 0.000001).

Table 2 .Fig. 7 .

 27 Fig. 7. Evolution of the residuum along the iterative process (two layer composite M = 3,j = 5,£ = O.oi, plane strain hypothesis).

Fig. 8 .

 8 Fig. 8. Fiber-matrix composite. (a) Young's modulus: 72 GPa, Poisson's ratio: 0.32. (b) Young's modulus: 410GPa, Poisson's ratio: 0.19.

Table 4 .Fig. 9 .

 49 Fig. 9. Evolution of the residuum along the iterative process (fiber-matrix composite M = 3,j = 5,£ = 0.01, plane strain hypothesis).

  AI. rJ0, for (M = 3 and Ml = I) r.l.,, for (M = 5 and Ml = I)

Table 3 .

 3 Macroscopic coefficients (MPa) (fiber-matrix composite, plane stress hypothesis, M = 3,j = 5)

	Chom =	[	116 000 32 400 -1.94	32 400 1)6 000 -1.94	-1.94 -1.94 l 38 100

It is clear that {<Pi,k,, k1, k2 E 1::}, is an orthonormal where basis of \/).

With these notations, we obtain if '1 = 1 then n 1 = 1 and n2 = 0

(L~ (Y))2 = (U \1;)2.

If we denote {W;,j E a::} the multiresolution analysis of (L~ (Y))", then an element of W, is written with Ni = 2' -1.

Elastostatics discretization

The problem VVW is discretized using a Galerkin method written in the "wavelet basis" defined m Section 4.2. Then, we obtain the proposition 2.

Proposition 2. For plane elasticity, the projection of the elasticity operator into the "wavelet basis" with scale equal to j, is written. K = K(d.i2!.(kl.k2h K is a symmetric matrix of order 2 2 ' + 1 , where KuL'"!.(ki.k2 1 = K;k is an elementary matrix of order 2: For the proof see Ref. [START_REF] Dumont | Representation of plane elastostatics operators in Daubechies wavelets[END_REF].

It is clear, from the form of the elementary matrix, that the matrix K is symmetric. Due to the orthogonality of the wavelet basis, the discretization of the term i Jr u•v dy gives us dd, where Id is the identity matrix of order 2 21 + 1

• Then the matrix of the problem is equal to K + dd. In the next section, we propose a technique to compute the terms of the matrix K. and P'' is the derivative of order s(s = 0, I, 2).

Thus, we have to compute the scalar product of two wavelets and their derivatives. The algorithm to compute these terms is given [I 9] and is based on a theorem given by Beylkin [I4]. These terms are computed via filter banks as eigenvectors of a low order matrix.

The second case: C is not a constant function on the intersection of the supports of <P! and <Pi

The function Cis decomposed into a wavelet basis which is not necessarily the same as in Section 4.2. Due to the form of C, 1 Jo the best choice seems to be the Haar basis (corresponding toM= 1). Let() be the wavelet basis of decomposition (order M) of C,p. Then

with N 1 = 2J -1.

J is not necessarily equal to j, but usually J;:,: j is chosen to have 2 1 -1 in 1' \:J.

(p 1•P2) = (0.0)

with r, = i;-k; and s; = p;-2 1 -'k,. Thus, we have to compute elementary terms which (52) can be seen as the "product of three wavelets". The algorithm to compute these terms is given [START_REF] Dumont | Representation of plane elastostatics operators in Daubechies wavelets[END_REF]. They Then are given as eigenmatrices of a fourth order tensor. A method to perform these values is given in Section 4.7.

7. Evaluation of two wavelet products in the right hand side

Using a change of variable, it is clear that f IJ,P (x)<f>),"' (x) dx = f IJ" (x)<f>X' (x) dx (67) with s = p-2 1 -1 i.

Then, we have to evaluate the terms r;;k = f IJ1, (x)</>X' (x) dx. (68)

The two wavelets verify the following conditions:


Khaled Belahcene
email: khaled.belahcene@centralesupelec.fr

Yann Chevaleyre
email: yann.chevaleyre@dauphine.fr

Nicolas Maudet
email: nicolas.maudet@lip6.fr

Christophe Labreuche
email: christophe.labreuche@thalesgroup.com

Vincent Mousseau
email: vincent.mousseau@centralesupelec.fr

Wassila Ouerdane
email: wassila.ouerdane@centralesupelec.fr

Accountable Approval Sorting

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

A committee meets to decide upon the sorting of a number of candidates into two categories (e.g. candidates to accept or not, projects to fund or not). The committee applies a decision process which is public, the outcomes are public as well, however the details of the votes are sensitive and should not be made available. Recently, the issue of the accountability of algorithmic decisions has become a primary concern of our society [START_REF] Doshi-Velez | Accountability of AI under the law: The role of explanation[END_REF][START_REF] Wachter | [END_REF]. To what extent can we make the committee accountable of its decisions? In particular, in our setting, a distinctive feature is that the decision may concern several individuals: being accountable for the classification of an individual may not be the same as being accountable for all the classifications. To make things more precise, it is thus useful to distinguish the following situations: S1: an independent audit agency is commissioned to check that the decisions of the committee indeed comply with the publicly announced decision rule. S2: a candidate, (supposedly) unsatisfied with the outcome of the process regarding his own classification, challenges the committee and asks for a justification.

Situation S1 is sometimes called procedural regularity, see for instance [START_REF] Kroll | [END_REF], which calls for systems able to prove to oversight authorities that "decisions are made under an announced set of rules consistently applied in each case". A typical way to address situation S1 is to require transparency and let the audit agency access all the available information. This suffers from two drawbacks: (i) there are often exceptions making full disclosure of the decision procedure impossible, (ii) the burden of proof lies on the shoulders of the audit agency, which (depending on the model) may be too demanding. Alternatively, we can leave the burden of proof on the committee's side and ask for evidence that the set of classifications is compliant with the decision process. This may be done by exhibiting only part of the information, illustrating that the obtained classification is a possible outcome of the sorting process. Since, typically, many other outcomes would also be possible, this could preserve to some extent the privacy of the committee's votes. On the other hand, failing this test would be evidence that the process was biased.

Regarding situation S2, the objective is to justify the classification of the complaining individual, again with minimal disclosure of the committee's votes. In this case, the committee will aim for evidence that the classification of the candidate cannot be otherwise, as long as a number of other classification outcomes are accepted. We can think of such decisions as reference cases. Technically, this requires to show the impossibility to rank the candidate in a different category, i.e. the decision is necessary with respect to the jurisprudence.

More precisely, we shall primarily be concerned with a general sorting model where voters express binary judgments [START_REF] Laslier | Studies in Choice and Welfare[END_REF], and candidates are sorted as either good or bad depending on the fact that the coalition of voters supporting this classification is winning or not. An important hypothesis is that the set of winning coalitions has to remain constant for the set of classifications under scrutiny. This can be seen as a requirement for the process to be unbiased. In this setting, the "details of the votes" cover two aspects: (i) the approval of voters at the individual level, (ii) the winning coalitions at the committee level. In this paper we address the following research question:

Can we make the decisions of a committee using approval sorting accountable while preserving as much as possible the details of the votes?

The details of the sorting model are given in Section 2. At the core of our proposal lies a characterization result of the sorting model which avoids explicit reference to winning coalitions, and leads to a SAT encoding (Section 3). In Section 4, we consider the different scenarios discussed in the introduction and show how this formal machinery allows us to provide argument schemes which answer, at least partially, the accountability requirements. Section 5 discusses related work and concludes.

Noncompensatory Sorting

We are interested in situations where there is a need to aggregate diverse, potentially conflicting, points of view forming a set N -each i ∈ N can be seen as an agent, a voter, or a criterion -into a single sorting of some alternatives taken in a set X between two categories, GOOD and BAD, expressed by an assignment α : X → {GOOD, BAD}. Each point of view i ∈ N has an opinion on the entire set of alternatives in the form of a complete preorder i (i.e. i is a complete, reflexive and transitive binary relation on X) . This preference may stem from numeric or symbolic performance, as it is often the case in multi-criteria decision aiding, or be intrinsically ordinal, as it is often assumed in social choice contexts. Nevertheless, the aggregation procedure requires that each point of view i ∈ N expresses only a binary judgment on each alternative x ∈ X which is either approved or not according to i. We shall also consider a subset X ⊆ X of alternatives with a reference status, with their assignment α : X → {GOOD, BAD} serving as a basis for elaborating justifications.

This abstract description covers several well-documented decision processes, e.g. :

• a multiple criteria sorting problem [Bouyssou et al., 2006] with ordinal preferences (each point of view i ∈ N is a criterion);

• a committee decision context (each point of view i ∈ N is a voter and the GOOD category is the set of winners). Example 1. We consider a situation with six alternatives X := {a, b, c, d, e, f }, assessed from five points of view N := {1, 2, 3, 4, 5} in the following manner:

a 1 b 1 f 1 e 1 c 1 d e 2 b 2 c 2 d 2 a 2 f f 3 a 3 b 3 d 3 e 3 c d 4 a 4 c 4 e 4 f 4 b c 5 e 5 b 5 f 5 d 5 a
We recall the definitions of an upset and the upper closure of a subset w.r.t. a binary relation: Definition 1 (Upset and upper closure). Let A be a set and R a binary relation on A. An upset of (A, R) is a subset B ⊆ A such that ∀a ∈ A, ∀b ∈ B, aRb ⇒ a ∈ B. The upper closure of a subset of (A, R) is the smallest upset of (A, R)

containing it: ∀B ⊆ A, cl R A (B) := {a ∈ A : ∃b ∈ B aRb}.
We postulate that the process is bounded by two assumptions of rationality, individual and collective.

• At the individual level, for all points of view i ∈ N , the approved subset of alternatives A i ⊆ X should be an upset for the preference relation i . Hence, there is no pair of alternatives x, x ∈ X where x is preferred to x w.r.t. i , x is approved by i but not x.

• At the collective level, an alternative x ∈ X is collectively approved and sorted into the upper category if, and only if, it is approved by a sufficient coalition of points of view. We assume the set of sufficient coalitions S ⊆ P(N ) is fixed, and is an upset for inclusion. Hence, if a coalition is sufficient, any superset of this coalition is also sufficient (and if a coalition is insufficient, any subset of it is also insufficient). We do not assume the set of sufficient coalitions has an additive structure, as opposed to weighted voting games or approval balloting [START_REF] Laslier | Studies in Choice and Welfare[END_REF].

These two stages form the noncompensatory sorting model:

Definition 2 (NCS -noncompensatory sorting model, [START_REF] Bouyssou | [END_REF]). Given a set of alternatives X, a set of points of view N , and a tuple of complete preorders i , i ∈ N , if S is an upset of (P(N ), ⊆) and a tuple A i of upsets of (P(X), i ) ,1 the noncompensatory sorting model with parameters (S, A i ) is the function N CS S, Ai mapping alternatives from X to categories in {GOOD, BAD} such that the alternative x is assigned to the upper category GOOD if, and only if, the set of points of view according to which x is approved is sufficient, i.e.

N CS S, Ai (x) = GOOD, if {i ∈ N : x ∈ A i } ∈ S BAD, else
S is the set of sufficient coalitions of the model, and each A i is the approved set according to the point of view i ∈ N .

Example 2. (ex. 1 continued) Suppose the approved sets are as follows: A 1 := {a, b, f }, A 2 := {e, b, c}, A 3 := {f, a, b}, A 4 := {d, a, c}, A 5 := {c, e, b}, corresponding to the three best alternatives according to the respective points of view (3-approval). Suppose also the points of view are aggregated according to the simple majority rule, i.e. B ∈ S ⇐⇒ |B| ≥ 3. Then, the corresponding noncompensatory model assigns a, b, c to the GOOD category, and d, e, f to the BAD one. Hence, α := {(a, GOOD), (b, GOOD), (c, GOOD), (d, BAD), (e, BAD), (f, BAD)}. We note the same assignment α can be obtained with different sorting parameters, e.g. approved sets This model may appear particularly unwieldy to use explicitly, as it requires to handle a set of sufficient coalitions that lies in the power set of the points of view.

A 1 := {a, b, f }, A 2 := {e, b, c, d, a}, A 3 := {}, A 4 := {d,
We propose an indirect approach w.r.t. the parameters of the noncompensatory sorting model implicitly describing the decision process: we suppose the inputs (ordinal preferences over the alternatives according to each point of view) and outputs (an assignment of each alternative to a category, either GOOD or BAD) of the aggregation model are given, and we query the parameters (sufficient coalitions of points of view and accepted sets according to each point of view) of the model. Unlike the usual learning approach, based on the inverse problem of finding the value of a suitable tuple of parameters permitting to restore the output given the input, we instead focus on versions of this problem where the issue is merely the existence of such a tuple of parameters, and, in the case of a positive answer, to find suitable values for the accepted sets (but not for the set of sufficient coalitions).

Definition 3 (Inverse noncompensatory sorting problem: Inv-NCS). Given an assignment α : X → {GOOD, BAD} of alternatives to categories, we say that α can be represented in the noncompensatory sorting model if, and only if, there is a pair of parameters (S, A i ) where S is an upset of (P(N ), ⊆) and A i i∈N is a tuple of subsets of X such that, for all i ∈ N , A i is an upset of (X, i ), so that α ≡ N CS S, Ai .

We say that α is a possible assignment if it is a YES instance of Inv-NCS, i.e. α can be represented in the noncompensatory sorting model. When there is some jurisprudence α , the assignment of a new candidate x can be necessary, in the sense that no other assignment is possible.

Definition 4 (Necessary assignment w.r.t. reference cases). Given a YES instance α of Inv-NCS, an alternative x ∈ X is necessarily assigned to a category C ∈ {GOOD, BAD} w.r.t. assignment α if α ∪ {(x, C)} is a NO instance of Inv-NCS, where C denotes the category opposite to C.

Feasibility of the Inverse NCS Problem

In this section, we propose a characterization of the possibility, given ordinal preferences over the alternatives according to each point of view and an assignment of each alternative to a category, either GOOD or BAD, of representing this assignment in the non-compensatory sorting model. This formulation circumvents any reference to the power set of points of view, so we derive a compact SAT formulation for the inverse problem, which is shown to be NP-hard.

Inv-NCS with Fixed Approved Sets

When the approved sets are given, solving the inverse NCS problem -i.e. learning a set of sufficient coalitions permitting to represent the assignment in the noncompensatory sorting model -is similar to learning a disjunctive normal form from training examples. From this observation, we derive a tractable (computable in polynomial time) algorithm yielding the version space [Mitchell, 1982] of the noncompensatory sorting model with fixed approved sets: Definition 5 (Observed sufficient and insufficient coalitions given approved sets). Given α : X → {GOOD, BAD} and a tuple A i of upsets of (P(X), i ) , we note:

T Ai (α) := cl ⊇ P(N ) g∈α -1 (GOOD) {i ∈ N : g ∈ A i } , F Ai (α) := cl ⊆ P(N ) b∈α -1 (BAD) {i ∈ N : b ∈ A i }
Proposition 1 (Lower and upper bounds for the sufficient coalitions given the approved sets). Given an assignment α, a tuple A i of upsets of (P(X), i ) and an upset S of (P(N ), ⊆), α is represented by the noncompensatory sorting model N CS S, Ai if, and only if:

T Ai (α) ⊆ S ⊆ P(N ) \ F Ai (α) Proof. α is represented by N CS S, Ai iff i) for all alterna- tives g ∈ α -1 (GOOD), N CS S, Ai (g) = GOOD; and ii) for all alternatives b ∈ α -1 (BAD), N CS S, Ai (b) = BAD i) holds iff S contains g∈α -1 (GOOD) {i ∈ N : g ∈ A i
} and, as a consequence of being an upset for inclusion, S contains T Ai (α). ii) holds iff S does not contain any coalition pertaining neither to b∈α

-1 (BAD) {i ∈ N : b ∈ A i } nor to F Ai (α).
Corollary 1 (complexity of Inv-NCS with fixed approved sets). Given an assignment α of alternatives to categories and a tuple A i of upsets of (P(X), i ) , the problem of deciding whether α can be represented in the noncompensatory sorting model with approved sets A i is tractable (computable in polynomial time).

Indeed, it boils down to checking whether T

Ai (α) ∩ F Ai (α) is empty or not, which is O(|X| 2 • |N |).

A Pairwise Formulation for Inv-NCS

The following Theorem is very important as it says that, in order to check that an assignment α is compatible with NCS, it is equivalent to find approval subsets over each point of view such that one can discriminate each pair of GOOD and BAD alternatives on at least one point of view (i.e. the GOOD alternative is approved on this point of view, and not the BAD one). Interestingly, the concept of sufficient coalitions disappears in the characterization. Theorem 1 (Pairwise formulation of the noncompensatory sorting model). An assignment α of alternatives to categories can be represented in the noncompensatory sorting model if, and only if, there is a tuple A i ∈ P(X) N such that:

1. for each point of view i ∈ N , A i is an upset of (X, i ) 2. for each pair of alternatives (g, b) ∈ α -1 (GOOD) × α -1 (BAD), there is at least one point of view i ∈ N such that g ∈ A i and b / ∈ A i .
Proof. [¬(1+2) ⇒ ¬NCS] If there are two alternatives g ∈ α -1 (GOOD) and b ∈ α -1 (BAD) that falsify Condition 2, then, for any potential parameters S, A i of a noncompensatory sorting model, the nesting {i ∈ N : g ∈ A i } ⊆ {i ∈ N : b ∈ A i } results in a sorting N CS S, Ai at least as favorable to b as to g, whereas α(b) = BAD is strictly worse than α(g) = GOOD.

[(1+2) ⇒ NCS] Given a tuple A i ∈ P(X) N satisfying conditions 1 and 2, we consider the sets of coalitions T Ai (α) and F Ai (α).

According to Proposition 1, α can be represented in the noncompensatory model iff T Ai (α) ∩ F Ai (α) = ∅. Suppose this intersection is nonempty, and let B ∈ T Ai (α) ∩ F Ai (α). By definition of T Ai (α), there is an alternative g ∈ α -1 (GOOD) such that B ⊇ {i ∈ N : g ∈ A i }: for all points of view i / ∈ B, g / ∈ A i . By definition of F Ai (α), there is an alternative b ∈ α -1 (BAD) such that B ⊆ {i ∈ N : b ∈ A i }: for all points of view i ∈ B, b ∈ A i . Consequently, there is no point of view according to which g is accepted but not b, contradicting condition 2. Hence, T Ai (α) ∩ F Ai (α) = ∅.

Complexity of Inv-NCS

We show that the inverse NCS problem is intractable.

Proposition 2 (NP-hardness of Inv-NCS). Given an assignment α of alternatives to categories, the problem of deciding whether α can be represented in the noncompensatory sorting model is NP-hard.

Proof. By reduction from SAT: consider a SAT instance in conjunctive normal form, with n variables y 1 , . . . , y n and m clauses c 1 ∧ • • • ∧ c m . We build a gadget assignment with m + n points of view and 2m alternatives: g 1 , . . . , g m are assigned to GOOD whereas b 1 , . . . , b m are assigned to BAD. First, let us focus on the first m points of view:

for each k ∈ 1 . . . m, let g k ∼ k b k k g 1 ∼ k • • • ∼ k g k-1 ∼ k g k+1 ∼ k • • • ∼ k g m ∼ k b 1 ∼ k • • • ∼ k b k-1 ∼ k b k+1 ∼ k • • • ∼ k b m .
The preference k has two equivalence classes, the upper one containing {g k , b k } and the lower one containing k =k {g k , b k }. The n last points of view of the gadget are built considering the SAT formula. From the j-th clause, written in disjunctive form c j := k∈Pj y k ∨ k∈Nj ¬y k , where P j and N j are disjoint subsets of 1 . . . n indexing the positive (resp. negative) atoms of c j , we build the preference relation j+m . It has at most 3 equivalence classes: the uppermost containing the alternatives k∈Pj {g k }, the one in the middle containing k∈Pj {b k }∪ k∈Nj {g k }, and the lowest containing k∈Nj {b k } ∪ k / ∈Pj ∪Nj {g k , b k }. We note trivial accepted sets -i.e. points of view i ∈ N such that A i = ∅ or A i = X -do not contribute to the feasibility of the inverse NCS problem. For the m first points of view, there is only one nontrivial accepted set: it accepts the upper class and rejects the lower one. For the n last points of view of the gadget, the nontrivial accepted sets accept the uppermost equivalence class, reject the lowest class, and either accept or reject the class in the middle. We define a one-to-one mapping between the nontrivial accepted sets of the gadget and the assignment of the n variables of the SAT problem: y j is False ⇐⇒ k∈Pj {b k } ∪ k∈Nj {g k } ∈ A m+j . Each non trivial assignment discriminates all pairs (g k , b k ) with k = k w.r.t. the point of view k. The pairs (g k , b k ) is discriminated iff the clause c k is satisfied. Thus, a solution of the SAT problem is mapped to a tuple of accepted sets that discriminates all pairs with opposite assignments and reciprocally.

A Compact SAT Formulation for Inv-NCS

We leverage Theorem 1 by formulating a boolean satisfiability problem that answers the decision problem: can the assignment α be represented in the non-compensatory model? If the instance is a YES, any solution of the satisfiability problem translates into suitable, yet arbitrary, explicit values for the approved sets. Upper and lower bounds for the set of sufficient coalitions can be obtained thanks to Proposition 1. Corollary 2 (CNF Pairwise SAT formulation for NCS). Let α : X → {GOOD, BAD} an assignment. We define the boolean function φ pairwise α with variables: • λ i,x indexed by a point of view i ∈ N , and a value x ∈ X, • µ i,g,b indexed by a point of view i ∈ N , a good alternative g ∈ α -1 (GOOD) and a bad alternative b ∈ α -1 (BAD), as the conjunction of clauses:

φ pairwise α := φ 1 α ∧φ 2 α ∧φ 3 α ∧φ 4 α φ 1 α := i∈N x ix (λ i,x ∨ ¬λ i,x ) φ 2 α := i∈N , g∈α -1 (GOOD), b∈α -1 (BAD) (¬µ i,g,b ∨ ¬λ i,b ) φ 3 α := i∈N , g∈α -1 (GOOD), b∈α -1 (BAD) (¬µ i,g,b ∨ λ i,g ) φ 4 α := g∈α -1 (GOOD), b∈α -1 (BAD) ( i∈N µ i,g,b )
α can be represented in the noncompensatory sorting model if, and only if, φ pairwise α is satisfiable. Moreover, if λ i,x , µ i,g,b is an antecedent of 1 by φ pairwise α , then the noncompensatory sorting model N CS S, Ai with accepted sets defined by A i := {x ∈ X : λ i,x = 1} and any upset S of (P(N ), ⊆) of sufficient coalitions containing the upset T Ai (α) and disjoint from the lower set F Ai (α) satisfies α ≡ N CS S, Ai .

Variables λ i,x are assigned to 1 when the alternative x is accepted from the point of view i, and variables µ i,g,b are assigned to 1 when the point of view i accepts g but not b.

The clauses φ 1 α ensure the sets of accepted values of each point of view meet the first condition of Theorem 1, i.e. A i is an upset. The clauses φ 2 α (resp. φ 3 α ) ensure each variable µ i,g,b cannot take a value of one unless g is accepted (resp. unless b is not accepted). The clauses φ 4 α ensure the second condition of Theorem 1 is met.

The formulation is compact:

O(|N | • |X| 2 ) variables, O(|N | • |X| 2 ) binary clauses and O(|X| 2 ) |N |-ary clauses.

Accountable Decisions with Inv-NCS

In this section we describe how the theoretical and algorithmic tools described in Section 3 in order to assess the feasibility of the inverse NCS problem (see Def. 3) can be used to support a decision process. More precisely, we address the situation described in Section 1 where a committee has to assign alternatives either to the GOOD or the BAD category, and to account for this assignment. Section 4.1 addresses the first situation S1, where an audit is commissioned to check the compliance of the committee to its terms of reference, by referring to the notion of possible assignment. Section 4.2 addresses the second situation S2, where the committee is challenged by a stakeholder to defend a specific decision, by referring to the notion of necessary assignment.

Auditing Conformity

We consider the situation S1 depicted in Section 1, where an independent audit agency has to check that the decision α of the committee on candidates X is compatible with NCS. We assume X = ∅: all the assignments should be justified together, and none should be taken for granted.

Should the burden of proof be left to the auditor, the audit procedure could require either i) full disclosure of the preference profile (X, i ) i∈N , and the auditor solving the NPhard Inv-NCS problem, e.g. using a SAT solver and Corollary 2; or ii) full disclosure of the approved sets A i i∈N , and the auditor solving the tractable Inv-NCS with fixed accepted sets problem as described by Proposition 1.

If we consider putting the burden of proof on the committee, Theorem 1 can be leveraged to compute and provide a certificate of feasibility for Inv-NCS(α) that involves the disclosure of less information, as illustrated below: Example 3. (ex. 2 cont.) If the approved sets of the committee are A 1 , . . . , A 5 , then it needs to disclose information concerning three points of view in order to prove the assignment α is consistent with an approval procedure, e.g. :

• according to the first point of view, b is approved (and so is a which is better than b) whereas e is not (and neither is d which is worse than e), hence the procedure is able to discriminate a, b from d, e;

• according to the second point of view, c is approved (and so is b which is better than c) whereas d is not (and neither is f which is worse than d), hence the procedure is able to discriminate b, c from d, f ;

• according to the fourth point of view, c is approved (and so is a which is better than c) whereas e is not (and neither is f which is worse than e), hence the procedure is able to discriminate a, c from e, f .

The following table summarizes the points of view permitting to discriminate each pair:

BAD d e f a 1 1 4 GOOD b 1 1 2 c 2 4 2
This manner of arguing that a given assignment is indeed a possible outcome of an approval sorting procedure can be formalized into an argument scheme, an operator tying a tuple of premises -pieces of information satisfying some conditions -to a conclusion [Walton, 1996]. Definition 6 (Argument Scheme (AS1)). We say a tuple

(i 1 , g 1 , G 1 , b 1 , B 1 ), . . . , (i n , g n , G n , b n , B n ) instantiates the argument scheme AS1 supporting the assignment α if: i) for all k ∈ {1 . . . n}, i k ∈ N , g k ∈ G k , α(G k ) = {GOOD}, ∀g ∈ G k , g i k g k , b k ∈ B k , α(B k ) = {BAD}, ∀b ∈ B k , b k i k b and g k i k b k ; and ii) k∈{1...n} G k × B k = α -1 (GOOD) × α -1 (BAD)
Hence, according to the point of view i k , g k is the least preferred alternative in the subset of GOOD alternatives G k and it is preferred to b k , the most preferred alternative in the subset of BAD alternatives B k . This scheme is somewhat frugal in the number of pairs of the profile (X, i ) i∈N revealed to the auditor, as the comparisons inside G k × G k or B k × B k are not disclosed. Theorem 1 can be reworded as follows: Corollary 3. An assignment α is a YES instance of Inv-NCS if, and only if, there is an instance of AS1 supporting it. Example 4. (Example 3 cont.) The explanations given in Example 3 instantiate AS1 as follows: (1, b, {a, b}, e, {d, e}), (2, c, {b, c}, d, {d, f }), (4, c, {a, c}, e, {e, f })

The length n of an explanation instantiating the argument scheme AS1 offers an indication regarding its cognitive complexity as well as the amount of information disclosed to the auditor. Therefore, we would rather provide the shortest possible explanations, and strive to mention as few points of view as possible. Obviously, an explanation needs to reference a specific point of view at most once, so n ≤ |N |. Unfortunately, the following result shows that one might require all points of view in a complete explanation, even in situations with relatively few alternatives. Proposition 3. For every set of points of view N , there exists a set of |N | + 1 alternatives X and an assignment α : X → {GOOD, BAD} for which any tuple instantiating the argument scheme AS1 and supporting α has length |N |. Sketch of the Proof. The result is shown by induction on |N |. For |N | = {1}, we consider α 1 := {(g, GOOD), (b, BAD)} with g 1 b. Consider by induction an assignment α p on p candidates X p assessed on points of view N = {1 . . . p}. We introduce a new alternative z, judged as GOOD, and a new point of view p + 1, such that the candidates in X p are indifferent on the new point of view, and z can be discriminated from b only on the new point of view.

Justifying Individual Decisions

We now wish to justify the decision of the committee on a candidate x ∈ X (Situation S2). As we have seen in the previous section, a complete explanation of the assignment of x necessarily implies the disclosure of many information related to the other candidates, which might not be acceptable.

A possible solution is for committee to base their decision on reference cases, an assignment α * : X * → {GOOD, BAD}, e.g. compiling past decisions that are representative of its functioning mode. In order to get rid of the influence of the other candidates, we are looking for necessary assignments given these reference cases. Example 5. (ex. 2 cont.) We consider the alternatives a, b, c, d, e, f and their assignment α have a reference status, and we are interested in deciding on the assignment of two candidates, x, y such that: It is not possible to represent the assignment (x, GOOD) together with the reference assignment α. Thus, x is necessarily assigned to BAD . On the contrary, both assignments (y, GOOD) and (y, BAD) can be represented together with α.

a 1 f 1 b 1 e 1 c 1 y 1 d 1 x e 2 b 2 y 2 c 2 d 2 a 2 f 2 x f 3 a 3 d
Necessary Decisions Entailed by the Jurisprudence An explanation of the necessity of an assignment is intrinsically more complex than that for its possibility: one needs to prove that it is not possible to separate all pairs of GOOD and BAD candidates on at least one point of view. The proof relies on some deadlock that needs to be shown. Formally, this situation manifests itself in the form of an unsatisfiable boolean formula, e.g. given by Corollary 2. The unsatisfiability of the entire formula can be reduced to a ⊆-minimal unsatisfiable subset of clauses (MUS), which are commonly used as certificates of infeasibility, and can also be leveraged to produce explanations [Junker, 2004;[START_REF] Besnard | [END_REF][START_REF] Geist | Christian Geist and Dominik Peters. Computer-aided methods for social choice theory[END_REF]. In the case of the necessary decisions by approval sorting with a reference assignment, any MUS pinpoints a set of pairs of alternatives in (α -1 (GOOD)∪ {x}) × α -1 (BAD) that cannot be discriminated simultaneously according to the points of view.

Example 6. (ex. 5 cont.) Consider the subset of alternatives c, d, e, f, x, and assume x to be assigned to GOOD. Each pair in GB := {(c, e), (x, d), (x, f )} needs to be discriminated from at least one point of view in N , but this is not possible simultaneously: i) none of the pairs in GB can be discriminated neither from the first, the second nor the third point of view, as the overall GOOD alternative is deemed worse than the BAD one. ii) no more than one pair in GB can be discriminated according to each point of view among {4, 5}, and there are more pairs to discriminate than points of view.

The pattern of deadlock illustrated by Example 6 can be generalized and formalized into an argument scheme, with premises: i) a k-tuple of pairs (g 1 , b 1 ), . . . , (g k , b k ) of alternatives with opposite assignment, ii) a subset of points of view B ⊆ N with cardinality k -1, such that, according to all points of view i / ∈ B, b j i g j for all j, and, according to all points of view i ∈ B the intervals ]b 1 , g 1 ] i , . . . , ]b k , g k ] i are pairwise disjoint.

Clearly, the existence of an argument instantiating the premises of this scheme is a sufficient condition for the infeasibility of representing the given assignment in the noncompensatory model, which in turn yields the conclusion that the candidate x is necessarily assigned to the other category.

If we assume that the cognitive burden demanded by an explanation along the lines of this argument scheme increases with the number of its premises, we derive an implicit hierarchy among the necessary decisions supported by the scheme, with a nesting

E 1 ⊆ E 2 ⊆ • • • ⊆ E |N |+1
, where E k denotes the set of decisions supported by a scheme with premises referencing at most k pairs of alternatives with opposite assignment. E 1 is exactly the set of decisions stemming from Pareto dominance, where a candidate is either at least as good as a reference alternative in the GOOD category, or at most as good as a reference alternative in the BAD category.

The question of deciding if this scheme captures a necessary condition, i.e. if any decision entailed by the jurisprudence can be supported by such an explanation, is left open.

Ambivalent Situations

It may happen that, for a given candidate, both assignments to GOOD and to BAD are possible. This situation is obviously all the more frequent as the reference set is small, or the number of points of view is high. In such a case, a design option would consist in constraining the decision of the committee, either favorably (e.g. following an innocent unless proven guilty principle) or unfavorably (e.g. following a precautionary principle). Another, more common, venue would give the freedom of choice to the committee. In this case, as opposed to the situation where the decision is entailed by the jurisprudence, and where the committee just needs to make obvious the link between the current case and the reference cases, the committee needs to disclose some information concerning its inner functioning. In some cases, though, Proposition 1 offers a solution that avoids a complete disclosure: suppose that, given the approved sets A i , the candidate is approved from a coalition of points of view that is known to be insufficient (resp. sufficient), because a reference alternative is assigned to the BAD (resp. GOOD) category in a similar, or even better (resp. worse) situation than the candidate. This fortunate situation circumvents the need of discussing the particulars of the set of sufficient coalitions by referring to its upper bound P(N ) \ F Ai (α) (resp. lower bound T Ai (α)).

Example 7. (ex. 6 cont.) According to the first point of view, y is disapproved, as it is worse than c / ∈ A 1 . According to the third point of view, y is disapproved, as it is worse than b / ∈ A 3 . According to the fifth point of view, y is disapproved, as it is worse than f / ∈ A 5 . Furthermore, being approved according to both the second and fourth points of view is not enough to warrant access to the GOOD category, as illustrated by e. Hence, y is assigned to the BAD category.

Related Work and Conclusion

In this paper we are interested in the problem of accountability of decisions issued from a noncompensatory sorting model (NCS) [START_REF] Bouyssou | [END_REF]. Two situations have been mainly studied. In the first one, the committee needs to justify that its decision is a possible NCS assignment. A characterization result helps to turn the existence of such assignment to finding separations of the pairs of GOOD and BAD candidates over at least one point of view, which can be formulated as a SAT problem. This allows us to generate a single argument scheme that can explain all possible NCS assignments. The second situation arises when the assignment of a new candidate is necessarily derived from jurisprudence. Thanks to the characterization result, one can also construct an argument scheme representing deadlock situations. The use of argument schemes as formal tools to convey explanation in the context of multi-criteria aiding has also been advocated in [Labreuche, 2011;Nunes et al., 2014;[START_REF] Belahcene | [END_REF].

Our solutions stem from an original take of the dual notions of possibility and necessity, often used in so-called robust optimization, decision making [START_REF] Greco | [END_REF] or voting contexts [START_REF] Boutilier | [END_REF] to account for incomplete information, conveying epistemic stances of skepticism or credulousness. Instead we use them to describe the leeway left to the committee in setting its expectations: the decisions taken are bound from above by possibility, described as the feasibility of the Inv-NCS problem related to their decision, and from below by necessity, described as the infeasibility of the Inv-NCS problem simultaneously related to the reference cases and impossible assignments. [START_REF] Barrot | [END_REF] study the problem of identifying the possible winners of an approval election, when votes are given but approval thresholds are unspecified. They show that determining whether a set of candidates are co-winners is NPcomplete when voters have fixed (even equal) importance. Approval voting has been studied in the context of multiwinner elections [Aziz et al., 2015], which may seem close to our setting: indeed, we could see the candidates ranked in GOOD as the winners. However, in our context, each candidate is ranked without consideration to the other candidates, and voters are not assumed to have equal importance.

Finally, several algorithms have been proposed to learn the parameters of a noncompensatory sorting model from observation: [START_REF] Leroy | [END_REF] relies on a MIP formulation, [START_REF] Sobrie | [END_REF] relies on a metaheuristic.

  a, c}, A 5 := {c} and sufficient coalitions S containing the coalitions {1, 2}, {5} and their supersets.

  3 b 3 y 3 x 3 e 3 c d 4 a 4 c 4 e 4 x 4 y 4 f 4 b c 5 y 5 e 5 b 5 f 5 x 5 d 5 a

Meaning Ai i∈N is a tuple of subsets of X such that, for all i ∈ N , Ai is an upset of (X, i). Also, throughout the paper, when the indexing is left unspecified, the tuples are indexed by points of view i ∈ N .

Acknowledgments

This work is partially supported by the ANR project 14-CE24-0007-01 -CoCoRICo-CoDec.


Marc Coquand

D Bocquet

E Garbin

C Vianello

V Carabasse

C Delaye

Pellissier

G Piccolboni
email: giuseppe.piccolboni@cea.fr

G Molas

J M Portal

R Coquand

M Bocquet

D Garbin

E Vianello

C Carabasse

V Delaye

C Pellissier

T Magis

C Cagli

M Gely

O Cueto

D Deleruyelle

G Ghibaudo

B De Salvo

L Perniola

Investigation of the potentialities of Vertical Resistive RAM (VRRAM) for neuromorphic applications

Investigation of the potentialities of Vertical Resistive RAM (VRRAM) for neuromorphic applications

Introduction

Combining Resistive RAM concept with Vertical NAND technology and design, Vertical RRAM (VRRAM) was recently proposed as a cost-effective and extensible technology for future mass data storage applications [1]. 3D RRAM based neural networks were also proposed to emulate the potentiation and depression of a synapse [2], but more complex circuits were not discussed. In previous works [START_REF] Suri | IEDM 2012 Tech. Dig[END_REF][START_REF] Garbin | IEDM 2014 Tech. Dig[END_REF], various RRAM based neuromorphic circuits were proposed and investigated, using planar devices. In this paper, we investigate for the 1 st time the potentiality of the VRRAM concept for various neuromorphic applications, one synapse being emulated by one VRRAM pillar. First, basic functionality of HfO 2 based VRRAM is presented. 20ns switching time, up to 10 7

cycles and stable 200°C retention were demonstrated. Then specific analyses are made on the resistance and switching voltage variability. We demonstrate that a correlation effect exists between adjacent cycles, meaning the filament keeps a memory of its shape in the previous state, leading to reduced cycle to cycle variability. Based on this preliminary study, using compact model and circuit simulations, VRRAM are proposed for cochlea and convolutional neural network applications, showing good reliability with significant area gain with respect to planar approaches.

Technological details

TEM cross section of our VRRAM is presented in fig. 1. A TiN/SiO 2 double layer is deposited on a W plug, the TiN thickness being 10nm. Dry etching is used to pattern a cylinder and reveal a TiN liner, used as a bottom electrode (BE). The etching conditions are particularly critical and were optimized to ensure a vertical profile of the top electrode and reduce the corners effects at the TiN/SiO 2 interfaces. NMOS transistor is used as selector of the memory.

VRRAM characteristics

1. Performances -Typical bipolar IV forming SET and RESET characteristics are showed in fig. 2. Low resistance state (LRS) and high resistance state (HRS) resistances versus SET current (I SET ) dependence (fig. 3) show an increase of both R LRS and R HRS as I SET decreases. Functionality down to 7µA -with ~2.5 decades of mean window margin but higher dispersion -is put in evidence. The higher R HRS at low operating currents results in higher V SET as seen in fig. 4. HRS resistance gradually increases with the RESET voltage as illustrated in fig. 5. The forming voltage (V F ) is controlled by the Ti top electrode thickness (fig. 6), V F saturating to ~3.3V for Ti>30nm. 200°C retention (fig. 7) is insured for both LRS and HRS (I SET =100µA). Switching capability is demonstrated down to 20ns at 2.3V (fig. 8). Endurance performances can be adjusted, playing with the SET and RESET conditions, in order to optimize the window margin, the number of cycles or the SET current (fig. 9). At least 10 7 cycles could be achieved with 1 decade of window margin (fig. 11). 2. Variability -Resistance and switching voltages variability (including both cell to cell and cycle to cycle contributions) can lead to reliability degradation of RRAM based neural networks, in particular in case of internal switching probability. As expected, the resistance standard deviation increases with the mean value for both HRS and LRS (fig. 12) in agreement with [START_REF] Garbin | IEDM 2014 Tech. Dig[END_REF]. Moreover, an interesting feature concerns the fact that the resistance values during cycling do not follow a pure random process but are correlated from one cycle to the other [START_REF] Calderoni | proc. of IMW[END_REF] (fig. 13). Correlation (quantified by the correlation coefficient) decreases over cycling after ~50 cycles (fig. 14). Cycle to cycle correlation means that, despite no resistance drift is measured (fig. 15 bottom), the dispersion of the resistance for a given cycle increases as cycling goes on (fig. 15 top). This means that the conductive filament keeps for ~50 cycles a "memory" of the shape and resistance it had in the previous cycles. This resistance correlation leads to a correlation of the switching voltage itself, as seen in fig. 16. Again, no switching voltage drift is measured but its standard deviation increases during endurance, and saturates after ~30 cycles (fig. 17

). In summary, for applications requiring a limited (~10) number of cycles, correlation between adjacent cycles reduces variability (fig.18).

Neuromorphic applications

1. Synapse behavior implementation -In our approach, a synapse is composed by stacked VRRAM with one common select transistor (Fig. 25 left). This offers significant area gain with respect to neural networks in planar configuration with 1T1R elements in parallel (Fig. 25 right) [8]. The OxRAM cells operate in binary mode, only two distinct resistive states (LRS and HRS) per device. The analog-like conductance behaviour is achieved thanks to the parallel of n OxRAM cells. We use the intrinsic variability of RRAM in order to implement progressive on line learning (for instance the stochastic learning rule [START_REF] Suri | IEDM 2012 Tech. Dig[END_REF]). The switching probability is governed by the RRAM itself (internal switching probability). Consequently, VRRAM based neural networks (this work) offer area gain due to (1) stacked VRRAM, (2) 1TNR configuration and (3) no random number generator circuit. 1 st , we use VRRAM to emulate the typical progressive behaviour of synapse response. Fig. 19 shows the percentage of switched cells (~50 VRRAM measured) as a function of the applied bias and pulse times. SET and RESET conditions can be identified to control the probability to switch the memory with a given value for each pulse, the probability being imposed by the application and neural network structure. An OXRAM compact model [START_REF] Bocquet | [END_REF] is then used to set a model card based on our experimental results. Fig. 19 is fitted with good agreement, while cell-to-cell and cycle-to-cycle variability is well reproduced (fig. 20). Then the model is used to simulate a synapse composed by stacked VRRAM with 2 to 24 levels (fig. 23). The VRRAM are addressed in the same time (one selector for one VRRAM pillar), and the output signal corresponds to the sum of all the VRRAM in parallel (fig. 22). Then we calculated the standard deviation of the number or required pulses to SET or RESET half of the VRRAM stacked in one pillar (fig. 23). Fig. 24 shows that σ decreases as the number of levels increases. Thus it is possible to identify the required number of levels to reach a given σ and emulate typical analogic synaptic behaviour. 2. Cochlea -In the case of real-time auditory pattern extraction (inspired from a 64-channel silicon cochlea emulator, figs.25-26) [START_REF] Suri | IEDM 2012 Tech. Dig[END_REF] at least 3 RRAM are required per synapse [START_REF] Garbin | IEDM 2014 Tech. Dig[END_REF]. In our case, one synapse is thus composed by 3 stacked VRRAM with one select transistor, offering an integration density improvement of >3 with respect to previous work [START_REF] Garbin | IEDM 2014 Tech. Dig[END_REF]. Pulse times and voltages are adjusted based on fig. 19 in order to target switching percentages of 20% for SET and 5% for RESET [7]. As the number of required cycles in cochlea application is high (>10 5 ) [7], both cell-to-cell and cycle-to-cycle variability are taken into account and affect the internal switching probability. Nevertheless, the circuit behaviour shows good agreement with respect to the perfect case involving an external random number generator (fig. 27). Finally, we also assumed a perfectly controlled VRRAM technology where only cycle-to-cycle variability leads to switching voltage dispersion (σ/3 in fig. 18). In this configuration, very similar results to the perfect case are obtained (fig. 28).

Convolutional Neural Network (CNN)

-VRRAM can also be a suitable solution for visual pattern extraction applications (inspired from the processing inside visual cortex). It has been demonstrated that for Convolutional Neural Networks (CNN) a higher VRRAM density per synapse is required (~20) [8]. Based on the design used for the recognition of handwritten digits shown in fig. 29 and thoroughly described in [START_REF] Garbin | IEDM 2014 Tech. Dig[END_REF] it appears (from simulations, fig. 30) that given a certain resistance distribution (fig. 18 left) the recognition rate depends on the number of stacked VRRAM cells. Thus, at least 12 VRRAM levels are required to reach >98% circuit reliability. As CNN applications require limited number of cycles, correlation reduces RRAM cycle to cycle variability and improves circuit reliability with internal switching probability. Being able to stack several memory cells on a pillar (VRRAM) a considerable gain in total area (x10) is obtained compared to a standard design using planar devices. Further gain could even be envisaged for more complex applications requiring more synaptic levels.

Conclusions

In this paper, vertical RRAM are investigated and proposed to increase the density of neuromorphic circuits, one 1TnR pillar emulating one synapse. For cochlea application, good agreement with planar binary OXRAM configuration with random generator is obtained, with an area gain of more than a factor 3. Resistance correlation between adjacent cycles improves the reliability for neuromorphic applications requiring low endurance performances. Thus, for convolutional neural network, 10-15 RRAM levels are sufficient to reach a recognition rate of more than 98%. VRRAM based synapses open the path to high density neuromorphic circuits requiring aggressive synaptic levels. Fig. 4 VSET and VRESET as a function of the SET current. Higher VSET is due to higher RHRS (fig. 3).

and LRS retention. tiles (30%-70%) are sented. CtC (correlation between cycles)

Fig. 3 Fig. 6

 36 Fig.3 LRS and H function of th

Fig. 7 Fig

 7 Fig.7 200°C HRS a Median and percent repres

Fig 1 .

 1 Fig 1. Description of the integration flow and dark field) of the TiN

Fig. 8

 8 Fig.8 LRS and HRS distributions for various programming pulse widths (20ns -1µs) for Vpulse=2.3V.

  Fig.5 HRS resistance as a function of the bit line RESET voltage.

Fig. 9

 9 Fig.9 Relation between LRS resistance (related to operating current) and achieved number of cycles during endurance.

Fig. 13

 13 Fig.13 Zoom on cell endurance (fig.11) showing resistance correlation between adjacent cycles.

  Fig.18 SET voltage distribution for 50 cells for 5 (right) and 100 number of cycles, correlation reduces the disper

Fig. 24

 24 Fig.24 Mean value and stan deviation of the number of c to SET 50% of the cells in a as function of the number stacked VRRAM.

Fig. 27 Fig

 27 Fig.27 Cochlea application: circuit simulated with synapses compo 3 stacked VVRAM. SET conditions are fixed to target 20% of occu probability (fig. 19). Distributions of required # of pulses to SET respectively 1, 2 or 3 cells per pilar are represented and compared w theoretical case.

Fig

  Fig.22 Si is compos in pa