🔢 mathematics

FINOM: Fast Sinkhorn on Non-uniform Meshes

This paper introduces FINOM, a linear-complexity algorithm that accelerates the computation of the Wasserstein-1 distance on non-uniform meshes by leveraging a newly identified quasi-collinear structure via a "dividing index" to reduce per-iteration complexity from $O(N^2)$ to $O(N)$ .

Original authors: Qihao Cheng, Qichen Liao, Hao Wu, Shuai Yang

Published 2026-05-27

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Qihao Cheng, Qichen Liao, Hao Wu, Shuai Yang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a logistics manager trying to move a pile of sand from one location to another. You have a source pile (the "supply") and a destination pile (the "demand"). Your goal is to move the sand in the most efficient way possible, minimizing the total distance traveled. In the world of mathematics and data science, this is called Optimal Transport.

The paper introduces a new tool called FINOM (Fast Sinkhorn on Non-Uniform Meshes) to solve this problem much faster than before, especially when the "sand" isn't spread out evenly.

Here is the breakdown of the problem and the solution, using simple analogies:

1. The Problem: The "Grid" and the "Uneven Sand"

To solve this math problem on a computer, we usually lay down a grid (like graph paper) over the area where the sand is.

Uniform Mesh (The Old Way): Imagine a perfectly even grid, like a chessboard. Every square is the same size. In the past, researchers found a clever shortcut (a "Fast Sinkhorn" algorithm) to solve the sand-moving problem on these perfect grids. It was like having a magic calculator that could do the math in seconds.
Non-Uniform Mesh (The Real World): In real life, things aren't perfect. Sometimes you have a huge pile of sand in one spot and almost none in another. To be efficient, you might use a grid where the squares are tiny near the big pile (to be precise) and huge in the empty areas (to save space). This is a non-uniform mesh.
The Bottleneck: The old "magic calculator" (Fast Sinkhorn) only worked on the perfect chessboard grids. When scientists tried to use it on these uneven, real-world grids, the math broke down. They had to go back to the slow, brute-force method, which took a very long time (imagine calculating the distance for every single grain of sand against every other grain).

2. The Innovation: The "Dividing Index"

The authors of this paper asked: "Can we make the magic calculator work on the uneven grids?"

They discovered a way to slice the messy, uneven grid into two neat, manageable pieces. They invented a concept called the "Dividing Index."

The Analogy: Imagine you have a long, wobbly line of people of different heights. You want to organize them. Instead of trying to sort the whole line at once, you find a specific "cutting point" for each person.
- For the people on the left, you group them into a block where the math behaves nicely (like a staircase).
- For the people on the right, you do the same.
The "Quasi-Collinear" Secret: Even though the grid is uneven, once they split it using this "Dividing Index," they found that each half has a hidden pattern. It's not perfectly straight, but it's "almost straight" (quasi-collinear). This pattern allows the computer to use a Dynamic Programming trick.

What is Dynamic Programming here?
Think of it like climbing a staircase. If you want to know how many steps are in the whole staircase, you don't count every single step from the bottom every time. You just count the steps in the first flight, then add the steps in the next flight, and so on. You use the previous answer to get the next one.

Old Method: Count every single step from scratch every time (Slow: $O(N^2)$ ).
FINOM Method: Use the previous count to jump to the next step (Fast: $O(N)$ ).

3. The Result: FINOM

By using this "Dividing Index" to split the problem and then applying the "staircase" counting trick, the authors created FINOM.

Speed: They claim FINOM is linear complexity. In plain English, if you double the amount of data, the time it takes only doubles. The old method was "quadratic," meaning if you doubled the data, the time quadrupled (or worse).
Accuracy: They didn't cheat to get the speed. They proved that FINOM gives the exact same answer as the slow, accurate method. It's just much faster at getting there.
Scale: They tested this on 1D (a line) and 2D (a flat surface) problems with random, messy grids.
- In 1D, it was hundreds of times faster.
- In 2D, it was thousands of times faster (speed-ups of over 10,000x for large problems).

4. Why This Matters (According to the Paper)

The paper specifically mentions that this is useful for fields where data isn't spread out evenly, such as:

Computational Fluid Dynamics: Simulating how air or water flows (where you need high detail near a wing or a pipe, but low detail in empty space).
Finance: Modeling financial risks where extreme events are rare but important.

Summary

The paper presents FINOM, a new algorithm that acts like a "turbocharger" for calculating how to move probability distributions (like sand) on uneven grids.

The Problem: The fast way to do this math only worked on perfect, even grids. Real-world grids are messy.
The Fix: They invented a "Dividing Index" to chop the messy grid into two pieces that act like they are on a perfect grid.
The Payoff: This allows the computer to use a "staircase" shortcut (Dynamic Programming) to solve the math.
The Outcome: The solution is just as accurate as the slow method but runs thousands of times faster, making complex simulations on uneven grids practical for the first time.

Technical Summary: FINOM – Fast Sinkhorn on Non-Uniform Meshes

Problem Statement

The paper addresses the computational challenge of calculating the Wasserstein-1 distance between two discrete probability measures defined on non-uniform meshes. While the Optimal Transport (OT) problem is fundamental to applications in fluid dynamics, finance, and machine learning, solving it efficiently on non-uniform grids remains difficult.

Standard numerical approaches, such as the Sinkhorn algorithm (which uses entropy regularization), typically incur a computational complexity of $O(N^2)$ per iteration due to dense matrix-vector multiplications involving the kernel matrix $K$ . Previous work by the authors and others successfully accelerated the Sinkhorn algorithm to $O(N)$ complexity for uniform meshes by exploiting a "collinear" structure in the kernel matrix. However, this collinear property breaks down on non-uniform meshes, preventing the direct application of these fast methods. Consequently, the computational savings gained by using non-uniform meshes (fewer grid points for concentrated densities) are often negated by the high cost of the $O(N^2)$ Sinkhorn iterations.

Methodology

The authors propose FINOM (Fast SInkhorn algorithm on NOn-uniform Meshes), a dynamic programming approach that restores linear complexity $O(N)$ for 1D problems and $O(NM)$ for 2D problems, even on non-uniform grids.

1. The Dividing Index and Block Partitioning

The core innovation is the introduction of a "dividing index" $\zeta(i)$ . For a sorted source mesh $x$ and target mesh $y$ , $\zeta(i)$ identifies the index in $y$ such that $y_{\zeta(i)} \le x_i < y_{\zeta(i)+1}$ . This index allows the kernel matrix $K$ (where $k_{ij} = e^{-|x_i - y_j|/\varepsilon}$ ) to be partitioned into two complementary sub-blocks:

Lower Block ( $K_L$ ): Contains entries where $j \le \zeta(i)$ .
Upper Block ( $K_U$ ): Contains entries where $j > \zeta(i)$ .

2. Quasi-Collinear Structure

While the full kernel matrix on a non-uniform mesh lacks the strict collinearity found in uniform meshes, the authors demonstrate that the partitioned blocks $K_L$ and $K_U$ exhibit a "quasi-collinear" property. Specifically:

Within the non-zero regions of these blocks, the ratio between consecutive rows is constant (row-wise constant-ratio property).
The non-zero entries form a "staircase" pattern determined by the dividing index.

3. Vector Representation and Dynamic Programming

Leveraging the quasi-collinear property, the authors prove that $K_L$ and $K_U$ can be fully represented by:

A ratio vector ( $r$ or $r'$ ) capturing the constant row-to-row scaling factors.
A set of block-edge vectors ( $\eta$ or $\eta'$ ) capturing the unique values at the boundaries of the staircase.

This representation enables a recursive computation for matrix-vector multiplication ( $K\psi$ and $K^\top\phi$ ). Instead of computing the full dot product for every row, the algorithm updates the result iteratively:
$p_{i+1} = r_i p_i + \eta_{i+1} \cdot \psi_{i+1}$
This reduces the cost of a single matrix-vector multiplication from $O(N^2)$ to $O(N)$ .

4. Extension to Higher Dimensions

For 2D and higher-dimensional problems, the kernel matrix factorizes into a Kronecker product of 1D kernel matrices ( $K = K_y \otimes K_x$ ). The authors extend FINOM by applying the 1D fast multiplication algorithm successively along each coordinate direction. This preserves the linear complexity relative to the total number of grid points ($O(NM)$ for 2D).

Key Contributions

Generalization of Fast Sinkhorn: The paper extends the $O(N)$ fast Sinkhorn algorithms previously limited to uniform meshes to the general case of non-uniform meshes.
Dividing Index Concept: The introduction of the dividing index to partition the kernel matrix into blocks with quasi-collinear structures.
Linear Complexity Algorithm: The development of FINOM, which achieves $O(N)$ complexity per iteration for 1D and $O(NM)$ for 2D, maintaining the exactness of the original matrix-vector products (unlike approximation methods).
Numerical Validation: Extensive experiments confirming that FINOM achieves speed-ups of several orders of magnitude compared to the standard Sinkhorn algorithm while producing transport plans indistinguishable from the standard method (differences at machine precision).

Results

The authors conducted numerical experiments on 1D and 2D problems with random distributions on both Chebyshev and random non-uniform nodes.

1D Performance: FINOM demonstrated speed-up ratios ranging from $\approx 10^2$ to $\approx 10^3$ as $N$ increased from 500 to 8,000. The observed scaling was approximately $O(N^{1.13})$ for FINOM versus $O(N^{2.58})$ for standard Sinkhorn.
2D Performance: For 2D grids ( $N \times N$ ), the speed-up ratio grew rapidly, exceeding $10^4$ for a $160 \times 160$ grid. The observed scaling was approximately $O(N^{1.74})$ for FINOM versus $O(N^{4.62})$ for standard Sinkhorn.
Accuracy: In all tests, the Frobenius norm of the difference between the transport plans ( $\Delta \Gamma$ ) computed by FINOM and the standard Sinkhorn algorithm was on the order of $10^{-17}$ to $10^{-18}$ , confirming that the acceleration does not compromise numerical accuracy.

Significance and Claims

The paper claims that FINOM resolves a critical bottleneck in applying Optimal Transport to practical problems involving non-uniform meshes (common in computational fluid dynamics and finance). By restoring linear complexity, the method allows practitioners to utilize non-uniform meshes to reduce the number of grid points required for accuracy without incurring the prohibitive $O(N^2)$ computational cost of standard algorithms.

The authors emphasize that their approach is not an approximation; it accelerates the exact Sinkhorn iteration. They note that while the theoretical complexity is linear, the observed exponents in experiments (e.g., $N^{1.13}$ ) are slightly higher than 1, likely due to implementation overheads, but the growth is drastically flatter than the quadratic or higher-order growth of standard methods. The work establishes a foundation for efficient, high-precision Optimal Transport on general, non-uniform discretizations.