# GPU-Accelerated Bregman Douglas-Rachford Splitting for Discrete Optimal Transport

arXiv: https://arxiv.org/abs/2610.04715 · HTML: https://mlsanity.com/paper/2610.04715/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 51 references that are in the map.
- First posted on arXiv 3 Oct 2026.

## Builds on (most cited first, 19 of 19)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Optimal Transport for Domain Adaptation](https://mlsanity.com/paper/1507.00504/) (2015)
- [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017)
- [Online normalizer calculation for softmax](https://mlsanity.com/paper/1805.02867/) (2018)
- [Optimal Transport Tools (OTT): A JAX Toolbox for all things Wasserstein](https://mlsanity.com/paper/2201.12324/) (2022)
- [Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems](https://mlsanity.com/paper/1610.06519/) (2016)
- [Practical Large-Scale Linear Programming using Primal-Dual Hybrid Gradient](https://mlsanity.com/paper/2106.04756/) (2021)
- [Screening Sinkhorn Algorithm for Regularized Optimal Transport](https://mlsanity.com/paper/1906.08540/) (2019)
- [DOTmark - A Benchmark for Discrete Optimal Transport](https://mlsanity.com/paper/1610.03368/) (2016)
- [A Fast and Accurate Splitting Method for Optimal Transport: Analysis and Implementation](https://mlsanity.com/paper/2110.11738/) (2021)
- [Computing Kantorovich-Wasserstein Distances on d-dimensional histograms using (d+1)-partite graphs](https://mlsanity.com/paper/1805.07416/) (2018)
- [cuPDLPx: A Further Enhanced GPU-Based First-Order Solver for Linear Programming](https://mlsanity.com/paper/2507.14051/) (2025)
- [PDOT: a Practical Primal-Dual Algorithm and a GPU-Based Solver for Optimal Transport](https://mlsanity.com/paper/2407.19689/) (2024)
- [HOT: An Efficient Halpern Accelerating Algorithm for Optimal Transport Problems](https://mlsanity.com/paper/2408.00598/) (2024)
- [Bregman Douglas-Rachford Splitting Method](https://mlsanity.com/paper/2509.08739/) (2025)
- [ITERATED INSIDE OUT: a new exact algorithm for the transportation problem](https://mlsanity.com/paper/2302.10826/) (2023)
- [D-PDLP: Scaling PDLP to Distributed Multi-GPU Systems](https://mlsanity.com/paper/2601.07628/) (2026)
- [Distributed Linear Programming on GPU Clusters at Extreme Scale](https://mlsanity.com/paper/2609.09108/) (2026)

## Abstract (arXiv)

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.