Researchers solve a 268-million-point transport problem in 2.5 hours

A team of researchers has published a new method for solving a complex mathematical problem known as entropic optimal transport. The work, detailed in a paper on arXiv, introduces a tool called FlashSinkhorn 2. This algorithm allows computers to match two huge sets of data points efficiently.

Imagine you have a map with 134 million red dots and another with 134 million blue dots. The goal is to find the cheapest way to move every red dot to a blue dot. This is a classic logistics problem, but doing it for 268 million points is usually too slow for standard software.

Previous methods, like the original FlashSinkhorn, had to check every single pair of points in every step. This creates a massive computational burden. The new approach changes how the computer looks at the data. It groups points into blocks and solves the problem at a coarser level first.

The system uses a two-stage process. In the first stage, it works with the centers of these blocks rather than individual points. This speeds up the initial calculations significantly. If the result is not accurate enough, the system refines the answer in a second, finer stage.

The researchers tested this method on a single A100 graphics processing unit. They ran it on data from a cosmological simulation involving 134 million particles on each side. The total number of points was 268 million.

The solver reached a high level of accuracy in under 2.5 hours. The error in the final matching was kept below 0.01. The paper notes that this is the largest discrete problem of this type solved to this accuracy within a few hours.

The method relies on specific hardware features. It uses a technique called fused tensor-core execution to handle the math quickly. The blocks are ordered in a way that allows the computer to skip unnecessary calculations.

This has implications for fields that work with large datasets. Cosmology, for example, often deals with simulations of billions of particles. Being able to process these faster could speed up research into the structure of the universe.

The developers have released an open-source version of the code. This allows other researchers to test the method on their own data. The paper provides details on how the algorithm handles the specific costs of moving points in low-dimensional spaces.

The method is specialized for squared-Euclidean cost, which is a common way to measure distance. It is designed for low-dimensional point clouds. It does not replace all transport solvers but offers a faster path for specific large-scale problems.

The source does not provide benchmarks for other types of cost functions or higher-dimensional data. The results are specific to the hardware and problem size tested in the paper.