From geodesic extrapolation to a variational BDF2 scheme for Wasserstein gradient flows

Gallouët, Thomas; Natale, Andrea; Todeschi, Gabriele

doi:10.1090/mcom/3951

From geodesic extrapolation to a variational BDF2 scheme for Wasserstein gradient flows
HTML articles powered by AMS MathViewer

by Thomas O. Gallouët, Andrea Natale and Gabriele Todeschi;

Math. Comp. 93 (2024), 2769-2810

DOI: https://doi.org/10.1090/mcom/3951

Published electronically: February 29, 2024

HTML | PDF | Request permission

Abstract:

We introduce a time discretization for Wasserstein gradient flows based on the classical Backward Differentiation Formula of order two. The main building block of the scheme is the notion of geodesic extrapolation in the Wasserstein space, which in general is not uniquely defined. We propose several possible definitions for such an operation, and we prove convergence of the resulting scheme to the limit partial differential equation (PDE), in the case of the Fokker-Planck equation. For a specific choice of extrapolation we also prove a more general result, that is convergence towards Evolutional Variational Inequality flows. Finally, we propose a variational finite volume discretization of the scheme which numerically achieves second order accuracy in both space and time.

References

Luigi Ambrosio, Elia Brué, and Daniele Semola, Lectures on optimal transport, Unitext, vol. 130, Springer, Cham, [2021] ©2021. La Matematica per il 3+2. MR 4294651, DOI 10.1007/978-3-030-72162-6
Luigi Ambrosio, Nicola Gigli, and Giuseppe Savaré, Gradient flows in metric spaces and in the space of probability measures, 2nd ed., Lectures in Mathematics ETH Zürich, Birkhäuser Verlag, Basel, 2008. MR 2401600
B. Ben Moussa and G. T. Kossioris, On the system of Hamilton-Jacobi and transport equations arising in geometrical optics, Comm. Partial Differential Equations 28 (2003), no. 5-6, 1085–1111. MR 1986062, DOI 10.1081/PDE-120021187
Jean-David Benamou and Yann Brenier, A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem, Numer. Math. 84 (2000), no. 3, 375–393. MR 1738163, DOI 10.1007/s002110050002
Jean-David Benamou, Guillaume Carlier, and Maxime Laborde, An augmented Lagrangian approach to Wasserstein gradient flows and applications, Gradient flows: from theory to application, ESAIM Proc. Surveys, vol. 54, EDP Sci., Les Ulis, 2016, pp. 1–17 (English, with English and French summaries). MR 3565819, DOI 10.1051/proc/201654001
A. Blanchet, A gradient flow approach to the Keller-Segel systems, RIMS Kokyuroku’s Lecture Notes, vol. 1837, June 2013, pp. 52–73.
I. A. Bogaevsky, Matter evolution in Burgulence, Preprint, arXiv:math-ph/0407073, 2004.
Yann Brenier and Emmanuel Grenier, Sticky particles and scalar conservation laws, SIAM J. Numer. Anal. 35 (1998), no. 6, 2317–2328. MR 1655848, DOI 10.1137/S0036142997317353
Vincent Calvez and Thomas O. Gallouët, Particle approximation of the one dimensional Keller-Segel equation, stability and rigidity of the blow-up, Discrete Contin. Dyn. Syst. 36 (2016), no. 3, 1175–1208. MR 3431250, DOI 10.3934/dcds.2016.36.1175
Clément Cancès, Thomas O. Gallouët, and Gabriele Todeschi, A variational finite volume scheme for Wasserstein gradient flows, Numer. Math. 146 (2020), no. 3, 437–480. MR 4169480, DOI 10.1007/s00211-020-01153-9
Clément Cancès, Thomas O. Gallouët, and Léonard Monsaingeon, Incompressible immiscible multiphase flows in porous media: a variational approach, Anal. PDE 10 (2017), no. 8, 1845–1876. MR 3694008, DOI 10.2140/apde.2017.10.1845
Clément Cancès, Daniel Matthes, and Flore Nabet, A two-phase two-fluxes degenerate Cahn-Hilliard model as constrained Wasserstein gradient flow, Arch. Ration. Mech. Anal. 233 (2019), no. 2, 837–866. MR 3951694, DOI 10.1007/s00205-019-01369-6
G. Carlier, Remarks on Toland’s duality, convexity constraint and optimal transport, Pac. J. Optim. 4 (2008), no. 3, 423–432. MR 2541254
Guillaume Carlier, Vincent Duval, Gabriel Peyré, and Bernhard Schmitzer, Convergence of entropic schemes for optimal transport and gradient flows, SIAM J. Math. Anal. 49 (2017), no. 2, 1385–1418. MR 3635459, DOI 10.1137/15M1050264
José A. Carrillo, Katy Craig, Li Wang, and Chaozhen Wei, Primal dual methods for Wasserstein gradient flows, Found. Comput. Math. 22 (2022), no. 2, 389–443. MR 4407747, DOI 10.1007/s10208-021-09503-1
Peter Deuflhard and Folkmar Bornemann, Scientific computing with ordinary differential equations, Texts in Applied Mathematics, vol. 42, Springer-Verlag, New York, 2002. Translated from the 1994 German original by Werner C. Rheinboldt. MR 1912409, DOI 10.1007/978-0-387-21582-2
Matthias Erbar, Martin Rumpf, Bernhard Schmitzer, and Stefan Simon, Computation of optimal transport on discrete metric measure spaces, Numer. Math. 144 (2020), no. 1, 157–200. MR 4050090, DOI 10.1007/s00211-019-01077-z
Robert Eymard, Thierry Gallouët, and Raphaèle Herbin, Finite volume methods, Handbook of numerical analysis, Vol. VII, Handb. Numer. Anal., VII, North-Holland, Amsterdam, 2000, pp. 713–1020. MR 1804748, DOI 10.1016/S1570-8659(00)07005-8
E. Facca, G. Todeschi, A. Natale, and M. Benzi, Efficient preconditioners for solving dynamical optimal transport via interior point methods, Preprint, arXiv:2209.00315, 2022.
Dominik Forkert, Jan Maas, and Lorenzo Portinale, Evolutionary $\Gamma$-convergence of entropic gradient flow structures for Fokker-Planck equations in multiple dimensions, SIAM J. Math. Anal. 54 (2022), no. 4, 4297–4333. MR 4452956, DOI 10.1137/21M1410968
Peter Gladbach, Eva Kopfer, and Jan Maas, Scaling limits of discrete optimal transport, SIAM J. Math. Anal. 52 (2020), no. 3, 2759–2802. MR 4110822, DOI 10.1137/19M1243440
Richard Jordan, David Kinderlehrer, and Felix Otto, The variational formulation of the Fokker-Planck equation, SIAM J. Math. Anal. 29 (1998), no. 1, 1–17. MR 1617171, DOI 10.1137/S0036141096303359
Konstantin Khanin and Andrei Sobolevski, Particle dynamics inside shocks in Hamilton-Jacobi equations, Philos. Trans. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci. 368 (2010), no. 1916, 1579–1593. MR 2596482, DOI 10.1098/rsta.2009.0283
Philippe Laurençot and Bogdan-Vasile Matioc, A gradient flow approach to a thin film approximation of the Muskat problem, Calc. Var. Partial Differential Equations 47 (2013), no. 1-2, 319–341. MR 3044141, DOI 10.1007/s00526-012-0520-5
H. Lavenant, S. Claici, E. Chien, and J. Solomon, Dynamical optimal transport on discrete surfaces, ACM Trans. Graph. (TOG) 37 (2018), no. 6, 1–16.
Hugo Leclerc, Quentin Mérigot, Filippo Santambrogio, and Federico Stra, Lagrangian discretization of crowd motion and linear diffusion, SIAM J. Numer. Anal. 58 (2020), no. 4, 2093–2118. MR 4123686, DOI 10.1137/19M1274201
Guillaume Legendre and Gabriel Turinici, Second-order in time schemes for gradient flows in Wasserstein and geodesic metric spaces, C. R. Math. Acad. Sci. Paris 355 (2017), no. 3, 345–353 (English, with English and French summaries). MR 3621265, DOI 10.1016/j.crma.2017.02.001
Daniel Matthes and Horst Osberger, Convergence of a variational Lagrangian scheme for a nonlinear drift diffusion equation, ESAIM Math. Model. Numer. Anal. 48 (2014), no. 3, 697–726. MR 3177862, DOI 10.1051/m2an/2013126
Daniel Matthes and Simon Plazotta, A variational formulation of the BDF2 method for metric gradient flows, ESAIM Math. Model. Numer. Anal. 53 (2019), no. 1, 145–172. MR 3934881, DOI 10.1051/m2an/2018045
Andrea Natale and Gabriele Todeschi, TPFA finite volume approximation of Wasserstein gradient flows, Finite volumes for complex applications IX—methods, theoretical aspects, examples—FVCA 9, Bergen, Norway, June 2020, Springer Proc. Math. Stat., vol. 323, Springer, Cham, [2020] ©2020, pp. 193–201. MR 4111588
Andrea Natale and Gabriele Todeschi, Computation of optimal transport with finite volumes, ESAIM Math. Model. Numer. Anal. 55 (2021), no. 5, 1847–1871. MR 4313377, DOI 10.1051/m2an/2021041
Felix Otto, The geometry of dissipative evolution equations: the porous medium equation, Comm. Partial Differential Equations 26 (2001), no. 1-2, 101–174. MR 1842429, DOI 10.1081/PDE-100002243
Simon Plazotta, A BDF2-approach for the non-linear Fokker-Planck equation, Discrete Contin. Dyn. Syst. 39 (2019), no. 5, 2893–2913. MR 3927537, DOI 10.3934/dcds.2019120
Filippo Santambrogio, Optimal transport for applied mathematicians, Progress in Nonlinear Differential Equations and their Applications, vol. 87, Birkhäuser/Springer, Cham, 2015. Calculus of variations, PDEs, and modeling. MR 3409718, DOI 10.1007/978-3-319-20828-2
Filippo Santambrogio, {Euclidean, metric, and Wasserstein} gradient flows: an overview, Bull. Math. Sci. 7 (2017), no. 1, 87–154. MR 3625852, DOI 10.1007/s13373-017-0101-1
Filippo Santambrogio, Crowd motion and evolution PDEs under density constraints, SMAI 2017—$8^\textrm {e}$ Biennale Française des Mathématiques Appliquées et Industrielles, ESAIM Proc. Surveys, vol. 64, EDP Sci., Les Ulis, 2018, pp. 137–157 (English, with English and French summaries). MR 3883985, DOI 10.1051/proc/201864137
G. Todeschi, Finite volume approximation of optimal transport and Wasserstein gradient flows, Ph.D. Thesis, PSL Université Paris Dauphine, 2021.
Cédric Villani, Topics in optimal transportation, Graduate Studies in Mathematics, vol. 58, American Mathematical Society, Providence, RI, 2003. MR 1964483, DOI 10.1090/gsm/058
Cédric Villani, Optimal transport, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 338, Springer-Verlag, Berlin, 2009. Old and new. MR 2459454, DOI 10.1007/978-3-540-71050-9