Optimisation
À la recherche du transport optimal
Date:
Mis à jour le 07/11/2024
Comment déplacer de la matière en minimisant l’effort déployé ? Cette question est au cœur des recherches de ParMA, nouvelle équipe-projet au Centre Inria de Saclay, spécialisée dans le transport optimal. A la suite de Gaspard Monge, les récents travaux du mathématicien Yann Brenier améliorent la compréhension des mouvements de matière. Ce qui ouvre la voie à de nouvelles applications dans de multiples domaines comme la cosmologie, la chimie quantique, la mécanique des fluides.
À première vue, l’image ci-dessus ressemble à un feu d’artifices, mais en réalité, c’est une carte. Elle représente le chemin parcouru par les galaxies dans le cosmos depuis 13,8 milliards d’années. Cette cartographie d’un genre nouveau, l’un des projets de recherche phare de l’équipe ParMA, va permettre aux astrophysiciens de mieux comprendre la formation de l’univers. Elle est le produit d’une simulation numérique rendue possible par une série d’avancées en mathématiques et en algorithmique.
“Nous sommes une équipe de mathématiques appliquées basée sur le transport optimal. Nous avons une approche très physique qui s’efforce de minimiser des déplacements ou de minimiser des énergies, résume Thomas Gallouët, responsable de ParMA.
L'équipe-projet ParMA
Cette nouvelle équipe-projet associe le Centre Inria de Saclay, l’Université Paris-Saclay et le CNRS au sein du Laboratoire de Mathématiques d'Orsay, en partenariat avec l’Institut d’Astrophysique de Paris. ParMA se compose de six chercheurs permanents (Yann Brenier, Thomas Gallouët, Bruno Lévy, Bertrand Maury, Quentin Mérigot et Luca Nenna), de deux ingénieurs de recherche (Hugo Leclerc et Sylvain Faure), une post-doctorante (Kathy Eichinger) et huit doctorants.
Cette nouvelle équipe-projet associe le Centre Inria de Saclay, l’Université Paris-Saclay et le CNRS au sein du Laboratoire de Mathématiques d'Orsay, en partenariat avec l’Institut d’Astrophysique de Paris. ParMA se compose de six chercheurs permanents (Yann Brenier, Thomas Gallouët, Bruno Lévy, Bertrand Maury, Quentin Mérigot et Luca Nenna), de deux ingénieurs de recherche (Hugo Leclerc et Sylvain Faure), une post-doctorante (Kathy Eichinger) et huit doctorants.
Des ponts entre mathématiques et physique
Parmi ses membres, l’équipe ParMA compte le mathématicien Yann Brenier. Le théorème qui porte son nom a apporté une contribution majeure au transport optimal. “Yann possède une grande culture scientifique en mathématiques, mais aussi en physique. Il a pu créer des ponts entre ces disciplines témoigne Bruno Lévy chercheur en informatique et membre de ParMA. Il s’est rendu compte que le transport optimal se comportait comme ce l’on appelle en physique les « fluides incompressibles ». » C’est intéressant à deux titres. Premièrement, du point de vue mathématique : en convoquant des outils de la physique, on peut trouver des propriétés, révéler des théorèmes, découvrir de la structure et résoudre numériquement le problème. Deuxièmement, cela met en évidence un lien entre le transport optimal et la physique.
Cette contribution fondamentale fut complétée en 2012 par Quentin Mérigot, dont les travaux permettent d’effectuer les calculs plus rapidement “Il a montré que pour certaines configurations, quand le paysage-destination est un ensemble de points (et non un paysage continu), on pouvait avoir un algorithme de calcul beaucoup plus efficace que tout ce qui existait avant ». Quentin dispose, avec ses co-auteurs Jun Kitagawa et Boris Thibert, d’une preuve mathématique. Cela s’avère très intéressant pour la physique, et notamment pour la cosmologie. A l’échelle où travaille l’équipe, ces points sont les galaxies dispersées dans l’univers.
Résoudre des problèmes de transport optimal de très grande taille
Image
Verbatim
Si on va deux fois plus vite en mathématiques, deux fois plus vite en géométrie, deux fois plus vite en informatique, on va huit fois plus vite au total. Cela nous permet de résoudre des problèmes de transport optimal de très grande taille et de les appliquer pour de vrai à des problèmes de physique théorique.
Auteur
Poste
Chercheur au sein de l’équipe ParMA
Un des défis de l’équipe porte sur le passage à l’échelle. “Les premiers solveurs de Quentin fonctionnaient pour 10 000 ou 100 000 points, indique Thomas Gallouët. Bruno est passé à la 3D et a poussé le curseur jusqu’à 100 millions de points. Maintenant, nous voudrions aller au milliard de points.”
Au sein de l’équipe ParMA, les scientifiques combinent les approches mathématiques et informatiques pour passer à l’échelle. A l'origine, c’est l'analyse mathématique du problème par Yann, puis celle de Quentin, qui ont permis d’aller beaucoup plus vite. Après, pour programmer cela dans un ordinateur, ils ont exploité des considérations géométriques.
Reste ensuite à optimiser toute la machinerie informatique. “Organiser les calculs parallèles, comprendre le fonctionnement bas niveau, etc. On a poussé le curseur au maximum sur toutes ces dimensions répond Bruno Lévy. Et sur toutes ces dimensions, à chaque fois que l’on gagne un facteur multiplicatif, il est multiplicatif par rapport aux autres dimensions. Si on va deux fois plus vite en mathématiques, deux fois plus vite en géométrie, deux fois plus vite en informatique, on va huit fois plus vite au total. Cela nous permet de résoudre des problèmes de transport optimal de très grande taille et de les appliquer pour de vrai à des problèmes de physique théorique, ce dont nous sommes très fiers !”
Mettre ces outils à disposition d’un plus large public
Les équations et les schémas numériques élaborés dans ParMA peuvent concerner beaucoup de domaines de recherche.
Image
Verbatim
Ce sont parfois les mêmes calculs que nous utilisons dans des contextes complètement différents. Notre collègue Luca Nenna étudie des problèmes de chimie quantique avec des approches novatrices. Sylvain Faure et Bertrand Maury, eux, s’intéressent, entre autres, à la mécanique des fluides pour effectuer de la modélisation de mouvements de foules.
Auteur
Poste
Chercheur et Responsable de l’équipe ParMA
“On pourrait se demander pourquoi des thèmes aussi différents se retrouvent dans la même équipe, souligne Bruno Lévy. Cela vient du lien très profond entre le transport optimal et la physique. Cela fait écho au principe de moindre action qui permet de décrire énormément de phénomènes en physique. Cela va des fluides jusqu’à la physique quantique en passant par la relativité générale. En touchant autant de domaines mathématiques, on arrive à dire des choses pertinentes dans beaucoup d’autres disciplines.”
“Ces optimisations permettent des calculs plus puissants, mais elles restent réservées à des gens maîtrisant très bien le code, conclue Thomas Gallouët. Nous souhaiterions parvenir à les diffuser vers un plus large public. Nous voudrions faire en sorte que quelqu’un qui ne soit pas mathématicien puisse les prendre en main et les appliquer à son domaine. Par exemple, dans l’idéal, que des lycéens avec leur professeur de physique puissent les installer eux-mêmes sur leur ordinateur pour effectuer leur propre reconstruction de l’univers.”
L’origine du concept du transport optimal
Le savant Gaspard Monge et son Mémoire sur la théorie des déblais et des remblais, publié en 1781. “Il avait posé le problème, raconte Bruno Lévy. Étant donné les jardins du château de Versailles avec des creux et des bosses comme paysage-source, étant donné les creux et les bosses que l’on voudrait obtenir comme paysage-destination, étant donné que l’on emploie des manœuvres poussant des brouettes, comment faire pour déplacer la terre en se fatiguant le moins possible ? Monge avait identifié certaines propriétés. Par exemple, le fait que les manœuvres ne doivent pas se croiser. Mais il n’avait guère résolu le problème, car celui-ci est très difficile.”
Il faudra attendre 1939 et Leonid Kantorovitch pour trouver une première avancée. Au lieu de transporter un colis à un endroit, le mathématicien considère que l’on peut fractionner ce colis pour amener différentes parties à des endroits différents. Ce déplacement s’organise comme un tableau qui stipule combien de matière est transférée du point A au point B.
“À première vue, cela n’a l’air de rien. Mais ainsi relaxé, le problème devient beaucoup plus simple. Il devient linéaire avec des contraintes linéaires. Monge posait la question : qui va où ? Partant d’un point A, un manœuvre ne pouvait donc se rendre qu’à un seul point B. Avec Kantorovitch, on peut désormais associer différents lieux B au même point A. On peut couper des mottes de terre en deux, d’une certaine manière. Et parfois, il faut le faire. Car la solution mathématique demande de couper des mottes de terre en deux. Mais surtout, le problème présente une solution. Il possède une structure. Le travail en mathématique consiste justement à mettre en évidence de la structure. Or, parfois, elle est cachée. Pour la faire apparaître, il faut alors considérer le problème d’une manière différente. Le fait d’autoriser à couper les mottes de terre permet de résoudre le problème. Quelquefois, finalement, il n’y a pas besoin de couper. Mais si on ne l’avait pas autorisé, on n’aurait jamais trouvé la solution.”
Le savant Gaspard Monge et son Mémoire sur la théorie des déblais et des remblais, publié en 1781. “Il avait posé le problème, raconte Bruno Lévy. Étant donné les jardins du château de Versailles avec des creux et des bosses comme paysage-source, étant donné les creux et les bosses que l’on voudrait obtenir comme paysage-destination, étant donné que l’on emploie des manœuvres poussant des brouettes, comment faire pour déplacer la terre en se fatiguant le moins possible ? Monge avait identifié certaines propriétés. Par exemple, le fait que les manœuvres ne doivent pas se croiser. Mais il n’avait guère résolu le problème, car celui-ci est très difficile.”
Il faudra attendre 1939 et Leonid Kantorovitch pour trouver une première avancée. Au lieu de transporter un colis à un endroit, le mathématicien considère que l’on peut fractionner ce colis pour amener différentes parties à des endroits différents. Ce déplacement s’organise comme un tableau qui stipule combien de matière est transférée du point A au point B.
“À première vue, cela n’a l’air de rien. Mais ainsi relaxé, le problème devient beaucoup plus simple. Il devient linéaire avec des contraintes linéaires. Monge posait la question : qui va où ? Partant d’un point A, un manœuvre ne pouvait donc se rendre qu’à un seul point B. Avec Kantorovitch, on peut désormais associer différents lieux B au même point A. On peut couper des mottes de terre en deux, d’une certaine manière. Et parfois, il faut le faire. Car la solution mathématique demande de couper des mottes de terre en deux. Mais surtout, le problème présente une solution. Il possède une structure. Le travail en mathématique consiste justement à mettre en évidence de la structure. Or, parfois, elle est cachée. Pour la faire apparaître, il faut alors considérer le problème d’une manière différente. Le fait d’autoriser à couper les mottes de terre permet de résoudre le problème. Quelquefois, finalement, il n’y a pas besoin de couper. Mais si on ne l’avait pas autorisé, on n’aurait jamais trouvé la solution.”
À rebours vers le Big Bang
Début 2000, à Nice, le physicien Uriel Frisch et sa post-doctorante Roya Mohayaee tentent de comprendre comment inverser certaines équations et retracer le passé de l'Univers. “Nous sommes arrivés à une équation compliquée, non linéaire, difficile à résoudre, témoigne la cosmologiste. À ce moment-là, le mathématicien Yann Brenier travaillait également à Nice. Lors d'une conversation, au déjeuner, à l'observatoire, nous lui avons demandé s'il avait déjà rencontré cette équation qui nous occupait. Et bien sûr, il a vu l'équation de Monge-Ampère et la relation avec le transport optimal. C’est comme cela que tout a commencé...”
Dans les années 1990, le théorème de Brenier avait permis d’analyser la structure des solutions dans le Transport Optimal. Cette contribution fondamentale fut complétée circa 2012 par Quentin Mérigot, dont les travaux permettent d’effectuer les calculs plus rapidement. Les bases théoriques étant ainsi progressivement posées, il restait encore à construire l’outil informatique.
“Je suis arrivé dans le Transport Optimal en 2015, se souvient Bruno Lévy, chercheur alors au Centre Inria de Nancy. On m’a présenté Roya Mohayaee et son travail sur le chemin des galaxies à l’Institut d’Astrophysique de Paris. Je me suis dit : il faut que l’on arrive à calculer ça ! Donc j’ai utilisé ma ‘trousse à outils d’informaticien’ pour inventer un nouvel algorithme efficace, fonctionnant en 3D pour de très grands ensembles de points, des centaines de millions. Puis peu à peu, j’ai basculé mon centre de gravité vers l’astrophysique.”
Dans un premier temps, ce nouveau tandem s’est employé à valider le principe à l’aide de données synthétiques. “Roya a d’abord construit une simulation numérique d’évolution de l’univers sur 13,8 milliards d’années en partant d’une condition initiale qui ressemble un peu à celle du Big Bang. Pour le solveur numérique, le jeu consistait à revenir en arrière en calculant le point de départ.” Résultat ? “Ça marche ! On parvient à reconstituer le signal.” En l’occurrence, il s’agit d’une onde de pression qui s’est propagée 380 000 ans après le Big Bang. On l’appelle l’oscillation acoustique des baryons.
Ce succès ouvre la voie à une nouvelle étape. “Refaire tout cela avec des données réelles. Nous utiliserons des cartes du cosmos en 3D issues des observations du Dark Energy Spectroscopic Instrument (DESI) qui positionnent des millions de galaxies sur des milliards d’années lumière.”
Là, les choses se compliquent... “C’est difficile parce les données sont bruitées. On ne voit pas toutes les galaxies. Et qui plus est, leur position observée est différente de leur position réelle (la fameuse ’distortion red-shift’). Il faut développer des nouvelles méthodes pour prendre en compte ces difficultés. C’est déjà un défi mathématique, mais nous avons une idée de l’équation qui décrit ce qui se passe, et de la manière de la résoudre. Il faudra ensuite transformer tout cela en algorithme. Nous avons donc encore beaucoup de travail devant nous.” Et c’est ce qui va occuper en grande partie les chercheurs de l’équipe.
Début 2000, à Nice, le physicien Uriel Frisch et sa post-doctorante Roya Mohayaee tentent de comprendre comment inverser certaines équations et retracer le passé de l'Univers. “Nous sommes arrivés à une équation compliquée, non linéaire, difficile à résoudre, témoigne la cosmologiste. À ce moment-là, le mathématicien Yann Brenier travaillait également à Nice. Lors d'une conversation, au déjeuner, à l'observatoire, nous lui avons demandé s'il avait déjà rencontré cette équation qui nous occupait. Et bien sûr, il a vu l'équation de Monge-Ampère et la relation avec le transport optimal. C’est comme cela que tout a commencé...”
Dans les années 1990, le théorème de Brenier avait permis d’analyser la structure des solutions dans le Transport Optimal. Cette contribution fondamentale fut complétée circa 2012 par Quentin Mérigot, dont les travaux permettent d’effectuer les calculs plus rapidement. Les bases théoriques étant ainsi progressivement posées, il restait encore à construire l’outil informatique.
“Je suis arrivé dans le Transport Optimal en 2015, se souvient Bruno Lévy, chercheur alors au Centre Inria de Nancy. On m’a présenté Roya Mohayaee et son travail sur le chemin des galaxies à l’Institut d’Astrophysique de Paris. Je me suis dit : il faut que l’on arrive à calculer ça ! Donc j’ai utilisé ma ‘trousse à outils d’informaticien’ pour inventer un nouvel algorithme efficace, fonctionnant en 3D pour de très grands ensembles de points, des centaines de millions. Puis peu à peu, j’ai basculé mon centre de gravité vers l’astrophysique.”
Dans un premier temps, ce nouveau tandem s’est employé à valider le principe à l’aide de données synthétiques. “Roya a d’abord construit une simulation numérique d’évolution de l’univers sur 13,8 milliards d’années en partant d’une condition initiale qui ressemble un peu à celle du Big Bang. Pour le solveur numérique, le jeu consistait à revenir en arrière en calculant le point de départ.” Résultat ? “Ça marche ! On parvient à reconstituer le signal.” En l’occurrence, il s’agit d’une onde de pression qui s’est propagée 380 000 ans après le Big Bang. On l’appelle l’oscillation acoustique des baryons.
Ce succès ouvre la voie à une nouvelle étape. “Refaire tout cela avec des données réelles. Nous utiliserons des cartes du cosmos en 3D issues des observations du Dark Energy Spectroscopic Instrument (DESI) qui positionnent des millions de galaxies sur des milliards d’années lumière.”
Là, les choses se compliquent... “C’est difficile parce les données sont bruitées. On ne voit pas toutes les galaxies. Et qui plus est, leur position observée est différente de leur position réelle (la fameuse ’distortion red-shift’). Il faut développer des nouvelles méthodes pour prendre en compte ces difficultés. C’est déjà un défi mathématique, mais nous avons une idée de l’équation qui décrit ce qui se passe, et de la manière de la résoudre. Il faudra ensuite transformer tout cela en algorithme. Nous avons donc encore beaucoup de travail devant nous.” Et c’est ce qui va occuper en grande partie les chercheurs de l’équipe.