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

Benamou, Jean-David; Collino, Francis; Mirebeau, Jean-Marie

doi:10.1090/mcom/3080

Monotone and consistent discretization of the Monge-Ampère operator
HTML articles powered by AMS MathViewer

by Jean-David Benamou, Francis Collino and Jean-Marie Mirebeau;

Math. Comp. 85 (2016), 2743-2775

DOI: https://doi.org/10.1090/mcom/3080

Published electronically: March 22, 2016

PDF | Request permission

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

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, DOI 10.1016/j.jcp.2013.12.015
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, DOI 10.1051/m2an:2004034
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, DOI 10.1051/m2an/2011067
Bernard Chazelle, An optimal convex hull algorithm in any fixed dimension, Discrete Comput. Geom. 10 (1993), no. 4, 377–409. MR 1243335, DOI 10.1007/BF02573985
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, DOI 10.1098/rspa.1992.0004
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, DOI 10.1090/S0273-0979-1992-00266-5
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, DOI 10.1007/s10851-013-0446-3
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, DOI 10.1137/110825960
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, DOI 10.1137/100803092
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, DOI 10.1137/120875065
Brittany Dawn Froese, Numerical Methods for the Elliptic Monge-Ampere Equation and Optimal Transport, ProQuest LLC, Ann Arbor, MI, 2012. Thesis (Ph.D.)–Simon Fraser University (Canada). MR 3218235
Cristian E. Gutiérrez, The Monge-Ampère equation, Progress in Nonlinear Differential Equations and their Applications, vol. 44, Birkhäuser Boston, Inc., Boston, MA, 2001. MR 1829162, DOI 10.1007/978-1-4612-0195-3
Maciej Kocan, Approximation of viscosity solutions of elliptic partial differential equations on minimal grids, Numer. Math. 72 (1995), no. 1, 73–92. MR 1359708, DOI 10.1007/s002110050160
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, DOI 10.1137/0729008
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 (English, with English and French summaries). MR 2121899, DOI 10.1016/j.crma.2004.12.018
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
Jean-Marie Mirebeau, Efficient fast marching with Finsler metrics, Numer. Math. 126 (2014), no. 3, 515–557. MR 3164145, DOI 10.1007/s00211-013-0571-3
Jean-Marie Mirebeau, Adaptive, Anisotropic and Hierarchical Cones of Convex functions, preprint (2014).
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, DOI 10.1137/120861667
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. MR 2218974, DOI 10.1137/S0036142903435235
Adam M. Oberman, A numerical method for variational problems with convexity constraints, SIAM J. Sci. Comput. 35 (2013), no. 1, A378–A396. MR 3033053, DOI 10.1137/120869973
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, DOI 10.1007/BF01396762
Eduard Selling, Ueber die binären und ternären quadratischen Formen, J. Reine Angew. Math. 77 (1874), 143–229 (German). MR 1579602, DOI 10.1515/crll.1874.77.143
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, DOI 10.1515/crll.1997.487.115