{"id":"0994797b-e4c4-4162-a0f9-28d6d7540ee4","arxiv_id":"2605.26659","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"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.","lead":"The paper introduces FINOM, an algorithm that computes the Wasserstein-1 distance on non-uniform meshes in linear time per Sinkhorn iteration by partitioning the kernel matrix with a dividing index into quasi-collinear blocks. A smart generalist might read it to see how optimal transport can be accelerated for irregular grids used in fluid dynamics or finance without losing the speed gains previously limited to uniform meshes.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.3","headline":"Existence of dividing index yielding quasi-collinear blocks sufficient for exact O(N) DP on arbitrary non-uniform meshes","rationale":"The reader's weakest_assumption is precisely the step whose validity determines whether the complexity reduction holds. Because the supplied abstract asserts the property without proof details or mesh assumptions, and the full text (though referenced) is not reproduced here, the UNVERDICTED verdict with low confidence remains appropriate; no stronger objection is identifiable from the given material.","tokens_in":1727,"tokens_out":364,"duration_ms":46505,"concrete_test":"Take the 4-point non-uniform mesh x=[0,0.1,1,1.1], form the 4x4 kernel K_ij=exp(-|x_i-x_j|/ε) for ε=0.1, locate any dividing index k, and verify whether the matrix-vector product K v can be obtained via the claimed DP recurrence using only O(1) operations per entry rather than full summation.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The O(N) per-iteration claim rests on the kernel matrix (for W1 cost on non-uniform points) always admitting a dividing index that splits it into two blocks, each satisfying a quasi-collinear property strong enough for the same dynamic-programming recurrence used on uniform meshes. On sorted 1D points this may hold when spacings vary mildly, but the abstract gives no explicit condition on mesh regularity, no statement of the recurrence, and no indication how the construction extends to 2D unstructured meshes (where no canonical linear order exists). If the quasi-collinearity is only approximate or the index search costs more than O(N), the claimed linear complexity fails.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","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.","tokens_in":1880,"tokens_out":575,"duration_ms":19422,"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":[{"comment":"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.","section":"Abstract / dividing-index section"},{"comment":"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.","section":"Numerical experiments / 2D section"},{"comment":"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.","section":"Algorithm description"}],"minor_comments":[{"comment":"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.","section":"Abstract"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"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.","responses":[{"response":"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_made":"yes","referee_comment":"[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."},{"response":"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_made":"yes","referee_comment":"[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."},{"response":"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_made":"yes","referee_comment":"[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."}],"tokens_in":1524,"tokens_out":543,"duration_ms":35580,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The paper's core move is to define a dividing index that splits the kernel matrix on sorted non-uniform points into two blocks, each inheriting enough of the collinear structure from the uniform case to reuse the same dynamic-programming recurrence. That produces the claimed drop from quadratic to linear cost per Sinkhorn iteration for Wasserstein-1.\n\nThey do the extension cleanly. The two earlier uniform-mesh papers are cited directly, the new construction is presented as an independent observation rather than a parameter fit, and the abstract states that 1D and 2D experiments show both the speed-up and preserved accuracy. For someone who already runs Sinkhorn on irregular grids in CFD or finance, this is a concrete implementation-level improvement.\n\nThe soft spot is exactly the one the stress-test flags. The abstract gives no explicit regularity condition on the mesh spacings, no statement of the recurrence itself, and no indication how the dividing index is found or ordered in 2D unstructured meshes where a linear sort is not canonical. If the quasi-collinearity is only approximate or the index search is super-linear, the O(N) claim does not hold. Experiments are invoked but not described, so it is impossible to check whether the observed timings really scale linearly once the index overhead is included.\n\nThe work is aimed at practitioners who need fast W1 on irregular meshes and who are willing to add a modest amount of mesh-specific preprocessing. A reader already familiar with the uniform-mesh DP papers will see the incremental step immediately.\n\nI would send it to peer review. The algorithmic idea is new within the subfield and the target application is genuine; the manuscript simply needs to supply the missing conditions, the explicit recurrence, and the complexity accounting before the central claim can be accepted.","headline":"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.","tokens_in":2370,"tokens_out":445,"would_cite":false,"duration_ms":26244,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"A dividing index splits non-uniform kernel matrices into quasi-collinear blocks that support O(N) dynamic programming for Sinkhorn iterations.","keywords":["Sinkhorn algorithm","Wasserstein distance","non-uniform meshes","dynamic programming","optimal transport","linear complexity","kernel matrix"],"falsifier":"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.","tokens_in":2634,"feed_emoji":"","tokens_out":602,"duration_ms":36673,"temperature":0.7,"pith_summary":"The paper develops FINOM to compute the Wasserstein-1 distance on non-uniform meshes with linear per-iteration cost. It extends earlier uniform-mesh accelerations by locating a dividing index that splits the kernel matrix into two blocks. Each block retains a quasi-collinear property that lets dynamic programming replace the usual quadratic matrix-vector products. This matters for applications that routinely use irregular grids, such as fluid dynamics and finance, where standard Sinkhorn quickly becomes too slow.","feed_headline":"Dividing index cuts Sinkhorn cost to linear on non-uniform meshes","feed_subtitle":"A partition creates quasi-collinear blocks that let dynamic programming replace quadratic loops for Wasserstein-1 distance.","key_machinery":"The dividing index, which partitions the kernel matrix into two blocks each exhibiting a quasi-collinear property that enables dynamic programming acceleration.","core_discovery":"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).","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["Dividing index partitions kernel for linear Sinkhorn","Quasi-collinear blocks enable linear Sinkhorn","FINOM achieves linear Sinkhorn on non-uniform meshes","Dividing index unlocks O(N) Sinkhorn via dynamic programming"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"The kernel matrix on non-uniform meshes admits a dividing index that creates two blocks with enough quasi-collinearity for dynamic programming to work.","fun_headline_variants_meta":{"raw":{"variants":["Dividing index partitions kernel for linear Sinkhorn","Quasi-collinear blocks enable linear Sinkhorn","FINOM achieves linear Sinkhorn on non-uniform meshes","Dividing index unlocks O(N) Sinkhorn via dynamic programming"]},"model":"grok-4.3","cost_usd":0.006404,"raw_usage":{"total_tokens":3016,"prompt_tokens":694,"num_sources_used":0,"completion_tokens":61,"cost_in_usd_ticks":64037000,"prompt_tokens_details":{"text_tokens":694,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":2261,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":694,"tokens_out":61,"duration_ms":25311,"temperature":1.0,"reasoning_tokens":2261,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-06-29T16:04:07.566864+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"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.","supporting_citations":[],"review_version":1}