MATLAB-SDOT

MATLAB functions for solving semi-discrete optimal transport problems in 3D.

• SDOT_damped_Newton.m computes the optimal transport cost between the Lebesgue measure and a discrete measure on a 3D box with respect to the quadratic cost or the periodic quadratic cost, using the damped Newton method from
  • Jun Kitagawa, Quentin Mérigot, Boris Thibert, Convergence of a Newton algorithm for semi-discrete optimal transport. J. Eur. Math. Soc. 21 (2019), no. 9, pp. 2603–2651.
• SDOT_fminunc.m solves the same problem using the MATLAB function fminunc (slower).
• kantorovich.m computes the Kantorovich function and its gradient and Hessian.

Getting started

To use these MATLAB functions you must first install

• MATLAB-Voro

Examples

See the MATLAB live script Examples_MATLAB_SDOT.mlx and the corresponding PDF file Examples_MATLAB_SDOT.pdf. We have tested the code with target measures with up to 100,000 Dirac masses.

Licence

See LICENCE.md

Software limitations

• The code is limited to 3D (2D code coming soon).
• The source measure is the Lebesgue measure on a cuboid.
• The support of the discrete target measure must be contained in the support of the source measure.
• The transport cost is either the quadratic cost or the periodic quadratic cost.

We plan to address some of these limitations in future updates.

Related software

• pysdot by Quentin Mérigot & Hugo Leclerc
• Geogram by Bruno Lévy, documentation
• sdot by Jocelyn Meyron
• MongeAmpere and PyMongeAmpere by Quentin Mérigot
• Numerical Tours by Gabriel Peyré

Main contributors

• Steve Roper, University of Glasgow
• David Bourne, Heriot-Watt University and the Maxwell Institute for Mathematical Sciences
• Mason Pearce, Heriot-Watt University and the Maxwell Institute for Mathematical Sciences