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 -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 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.

Numerical solution of Monge--Kantorovich equations via a dynamic formulation

Daneri Sara;
2020

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 -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 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.
File in questo prodotto:
File Dimensione Formato  
2020_JSciComput_82_Facca.pdf

non disponibili

Tipologia: Versione Editoriale (PDF)
Licenza: Non pubblico
Dimensione 5.26 MB
Formato Adobe PDF
5.26 MB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/20.500.12571/25724
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 10
  • ???jsp.display-item.citation.isi??? 8
social impact