A Newton algorithm for semi-discrete optimal transport in 3D

@inproceedings{RUNKJRM70,
 abstract = { In this article, I am proposing an efficient algorithm for efficiently computing a certain form
of optimal transport in 3D. Optimal transport is concerned with computing certain applications
that “morph” an input “source” function (or probability measure) to a “target” function (or prob-
ability measure) with the same integral, while minimizing a certain cost and satisfying a “mass
preservation” constraint. I am interested in a certain form of the problem, where the source is a
piecewise linear function and the target is a sum of Dirac masses (semi-discrete optimal transport).
As compared to what I presented last year (2015) at the Gocad/Ring Meeting, I am replacing the
quasi-Newton algorithm (BFGS) with a full Newton algorithm. This gains in the best cases up to
two orders of magnitude in terms of speed. This requires computing the second order derivatives
of the objective function, for which I give explicit formulas as well as an efficient algorithm.
With the recent applications of optimal transport (in computer graphics, data analysis, mete-
orology, astrophysics . . . ) and the lack of efficient 3D solvers, it has a huge potential impact. On
a more general perspective, conservation of mass is a natural constraint in physics, and there is
no easy computational way of enforcing it. By controlling the volume of the cells of a mesh and
solving a form of the Monge-Amp`ere equation, this solver will fill this gap in the “scientific com-
puting toolbox”. Thus, I foresee this type of solver as a corner stone for a new family of numerical
methods. },
 author = { Levy, Bruno },
 booktitle = { 2016 RING Meeting },
 publisher = { ASGA },
 title = { A Newton algorithm for semi-discrete optimal transport in 3D },
 year = { 2016 }
}