Given two probability measures and a transportation cost, the optimal transport problem asks to find the most cost efficient way to transport one measure to the other.  Since its introduction in 1781 by Gaspard Monge, the optimal transport problem has found applications in logistics, economics, physics, PDEs, and more recently data science.  However, despite sustained attention from the numerics community, solving optimal transport problems has been a notoriously difficult task.  

In this talk I will introduce the back-and-forth method, a new algorithm to efficiently solve the optimal transportation problem for a general class of strictly convex transportation costs.  Given two probability measures supported on a discrete grid with n points, the method computes the optimal map in O(n log(n)) operations using O(n) storage space.   As a result, the method can compute highly accurate solutions to optimal transportation problems on spatial grids as large as 4096 x 4096 and 384 x 384 x 384 in a matter of minutes.  If time permits, I will demonstrate an extension of the algorithm to the simulation of a class of gradient flows.

This talk is joint work with Flavien Leger.