Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Monotone and consistent discretization of the Monge-Ampère operator


Authors: Jean-David Benamou, Francis Collino and Jean-Marie Mirebeau
Journal: Math. Comp. 85 (2016), 2743-2775
MSC (2010): Primary 35J96, 65N06
DOI: https://doi.org/10.1090/mcom/3080
Published electronically: March 22, 2016
MathSciNet review: 3522969
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We introduce a novel discretization of the Monge-Ampère operator, simultaneously consistent and degenerate elliptic, hence accurate and robust in applications. These properties are achieved by exploiting the arithmetic structure of the discrete domain, assumed to be a two dimensional cartesian grid. The construction of our scheme is simple, but its analysis relies on original tools seldom encountered in numerical analysis, such as the geometry of two dimensional lattices and an arithmetic structure called the Stern-Brocot tree. Numerical experiments illustrate the method's efficiency.


References [Enhancements On Off] (What's this?)

  • [1] Jean-David Benamou, Brittany D. Froese, and Adam M. Oberman, Numerical solution of the optimal transportation problem using the Monge-Ampère equation, J. Comput. Phys. 260 (2014), 107-126. MR 3151832, https://doi.org/10.1016/j.jcp.2013.12.015
  • [2] J. Frédéric Bonnans, Élisabeth Ottenwaelter, and Housnaa Zidani, A fast algorithm for the two dimensional HJB equation of stochastic control, M2AN Math. Model. Numer. Anal. 38 (2004), no. 4, 723-735. MR 2087732 (2005e:93165), https://doi.org/10.1051/m2an:2004034
  • [3] Susanne Cecelia Brenner and Michael Neilan, Finite element approximations of the three dimensional Monge-Ampère equation, ESAIM Math. Model. Numer. Anal. 46 (2012), no. 5, 979-1001. MR 2916369, https://doi.org/10.1051/m2an/2011067
  • [4] Bernard Chazelle, An optimal convex hull algorithm in any fixed dimension, Discrete Comput. Geom. 10 (1993), no. 4, 377-409. MR 1243335 (94h:52026), https://doi.org/10.1007/BF02573985
  • [5] J. H. Conway and N. J. A. Sloane, Low-dimensional lattices. VI. Voronoĭ reduction of three-dimensional lattices, Proc. Roy. Soc. London Ser. A 436 (1992), no. 1896, 55-68. MR 1177121 (93h:11074), https://doi.org/10.1098/rspa.1992.0004
  • [6] Michael G. Crandall, Hitoshi Ishii, and Pierre-Louis Lions, User's guide to viscosity solutions of second order partial differential equations, Bull. Amer. Math. Soc. (N.S.) 27 (1992), no. 1, 1-67. MR 1118699 (92j:35050), https://doi.org/10.1090/S0273-0979-1992-00266-5
  • [7] Jérôme Fehrenbach and Jean-Marie Mirebeau, Sparse non-negative stencils for anisotropic diffusion, J. Math. Imaging Vision 49 (2014), no. 1, 123-147. MR 3180960, https://doi.org/10.1007/s10851-013-0446-3
  • [8] Xiaobing Feng, Roland Glowinski, and Michael Neilan, Recent developments in numerical methods for fully nonlinear second order partial differential equations, SIAM Rev. 55 (2013), no. 2, 205-267. MR 3049920, https://doi.org/10.1137/110825960
  • [9] Brittany D. Froese and Adam M. Oberman, Convergent finite difference solvers for viscosity solutions of the elliptic Monge-Ampère equation in dimensions two and higher, SIAM J. Numer. Anal. 49 (2011), no. 4, 1692-1714. MR 2831067 (2012i:65230), https://doi.org/10.1137/100803092
  • [10] Brittany D. Froese and Adam M. Oberman, Convergent filtered schemes for the Monge-Ampère partial differential equation, SIAM J. Numer. Anal. 51 (2013), no. 1, 423-444. MR 3033017, https://doi.org/10.1137/120875065
  • [11] Brittany Dawn Froese, Numerical Methods for the Elliptic Monge-Ampere Equation and Optimal Transport, ProQuest LLC, Ann Arbor, MI. Thesis (Ph.D.)-Simon Fraser University (Canada), 2012. MR 3218235
  • [12] Cristian E. Gutiérrez, The Monge-Ampère Equation, Progress in Nonlinear Differential Equations and their Applications, 44, Birkhäuser Boston, Inc., Boston, MA, 2001. MR 1829162 (2002e:35075)
  • [13] Maciej Kocan, Approximation of viscosity solutions of elliptic partial differential equations on minimal grids, Numer. Math. 72 (1995), no. 1, 73-92. MR 1359708 (97k:65239), https://doi.org/10.1007/s002110050160
  • [14] Hung Ju Kuo and Neil S. Trudinger, Discrete methods for fully nonlinear elliptic equations, SIAM J. Numer. Anal. 29 (1992), no. 1, 123-135. MR 1149088 (93e:65129), https://doi.org/10.1137/0729008
  • [15] Grégoire Loeper and Francesca Rapetti, Numerical solution of the Monge-Ampère equation by a Newton's algorithm, C. R. Math. Acad. Sci. Paris 340 (2005), no. 4, 319-324. MR 2121899, https://doi.org/10.1016/j.crma.2004.12.018
  • [16] Juan J. Manfredi, Adam M. Oberman, and Alexander P. Sviridov, Nonlinear elliptic partial differential equations and $ p$-harmonic functions on graphs, Differential Integral Equations 28 (2015), no. 1-2, 79-102. MR 3299118
  • [17] Jean-Marie Mirebeau, Efficient fast marching with Finsler metrics, Numer. Math. 126 (2014), no. 3, 515-557. MR 3164145, https://doi.org/10.1007/s00211-013-0571-3
  • [18] Jean-Marie Mirebeau, Adaptive, Anisotropic and Hierarchical Cones of Convex functions, preprint (2014).
  • [19] Jean-Marie Mirebeau, Anisotropic fast-marching on Cartesian grids using lattice basis reduction, SIAM J. Numer. Anal. 52 (2014), no. 4, 1573-1599. MR 3229657, https://doi.org/10.1137/120861667
  • [20] Adam M. Oberman, Convergent difference schemes for degenerate elliptic and parabolic equations: Hamilton-Jacobi equations and free boundary problems, SIAM J. Numer. Anal. 44 (2006), no. 2, 879-895 (electronic). MR 2218974 (2007a:65173), https://doi.org/10.1137/S0036142903435235
  • [21] Adam M. Oberman, A numerical method for variational problems with convexity constraints, SIAM J. Sci. Comput. 35 (2013), no. 1, A378-A396. MR 3033053, https://doi.org/10.1137/120869973
  • [22] V. I. Oliker and L. D. Prussner, On the numerical solution of the equation $ (\partial ^2z/\partial x^2)(\partial ^2z/\partial y^2)-((\partial ^2z/\partial x\partial y))^2=f$ and its discretizations. I, Numer. Math. 54 (1988), no. 3, 271-293. MR 971703 (90h:65164), https://doi.org/10.1007/BF01396762
  • [23] Eduard Selling, Ueber die binären und ternären quadratischen Formen, J. Reine Angew. Math. 77 (1874), 143-229 (German). MR 1579602, https://doi.org/10.1515/crll.1874.77.143
  • [24] John Urbas, On the second boundary value problem for equations of Monge-Ampère type, J. Reine Angew. Math. 487 (1997), 115-124. MR 1454261 (98f:35057), https://doi.org/10.1515/crll.1997.487.115

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 35J96, 65N06

Retrieve articles in all journals with MSC (2010): 35J96, 65N06


Additional Information

Jean-David Benamou
Affiliation: Mokaplan, INRIA, Domaine de Voluceau, BP 105 78153, Le Chesnay Cedex, France
Email: jean-david.benamou@inria.fr

Francis Collino
Affiliation: Mokaplan, INRIA, Domaine de Voluceau BP 105 78153, Le Chesnay Cedex, France

Jean-Marie Mirebeau
Affiliation: Laboratoire de Mathématiques d’Orsay, University Paris-Sud, CNRS, University Paris-Saclay, 91405 Orsay, France
Email: jean-marie.mirebeau@math.u-psud.fr

DOI: https://doi.org/10.1090/mcom/3080
Keywords: Monge-Amp\`ere PDE, monotone finite differences scheme, lattice basis reduction, Stern-Brocot tree
Received by editor(s): September 23, 2014
Received by editor(s) in revised form: May 11, 2015
Published electronically: March 22, 2016
Additional Notes: This work was partially supported by the ANR grant NS-LBR ANR-13-JS01-0003-01
Article copyright: © Copyright 2016 American Mathematical Society

American Mathematical Society