{"id":"arxiv/2605.26659","url":"https://arxiv.org/abs/2605.26659","tags":["math.NA","math.OC"],"score":0,"title":"FINOM: Fast Sinkhorn on Non-uniform Meshes","domain":"math.NA","source":"arxiv","authors":["Qihao Cheng","Qichen Liao","Hao Wu","Shuai Yang"],"reviews":0,"subject":"math.NA","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-05-26","reactions":{}}