Numerical solution of the Optimal Transportation problem using the Monge–Ampère equation
Résumé
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