论文标题
最佳传输问题的快速迭代解决方案
Fast Iterative Solution of the Optimal Transport Problem on Graphs
论文作者
论文摘要
在本文中，我们介绍了无方向的加权图上最佳传输问题的数值解决方案，以最短的路径距离作为运输成本。最佳溶液是从梯度下降动力学的长时间极限获得的。在不同的时间阶梯过程中，该动力学的离散化过程中，向后的Euler时间步进方案与不精确的Newton-Raphson方法相结合，为图上最佳传输问题解决方案提供了强大而准确的方法。在实验上发现，该算法需要在$ \ Mathcal {O}（1）$和$ \ Mathcal {O}（M^{0.36}）$线性系统之间求解，涉及加权Laplacian矩阵的线性系统，其中$ m $是$ m $的数量。这些线性系统是通过代数多机方法求解的，从而为图形上的最佳传输问题提供了有效的求解器。
In this paper, we address the numerical solution of the Optimal Transport Problem on undirected weighted graphs, taking the shortest path distance as transport cost. The optimal solution is obtained from the long-time limit of the gradient descent dynamics. Among different time stepping procedures for the discretization of this dynamics, a backward Euler time stepping scheme combined with the inexact Newton-Raphson method results in a robust and accurate approach for the solution of the Optimal Transport Problem on graphs. It is found experimentally that the algorithm requires solving between $\mathcal{O}(1)$ and $\mathcal{O}(M^{0.36})$ linear systems involving weighted Laplacian matrices, where $M$ is the number of edges. These linear systems are solved via algebraic multigrid methods, resulting in an efficient solver for the Optimal Transport Problem on graphs.
