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

Bruno Levy. ( 2016 )
in: 2016 RING Meeting, ASGA

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.

Download / Links

BibTeX Reference

@INPROCEEDINGS{,
    author = { Levy, Bruno },
     title = { A Newton algorithm for semi-discrete optimal transport in 3D },
 booktitle = { 2016 RING Meeting },
      year = { 2016 },
 publisher = { ASGA },
  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. }
}