Gpu speeds up solving discrete optimal transport problems efficiently
GPU-Accelerated Bregman Douglas-Rachford Splitting for Discrete Optimal Transport
Machine Learning
Summary
Computing the best way to move or transform things from one set to another is a common problem called optimal transport. The authors developed a new approach that runs this computation using GPUs, making it much faster. They wrote special versions for different ways the problem can be presented, and tested their method against other leading tools. Their approach performed very well across all tested cases, showing improved speed and reliability.
What this means in practice
- •For computer graphics developers: Run fast optimal transport calculations for tasks like shape matching and texture mapping using GPU-accelerated methods tailored to input types.
- •For geospatial data engineers: Integrate efficient GPU-based optimal transport solvers when working with grid or point cloud data for spatial analysis and mapping.
Authors
Yifan Xu, Shiqian Ma
Abstract
We present GPU-accelerated Bregman Douglas--Rachford splitting algorithm (BDRS) for discrete optimal transport problem in three input formats: an explicit cost matrix, a point cloud with a ground cost between them, and a separable cost on a regular grid. For each input format, we propose hardware-aware designs of mathematically equivalent representations for the BDRS iterations to enhance numerical stability and empirical runtime. We benchmark the three proposed implementations against eight GPU baseline solvers from the literature on the same device. We demonstrate that our implementations of BDRS achieve state-of-the-art performance on their respective input formats. To the best of our knowledge, this is the first cross-solver study of GPU DOT solvers with a unified measure of optimality.