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

Bruno Lévy, Nicolas Ray, Quentin Mérigot, Hugo LeclercJournal of Computational Physics 2025 · OpenReview

TL;DR

This paper introduces a novel parallel and distributed algorithm for computing Voronoi diagrams, which is crucial for solving large-scale semi-discrete optimal transport problems. This advancement enables the analysis of massive datasets (billions of points) previously intractable, opening new avenues in fields like computational cosmology.

What Problem Does This Paper Address?

Optimal transport (OT) is a powerful mathematical framework for comparing probability distributions and understanding how to move mass from one distribution to another with minimal cost. While OT has found applications in diverse fields from machine learning to fluid dynamics, solving it for extremely large datasets (10^8 points or more) has been a significant computational bottleneck. Traditional methods struggle with the quadratic complexity of computations or the memory requirements for storing intermediate data structures. This is particularly problematic in areas like computational cosmology, where datasets represent vast numbers of celestial objects and require high resolution for accurate modeling. The paper specifically targets the "semi-discrete" OT problem, where one distribution is continuous (like the early universe density) and the other is a set of discrete points (like galaxy clusters).

Methods

The core innovation lies in a new algorithm for computing generalized Voronoi diagrams in a distributed manner. The authors observe that cells defined by a subgraph of the Delaunay graph contain Voronoi cells, and missing edges can be deduced from intersections between these cells. This leads to the Distributed Voronoi Diagram (DVD) algorithm.

The DVD algorithm works by:

  1. Partitioning: The domain and pointset are divided among multiple computational nodes.
  2. Local Computation: Each node computes a local Delaunay triangulation of its assigned points.
  3. Edge Exchange: Nodes exchange information about points whose Voronoi cells intersect the boundaries of neighboring regions. This is done in two phases to ensure all necessary edges are identified.
  4. Recomputation: Local Delaunay triangulations are updated with the exchanged information, leading to the correct Voronoi diagram.

This distributed approach aims to overcome the memory and computational limitations of traditional methods by distributing the workload and minimizing data exchange between nodes. The paper also leverages concepts from optimal transport theory, including the Kantorovich relaxation and the c-transform, to formulate the problem in a way amenable to numerical solution.

Datasets

The paper does not introduce new benchmark datasets. Instead, it uses a simulated cosmological dataset representative of early universe reconstruction problems. This dataset involves a large number of points (up to 134 million points in the experiments) with highly varying densities, posing a significant challenge for existing methods.

Key Insights and Ideas

  • Voronoi Cells from Delaunay Subgraphs: The key insight is that Voronoi cells can be effectively approximated and refined by considering subgraphs of the Delaunay triangulation. This provides a pathway to efficiently compute Voronoi diagrams.
  • Distributed Approach for Scalability: The paper demonstrates that by carefully managing data exchange between computational nodes, Voronoi diagram computation can be scaled to handle massive datasets, a critical step for applications like large-scale cosmological simulations.
  • Handling Extreme Density Variations: The proposed method is shown to be robust to the extreme variations in point density found in cosmological data, a common challenge for many geometric algorithms.
  • Laguerre Diagrams for OT: The paper connects Voronoi diagrams to Laguerre diagrams, which are essential for solving the semi-discrete optimal transport problem, particularly in the context of cosmological reconstruction.

Key Results

The paper presents experimental results demonstrating the feasibility of their distributed Voronoi diagram algorithm for large-scale semi-discrete optimal transport.

  • Scalability: The DVD algorithm is designed to handle datasets with billions of points, a significant leap from previous capabilities.
  • Performance: For a problem with 134 million points and periodic boundary conditions, the algorithm converged in 34 Newton iterations, taking approximately 1 hour and 15 minutes on a dual-CPU machine.
  • Robustness: The method successfully handles datasets with density variations spanning five orders of magnitude.
  • Computational Breakdown: For the 134M point problem, the timing breakdown shows that linear solves (37.89%) and Laguerre diagram computations (29.8%) are the most time-consuming parts, followed by Hessian assembly (28.1%).

Limitations and Future Work

  • Computational Cost: While distributed, the computation of Laguerre diagrams and linear solves remain the dominant costs. Further optimization in these areas is needed.
  • Data Exchange: The algorithm involves sending points between nodes, which can become a bottleneck if not managed efficiently. The paper notes that in some scenarios, cells might traverse multiple regions, requiring more complex communication patterns.
  • Future Work: The authors plan to scale up to problems with billions of particles, requiring the implementation of distributed linear solvers. They also aim to develop a fully parallel version of the Voronoi cell computation that bypasses the Bowyer-Watson algorithm and explore other methods for managing distributed diagrams. The ultimate goal is to apply these methods to large-scale cosmological simulations and reconstruction problems.

Summary updated

BibTeX
@article{levy2025large,
  author = {Bruno Lévy and Nicolas Ray and Quentin Mérigot and Hugo Leclerc},
  title = {{Large-scale semi-discrete optimal transport with distributed Voronoi diagrams}},
  journal = {Journal of Computational Physics},
  year = {2025},
  url = {https://openreview.net/forum?id=6IarWCDsYn},
}
Figure