FINOM: Fast Sinkhorn on Non-uniform Meshes
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913162668802048 |
|---|---|
| author | Cheng, Qihao Liao, Qichen Wu, Hao Yang, Shuai |
| author_facet | Cheng, Qihao Liao, Qichen Wu, Hao Yang, Shuai |
| contents | A linear-complexity algorithm for computing the Wasserstein-1 distance on non-uniform meshes is proposed. This work extends the fast Sinkhorn algorithms from [Q. Liao et al., Commun. Math. Sci., 20(2022)] and [Q. Liao et al., J. Sci. Comput., 98 (2024)] to non-uniform meshes. In those prior works, a distinctive collinear structure of the kernel matrix on uniform meshes was identified, enabling \(O(N)\) acceleration via dynamic programming. While non-uniform meshes are prevalent in practical applications like computational fluid dynamics and finance, their lack of collinearity has hindered direct acceleration. In this paper, we introduce the concept of a ``dividing index'', which partitions the kernel matrix into two blocks. We demonstrate that each block exhibits a quasi-collinear property, a generalization of the structure found in uniform meshes. Leveraging this insight, we develop \textbf{F}ast S\textbf{I}nkhorn algorithm on \textbf{NO}n-uniform \textbf{M}eshes (\textbf{FINOM}), a dynamic programming approach that reduces the per-iteration complexity of the Sinkhorn algorithm from \(O(N^2)\) to \(O(N)\). Extensive numerical experiments on 1D and 2D problems confirm these improvements, achieving speed-ups of several orders of magnitude while maintaining accuracy. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_26659 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | FINOM: Fast Sinkhorn on Non-uniform Meshes Cheng, Qihao Liao, Qichen Wu, Hao Yang, Shuai Numerical Analysis Optimization and Control A linear-complexity algorithm for computing the Wasserstein-1 distance on non-uniform meshes is proposed. This work extends the fast Sinkhorn algorithms from [Q. Liao et al., Commun. Math. Sci., 20(2022)] and [Q. Liao et al., J. Sci. Comput., 98 (2024)] to non-uniform meshes. In those prior works, a distinctive collinear structure of the kernel matrix on uniform meshes was identified, enabling \(O(N)\) acceleration via dynamic programming. While non-uniform meshes are prevalent in practical applications like computational fluid dynamics and finance, their lack of collinearity has hindered direct acceleration. In this paper, we introduce the concept of a ``dividing index'', which partitions the kernel matrix into two blocks. We demonstrate that each block exhibits a quasi-collinear property, a generalization of the structure found in uniform meshes. Leveraging this insight, we develop \textbf{F}ast S\textbf{I}nkhorn algorithm on \textbf{NO}n-uniform \textbf{M}eshes (\textbf{FINOM}), a dynamic programming approach that reduces the per-iteration complexity of the Sinkhorn algorithm from \(O(N^2)\) to \(O(N)\). Extensive numerical experiments on 1D and 2D problems confirm these improvements, achieving speed-ups of several orders of magnitude while maintaining accuracy. |
| title | FINOM: Fast Sinkhorn on Non-uniform Meshes |
| topic | Numerical Analysis Optimization and Control |
| url | https://arxiv.org/abs/2605.26659 |