Journal Article

Numerical Solution of Monge–Kantorovich Equations via a Dynamic Formulation

Facca, Enrico, Cardin, Franco, Putti, Mario, Daneri, Sara

2020

Overview

We extend our previous work on a biologically inspired dynamic Monge–Kantorovich model (Facca et al. in SIAM J Appl Math 78:651–676, 2018) and propose it as an effective tool for the numerical solution of the L 1 -PDE based optimal transportation model. We first introduce a new Lyapunov-candidate functional and show that its derivative along the solution trajectory is strictly negative. Moreover, we are able to show that this functional admits the optimal transport density as a unique minimizer, providing further support to the conjecture that our dynamic model is time-asymptotically equivalent to the Monge–Kantorovich equations governing L 1 optimal transport. Remarkably, this newly proposed Lyapunov-candidate functional can be effectively used to calculate the Wasserstein-1 (or earth mover’s) distance between two measures. We numerically solve these equations via a simple approach based on standard forward Euler time stepping and linear Galerkin finite element. The accuracy and robustness of the proposed solver is verified on a number of test problems of mixed complexity also in comparison with other approaches proposed in the literature. Numerical results show that the proposed scheme is very efficient and accurate for the calculation the Wasserstein-1 distances.

• Publisher: Springer US,Springer Nature B.V
• Subject: Algorithms / Approximation / Computational Mathematics and Numerical Analysis / Dynamic models / Linear algebra / Mathematical and Computational Engineering / Mathematical and Computational Physics / Mathematics / Mathematics and Statistics / Robustness (mathematics) / Theoretical