Bienvenue - Laboratoire Jacques-Louis Lions

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/geogram