Numerical solution of the optimal transportation problem using the Monge-Ampère equation

DOI10.1016/J.JCP.2013.12.015zbMATH Open1349.65554arXiv1208.4870OpenAlexW2068013644MaRDI QIDQ348765FDOQ348765

Authors: Jean-David Benamou, Brittany D. Froese, Adam Oberman 

Publication date: 5 December 2016

Published in: Journal of Computational Physics (Search for Journal in Brave)

Abstract: A numerical method for the solution of the elliptic Monge-Ampere 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-Ampere 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 (Benamou et al., 2012). In this paper, the algorithm is modified to a simpler compact stencil implementation and details of the implementation are given. Solutions are computed with densities supported on non-convex and disconnected domains. Computational examples demonstrate robust performance on singular solutions and fast computational times.

Full work available at URL: https://arxiv.org/abs/1208.4870

Recommendations

• A least-squares method for optimal transport using the Monge-Ampère equation
• Preface
• Optimal transport via a Monge-Ampère optimization problem
• Minimal convex extensions and finite difference discretisation of the quadratic Monge-Kantorovich problem
• An efficient numerical algorithm for the \(L^{2}\) optimal transport problem with periodic densities

zbMATH Keywords

convexitynumerical methodsoptimal transportationviscosity solutionsfinite difference methodsmonotone schemesfully nonlinear elliptic partial differential equationsMonge Ampère equation

Mathematics Subject Classification ID

Monge-Ampère equations (35J96) Finite difference methods for boundary value problems involving PDEs (65N06)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• The geometry of optimal transportation
• Polar factorization and monotone rearrangement of vector‐valued functions
• A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem
• THE GEOMETRY OF DISSIPATIVE EVOLUTION EQUATIONS: THE POROUS MEDIUM EQUATION
• Numerical simulation of diffusive and aggregation phenomena in nonlinear continuity equations by evolving diffeomorphisms
• Title not available (Why is that?)
• User’s guide to viscosity solutions of second order partial differential equations
• The Variational Formulation of the Fokker--Planck Equation
• Title not available (Why is that?)
• Convergent filtered schemes for the Monge-Ampère partial differential equation
• On the numerical solution of the equation \(\frac{\partial ^ 2z\partial ^ 2z}{\partial x^ 2\partial y^ 2}-(\frac{\partial ^ 2z}{\partial x\partial y})^ 2=f\) and its discretizations. I
• Auction algorithms for network flow problems: A tutorial introduction
• Numerical solution of the Monge--Ampère equation by a Newton's algorithm
• Title not available (Why is that?)
• Variational principles for Minkowski type problems, discrete optimal transport, and discrete Monge-Ampère equations
• Convergent Difference Schemes for Degenerate Elliptic and Parabolic Equations: Hamilton--Jacobi Equations and Free Boundary Problems
• Optimal mass transport for registration and warping
• Numerical solution of the optimal transportation problem using the Monge-Ampère equation
• On the second boundary value problem for equations of Monge-Ampère type.
• Boundary regularity of maps with convex potentials. II
• On the optimal mapping of distributions
• Convergent finite difference solvers for viscosity solutions of the elliptic Monge-Ampère equation in dimensions two and higher
• Title not available (Why is that?)
• An efficient numerical method for the solution of the \(L_2\) optimal mass transfer problem
• Classical solvability in dimension two of the second boundary-value problem associated with the Monge-Ampère operator
• A numerical method for the elliptic Monge-Ampère equation with transport boundary conditions
• \(\mathcal{C}^{0}\) penalty methods for the fully nonlinear Monge-Ampère equation
• Moving Mesh Generation Using the Parabolic Monge–Ampère Equation
• Generalised Lagrangian Solutions for Atmospheric and Oceanic Flows
• Construction of simple, stable, and convergent high order schemes for steady first order Hamilton-Jacobi equations
• Title not available (Why is that?)
• Exact semi-geostrophic flows in an elliptical ocean basin
• A convergent difference scheme for the infinity Laplacian: construction of absolutely minimizing Lipschitz extensions
• Approximation of Parabolic Equations Using the Wasserstein Metric
• An efficient numerical algorithm for the L2 optimal transport problem with periodic densities
• Fast finite difference solvers for singular solutions of the elliptic Monge-Ampère equation
• An optimal robust equidistribution method for two-dimensional grid adaptation based on Monge-Kantorovich optimization

Cited In (75)

• Optimal transportation for electrical impedance tomography
• A fast proximal gradient method and convergence analysis for dynamic mean field planning
• Randomized methods for computing optimal transport without regularization and their convergence analysis
• Efficient and exact multimarginal optimal transport with pairwise costs
• Hybridizable discontinuous Galerkin methods for the two-dimensional Monge-Ampère equation
• Techniques for continuous optimal transport problem
• A Scalable Deep Learning Approach for Solving High-Dimensional Dynamic Optimal Transport
• Fast sinkhorn. II: Collinear triangular matrix and linear time accurate computation of optimal transport
• Machine learning algorithm for the Monge-Ampère equation with transport boundary conditions
• A Newton Algorithm for Semidiscrete Optimal Transport with Storage Fees
• A Continuation Multiple Shooting Method for Wasserstein Geodesic Equation
• Confinement-induced drift in Marangoni-driven transport of surfactant: a Lagrangian perspective
• Adaptive Solution to Two-Dimensional Partial Differential Equations in Curved Domains Using the Monge--Ampére Equation
• A hierarchically low-rank optimal transport dissimilarity measure for structured data
• Primal dual methods for Wasserstein gradient flows
• Data-driven gradient flows
• Monotone discretization of the Monge–Ampère equation of optimal transport
• A Monge-Ampère problem with non-quadratic cost function to compute freeform lens surfaces
• Optimal transport: discretization and algorithms
• A Least-Squares Method for Optimal Transport Using the Monge--Ampère Equation
• On the convergence of augmented Lagrangian method for optimal transport between nonnegative densities
• ON THE CONVERGENCE RATE OF POTENTIALS OF BRENIER MAPS
• A least-squares method for the inverse reflector problem in arbitrary orthogonal coordinates
• A Perturbative Approach to the Parabolic Optimal Transport Problem
• Misfit function for full waveform inversion based on the Wasserstein metric with dynamic formulation
• The boundary method for semi-discrete optimal transport partitions and Wasserstein distance computation
• Minimal convex extensions and finite difference discretisation of the quadratic Monge–Kantorovich problem
• Iterative Bregman Projections for Regularized Transportation Problems
• Monotone and consistent discretization of the Monge-Ampère operator
• Optimal-Transport--Based Mesh Adaptivity on the Plane and Sphere Using Finite Elements
• The scaling and skewness of optimally transported meshes on the sphere
• A particle-evolving method for approximating the optimal transport plan
• A least-squares/relaxation method for the numerical solution of the three-dimensional elliptic Monge-Ampère equation
• Inverse reflector design for a point source and far-field target
• A convergent finite difference method for optimal transport on the sphere
• The geometry of relative arbitrage
• Numerical methods for the hyperbolic Monge-Ampère equation based on the method of characteristics
• Convergence of a Newton algorithm for semi-discrete optimal transport
• Optimal transportation, modelling and numerical simulation
• A convergence framework for optimal transport on the sphere
• Discrete ABP estimate and convergence rates for linear elliptic equations in non-divergence form
• Solution of Optimal Transportation Problems Using a Multigrid Linear Programming Approach
• The Monge-Ampère trajectory correction for semi-Lagrangian schemes
• Three-dimensional transient electromagnetic inversion with optimal transport
• An Algorithm for Optimal Transport between a Simplex Soup and a Point Cloud
• A sparse multiscale algorithm for dense optimal transport
• Error Bounds for Discretized Optimal Transport and Its Reliable Efficient Numerical Solution
• Numerical solution of the optimal transportation problem using the Monge-Ampère equation
• Domain decomposition for entropy regularized optimal transport
• A multigrid scheme for 3D Monge–Ampère equations
• Density-Equalizing Maps for Simply Connected Open Surfaces
• Convergence Rate Estimates for Aleksandrov's Solution to the Monge--Ampère Equation
• A fast approach to optimal transport: the back-and-forth method
• A graph space optimal transport distance as a generalization of L ^p distances: application to a seismic imaging inverse problem
• Convergence Framework for the Second Boundary Value Problem for the Monge--Ampère Equation
• Adaptive finite difference methods for nonlinear elliptic and parabolic partial differential equations with free boundaries
• The Sinkhorn algorithm, parabolic optimal transport and geometric Monge-Ampère equations
• The geometry of r-adaptive meshes generated using optimal transport methods
• A convergent finite difference method for computing minimal Lagrangian graphs
• An Iterative Least-Squares Method for Generated Jacobian Equations in Freeform Optical Design
• Optimal Transport via a Monge--Ampère Optimization Problem
• Vector and Matrix Optimal Mass Transport: Theory, Algorithm, and Applications
• Fast Entropic Regularized Optimal Transport Using Semidiscrete Cost Approximation
• A Discontinuous Galerkin Finite Element Method fOR Uniformly Elliptic Two Dimensional Oblique Boundary-Value Problems
• Numerical methods for fully nonlinear and related PDEs. Abstracts from the workshop held June 27 -- July 3, 2021 (hybrid meeting)
• Minimal Geodesics Along Volume-Preserving Maps, Through Semidiscrete Optimal Transport
• Numerical analysis of strongly nonlinear PDEs
• An efficient algorithm for matrix-valued and vector-valued optimal mass transport
• The second boundary value problem for a discrete Monge-Ampère equation
• A numerical method for the elliptic Monge-Ampère equation with transport boundary conditions
• Independent Nonlinear Component Analysis
• Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems
• Title not available (Why is that?)
• Optimal Transport for Particle Image Velocimetry: Real Data and Postprocessing Algorithms
• Asymptotic analysis of domain decomposition for optimal transport

This page was built for publication: Numerical solution of the optimal transportation problem using the Monge-Ampère equation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q348765)