REVIEW 3 major objections 1 minor 3 references
A dividing index splits non-uniform kernel matrices into quasi-collinear blocks that support O(N) dynamic programming for Sinkhorn iterations.
Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →
FINOM extends fast Sinkhorn to non-uniform meshes via a dividing index that creates quasi-collinear kernel blocks, reducing per-iteration cost from O(N^2) to O(N) with supporting 1D/2D experiments.
T0 review reviewed 2026-06-29 challenge →
load-bearing objection FINOM adds a dividing index to split non-uniform kernel matrices into quasi-collinear blocks for O(N) Sinkhorn iterations on W1, but the guarantee for arbitrary 2D meshes rests on unstated conditions. the 3 major comments →
FINOM: Fast Sinkhorn on Non-uniform Meshes
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
Core claim
By introducing the concept of a dividing index, the kernel matrix on non-uniform meshes is partitioned into two blocks. Each block exhibits a quasi-collinear property that generalizes the collinear structure previously used on uniform meshes. This property is then leveraged to develop the FINOM algorithm, which applies dynamic programming to reduce the per-iteration complexity of Sinkhorn from O(N^2) to O(N).
What carries the argument
The dividing index, which partitions the kernel matrix into two blocks each exhibiting a quasi-collinear property that enables dynamic programming acceleration.
Load-bearing premise
The kernel matrix on non-uniform meshes admits a dividing index that creates two blocks with enough quasi-collinearity for dynamic programming to work.
What would settle it
A non-uniform mesh test case in which no dividing index produces blocks that allow accurate O(N) computation of the Sinkhorn updates, or where the resulting distances differ from a reference quadratic implementation beyond floating-point error.
If this is right
- Sinkhorn iterations on non-uniform meshes drop from quadratic to linear cost.
- Wasserstein-1 distances become practical for large 1D and 2D irregular grids.
- The method delivers speed-ups of several orders of magnitude while preserving accuracy.
- The same partitioning applies to both one- and two-dimensional problems arising in CFD and finance.
Where Pith is reading between the lines
- The dividing-index idea may extend to unstructured or adaptive meshes in higher dimensions.
- Quasi-collinear structure could be sought in other kernel matrices used in optimal transport or machine learning to obtain similar accelerations.
- FINOM might be combined with multilevel or hierarchical methods for even larger-scale transport problems.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes FINOM, an extension of prior fast Sinkhorn algorithms to non-uniform meshes for computing the Wasserstein-1 distance. It introduces a 'dividing index' that partitions the kernel matrix into two blocks, each claimed to satisfy a quasi-collinear property generalizing the uniform-mesh case. This structure is used to derive a dynamic-programming acceleration that reduces per-iteration cost from O(N²) to O(N). Numerical experiments on 1D and 2D problems are reported to confirm both the complexity reduction and maintained accuracy.
Significance. A verified O(N) per-iteration Sinkhorn method on arbitrary non-uniform meshes would be useful for applications in CFD and finance. The numerical speed-up results constitute concrete evidence of practical gain over the uniform-mesh predecessors, but the absence of an explicit recurrence, mesh-regularity hypotheses, or complexity proof in the provided text leaves the generality of the dividing-index construction unverified.
major comments (3)
- [Abstract / dividing-index section] Abstract and § on the dividing-index construction: the claim that every kernel matrix on an arbitrary non-uniform mesh admits a dividing index yielding two blocks with a quasi-collinear property strong enough for exact O(N) DP is load-bearing for the central complexity result, yet no explicit definition of the index, no statement of the recurrence, and no proof of existence or of the required quasi-collinearity are supplied. The skeptic note correctly flags that this must be demonstrated rather than asserted.
- [Numerical experiments / 2D section] Extension to 2D unstructured meshes: the abstract asserts applicability to 2D problems, but the linear ordering implicit in the 1D dividing-index construction has no canonical analogue on unstructured 2D meshes; the manuscript must specify how the partition and DP recurrence are defined in 2D and whether the O(N) bound survives.
- [Algorithm description] Complexity analysis: the O(N) per-iteration claim requires both that the index search itself is O(N) and that the subsequent DP is exact (not approximate). Neither the cost of locating the dividing index nor a formal complexity proof appears in the abstract; these must be supplied to support the stated reduction.
minor comments (1)
- [Abstract] The abstract refers to 'extensive numerical experiments' but does not state the mesh sizes, the range of non-uniformity tested, or the precise error metric used to claim 'maintained accuracy'; these details should be added for reproducibility.
Simulated Author's Rebuttal
We thank the referee for the careful reading and constructive comments. We address each major comment below, acknowledging where additional details are needed and outlining the revisions.
read point-by-point responses
-
Referee: [Abstract / dividing-index section] Abstract and § on the dividing-index construction: the claim that every kernel matrix on an arbitrary non-uniform mesh admits a dividing index yielding two blocks with a quasi-collinear property strong enough for exact O(N) DP is load-bearing for the central complexity result, yet no explicit definition of the index, no statement of the recurrence, and no proof of existence or of the required quasi-collinearity are supplied. The skeptic note correctly flags that this must be demonstrated rather than asserted.
Authors: We acknowledge that the manuscript presents the dividing-index construction at a summary level and does not supply an explicit definition, recurrence, or proof in the provided text. In the revision we will add a dedicated subsection containing the formal definition of the dividing index, the DP recurrence relations, and a proof of the quasi-collinear property (under the assumption that mesh points are sorted). revision: yes
-
Referee: [Numerical experiments / 2D section] Extension to 2D unstructured meshes: the abstract asserts applicability to 2D problems, but the linear ordering implicit in the 1D dividing-index construction has no canonical analogue on unstructured 2D meshes; the manuscript must specify how the partition and DP recurrence are defined in 2D and whether the O(N) bound survives.
Authors: We agree that the 2D case requires an explicit description of the ordering used to apply the dividing-index construction. The revised manuscript will specify how the partition and DP recurrence are defined on unstructured 2D meshes and state the conditions under which the O(N) bound is preserved. revision: yes
-
Referee: [Algorithm description] Complexity analysis: the O(N) per-iteration claim requires both that the index search itself is O(N) and that the subsequent DP is exact (not approximate). Neither the cost of locating the dividing index nor a formal complexity proof appears in the abstract; these must be supplied to support the stated reduction.
Authors: We agree that a formal complexity analysis is required. The revised manuscript will include an explicit statement that the dividing-index search is performed in O(N) time by a linear scan and that the DP is exact, together with a complete complexity proof. revision: yes
Circularity Check
No significant circularity; dividing-index construction is an independent structural observation
full rationale
The paper introduces a new 'dividing index' concept that partitions the kernel matrix on non-uniform meshes into blocks claimed to satisfy a quasi-collinear property, then applies dynamic programming. This construction is presented as a novel generalization of the uniform-mesh collinearity identified in prior (self-cited) work, with no equations reducing the O(N) claim to a fitted parameter, self-referential definition, or load-bearing self-citation chain. The prior citations support only the uniform baseline; the extension to non-uniform meshes rests on the authors' explicit demonstration of the dividing index and quasi-collinearity, which is not shown to be equivalent to the input by construction. The derivation chain is therefore self-contained against external benchmarks.
Axiom & Free-Parameter Ledger
invented entities (1)
-
dividing index
no independent evidence
Cite this review
Pith. "Pith review of FINOM: Fast Sinkhorn on Non-uniform Meshes." pith.science (2026). https://pith.science/paper/KMLDWWYM
@misc{pith2026260526659,
author = {Pith},
title = {Pith review of: FINOM: Fast Sinkhorn on Non-uniform Meshes},
year = {2026},
howpublished = {\url{https://pith.science/paper/KMLDWWYM}},
note = {Machine review of arXiv:2605.26659}
}
abstract
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.
Figures
Reference graph
Works this paper leans on
-
[1]
[1]J. Altschuler, F. Bach, A. Rudi, and J. Niles-Weed, Massively scalable Sinkhorn distances via the Nystr¨ ommethod, Advances in Neural Information Processing Systems, 32 (2019). 1 [2]J. Altschuler, J. Niles-Weed, and P. Rigollet, Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration, Advances in Neural Information Proces...
-
[2]
1, 2.1, 2.2 [22]T. Y. Lin, N. Ho, and M. Jordan, On efficient optimal transport: An analysis of greedy and accelerated mirror descent algorithms, in International Conference on Machine Learning, PMLR, 2019, pp. 3982–3991. 1 [23]C. Mavriplis, Adaptive mesh strategies for the spectral element method, Computer Methods in Applied Mechanics and Engineering, 11...
work page internal anchor Pith review Pith/arXiv arXiv 2019
-
[3]
1 [33]W. S. Wang, Y. Z. Chen, and H. Fang, On the variable two-step IMEX BDF method for parabolic integro-differential equations with nonsmooth initial data arising in finance, SIAM Journal on Numerical Analysis, 57 (2019), pp. 1289–1317. 1 [34]S. T. Wu, W. H. Ye, H. Wu, H. H. Wu, W. Y. Zhang, and B. Bai, A communication optimal transport approach to the ...
2019
This paper was first reviewed by grok-4.3 on June 29, 2026.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.