Numerical methods

The core of both PIR0 and PIR1 consist in solving optimal transport problems, with a quadratic cost function for PIR0, and a logarithmic cost function for PIR1. There are currently three different algorithms available to solve the first and one for the latter. Here are two schematics illustrating the global structure of our applications, with the main mathematical transformations. Below are links to the different solvers documentation.

  1. Algorithms structures
  2. layoutpir0

    layoutpir1

  3. Solvers
  4. Semi-Discrete
    This algorithm computes the solution of the Latex formula optimal transport problem between a piecewise linear density and a finite number of Dirac masses, both located in the Euclidian plane. It is therefor only usable for the PIR0 problem. The density support has to be convex and is numerically represented by a piecewise linear triangulation. For simple densities such as uniform polygons, defined with their convex envelope, the triangulation will have a small number of triangles, making the algorithm very competitive compared to the other ones.

    Far-field reflector problem and intersection of paraboloids
    Pedro Manhães Machado de Castro, Quentin Mérigot, Boris Thibert
    Numerische Mathematik, Springer Verlag, 2015

    Far-Field reflector problem under design constraints
    Far-field reflector problem under design constraints
    Julien André, Dominique Attali, Quentin Mérigot, Boris Thibert
    International Journal of Computational Geometry and Applications, Vol 25, No 2, pp 143-163, 2015

    Intersection of paraboloids and application to Minkowski-type problems
    Pedro Manhães Machado de Castro, Quentin Mérigot, Boris Thibert
    Computational geometry (SoCG’14), 308–317, ACM, New York, 2014.

    A comparison of two dual methods for discrete optimal transport
    Quentin Mérigot
    Geometric science of information, 389–396, Lecture Notes in Computer Science, 8085, Springer, Heidelberg, 2013

    A numerical algorithm for L2 semi-discrete optimal transport in 3D
    Bruno Lévy
    ESAIM: Mathematical Modelling and Numerical Analysis, EDP Sciences, 2015, 49 (6), pp.1693 – 1715

    IPFP
    This algorithm is a discrete algorithm which relies on introducing an entropic regularization to the Kantorovich formulation of the optimal transport problem.
    A COMPLETER
    With this solver, best results are obtained with the same resolution for the source and for the target. It is important to notice that the amount of RAM used by this algorithm is ~source resolution * target resolution. For instance, a simple implementation of the IPFP with two marginals of 40000 diracs would use 13Gb of RAM to store the Gibbs Kernel matrix. An optimized version, using sparse matrices and a refinement approach, has been written and is only available for PIR0. A PIR1 version will soon be available.

    Iterative Bregman projections for regularized transportation problems
    Jean-David Benamou, Guillaume Carlier, Marco Cuturi, Luca Nenna, Gabriel Peyré
    SIAM Journal on Scientific Computing, Society for Industrial and Applied Mathematics, 2015, 2 (37), pp.A1111-A1138

    Scaling Algorithms for Unbalanced Transport Problems
    Lenaic Chizat, Gabriel Peyré, Bernhard Schmitzer, François-Xavier Vialard
    arXiv:1607.05816 [pdf, other]

    Convergence of Entropic Schemes for Optimal Transport and Gradient Flows
    Guillaume Carlier, Vincent Duval, Gabriel Peyré, Bernhard Schmitzer
    arXiv:1512.02783 [pdf, other]

    Finite differences
    A REMPLIR

    Monotone and consistent discretization of the Monge-Ampère operator
    Jean-David Benamou, Francis Collino, Jean-Marie Mirebeau
    Math. Comp. 85 (2016), no. 302, 2743–2775.

    Numerical solution of the optimal transportation problem using the Monge-Ampère equation
    Jean-David Benamou, Brittany D. Froese, Adam M. Oberman
    Journal of Computational Physics, Elsevier, 2014, 260 (1), pp.107-126

    Finite difference discretization of the quadratic Monge Kantorovich problem using minimal convex extensions of Brenier solutions
    Jean-David Benamou, Vincent Duval
    In preparation (2016)