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
• Propagation of an acoustic wave in a junction of two thin slots
  
  • Joly Patrick
  • Semin Adrien
  , 2008, pp.61. In this research report, 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 model. These conditions are analyzed and validated numerically.
• Singular trajectories of control-affine systems
  
  • Chitour Yacine
  • Jean Frédéric
  • Trélat Emmanuel
  SIAM Journal on Control and Optimization, Society for Industrial and Applied Mathematics, 2008, 47 (2), pp.1078--1095. When applying methods of optimal control to motion planning or stabilization problems, some theoretical or numerical difficulties may arise, due to the presence of specific trajectories, namely, singular minimizing trajectories of the underlying optimal control problem. In this article, we provide characterizations for singular trajectories of control-affine systems. We prove that, under generic assumptions, such trajectories share nice properties, related to computational aspects; more precisely, we show that, for a generic system -- with respect to the Whitney topology --, all nontrivial singular trajectories are of minimal order and of corank one. These results, established both for driftless and for control-affine systems, extend previous results. As a consequence, for generic systems having more than two vector fields, and for a fixed cost, there do not exist minimizing singular trajectories. We also prove that, given a control system satisfying the LARC, singular trajectories are strictly abnormal, generically with respect to the cost. We then show how these results can be used to derive regularity results for the value function and in the theory of Hamilton-Jacobi equations, which in turn have applications for stabilization and motion planning, both from the theoretical and implementation issues. (10.1137/060663003)
  DOI : 10.1137/060663003
• A monotonic evaluation of lower bounds for inf-sup stability constants in the frame of reduced basis approximations
  
  • Chen Yanlai
  • Hesthaven Jan S.
  • Maday Yvon
  • Rodríguez Jerónimo
  Comptes Rendus. Mathématique, Académie des sciences (Paris), 2008, 346 (23-24), pp.1295-1300. For accurate a posteriori error analysis of the reduced basis method for coercive and non-coercive problems, a critical ingredient lies in the evaluation of a lower bound for the coercivity or inf-sup constant. In this short Note, we generalize and improve the successive constraint method first presented by Huynh (2007) by providing a monotonic version of this algorithm that leads to both more stable evaluations and fewer offline computations. © 2008 Académie des sciences. (10.1016/j.crma.2008.10.012)
  DOI : 10.1016/j.crma.2008.10.012
• A characterization of singular electromagnetic fields by an inductive approach
  
  • Assous F.
  • Ciarlet Patrick
  • Garcia E.
  International Journal of Numerical Analysis and Modeling, Institute for Scientific Computing and Information, 2008, 5 (3), pp.491-515. In this article, we are interested in the mathematical modeling of singular electromagnetic fields, in a non-convex polyhedral domain. We first describe the local trace (i. e. defined on a face) of the normal derivative of an L2 function, with L2 Laplacian. Among other things, this allows us to describe dual singularities of the Laplace problem with homogeneous Neumann boundary condition. We then provide generalized integration by parts formulae for the Laplace, divergence and curl operators. With the help of these results, one can split electromagnetic fields into regular and singular parts, which are then characterized. We also study the particular case of divergence-free and curl-free fields, and provide non-orthogonal decompositions that are numerically computable. © 2008 Institute for Scientific Computing and Information.
• Generalized impedance boundary conditions for scattering problems from strongly absorbing obstacles: the case of Maxwell's equations
  
  • Haddar Houssem
  • Joly Patrick
  • Nguyen Hoai-Minh
  Mathematical Models and Methods in Applied Sciences, World Scientific Publishing, 2008, 18 (10), pp.1787-1827. (10.1142/S0218202508003194)
  DOI : 10.1142/S0218202508003194
• Numerical solution of large-scale Lyapunov equations, Riccati equations, and linear-quadratic optimal control problems
  
  • Benner Peter
  • Li Jing-Rebecca
  • Penzl Thilo
  Numerical Linear Algebra with Applications, Wiley, 2008, 15 (9), pp.755-777. We study large-scale, continuous-time linear time-invariant control systems with a sparse or structured state matrix and a relatively small number of inputs and outputs. The main contributions of this paper are numerical algorithms for the solution of large algebraic Lyapunov and Riccati equations and linearquadratic optimal control problems, which arise from such systems. First, we review an alternating direction implicit iteration-based method to compute approximate low-rank Cholesky factors of the solution matrix of large-scale Lyapunov equations, and we propose a refined version of this algorithm. Second, a combination of this method with a variant of Newton's method (in this context also called Kleinman iteration) results in an algorithm for the solution of large-scale Riccati equations. Third, we describe an implicit version of this algorithm for the solution of linear-quadratic optimal control problems, which computes the feedback directly without solving the underlying algebraic Riccati equation explicitly. Our algorithms are efficient with respect to both memory and computation. In particular, they can be applied to problems of very large scale, where square, dense matrices of the system order cannot be stored in the computer memory. We study the performance of our algorithms in numerical experiments. (10.1002/nla.622)
  DOI : 10.1002/nla.622
• Complexity results for the horizontal bar packing problem
  
  • Costa Marie-Christine
  • Jarray Fethi
  • Picouleau Christophe
  Information Processing Letters, Elsevier, 2008, 108 (6), pp.356-359. The paper deals with the problem of packing a set of horizontal bars by taking into account some constraints on the distance between two consecutive bars on the same row. This problem is deeply connected with Discrete Tomography and it finds application in workforce scheduling. We study the complexity of the problem and show that, depending on the kind of constraints considered, the problem can be polynomial or NP-Complete. We analyze in details the case where a minimal distance between consecutive bars is required and propose a greedy algorithm which solves this problem in polynomial time. (10.1016/j.ipl.2008.07.007)
  DOI : 10.1016/j.ipl.2008.07.007
• 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.
• 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
• 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.
• 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