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

Jean David Benamou, Brittany D. Froese, Adam M. Oberman

Research output: Contribution to journalArticlepeer-review

92 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)107-126
Number of pages20
JournalJournal of Computational Physics
Volume260
DOIs
StatePublished - Mar 1 2014
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Numerical Analysis
  • Modeling and Simulation
  • Physics and Astronomy (miscellaneous)
  • Physics and Astronomy(all)
  • Computer Science Applications
  • Computational Mathematics
  • Applied Mathematics

Keywords

  • Convexity
  • Finite difference methods
  • Fully nonlinear elliptic partial differential equations
  • Monge Ampère equation
  • Monotone schemes
  • Numerical methods
  • Optimal Transportation
  • Viscosity solutions

Fingerprint

Dive into the research topics of 'Numerical solution of the Optimal Transportation problem using the Monge-Ampère equation'. Together they form a unique fingerprint.

Cite this