Numerical solution of the Optimal Transportation problem using the Monge–Ampère equation

Abstract : A numerical method for the solution of the elliptic Monge–Ampère Partial Differential Equation, with boundary conditions corresponding to the Optimal Transportation (OT) problem, is presented. A local representation of the OT boundary conditions is combined with a finite difference scheme for the Monge–Ampère equation. Newtonʼs method is implemented, leading to a fast solver, comparable to solving the Laplace equation on the same grid several times. Theoretical justification for the method is given by a convergence proof in the companion paper [4]. Solutions are computed with densities supported on non-convex and disconnected domains. Computational examples demonstrate robust performance on singular solutions and fast computational times
Document type :
Journal articles
Complete list of metadatas

https://hal.inria.fr/hal-01115626
Contributor : Brigitte Briot <>
Submitted on : Wednesday, February 11, 2015 - 2:07:00 PM
Last modification on : Monday, February 11, 2019 - 4:40:02 PM

Links full text

Identifiers

Collections

Citation

Jean-David Benamou, Brittany D. Froese, Adam M. Oberman. Numerical solution of the Optimal Transportation problem using the Monge–Ampère equation. Journal of Computational Physics, Elsevier, 2014, 260 (1), pp.107-126. ⟨10.1016/j.jcp.2013.12.015⟩. ⟨hal-01115626⟩

Share

Metrics

Record views

255