Numerical Solution of Monge-Kantorovich Equations via a Dynamic Formulation
Enrico Facca, Sara Daneri, Franco Cardin, Mario Putti
Abstract
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 L1-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 L1 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.