Aller au contenu  Aller au menu  Aller à la recherche

Bienvenue - Laboratoire Jacques-Louis Lions

Partenariats

CNRS

UPMC

UdP
Print this page |
5 postes ATER en mathématiques à Sorbonne Université
date limite le 5 avril à 16h
Détails ici

Chiffres-clé

Chiffres clefs

189 personnes travaillent au LJLL

90 permanents

82 chercheurs et enseignants-chercheurs permanents

8 ingénieurs, techniciens et personnels administratifs

99 personnels non permanents

73 doctorants

14 post-doc et ATER

12 émérites et collaborateurs bénévoles

 

Chiffres mars 2019

 

Séminaire du LJLL : B. Levy

23 janvier 2015 — 14h00
Bruno Levy (Inria Nancy Grand Est)
Un algorithme numérique pour le transport optimal semi-discret en 3d
Résumé
 Dans cette présentation, je m’intéresse au problème du calcul numérique du transport optimal L_2 en 3d. Etant données deux mesures de probabilités\mu et \nu supportées par \Omega, le problème consiste à trouver l’application T qui pousse \mu sur \nu et qui minimise le coût de transport \int_\Omega | x - T(x) |^2 d\mu.
 Des solutions numériques efficaces pour ce problème sont susceptibles de faciliter la simulation de certains phénomènes physiques, tels que l’évolution de la densité de matière à large échelle dans l’univers [Frisch et al., Nature 2002, Brenier et al., MNRAS 2003]. Les méthodes numériques utilisées jusqu’à présent optimisent le transport entre deux mesures discrètes (sommes de masses de Dirac) à l’aide d’un algorithme combinatoire, qui passe difficilement à l’échelle au delà de quelques dizaines de milliers de masses de Dirac.
 Dans le cas où \mu a une densité et où \nu est discrète (cas "semi-discret"), par une conséquence directe du théorème de décomposition polaire des champs de vecteurs [Brenier 1990], la pré-image des masses de Dirac par l’application de transport optimal T est une structure bien connue en géométrie algorithmique, à savoir un diagramme de puissance. Les paramètres (poids) de ce diagramme de puissance sont déterminés par le maximum unique d’une fonction concave [Aurenhammer et al., Algorithmica 1998]. Cette caractérisation aboutit naturellement à un algorithme numérique, qui, combiné avec une approche multi-échelle, permet de calculer efficacement le transport optimal dans le plan [Merigot, Computer Graphics Forum 2011] et de l’appliquer à la résolution en 2d d’équations de type Monge-Ampère (Fokker-Planck, dynamique des foules...) [Benamou et al., arXiv:1408.4536].
 Je montre comment adapter cet algorithme en 3d dans le cas où \mu a une densité linéaire par morceaux supportée par un maillage tétraédrique et où\nu est discrète. Le coeur de l’algorithme calcule l’intersection entre un diagramme de puissance et un maillage tétraédrique par propagation simultanée sur les deux maillages. Les cas dégénérés sont traités par des méthodes de calcul en précision arbitraire [Shewchuk, DCG 1997] et par des perturbations symboliques [Edelsbrunner et al., TOG 1990]. L’implantation parallèle de l’algorithme permet de calculer le transport optimal pour des problèmes de l’ordre du million de masses de Dirac sur un ordinateur personnel de configuration standard.
 L’implantation de l’algorithme est disponible à l’adresse
 http://alice.loria.fr/software/geogramNouvelle fenêtre