We introduce a monotone (degenerate elliptic) discretization of the Monge−Ampere operator, on domains discretized on cartesian grids. The scheme is consistent provided the solution hessian condition number is uniformly bounded. Our approach enjoys the simplicity of the Wide Stencil method [B.D. Froese and A.M. Oberman, J. Comput. Phys. 230 (2011) 818–834.], but significantly improves its accuracy using ideas from discretizations of optimal transport based on power diagrams [F. Aurenhammer, F. Hoffmann and B. Aronov, Algorithmica (1998)]. We establish the global convergence of a damped Newton solver for the discrete system of equations. Numerical experiments, in three dimensions, illustrate the scheme efficiency.
DOI : 10.1051/m2an/2015016
Mots clés : Viscosity solutions, monotone numerical scheme, finite difference methods, Monge−Ampere operator
@article{M2AN_2015__49_5_1511_0, author = {Mirebeau, Jean-Marie}, title = {Discretization of the 3d monge\ensuremath{-}ampere operator, between wide stencils and power diagrams}, journal = {ESAIM: Mathematical Modelling and Numerical Analysis }, pages = {1511--1523}, publisher = {EDP-Sciences}, volume = {49}, number = {5}, year = {2015}, doi = {10.1051/m2an/2015016}, mrnumber = {3423234}, zbl = {1330.65161}, language = {en}, url = {http://www.numdam.org/articles/10.1051/m2an/2015016/} }
TY - JOUR AU - Mirebeau, Jean-Marie TI - Discretization of the 3d monge−ampere operator, between wide stencils and power diagrams JO - ESAIM: Mathematical Modelling and Numerical Analysis PY - 2015 SP - 1511 EP - 1523 VL - 49 IS - 5 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/m2an/2015016/ DO - 10.1051/m2an/2015016 LA - en ID - M2AN_2015__49_5_1511_0 ER -
%0 Journal Article %A Mirebeau, Jean-Marie %T Discretization of the 3d monge−ampere operator, between wide stencils and power diagrams %J ESAIM: Mathematical Modelling and Numerical Analysis %D 2015 %P 1511-1523 %V 49 %N 5 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/m2an/2015016/ %R 10.1051/m2an/2015016 %G en %F M2AN_2015__49_5_1511_0
Mirebeau, Jean-Marie. Discretization of the 3d monge−ampere operator, between wide stencils and power diagrams. ESAIM: Mathematical Modelling and Numerical Analysis , Tome 49 (2015) no. 5, pp. 1511-1523. doi : 10.1051/m2an/2015016. http://www.numdam.org/articles/10.1051/m2an/2015016/
Minkowski-type theorems and least-squares clustering. Algorithmica 20 (1998) 61–76. | DOI | MR | Zbl
, and ,J.D. Benamou and B.D. Froese, A viscosity framework for computing Pogorelov solutions of the Monge−Ampere equation. Preprint (2014) . | arXiv
J.-D. Benamou, F. Collino and J.-M. Mirebeau, Monotone and Consistent discretization of the Monge−Ampere operator Preprint (2014) . | arXiv | MR
Finite element approximations of the three dimensional Monge-Ampère equation. ESAIM: M2AN 46 (2012) 979–1001. | DOI | Numdam | MR | Zbl
and ,User’s guide to viscosity solutions of second order partial differential equations. Bull. Amer. Math. Soc. 27 (1992) 1–67. | DOI | MR | Zbl
, and ,Low-Dimensional Lattices. VI. Voronoi Reduction of Three-Dimensional Lattices. Proc. Roy. Soc. A: Math., Phys. Eng. Sci. 436 (1992) 55–68. | MR | Zbl
and ,Globally convergent inexact Newton methods. SIAM J. Optim. 4 (1994) 393–422. | DOI | MR | Zbl
and ,Fast finite difference solvers for singular solutions of the elliptic Monge–Ampère equation. J. Comput. Phys. 230 (2011) 818–834. | DOI | MR | Zbl
and ,Convergent filtered schemes for the Monge–Ampère partial differential equation. SIAM J. Numer. Anal. 51 (2013) 423–444. | DOI | MR | Zbl
and ,C.E. Gutiérrez, The Monge-Ampère Equation. In Progr. Nonlin. Differ. Eqs. Appl. Springer (2001). | MR | Zbl
B. Lévy, A numerical algorithm for semi-discrete optimal transport in 3D. To appear in ESAIM: M2AN (2015). Doi:. | DOI | MR
G. Loeper and F. Rapetti, Numerical solution of the Monge-Ampère equation by a Newton’s algorithm. C. R. Math. Acad. Sci. Paris (2005). | MR | Zbl
A Multiscale approach to optimal transport. Computer Graphics Forum 30 (2011) 1583–1592. | DOI
,Quadratic finite element approximations of the Monge-Ampère equation. J. Sci. Comput. 54 (2012) 200–226. | DOI | MR | Zbl
,Convergent difference schemes for degenerate elliptic and parabolic equations: Hamilton–Jacobi equations and free boundary problems. SIAM J. Numer. Anal. 44 (2006) 879–895. | DOI | MR | Zbl
,On the numerical solution of the equation and its discretizations, I. Numer. Math. 54 (1988) 271–293. | DOI | MR | Zbl
and ,F.P. Preparata and M. Shamos, Computational Geometry. Springer (2012). | Zbl
Cité par Sources :