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.
- Algorithms structures
- Solvers
– Semi-Discrete
This algorithm computes the solution of the 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)