View in EDS

Large-scale semi-discrete optimal transport with distributed Voronoi diagrams.

Saved in:
Bibliographic Details
Title: Large-scale semi-discrete optimal transport with distributed Voronoi diagrams.
Authors: Lévy, Bruno1 (AUTHOR) bruno.levy@inria.fr, Ray, Nicolas2 (AUTHOR) nicolas.ray@inria.fr, Mérigot, Quentin1 (AUTHOR) quentin.merigot@universite-paris-saclay.fr, Leclerc, Hugo1 (AUTHOR) hugo.leclerc@universite-paris-saclay.fr
Source: Journal of Computational Physics. Dec2025, Vol. 542, pN.PAG-N.PAG. 1p.
Subjects: Distributed computing, Fluid dynamics, Voronoi polygons, Assignment problems (Programming), Physical cosmology, Numerical analysis, Scalability
Abstract: • Optimal transport has important applications in cosmology and fluid dynamics. • Semi-discrete optimal transport is robust to huge variations of density (5 orders of magnitude). • Semi-discrete optimal transport can be made scalable to problems of gigantic scale (10 8 to 10 1 0 points). [Display omitted] In this article, we propose a numerical method to solve semi-discrete optimal transport problems for gigantic pointsets (10 8 points and more). By pushing the limits by several orders of magnitude, it opens the path to new applications in cosmology, fluid simulation and data science to name but a few. The method is based on a new algorithm that computes (generalized) Voronoi diagrams in parallel and in a distributed way. First we make the simple observation that the cells defined by a subgraph of the Delaunay graph contain the Voronoi cells, and that one can deduce the missing edges from the intersections between those cells. Based on this observation, we introduce the Distributed Voronoi Diagram algorithm (DVD) that can be used on a cluster and that exchanges vertices between the nodes as need be. We also report early experimental results, demonstrating that the DVD algorithm has the potential to solve some giga-scale semi-discrete optimal transport problems encountered in computational cosmology. [ABSTRACT FROM AUTHOR]
Copyright of Journal of Computational Physics is the property of Academic Press Inc. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
Description
Abstract:• Optimal transport has important applications in cosmology and fluid dynamics. • Semi-discrete optimal transport is robust to huge variations of density (5 orders of magnitude). • Semi-discrete optimal transport can be made scalable to problems of gigantic scale (10 8 to 10 1 0 points). [Display omitted] In this article, we propose a numerical method to solve semi-discrete optimal transport problems for gigantic pointsets (10 8 points and more). By pushing the limits by several orders of magnitude, it opens the path to new applications in cosmology, fluid simulation and data science to name but a few. The method is based on a new algorithm that computes (generalized) Voronoi diagrams in parallel and in a distributed way. First we make the simple observation that the cells defined by a subgraph of the Delaunay graph contain the Voronoi cells, and that one can deduce the missing edges from the intersections between those cells. Based on this observation, we introduce the Distributed Voronoi Diagram algorithm (DVD) that can be used on a cluster and that exchanges vertices between the nodes as need be. We also report early experimental results, demonstrating that the DVD algorithm has the potential to solve some giga-scale semi-discrete optimal transport problems encountered in computational cosmology. [ABSTRACT FROM AUTHOR]
ISSN:00219991
DOI:10.1016/j.jcp.2025.114374