Publications

2008

• Analyse asymptotique et numérique de la diffraction d'ondes par des fils minces
  
  • Claeys Xavier
  , 2008. Cette thèse traite de la modélisation de la propagation d'ondes dans des milieux comportant des fils minces i.e. dont l'épaisseur est bien plus petite que la longueur d'onde. En appliquant la méthode des développements raccordés, nous dérivons un développement de la solution de l'équation de Helmholtz en 2D autour d'un petit obstacle avec condition de Dirichlet sur le bord et proposons un modèle approché dans lequel intervient une condition de Dirichlet moyennée. Par ailleurs nous proposons et analysons deux méthodes numériques non standard pour en calculer la solution avec précision : l'une est adaptée de la méthode de la fonction singulière et l'autre est une version scalaire de la méthode de Holland. Nous démontrons la consistance de ces méthodes. Nous effectuons ensuite le même travail en 3D pour le problème de Helmholtz avec condition de Dirichlet sur le bord d'un objet filiforme dont les pointes sont arrondies ellipsoïdalement. Nous dérivons également un modèle approché dont l'étude mène à une justification théorique de l'équation de Pocklington dans sa version scalaire.
• Efficient methods for computing spectral projectors for linearized hydrodynamic equations
  
  • Hechme Grace
  • Nechepurenko Yuri
  • Sadkane Miloud
  SIAM Journal on Scientific Computing, Society for Industrial and Applied Mathematics, 2008, 31 (1), pp.667-686. This paper presents efficient methods for computing the spectral projectors for hydrodynamic equations, linearized at a steady state and approximated with respect to space. The focus is on the spectral projectors corresponding to a given part of the finite spectrum. In the case when the size of the problem is not too large, a QR-based method is proposed and compared with the $QZ$ method. In the large scale case, two variants of the Jacobi-Davidson method, with a deflation procedure, are developed. In both cases, the computed spectral projectors can be used to construct low-order models suited for the context of hydrodynamic stability. Numerical results are reported. (10.1137/050648122)
  DOI : 10.1137/050648122
• Construction and analysis of improved Kirchoff conditions for acoustic wave propagation in a junction of thin slots
  
  • Joly Patrick
  • Semin Adrien
  ESAIM: Proceedings, EDP Sciences, 2008, 25, pp.44-67. In this paper, we analyze via the theory of matched asymptotics the propagation of a time harmonic acoustic wave in a junction of two thin slots. This allows us to propose improved Kirchoff conditions for the 1D limit problem, These conditions are analyzed and validated numerically.
• Identification de cavités par la méthode de sensibilité topologique en élastodynamique temporelle
  
  • Bellis Cédric
  • Bonnet Marc
  , 2008.
• Application of Cagniard de Hoop Method to the Analysis of Perfectly Matched Layers
  
  • Diaz Julien
  • Joly Patrick
  , 2008. We show how Cagniard de Hoop method can be used, first to obtain error estimates for the Perfectly Matched Layers in acoustics (PML), then to understand the instabilities of the PML when applied to aeroacousics. The principle of the methods consists in applying to the equations a Laplace transform in time and a Fourier transform in one space variable to obtain an ordinary differential equation which can be explicitely solved.
• SHA-3 proposal: FSB
  
  • Finiasz Matthieu
  • Gaborit Philippe
  • Sendrier Nicolas
  • Manuel Stéphane
  , 2008.
• Cryptanalysis of MinRank
  
  • Faugère Jean-Charles
  • Levy-Dit-Vehel Françoise
  • Perret Ludovic
  , 2008, 5157, pp.280-296. In this paper, we investigate the difficulty of one of the most relevant problems in multivariate cryptography - namely MinRank - about which no real progress has been reported since [9, 19]. Our starting point is the Kipnis-Shamir attack [19]. We first show new properties of the ideal generated by Kipnis-Shamir's equations. We then propose a new modeling of the problem. Concerning the practical resolution, we adopt a Gröbner basis approach that permitted us to actually solve challenges A and B proposed by Courtois in [8]. Using the multi-homogeneous structure of the algebraic system, we have been able to provide a theoretical complexity bound reflecting the practical behavior of our approach. Namely, when r ′ the dimension of the matrices minus the rank of the target matrix in the MinRank problem is constant, then we have a polynomial time attack O(ln(q)n3r′2) . For the challenge C [8], we obtain a theoretical bound of 266.3 operations. (10.1007/978-3-540-85174-5_16)
  DOI : 10.1007/978-3-540-85174-5_16
• Asymptotic expansion of highly conductive thin sheets
  
  • Schmidt Kersten
  • Tordeux Sébastien
  PAMM, Wiley-VCH Verlag, 2008, 7, pp.2040011-2040012. Sensitive measurement and control equipment are protected from disturbing electromagnetic fields by thin shielding sheets. Alternatively to discretisation of the sheets, the electromagnetic fields are modeled only in the surrounding of the layer taking them into account with the so called Generalised Impedance Boundary Conditions. We study the shielding effect by means of the model problem of a diffusion equation with additional dissipation in the curved thin sheet. We use the asymptotic expansion techniques to derive a limit problem, when the thickness of the sheet $\varepsilon$ tends to zero, as well as the models for contribution to the solution of higher order in $\varepsilon$. These problems are posed in limit area of vanishing $\varepsilon$ with condition for the jump of the solution and it's normal derivative, which avoid to mesh the computational domain, even locally, at the scale of $\varepsilon$. We derive the problems for arbitrary order and show their existence and uniqueness. Numerical experiments for the problems up to second order show the asymptotic convergence of the solution of right order in mean of the thickness parameter $\varepsilon$.
• Application of kernel-based stochastic gradient algorithms to option pricing
  
  • Barty Kengy
  • Girardeau Pierre
  • Strugarek Cyrille
  • Roy Jean-Sébastien
  Monte Carlo Methods and Applications, De Gruyter, 2008, 14, pp.99-127. We present an algorithm for American option pricing based on stochastic approximation techniques. Besides working on a finite subset of the exercise dates (e.g. considering the associated Bermudean option), option pricing algorithms generally involve another step of discretization, either on the state space or on the underlying functional space. Our work, which is an application of a more general perturbed gradient algorithm introduced recently by the authors, consists in approximating the value functions of the classical dynamic programming equation at each time step by a linear combination of kernels. The so-called kernel-based stochastic gradient algorithm avoids any a priori discretization, besides the discretization of time. Thus, it converges toward the optimum of the non-discretized Bermudan option pricing problem. We present a comprehensive methodology to implement efficiently this algorithm, including discussions on the numerical tools used, like the Fast Gauss Transform, or Brownian bridge. We also compare our results to some existing methods, and provide empirical statistical results.
• Estimating the eddy-current modelling error
  
  • Schmidt Kersten
  • Sterz Oliver
  • Hiptmair Ralf
  IEEE Transactions on Magnetics, Institute of Electrical and Electronics Engineers, 2008, 44 (6), pp.686-689. The eddy-current model is an approximation of the full Maxwell equations. We will give estimates for the modeling error and show how the constants in the estimates are influenced by the geometry of the problem. Additionally, we analyze the asymptotic behavior of the modeling error when the angular frequency tends to zero. The theoretical results are complemented by numerical examples using high order finite elements. These demonstrate that the estimates are sharp. Hence, this work delivers a mathematical basis for assessing the scope of the eddy-current model. (10.1109/TMAG.2008.915834)
  DOI : 10.1109/TMAG.2008.915834
• A non-iterative FEM-based cavity identification method using topological sensitivity for 2D and 3D time domain elastodynamics
  
  • Bellis Cédric
  • Bonnet Marc
  , 2008. This communication addresses the application of topological sensitivity to the numerical solution of cavity identification in elastic media. The topological sensitivity analysis arises in connection with the investigation of the asymptotic behaviour of the featured cost functional (here introduced as a means of formulating the inverse problem in terms of a minimisation) with respect to the creation of a cavity of infinitesimal radius and prescribed location in an otherwise cavity-free solid. Initially developed for the topological optimization of structures, this method provides a non-iterative computational tool for constructing a reliable void indicator function, as previously discussed in e.g. [1,2]. The cost functional used here is classically based on exploiting data about the boundary traces of the mechanical fields arising in wave-imaging processes. It quantifies the gap between quantities (e.g. dis- placements) based on a trial topology domain and on a reference domain. In practice, the reference quantities can be provided by experimental measurements or by numerical simulations. Such problems involve naturally integral formulations. The framework of the topological derivative, ie owning to the infinitesimal size of a cavity, of general functionals is presented in [3] in the linear elasticity case. More details can be found in [2] on the mathematical developements which leads to an analytical first order asymptotic expansion of cost functionals in a frequency domain. The results presented here use the derivation technics based on the use of an adjoint state. This method allows to deal with the topological gradient of general functionals with high simplicity and efficiency. Our aim is to illustrate the efficiency of such non-iterative identification technique implemented in a conventional computational framework (here, the classical displacement-based finite element method together with a Newmark time-stepping algorithm). Results of numerical experiments will be presented for 2-D and 3-D time-domain elastodynamic cases, based on topological sensitivity formulas given in [1], in order to demonstrate the efficiency of the approach. Dynamical simulations will highlight the mechanisms underlying identification methods based on topological sensitivity. As well as other meth- ods such as the linear sampling method [4] (not yet implemented for time-domain problems, to the best of our knowledge), such approach is demonstrated through numerical experiments to provide qualita- tively good identification results while being computationally much more economical than ordinary, iterative, inversion procedures.
• Théorie des champs classiques
  
  • Perez Jérôme
  , 2008, pp.200 pages. De la physique de Newton, à la formulation de la gravitation dans le cadre de la relativité générale, en passant par la mécanique analytique, la relativité restreinte, et la formulation variationnelle de l'électromagnétisme, cet ouvrage présente une vision harmonisée de la physique. Il permettra étudiants de second cycle universitaire, ainsi qu'aux amateurs érudits qui possèdent des connaissances de ces différents pans de la physique et à qui l'on a demandé de patienter pour en savoir plus, de voir enfin sous un même angle l'ensemble de l'enseignement scientifique reçu, de goûter beauté de formulations unificatrices et d'acquérir enfin l'ouverture qui leur permettra de s'enivrer du vertige de la physique moderne. Cet ouvrage est le fruit d'un cours donné par l'auteur à l'École Nationale Supérieure de Techniques Avancées (ENSTA) depuis de nombreuses années
• Matching of asymptotic expansions for waves propagation in media with thin slots. II. The error estimates
  
  • Joly Patrick
  • Tordeux Sébastien
  ESAIM: Mathematical Modelling and Numerical Analysis, Société de Mathématiques Appliquées et Industrielles (SMAI) / EDP, 2008, 42 (2), pp.193--221. We are concerned with a 2D time harmonic wave propagation problem in a medium including a thin slot whose thickness $\epsilon$ is small with respect to the wavelength. In Part I [P. Joly and S. Tordeux, Multiscale Model. Simul. 5 (2006), no. 1, 304--336 (electronic); MR2221320 (2007e:35041)], we derived formally an asymptotic expansion of the solution with respect to $\epsilon$ using the method of matched asymptotic expansions. We also proved the existence and uniqueness of the terms of the asymptotics. In this paper, we complete the mathematical justification of our work by deriving optimal error estimates between the exact solutions and truncated expansions at any order. (10.1051/m2an:2008004)
  DOI : 10.1051/m2an:2008004
• Identification of generalized impedance boundary conditions in inverse scattering problems
  
  • Bourgeois Laurent
  • Haddar Houssem
  , 2008, pp.27. In the context of scattering problems in the harmonic regime, we consider the problem of identification of some Generalized Impedance Boundary Conditions (GIBC) at the boundary of an object (which is supposed to be known) from far field measurements associated with a single incident plane wave at a fixed frequency. The GIBCs can be seen as approximate models for thin coatings, corrugated surfaces or highly absorbing media. After pointing out that uniqueness does not hold in the general case, we propose some additional assumptions for which uniqueness can be restored. We also consider the question of stability when uniqueness holds. We prove in particular Lipschitz stability when the impedance parameters belong to a compact set. We also extend local stability results to the case of back-scattering data.
• A new approach for approximating linear elasticity problems
  
  • Ciarlet Philippe G.
  • Ciarlet Patrick
  Comptes Rendus. Mathématique, Académie des sciences (Paris), 2008, 346 (5-6), pp.351-356. In this Note, we present and analyze a new method for approximating linear elasticity problems in dimension two or three. This approach directly provides approximate strains, i.e., without simultaneously approximating the displacements, in finite element spaces where the Saint Venant compatibility conditions are exactly satisfied in a weak form. To cite this article: P.G. Ciarlet, P. Ciarlet, Jr., C. R. Acad. Sci. Paris, Ser. I 346 (2008). © 2008 Académie des sciences. (10.1016/j.crma.2008.01.014)
  DOI : 10.1016/j.crma.2008.01.014
• Dislocations dynamics with a mean curvature term: short time existence and uniqueness
  
  • Forcadel Nicolas
  Differential and integral equations, Khayyam Publishing, 2008, 21 (3-4), pp.285-304. In this paper, we study a new model for dislocation dynamics with a mean curvature term. The model is a non-local Hamilton-Jacobi equation. We prove a short time existence and uniqueness result for this equation. We also prove a Lipschitz estimate in space and an estimate of the modulus of continuity in time for the solution.
• The linear sampling method in a waveguide: A modal formulation
  
  • Bourgeois Laurent
  • Lunéville Éric
  Inverse Problems, IOP Publishing, 2008, 24 (1). This paper concerns the linear sampling method used to retrieve obstacles in a 2D or 3D acoustic waveguide. The classical mathematical results concerning the identifiability of the obstacle and the justification of the inverse method are established for this particular geometry. Our main concern is to derive a modal formulation of the linear sampling method that is well adapted to the waveguide configuration. In particular, thanks to such formulation, we highlight the fact that finding some obstacles from remote scattering data is more delicate in a waveguide than in free space. Indeed, the presence of evanescent modes increases the ill posedness of the inverse problem. However, we show that the numerical reconstruction of obstacles by using the far field is feasible, even by using a few incident waves. © 2008 IOP Publishing Ltd. (10.1088/0266-5611/24/1/015018)
  DOI : 10.1088/0266-5611/24/1/015018
• An improved multimodal approach for non-uniform acoustic waveguides
  
  • Hazard Christophe
  • Lunéville Éric
  IMA Journal of Applied Mathematics, Oxford University Press (OUP), 2008, 73 (4), pp.668-690. This paper explores from the point of view of numerical analysis a method for solving the acoustic time-harmonic wave equation in a locally non-uniform 2D waveguide. The multimodal method is based on a spectral description of the acoustic field in each transverse section of the guide, using Fourier-like series. In the case of sound-hard boundaries, the weak point of the method lies in the poor convergence of such series due to a poor approximation of the field near the boundaries. A remedy was proposed by Athanassoulis & Belibassakis (1999, J. Fluid Mech., 389, 275-301), where the convergence is improved thanks to the use of enhanced series. The present paper proposes a theoretical analysis of their idea and studies further improvements. For a general model which includes different kinds of non-uniformity (varying cross section, bend and inhomogeneous medium), a hybrid spectral/variational formulation is introduced. Error estimates are provided for a semi-discretized problem which concerns the effect of spectral truncation. These estimates are confirmed by numerical results. © The Author 2008. Published by Oxford University Press on behalf of the Institute of Mathematics and its Applications. All rights reserved. (10.1093/imamat/hxn006)
  DOI : 10.1093/imamat/hxn006
• Conditional stability for ill-posed elliptic Cauchy problems : the case of $C^{1,1}$ domains (part I)
  
  • Bourgeois Laurent
  , 2008. This paper is devoted to a conditional stability estimate related to the ill-posed Cauchy problems for the Laplace's equation in domains with $C^{1,1}$ boundary. It is an extension of an earlier result for domains of class $C^\infty$. Our estimate is established by using a global Carleman estimate near the boundary in which the exponential weight depends on the distance function to the boundary. Furthermore, we prove that this stability estimate is nearly optimal and induces a nearly optimal convergence rate for the method of quasi-reversibility to solve the ill-posed Cauchy problems.
• On a graph coloring problem arising from discrete tomography
  
  • Bentz Cédric
  • Costa Marie-Christine
  • de Werra Dominique
  • Picouleau Christophe
  • Ries Bernard
  Networks, Wiley, 2008, 51 (4), pp.256-267. Discrete tomography deals with the reconstruction of discrete homogenous objects from their projections. The reader is referred to the book of Hermann and Kuba [2] for an overview on discrete tomography. The image reconstruction problem is important since its solution is required for developing efficient procedures in image processing, data bases, crystallography, statistics, data compressing,... It can be formulated as follows: given a rectangular array where entries represent the pixels of a digitalized image coloured with k different colors, we consider the problem of reconstructing an image from the number of occurrences of each colour in every column and in every row. The problem is known to be polynomial for k=1, NP-complete for k=3 [1] and its complexity is still open for k=2. Here, we shall consider a graph colouring problem which generalizes both the well known basic graph colouring problem and the above image reconstruction problem. We are given a graph G=(V,E) and a collection P of p subsets Pi of vertices of G. We are also given a set of colours 1, 2, ..,k as well as a collection of p vectors h(Pi) of integers. The problem is to find a k-partition, i.e. a k-colouring, of V such that the number of vertices of Pi coloured with colour j is equal to the jth entry of the vector h(Pi), for all j=1,..,k and all i=1,..,p. The basic graph colouring problem deals with different colour assigned to adjacent vertices: we will call this a "proper" k-colouring otherwise we will call this simply a k-colouring. In this talk, we will consider colouring as well as proper colouring. Let us consider the special case where the graph G is a grid graph, the vertices, denoted by Xrs, are located on row r and column s, r=1,..,m and s=1,..,n, and P is the collection of the m+n chains corresponding to the rows and columns: the problem of finding a k-colouring of G corresponds exactly to the image reconstruction problem. In this talk we will consider some extensions by taking more general classes of graphs such as trees or bipartite graphs. We will restrict our attention to the case where each Pi is a chain in G. We call "cover index" of P, c(P), the maximum number of members of P which may cover a single element of V, i.e. which have a non empty intersection. We call "nested" a family P such that, for any pair of subsets, either one subset is included in the other or they are disjoint; then, the "nesticity" of P, nest(P), is the smallest number of nested families in a partition of P into nested families. First we will give several basic conditions for a solution to exist. Then, we will classify the problems according to the number of colours, the values of c(P) and nest(P), the class of the graph, the diameter of the graph, and so on. For each problem, either we will propose a polynomial time algorithm or we will give complexity results. For instance, we will prove that when G is a tree, the 2-colouring problem and the proper 3-colouring problems are NP-complete even if the maximum degree of G is bounded by 3; but we will propose a polynomial time algorithm solving the k-colouring problem when G is a tree and when any two Pi intersect in at most one vertex. All our results will be summarized in a table. (10.1002/net.20218)
  DOI : 10.1002/net.20218
• Conditional stability for ill-posed elliptic Cauchy problems : the case of Lipschitz domains (part II)
  
  • Bourgeois Laurent
  • Dardé Jérémi
  , 2008. This paper is devoted to a conditional stability estimate related to the ill-posed Cauchy problems for the Laplace's equation in domains with Lipschitz boundary. It completes the results obtained in \cite{bourgeois1} for domains of class $C^{1,1}$. This estimate is established by using an interior Carleman estimate and a technique based on a sequence of balls which approach the boundary. This technique is inspired from \cite{alessandrini}. We obtain a logarithmic stability estimate, the exponent of which is specified as a function of the boundary's singularity. Such stability estimate induces a convergence rate for the method of quasi-reversibility introduced in \cite{lions} to solve the Cauchy problems. The optimality of this convergence rate is tested numerically, precisely a discretized method of quasi-reversibility is performed by using a nonconforming finite element. The obtained results show very good agreement between theoretical and numerical convergence rates.
• A Fast Marching Method for Hamilton-Jacobi Equations Modeling Monotone Front Propagations
  
  • Cristiani Emiliano
  , 2008. In this paper we present a generalization of the Fast Marching method introduced by J. A. Sethian in 1996 to solve numerically the eikonal equation. The new method, named Buffered Fast Marching (BFM), is based on a semi-Lagrangian discretization and is suitable for Hamilton-Jacobi equations modeling monotonically advancing fronts, including Hamilton-Jacobi-Bellman and Hamilton-Jacobi- Isaacs equations which arise in the framework of optimal control problems and differential games. We also show the convergence of the algorithm to the viscosity solution. Finally we present several numerical tests proving that the BFM method is accurate and faster than the classical iterative algorithm in which every node of the grid is computed at every iteration.
• Computing electromagnetic eigenmodes with continuous Galerkin approximations
  
  • Ciarlet Patrick
  • Hechme Grace
  Computer Methods in Applied Mechanics and Engineering, Elsevier, 2008, 198 (2), pp.358-365. Costabel and Dauge proposed a variational setting to solve numerically the time-harmonic Maxwell equations in 3D polyhedral geometries, with a continuous approximation of the electromagnetic field. In order to remove spurious eigenmodes, three computational strategies are then possible. The original method, which requires a parameterization of the variational formulation. The second method, which is based on an a posteriori filtering of the computed eigenmodes. And the third method, which uses a mixed variational setting so that all spurious modes are removed a priori. In this paper, we discuss the relative merits of the approaches, which are illustrated by a series of 3D numerical examples. © 2008 Elsevier B.V. All rights reserved. (10.1016/j.cma.2008.08.005)
  DOI : 10.1016/j.cma.2008.08.005
• Higher order time stepping for second order hyperbolic problems and optimal CFL conditions
  
  • Gilbert Jean Charles
  • Joly Patrick
  , 2008, 16, pp.67-93. We investigate explicit higher order time discretizations of linear second order hyperbolic problems. We study the even order (2m) schemes obtained by the modified equation method. We show that the corresponding CFL upper bound for the time step remains bounded when the order of the scheme increases. We propose variants of these schemes constructed to optimize the CFL condition. The corresponding optimization problem is analyzed in detail and the analysis results in a specific numerical algorithm. The corresponding results are quite promising and suggest various conjectures. (10.1007/978-1-4020-8758-5_4)
  DOI : 10.1007/978-1-4020-8758-5_4
• Local time stepping and discontinuous Galerkin methods for symmetric first order hyperbolic systems
  
  • Ezziani Abdelaâziz
  • Joly Patrick
  Journal of Computational and Applied Mathematics, Elsevier, 2008. We present a new non conforming space-time mesh refinement method for symmetric first order hyperbolic system. This method is based on the one hand on the use of a conservative higher order discontinuous Galerkin approximation for space discretization and a finite difference scheme in time, on the other hand on appropriate discrete transmission conditions between the grids. We use a discrete energy technique to drive the construction of the matching procedure between the grids and guarantee the stability of the method.