The boundary method for numerical optimal transport

Applied and Computational Mathematics Seminar
Monday, November 7, 2016 - 2:05pm for 1 hour (actually 50 minutes)
Skiles 005
JD Walsh – GA Tech Mathematics, doctoral candidate
Martin Short
The boundary method is a new algorithm for solving semi-discrete transport problems involving a variety of ground cost functions. By reformulating a transport problem as an optimal coupling problem, one can construct a partition of its continuous space whose boundaries allow accurate determination of the transport map and its associated Wasserstein distance. The boundary method approximates region boundaries using the general auction algorithm, controlling problem size with a multigrid discard approach. This talk describes numerical and mathematical results obtained when the ground cost is a convex combination of lp norms, and shares preliminary work involving other ground cost functions.