Optimization
In search of optimal transportation
Date:
Changed on 23/09/2025
How can matter be moved with minimal effort? This question is at the heart of research carried out by ParMA, a new project team at the Inria Saclay Centre, specialising in optimal transportation. Following in the footsteps of Gaspard Monge, recent work by mathematician Yann Brenier has improved our understanding of the movement of matter. This unlocks new applications in a wide range of fields, including cosmology, quantum chemistry and fluid mechanics.
At first glance, this image looks like a fireworks display, but it is actually a map. It represents the paths travelled by galaxies in the cosmos over the last 13.8 billion years. This new kind of cartography is one of the ParMA team's flagship research projects and will enable astrophysicists to gain better understanding of the formation of the universe. It is the product of a digital simulation made possible by a series of advances in mathematics and algorithms.
"We are an applied mathematics team focused on optimal transportation. We have a very physics-based approach that strives to minimise movements and energy consumption,” says Thomas Gallouët, head of ParMA.
The ParMA project team
This new project team is a joint undertaking involving the Inria Saclay Centre, Paris-Saclay University and the CNRS within the Orsay Mathematics Laboratory, in partnership with the Paris Institute of Astrophysics. ParMA is made up of six permanent researchers (Yann Brenier, Thomas Gallouët, Bruno Lévy, Bertrand Maury, Quentin Mérigot and Luca Nenna), two research engineers (Hugo Leclerc and Sylvain Faure), a postdoctoral researcher (Kathy Eichinger) and eight PhD students.
Building bridges between mathematics and physics
The ParMA team includes mathematician Yann Brenier. The theorem that bears his name represents a major contribution to optimal transportation. "Yann has a strong scientific background in mathematics, but also in physics. He was able to build bridges between these disciplines," says Bruno Lévy, computer science researcher and member of ParMA. “He realised that optimal transportation behaved like what is known in physics as ‘incompressible fluids’.” This is interesting for two reasons. Firstly, from a mathematical point of view: by using physics tools, we can find properties, reveal theorems, discover structure and solve problems numerically. Secondly, it highlights a link between optimal transportation and physics.
This fundamental contribution was rounded off by Quentin Mérigot in 2012, whose work made it possible to perform calculations more quickly: "He showed that for certain configurations, when the destination landscape is a set of points (and not a continuous landscape), the calculation algorithm can be much more efficient than anything that previously existed". Quentin and his co-authors Jun Kitagawa and Boris Thibert produced a mathematical proof. That is very interesting for physics, and in particular for cosmology. For the scale at which the team works, the aforementioned points are galaxies scattered across the universe.
Solving very large optimal transportation problems
Image
Verbatim
If we go twice as fast in maths, twice as fast in geometry and twice as fast in computing, we go eight times faster in total. This allows us to solve very large optimal transportation problems and apply them to real theoretical physics problems.
Auteur
Poste
Researcher from the ParMA team
One of the team's challenges is scaling up. “Quentin's first solvers worked for 10,000 or 100,000 points,” says Thomas Gallouët. “Bruno switched to 3D and pushed it up to 100 million points. Now, we'd like to go for 1 billion points.”
Within the ParMA team, scientists are combining mathematical and computational approaches in order to scale up. Initially, it was Yann's mathematical analysis of the problem, followed by Quentin's, that made it possible to speed everything up. Then, to program it into a computer, they made use of geometric considerations.
The next step is to optimise all the IT equipment: ”Organising parallel calculations, understanding low-level operations, and so on. We pushed the parameters to the maximum for all these areas,” Bruno Lévy says. “And each time we gain a multiplicative factor, it is multiplicative in relation to the other dimensions as well. If we go twice as fast in maths, twice as fast in geometry and twice as fast in computing, we go eight times faster in total. This allows us to solve very large optimal transportation problems and apply them to real theoretical physics problems, which is something we're very proud of!”
Making these tools available to a wider audience
The equations and digital models developed by ParMA are applicable in many fields of research.
Image
Verbatim
Sometimes the same calculations are used in completely different contexts. Our colleague Luca Nenna is studying quantum chemistry problems using innovative approaches. Then there’s Sylvain Faure and Bertrand Maury, who are interested in fluid mechanics, among other things, to model crowd movements.
Auteur
Poste
Researcher and Head of the ParMA team
“You might ask yourself why such different themes end up in the same team," says Bruno Lévy. “It comes from the deep connection between optimal transportation and physics. This echoes the principle of least action, which can be used to describe a great number of phenomena in physics, from fluids to quantum physics and general relativity. By touching on so many areas of mathematics, we can produce research that is relevant for many other disciplines.”
“Such optimisation allows for more powerful calculations, but only for people with a very good command of code," says Thomas Gallouët. “We would like to be able to share it with a wider audience. We would like to ensure that someone who is not a mathematician can use it and apply it to their own field. For example, in an ideal world, high school physics students and their teachers could install it themselves on their computers, to carry out their own reconstruction of the universe."
The origins of the concept of optimal transportation
Scholar Gaspard Monge published his Mémoire sur la théorie des déblais et des remblais ("On the Theory of Cut and Fill") in 1781. “He formulated the problem," says Bruno Lévy. “Given the gardens at the Château de Versailles, with their hills and valleys, as a source landscape, and given the hills and valleys that you would like to achieve as a destination landscape, given that you perform manoeuvres pushing wheelbarrows, how can you shift the soil while causing as little fatigue as possible? Monge identified certain properties. For example, the fact that manoeuvres must not cross each other. But he didn’t really solve the problem, because it's a very difficult one."
It wasn't until 1939 that Leonid Kantorovitch made the first breakthrough. Instead of transporting a parcel to one place, the mathematician considered that the parcel can be split up and different parts taken to different places. This movement is organised as a table that stipulates how much matter is transferred from point A to point B.
"At first glance, it doesn't seem like much. But once loosened up in this way, the problem becomes much simpler. It becomes linear, with linear constraints. Monge asked the question: what goes where? Leaving from point A, a manoeuvre could therefore only go to one point B. With Kantorovich, we can now associate different point Bs with the same point A. You can cut clods of dirt in half, so to speak. And sometimes, you have to. The mathematical solution requires cutting clods of dirt in half. But above all, the problem has a solution. It has a structure. The mathematical work is to show this structure. Sometimes, it's hidden. To reveal it, we need to look at the problem in a different way. Allowing the clods to be cut into parts makes it possible to solve the problem. Sometimes, in the end, there's no need to cut them. But if we hadn't had the possibility to do so, we'd never have found the solution."
Back to the Big Bang
In early 2000, in Nice, physicist Uriel Frisch and his postdoctoral researcher Roya Mohayaee were trying to understand how to invert certain equations and retrace the history of the Universe. “We came up with a complicated, non-linear equation that was difficult to solve," says the cosmologist. “At the time, mathematician Yann Brenier was also working in Nice. During a conversation over lunch at the observatory, we asked him if he had ever come across the equation we were discussing. And of course, he thought of the Monge-Ampère equation and the relationship with optimal transportation. That's how it all started..."
In the 1990s, Brenier's theorem was used to analyse the structure of optimal transportation solutions. This fundamental contribution was rounded off by Quentin Mérigot around 2012, whose work made it possible to perform calculations more quickly. In this way, the theoretical foundations were slowly laid, but the computational tool still had to be created.
"I started to work in optimal transportation in 2015," says researcher Bruno Lévy, who was at the Inria Nancy Centre at the time. I was introduced to Roya Mohayaee and her work on galaxy paths at the Paris Institute of Astrophysics. I said to myself: we've got to find a way to calculate this! So, I used my 'computer scientist's toolkit' to invent a new, efficient algorithm, working in 3D for very large sets of points, hundreds of millions of them. Then, little by little, my centre of gravity shifted to astrophysics."
Initially, the new pair set about validating the principle using synthetic data. "Roya first built a numerical simulation of the evolution of the universe over 13.8 billion years, starting from initial conditions that resemble the Big Bang. For the solver program, the game was to go back and calculate the starting point." And in the end, "it worked! We managed to reconstruct the signal." In this case, it was a pressure wave that travelled 380,000 years after the Big Bang. This is known as baryon acoustic oscillations.
This success paved the way for a new phase: "redoing all this with real data. We will be using 3D maps of the cosmos derived from Dark Energy Spectroscopic Instrument (DESI) observations that position millions of galaxies over billions of light years.”
That's where things get complicated... "It's difficult because the data is noisy. We can't see all the galaxies. What's more, their observed position is different from their actual position (the famous ’redshift-space distortions’). New methods need to be developed to account for these difficulties. It's already a mathematical challenge, but we have an idea for an equation to describe what's going on, and how to solve it. All that then needs to be turned into an algorithm. So, we still have a lot of work ahead of us.” Plenty to keep the team's researchers busy!