Open Collections

Some algorithmic aspects of semi-discrete optimal transport.

Banff International Research Station for Mathematical Innovation and Discovery

In semi-discrete optimal transport, a measure with a density is transported to a sum of Dirac masses. This setting is very well adapted to a computer implementation, because the transport map is determined by a vector of parameters (associated with each Dirac mass) that maximizes a convex function (Kantorovich dual). An efficient numerical solution mechanism requires to carefully orchestrate the interplay of geometry and numerics. On geometry, I will present two algorithms to efficiently compute Laguerre cells, one that uses arbitrary precision predicates, and one that uses standard double-precision arithmetics. On numerical aspects, when implementing a Newton solver (a 3D version of [Kitagawa Merigot Thibert]), the main difficulty is to assemble the Hessian of the objective function, a sparse matrix with a non-zero pattern that changes during the iterations. By exploiting the relation between the Hessian and the 1-skeleton of the Laguerre diagram, it is possible to efficiently construct the Hessian. The algorithm can be used to simulate incompressible Euler fluids [Merigot Gallouet]. I will also show applications of these algorithms in more general settings (transport between surfaces and approximation of general Laguerre diagrams).

Mathematics; Calculus of variations and optimal control; optimization; Statistics; Scientific computing

video/mp4

Author affiliation: Inria Lorainne

2017-10-30

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/63479

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/