GPU-Accelerated Bregman Douglas-Rachford Splitting for Discrete Optimal Transport
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.
Related
- Douglas-Rachford splitting method for nonconvex stochastic optimal control
- ABrA-GD: Adaptive Bregman Accelerated Gradient Descent for Relatively Smooth and (Strongly-)Convex Optimization
- Accelerated Bregman Proximal Gradient Methods from Dual Geometric Perspectives
- Parameter Estimation for Unnormalized Discrete Models via Empirically Localized Deformed Bregman Divergence
- A Logarithmic-dual-update Bregman ADMM for Optimal Transport
BibTeX
@misc{xu2026gpuaccelerated,
title = {{GPU-Accelerated Bregman Douglas-Rachford Splitting for Discrete Optimal Transport}},
author = {Yifan Xu and Shiqian Ma},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.04715},
eprint = {2610.04715},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.04715},
}
RIS
TY - UNPB
TI - GPU-Accelerated Bregman Douglas-Rachford Splitting for Discrete Optimal Transport
AU - Yifan Xu
AU - Shiqian Ma
PY - 2026
DA - 2026/10/27
PB - arXiv
DO - 10.48550/arxiv.2610.04715
UR - https://arxiv.org/abs/2610.04715
AB - 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.
ER -