The ALICE project-team developed the first algorithm to compute semi-discrete optimal transport in 3D
Optimal Transport between a sphere and a 3D shape
The ALICE project-team developed the first algorithm to compute the optimal transport in 3D. This concerns a semi-discrete special case of computing the optimal transport map, between a piecewise linear density and a sum of Dirac masses in 3D. Bruno Lévy, the team manager, explains his work.
Optimal Transport is a domain of mathematics that studies some deformations of space with a minimal cost and subject to certain "preservation" constraints. It has many links with theoretical physics, that let envision the possibility to develop novel numerical simulation algorithm. These new algorithm are expected to be both more efficient and more accurate, by expoiting foundations that are at the intersection between mathematics, physics and computer sciences.
This research topic was initiated by Gaspard Monge during the french revolution. To leverage the right mathematical tools and characterize existence and uniqueness, one had to wait until world war II, for Leonid Kantorovich (Nobel prize of Economy 1975) to discover the theory of duality. Recently, Optimal Transportation has generated renewed interest in the Mathematics research community, under the influence of French mathematicians such as Yann Brenier and Cédric Villani.
Optimal Transport is a consise and elegant mathematical language, well-adapted to express certain laws in physics, such as the least action principle and conservation laws. Moreover, the manipulated mathematical objects are very general, and encompass not only "smooth" ideal objects such as continuous functions, but also less regular objects, such as point sets or meshes manipulated in computer science. This generality makes it possible to directly translate a mathematical description of the physics into a computer language without loosing any good property in translation.
The MOKAPLAN and ALICE teams of Inria are currently developing the efficient numerical algorithm that can be used to compute Optimal Transportation in a computer. They designed recently the very first "semi-discrete" solvers, first in 2D (MOKAPLAN) then in 3D (ALICE). These solvers are envisioned to become the fundamental "building blocs" for a new class of numerical simulation algorithms, with conservation laws and the least action principle hardwired in their "DNA". These two teams currently study applications in comutational fluid dynamics, in optics, in astrophysics and in material sciences. The early numerical experiments let envision a performance acceleration factor of several orders of magnitude.
- A demo of the live algorithm
These articles could interest you:
For more information
The algorithm live !