Large-scale semi-discrete optimal transport with distributed Voronoi diagrams.
Saved in:
| 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 |
| FullText | Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 188575750 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Large-scale semi-discrete optimal transport with distributed Voronoi diagrams. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Lévy%2C+Bruno%22">Lévy, Bruno</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> bruno.levy@inria.fr</i><br /><searchLink fieldCode="AR" term="%22Ray%2C+Nicolas%22">Ray, Nicolas</searchLink><relatesTo>2</relatesTo> (AUTHOR)<i> nicolas.ray@inria.fr</i><br /><searchLink fieldCode="AR" term="%22Mérigot%2C+Quentin%22">Mérigot, Quentin</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> quentin.merigot@universite-paris-saclay.fr</i><br /><searchLink fieldCode="AR" term="%22Leclerc%2C+Hugo%22">Leclerc, Hugo</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> hugo.leclerc@universite-paris-saclay.fr</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Journal+of+Computational+Physics%22">Journal of Computational Physics</searchLink>. Dec2025, Vol. 542, pN.PAG-N.PAG. 1p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Distributed+computing%22">Distributed computing</searchLink><br /><searchLink fieldCode="DE" term="%22Fluid+dynamics%22">Fluid dynamics</searchLink><br /><searchLink fieldCode="DE" term="%22Voronoi+polygons%22">Voronoi polygons</searchLink><br /><searchLink fieldCode="DE" term="%22Assignment+problems+%28Programming%29%22">Assignment problems (Programming)</searchLink><br /><searchLink fieldCode="DE" term="%22Physical+cosmology%22">Physical cosmology</searchLink><br /><searchLink fieldCode="DE" term="%22Numerical+analysis%22">Numerical analysis</searchLink><br /><searchLink fieldCode="DE" term="%22Scalability%22">Scalability</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: • 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] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>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.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=188575750 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1016/j.jcp.2025.114374 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 1 StartPage: N.PAG Subjects: – SubjectFull: Distributed computing Type: general – SubjectFull: Fluid dynamics Type: general – SubjectFull: Voronoi polygons Type: general – SubjectFull: Assignment problems (Programming) Type: general – SubjectFull: Physical cosmology Type: general – SubjectFull: Numerical analysis Type: general – SubjectFull: Scalability Type: general Titles: – TitleFull: Large-scale semi-discrete optimal transport with distributed Voronoi diagrams. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Lévy, Bruno – PersonEntity: Name: NameFull: Ray, Nicolas – PersonEntity: Name: NameFull: Mérigot, Quentin – PersonEntity: Name: NameFull: Leclerc, Hugo IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 12 Text: Dec2025 Type: published Y: 2025 Identifiers: – Type: issn-print Value: 00219991 Numbering: – Type: volume Value: 542 Titles: – TitleFull: Journal of Computational Physics Type: main |
| ResultId | 1 |
