Publications

2012

• Multigrid methods for zero-sum two player stochastic games
  
  • Detournay Sylvie
  , 2012. In this thesis, we present some algorithms and numerical results for the solution of large scale zero-sum two player repeated stochastic games. In particular, we consider the class of games with perfect information and infinite horizon. In this class, we consider the games with discounted payoff and the games with mean payoff. Our algorithms are mainly based on policy iteration type algorithms and multigrid methods, and are implemented in C. These algorithms are applied either to the dynamic programming equation of a true finite state space zero-sum two player game or to the discretization of an Isaacs PDE of a zero-sum stochastic differential game. In a first part, we propose an algorithm which combines policy iterations for discounted games and algebraic multigrid methods to solve the linear systems involved in the policy iterations. We present numerical tests on discretizations of Isaacs equations or variational inequalities. We also present a full multilevel policy iteration, similar to FMG, which allows one to improve substantially the computation time for solving some variational inequalities. For the games with mean payoff, we develop a policy iteration algorithm to solve zero-sum stochastic games with finite state and action spaces, perfect information and in the general multichain case (i.e. without irreducibility assumption on the Markov chains determined by the strategies of the players), following an idea of Cochet-Terrasson and Gaubert (2006). This algorithm relies on a notion of nonlinear spectral projection of dynamic programming operators of a one player games (which are monotone and convex). We show that the sequence of values and relative values satisfies a lexicographical monotonicity property, which implies that the algorithm does terminate. We present numerical results on a variant of Richman games and on pursuit-evasion games. We propose new algebraic multigrid algorithms to solve particular singular linear systems that arise for instance in the above policy iteration algorithm for zero-sum two player stochastic games with mean payoff. Furthermore, we introduce a new method to find the stationary probability of an irreducible Markov chain using a stochastic control approach and present an algorithm which combines the Howard policy iterations and algebraic multigrid iterations for singular systems.
• Noeud '7-trèfle' torique fractal
  
  • Colonna Jean-François
  , 2012. Fractal 7-foil torus knot (Noeud '7-trèfle' torique fractal)
• Noeud '5-trèfle' torique fractal
  
  • Colonna Jean-François
  , 2012. Fractal 5-foil torus knot (Noeud '5-trèfle' torique fractal)
• Introduction to stochastic calculus and to the resolution of PDEs using Monte Carlo simulations - Lectures notes of XV Spanish-French School on Numerical Simulation in Physics and Engineering
  
  • Gobet Emmanuel
  , 2012, pp.68. I give a pedagogical introduction to Brownian motion, stochastic calculus introduced by Ito in the fifties, following the elementary (at least not too technical) approach by Föllmer 1981. Based on this, I develop the connection with linear and semi-linear parabolic PDEs. Then, I provide and analyze some Monte Carlo methods to approximate the solution to these PDEs This course is aimed at master students, PhD students and researchers interesting in the connection of stochastic processes with PDEs and their numerical counterpart. The reader is supposed to be familiar with basic concepts of probability (say first chapters of the book "Probability essentials" by Jacod and Protter 2003), but no a priori knowledge on martingales and stochastic processes is required.
• Noeud '3-trèfle' torique fractal
  
  • Colonna Jean-François
  , 2012. Fractal 3-foil torus knot (Noeud '3-trèfle' torique fractal)
• Visualisation tridimensionnelle de la conjecture ABC
  
  • Colonna Jean-François
  , 2012. Tridimensional visualization of the ABC conjecture (Visualisation tridimensionnelle de la conjecture ABC)
• La conjecture ABC
  
  • Colonna Jean-François
  , 2012. The ABC conjecture (La conjecture ABC)
• La conjecture ABC
  
  • Colonna Jean-François
  , 2012. The ABC conjecture (La conjecture ABC)
• La conjecture ABC
  
  • Colonna Jean-François
  , 2012. The ABC conjecture (La conjecture ABC)
• Modelling targets for anticancer drug control optimisation in physiologically structured cell population models
  
  • Billy Frédérique
  • Clairambault Jean
  • Fercoq Olivier
  • Lorenzi Tommaso
  • Lorz Alexander
  • Perthame Benoît
  , 2012, 1479, pp.1323-1326. The main two pitfalls of therapeutics in clinical oncology, that limit increasing drug doses, are unwanted toxic side effects on healthy cell populations and occurrence of resistance to drugs in cancer cell populations. Depending on the constraint considered in the control problem at stake, toxicity or drug resistance, we present two different ways to model the evolution of proliferating cell populations, healthy and cancer, under the control of anti-cancer drugs. In the first case, we use a McKendrick age-structured model of the cell cycle, whereas in the second case, we use a model of evolutionary dynamics, physiologically structured according to a continuous phenotype standing for drug resistance. In both cases, we mention how drug targets may be chosen so as to accurately represent the effects of cytotoxic and of cytostatic drugs, separately, and how one may consider the problem of optimisation of combined therapies. (10.1063/1.4756399)
  DOI : 10.1063/1.4756399
• Electromagnetic time reversal and scattering by a small dielectric inclusion
  
  • Gdoura Souhir
  • Wahab Abdul
  • Lesselier Dominique
  Journal of Physics: Conference Series, IOP Science, 2012, 386, pp.012010. An asymptotic expression of the scattered electromagnetic far-field due to a small spherical dielectric inclusion illuminated by an impulsive vector source nearby is proposed first. Then, a time-reversal technique enabling to locate the position of this inclusion is developed and its performances are illustrated from numerical simulations. (10.1088/1742-6596/386/1/012010)
  DOI : 10.1088/1742-6596/386/1/012010
• Optimization of Perron eigenvectors and applications: from web ranking to chronotherapeutics
  
  • Fercoq Olivier
  , 2012. Search engines play a key role in the World Wide Web. They gather information on the web pages and for each query of a web surfer they give a sorted list of relevant web pages. Internet search engines use a variety of algorithms to sort web pages based on their text content or on the hyperlink structure of the web. Here, we focus on algorithms that use the latter hyperlink structure, called link-based algorithms, and among them PageRank, HITS, SALSA and HOTS. The basic notion for all these algorithms is the web graph, which is a digraph with a node for each web page and an arc between nodes i and j if there is a hyperlink from page i to page j. The original problem considered in the present work is the optimization of the ranking of the pages of a given web site. It consists in finding an optimal outlink strategy maximizing a scalar function of a given ranking subject to design constraints. PageRank, HITS and SALSA are Perron vector rankings, which means that they correspond to the principal eigenvector of a (elementwise) nonnegative matrix. When optimizing the ranking, we thus optimize a scalar utility function of the Perron eigenvector over a set of nonnegative irreducible matrices. The matrix is constructed from the web graph, so controlling the hyperlinks corresponds to controlling the matrix itself. We first study general PageRank optimization problems with a "total income" utility function and design constraints. This case is of particular interest since the value of the PageRank is an acknowledged economic issue. We reduced the PageRank optimization problem to Markov decision problems such that the action sets are implicitly defined as the vertices of polytopes that have a polynomial time separation oracle. We show that such Markov decision problems are solvable in polynomial time and we provide a scalable algorithm for the effective resolution of the PageRank optimization problem on large dataset. Then, we study the general problem of optimizing a scalar utility function of the Perron eigenvector over a set of nonnegative irreducible matrices. This covers all Perron vector rankings, including HITS and SALSA. We show that the matrix of partial derivatives of the objective has a low rank and can be computed by an algorithm with the same convergence properties as the power algorithm used to compute the ranking and so the value of the objective. We give an optimization algorithm that couples power and gradient iterations and prove its convergence to a stationary point of the optimization problem. Considering HOTS as a nonlinear Perron vector, we show that the HOTS algorithm converges with a linear rate of convergence, that the objective of the HOTS optimization problem has a low rank and that the coupled power and gradient algorithm applies. Finally, we extend the domain of application of the Perron eigenvalue and eigenvector optimization methods to the optimization of chemotherapy under the McKendrick model of population dynamics. We consider here that the cells behave differently at an hour of the day or another. We want to take advantage of this feature to minimize the growth rate of cancer cell population while we maintain the growth rate of healthy cell population over a given toxicity threshold. The objective and the constraint can be written as the Floquet eigenvalues of age-structured PDE models with periodic coefficients, and they are approximated by Perron eigenvalues in the discretized problem. We search for locally optimal drug infusion strategies by a method of multipliers, where the unconstrained minimizations are performed using the coupled power and gradient algorithm that we have developed in the context of web ranking optimization.
• Un polyèdre fractal
  
  • Colonna Jean-François
  , 2012. A fractal polyhedron (Un polyèdre fractal)
• Monument Valley à la façon de David Hockney
  
  • Colonna Jean-François
  , 2012. Monument Valley à la David Hockney (Monument Valley à la façon de David Hockney)
• Monument Valley à la façon de David Hockney
  
  • Colonna Jean-François
  , 2012. Monument Valley à la David Hockney (Monument Valley à la façon de David Hockney)
• Monument Valley à la façon de David Hockney
  
  • Colonna Jean-François
  , 2012. Monument Valley à la David Hockney (Monument Valley à la façon de David Hockney)
• Monument Valley à la façon de David Hockney
  
  • Colonna Jean-François
  , 2012. Monument Valley à la David Hockney (Monument Valley à la façon de David Hockney)
• New ODE Model for Diffusion MRI Signal
  
  • Nguyen Hang Tuan
  • Li Jing-Rebecca
  • Grebenkov Denis S.
  , 2012. Water diffusion in biological tissues is not Gaussian and signal attenuation is not monoexponential with b-value [1]. Approaches to deal with this behavior include the bi-exponential model [1,2], the Karger model [3], and Kurtosis approach [4]. We formulate an ODE model for diffusion MRI signal that is more general than Karger model, valid for more general diffusion gradient shapes and gives a good approximation to the ADC and Kurtosis. Given DMRI signals before and after cell swelling, we can estimate the amount of cell swelling after numerically solving an ODE system.
• Effective diffusion tensor computed by homogenization
  
  • Nguyen Dang Van
  • Li Jing-Rebecca
  • Grebenkov Denis S
  • Poupon Cyril
  • Le Bihan Denis
  , 2012. The convergence of the long-time apparent diffusion tensor under realistic DMR scanning conditions to the effective diffusion tensor obtained by homogenization theory was considered for a two-compartment model in both isotropic and anisotropic diffusion and general shapes. This gives a computationally efficient approach to get the homogenized diffusion tensor.
• Un ensemble de 4x3 stéréogrammes d'un agrandissement d'un ensemble de Mandelbrot dans l'ensemble des pseudo-octonions (un 'Mandelbulb')
  
  • Colonna Jean-François
  , 2012. A set of 4x3 stereograms of a close-up on a pseudo-octonionic Mandelbrot set (a 'Mandelbulb') (Un ensemble de 4x3 stéréogrammes d'un agrandissement d'un ensemble de Mandelbrot dans l'ensemble des pseudo-octonions (un 'Mandelbulb'))
• Agrandissement d'un ensemble de Mandelbrot dans l'ensemble des pseudo-octonions (un 'Mandelbulb')
  
  • Colonna Jean-François
  , 2012. Close-up on a pseudo-octonionic Mandelbrot set (a 'Mandelbulb') (Agrandissement d'un ensemble de Mandelbrot dans l'ensemble des pseudo-octonions (un 'Mandelbulb'))
• Un ensemble de 4x3 stéréogrammes d'une structure fractale tridimensionnelle -la 'mousse' de l'espace-temps ?
  
  • Colonna Jean-François
  , 2012. A set of 4x3 stereograms of a tridimensional fractal structure -the space-time foam ?- (Un ensemble de 4x3 stéréogrammes d'une structure fractale tridimensionnelle -la 'mousse' de l'espace-temps ?-)
• Un tore fractal
  
  • Colonna Jean-François
  , 2012. A fractal torus (Un tore fractal)
• Un ensemble de 4x3 stéréogrammes d'une sphère fractal
  
  • Colonna Jean-François
  , 2012. A set of 4x3 stereograms of a fractal torus (Un ensemble de 4x3 stéréogrammes d'une sphère fractal)
• Energy and regularity dependent stability estimates for the Gel'fand inverse problem in multidimensions
  
  • Isaev Mikhail
  • Novikov Roman
  Journal of Inverse and Ill-posed Problems, De Gruyter, 2012, 20 (3), pp.313-325. We prove new global Hölder-logarithmic stability estimates for the Gel'fand inverse problem at fixed energy in dimension $d\geq 3$. Our estimates are given in uniform norm for coefficient difference and related stability efficiently increases with increasing energy and/or coefficient regularity. Comparisons with preceeding results in this direction are given.