A multigrid scheme for 3D Monge–Ampère equationsFootnote^*

* The work described in this article is a result of a collaboration made possible by the IMA's New Directions Short Course on ‘Topics on Control Theory: Optimal Mass Transportation’ in June, 2014.

References

• G. Barles and P.E. Souganidis, Convergence of approximation schemes for fully nonlinear second order equations, Asymptot. Anal. 4(3) (1991), pp. 271–283.
   Google Scholar
• J.-D. Benamou, B.D. Froese, and A.M. Oberman, Two numerical methods for the elliptic Monge-Ampère equation, M2AN Math. Model. Numer. Anal. 44(4) (2010), pp. 737–758. doi: 10.1051/m2an/2010017
   Web of Science ®Google Scholar
• J.-D. Benamou, B.D. Froese, and A.M. Oberman, Numerical solution of the optimal transportation problem using the Monge-Ampère equation, J. Comput. Phys. 260 (2014), pp. 107–126. doi: 10.1016/j.jcp.2013.12.015
   Web of Science ®Google Scholar
• A. Brandt, Multi-level adaptive solutions to boundary-value problems, Math. Comp. 31(138) (1977), pp. 333–390. doi: 10.1090/S0025-5718-1977-0431719-X
   Web of Science ®Google Scholar
• A. Brandt and O. Livne, Multigrid Techniques: 1984 Guide with Applications to Fluid Dynamics, Revised Edition, Classics in Applied Mathematics, SIAM, Philadelphia, PA, 2011.
   Google Scholar
• S.C. Brenner, T. Gudi, M. Neilan, and L.-y. Sung, C0 penalty methods for the fully nonlinear Monge-Ampère equation, Math. Comp. 80(276) (2011), pp. 1979–1995. doi: 10.1090/S0025-5718-2011-02487-7
   Web of Science ®Google Scholar
• S.C. Brenner and M. Neilan, Finite element approximations of the three dimensional Monge-Ampère equation, ESAIM Math. Model. Numer. Anal. 46(5) (2012), pp. 979–1001. doi: 10.1051/m2an/2011067
   Web of Science ®Google Scholar
• W.L. Briggs, V.E. Henson, and S.F. McCormick, A Multigrid Tutorial, SIAM, Philadelphia, PA, 2000.
   Google Scholar
• L. Caffarelli, L. Nirenberg, and J. Spruck, The Dirichlet problem for nonlinear second-order elliptic equations. I. Monge-Ampère equation, Comm. Pure Appl. Math. 37(3) (1984), pp. 369–402. doi: 10.1002/cpa.3160370306
   Web of Science ®Google Scholar
• L. Chacón, G.L. Delzanno, and J.M. Finn, Robust, multidimensional mesh-motion based on Monge-Kantorovich equidistribution, J. Comput. Phys. 230(1) (2011), pp. 87–103. doi: 10.1016/j.jcp.2010.09.013
   Web of Science ®Google Scholar
• Y. Chen and S.R. Fulton, An adaptive continuation-multigrid method for the balanced vortex model, J. Comput. Phys. 229(6) (2010), pp. 2236–2248. doi: 10.1016/j.jcp.2009.11.032
   Web of Science ®Google Scholar
• N. Chumchob and K. Chen, A robust multigrid approach for variational image registration models, J. Comput. Appl. Math. 236(5) (2011), pp. 653–674. doi: 10.1016/j.cam.2011.06.026
   Web of Science ®Google Scholar
• G. L. Delzanno, L. Chacón, J.M. Finn, Y. Chung, and G. Lapenta, An optimal robust equidistribution method for two-dimensional grid adaptation based on Monge–Kantorovich optimization, J. Comput. Phys. 227(23) (2008), pp. 9841–9864. doi: 10.1016/j.jcp.2008.07.020
   Web of Science ®Google Scholar
• B. Engquist and B.D. Froese, Application of the Wasserstein metric to seismic signals, Commun. Math. Sci. 12(5) (2014), pp. 979–988. doi: 10.4310/CMS.2014.v12.n5.a7
   Web of Science ®Google Scholar
• X. Feng, R. Glowinski, and M. Neilan, Recent developments in numerical methods for fully nonlinear second order partial differential equations, SIAM Rev. 55(2) (2013), pp. 205–267. doi: 10.1137/110825960
   Web of Science ®Google Scholar
• X. Feng and M. Neilan, Mixed finite element methods for the fully nonlinear Monge-Ampère equation based on the vanishing moment method, SIAM J. Numer. Anal. 47(2) (2009), pp. 1226–1250. doi: 10.1137/070710378
   Web of Science ®Google Scholar
• X. Feng and M. Neilan, Vanishing moment method and moment solutions for fully nonlinear second order partial differential equations, J. Sci. Comput. 38(1) (2009), pp. 74–98. doi: 10.1007/s10915-008-9221-9
   Web of Science ®Google Scholar
• B.D. Froese and A.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(4) (2011), pp. 1692–1714. doi: 10.1137/100803092
   Web of Science ®Google Scholar
• B.D. Froese and A.M. Oberman, Fast finite difference solvers for singular solutions of the elliptic Monge-Ampère equation, J. Comput. Phys. 230(3) (2011), pp. 818–834. doi: 10.1016/j.jcp.2010.10.020
   Web of Science ®Google Scholar
• B.D. Froese and A.M. Oberman, Convergent filtered schemes for the Monge-Ampère partial differential equation, SIAM J. Numer. Anal. 51(1) (2013), pp. 423–444. doi: 10.1137/120875065
   Web of Science ®Google Scholar
• M.M. Gupta and J. Zhang, High accuracy multigrid solution of the 3D convection-diffusion equation, Appl. Math. Comput. 113(2–3) (2000), pp. 249–274.
   Web of Science ®Google Scholar
• E. Haber and J. Modersitzki, Image registration with guaranteed displacement regularity, Int. J. Comput. Vis. 71(3) (2007), pp. 361–372. doi: 10.1007/s11263-006-8984-4
   Web of Science ®Google Scholar
• E. Haber, T. Rehman, and A. Tannenbaum, An efficient numerical method for the solution of the L2 optimal mass transfer problem, SIAM J. Sci. Comput. 32(1) (2010), pp. 197–211. doi: 10.1137/080730238
   PubMed Web of Science ®Google Scholar
• S. Haker, L. Zhu, A. Tannenbaum, and S. Angenent, Optimal mass transport for registration and warping, Int. J. Comput. Vision 60(3) (2004), pp. 225–240. doi: 10.1023/B:VISI.0000036836.66311.97
   Web of Science ®Google Scholar
• R. LeVeque, Finite Difference Methods for Ordinary and Partial Differential Equations: Steady-state and Time-Dependent Problems, SIAM, Philadelphia, PA, 2007.
   Google Scholar
• G. Loeper and F. Rapetti, Numerical solution of the Monge-Ampère equation by a Newton's algorithm, C. R. Math. Acad. Sci. Paris 340(4) (2005), pp. 319–324. doi: 10.1016/j.crma.2004.12.018
   Web of Science ®Google Scholar
• T.S. Motzkin and W. Wasow, On the approximation of linear elliptic differential equations by difference equations with positive coefficients, J. Math. Phys. 31(1–4) (1952), pp. 253–259. doi: 10.1002/sapm1952311253
   Web of Science ®Google Scholar
• M. Neilan, Quadratic finite element approximations of the Monge-Ampère equation, J. Sci. Comput. 54(1) (2013), pp. 200–226. doi: 10.1007/s10915-012-9617-4
   Web of Science ®Google Scholar
• A.M. Oberman, Wide stencil finite difference schemes for the elliptic Monge-Ampère equation and functions of the eigenvalues of the Hessian, Discrete Contin. Dyn. Syst. Ser. B 10(1) (2008), pp. 221–238. doi: 10.3934/dcdsb.2008.10.221
   Web of Science ®Google Scholar
• J.M. Ortega and W.C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, SIAM, Philadelphia, PA, 2000.
   Google Scholar
• C.R. Prins, J.H.M. Ten Thije Boonkkamp, J. van Roosmalen, W.L. Ijzerman, and T.W. Tukker, A Monge-Ampère-solver for free-form reflector design, SIAM J. Sci. Comput. 36(3) (2014), pp. B640–B660. doi: 10.1137/130938876
   Web of Science ®Google Scholar
• T.U. Rehman, E. Haber, G. Pryor, J. Melonakos, and A. Tannenbaum, 3d nonrigid registration via optimal mass transport on the GPU, Med. Image Anal. 13(6) (2009), pp. 931–940. doi: 10.1016/j.media.2008.10.008
   PubMed Web of Science ®Google Scholar
• Y. Saad, Iterative Methods for Sparse Linear Systems, SIAM, Philadelphia, PA, 2003.
   Google Scholar
• L.-P. Saumier, M. Agueh, and B. Khouider, An efficient numerical algorithm for the L2 optimal transport problem with periodic densities, IMA J. Appl. Math. 80(1) (2015), pp. 135–157. doi: 10.1093/imamat/hxt032
   Web of Science ®Google Scholar
• A.K. Soin, Multigrid for elliptic Monge-Ampère equation, Master's thesis, University of Waterloo, Waterloo, Ontario, Canada, 2011.
   Google Scholar
• M.M. Sulman, J.F. Williams, and R.D. Russell, An efficient approach for the numerical solution of the Monge-Ampère equation, Appl. Numer. Math. 61(3) (2011), pp. 298–307. doi: 10.1016/j.apnum.2010.10.006
   Web of Science ®Google Scholar
• E. Tadmor, A review of numerical methods for nonlinear partial differential equations, Bull. Amer. Math. Soc. (N.S.) 49(4) (2012), pp. 507–554. doi: 10.1090/S0273-0979-2012-01379-4
   Web of Science ®Google Scholar
• U. Trottenberg, C.W. Oosterlee, and A. Schüller, Multigrid, Academic Press Inc., San Diego, CA, 2001.
   Google Scholar
• N.S. Trudinger and X.-J. Wang, The Monge-Ampere equation and its geometric applications, Handbook Geom. Anal. 1 (2008), pp. 467–524.
   Google Scholar
• J. Zhang, Fast and high accuracy multigrid solution of the three-dimensional Poisson equation, J. Comput. Phys. 143(2) (1998), pp. 449–461. doi: 10.1006/jcph.1998.5982
   Web of Science ®Google Scholar
• V. Zheligovsky, O. Podvigina, and U. Frisch, The Monge-Ampère equation: Various forms and numerical solution, J. Comput. Phys. 229(13) (2010), pp. 5043–5061. doi: 10.1016/j.jcp.2010.03.025
   Web of Science ®Google Scholar