PDOT: a Practical Primal-Dual Algorithm and a GPU-Based Solver for Optimal Transport
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914891121557504 |
|---|---|
| author | Lu, Haihao Yang, Jinwen |
| author_facet | Lu, Haihao Yang, Jinwen |
| contents | In this paper, we propose a practical primal-dual algorithm with theoretical guarantees and develop a GPU-based solver, which we dub PDOT, for solving large-scale optimal transport problems. Compared to Sinkhorn algorithm or classic LP algorithms, PDOT can achieve high-accuracy solution while efficiently taking advantage of modern computing architecture, i.e., GPUs. On the theoretical side, we show that PDOT has a data-independent $\widetilde O(mn(m+n)^{1.5}\log(\frac{1}ε))$ local flop complexity where $ε$ is the desired accuracy, and $m$ and $n$ are the dimension of the original and target distribution, respectively. We further present a data-dependent $\widetilde O(mn(m+n)^{3.5}Δ+ mn(m+n)^{1.5}\log(\frac{1}ε))$ global flop complexity of PDOT, where $Δ$ is the precision of the data. On the numerical side, we present PDOT, an open-source GPU solver based on the proposed algorithm. Our extensive numerical experiments consistently demonstrate the well balance of PDOT in computing efficiency and accuracy of the solution, compared to Gurobi and Sinkhorn algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_19689 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | PDOT: a Practical Primal-Dual Algorithm and a GPU-Based Solver for Optimal Transport Lu, Haihao Yang, Jinwen Optimization and Control In this paper, we propose a practical primal-dual algorithm with theoretical guarantees and develop a GPU-based solver, which we dub PDOT, for solving large-scale optimal transport problems. Compared to Sinkhorn algorithm or classic LP algorithms, PDOT can achieve high-accuracy solution while efficiently taking advantage of modern computing architecture, i.e., GPUs. On the theoretical side, we show that PDOT has a data-independent $\widetilde O(mn(m+n)^{1.5}\log(\frac{1}ε))$ local flop complexity where $ε$ is the desired accuracy, and $m$ and $n$ are the dimension of the original and target distribution, respectively. We further present a data-dependent $\widetilde O(mn(m+n)^{3.5}Δ+ mn(m+n)^{1.5}\log(\frac{1}ε))$ global flop complexity of PDOT, where $Δ$ is the precision of the data. On the numerical side, we present PDOT, an open-source GPU solver based on the proposed algorithm. Our extensive numerical experiments consistently demonstrate the well balance of PDOT in computing efficiency and accuracy of the solution, compared to Gurobi and Sinkhorn algorithms. |
| title | PDOT: a Practical Primal-Dual Algorithm and a GPU-Based Solver for Optimal Transport |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2407.19689 |