In this paper we address the numerical solution of the quadratic optimal transport problem in its dynamical form, the so-called Benamou-Brenier formulation. When solved using interior point methods, the main computational bottleneck is the solution of large saddle point linear systems arising from the associated Newton-Raphson scheme. The main purpose of this paper is to design efficient preconditioners to solve these linear systems via iterative methods. Among the proposed preconditioners, we introduce one based on the partial commutation of the operators that compose the dual Schur complement of these saddle point linear systems, which we refer as BB-preconditioner. A series of numerical tests show that the BB-preconditioner is the most efficient among those presented, with a CPU-time scaling only slightly more than linearly with respect to the number of unknowns used to discretize the problem.
翻译:在本文中,我们用动态形式,即所谓的Benamou-Brenier配方,探讨四极最佳运输问题的数字解决办法。在使用内部点方法解决时,主要的计算瓶颈是相关的牛顿-拉夫森计划产生的大型马鞍点线性系统的解决办法。本文的主要目的是设计有效的先决条件,通过迭接方法解决这些线性系统。在拟议的前提条件中,我们引入了一种基于对构成这些马鞍点线性系统的双份舒尔补充的操作者进行部分减刑的办法,我们称之为BB-预设装置。一系列数字测试显示,BB-预设装置是最有效率的,而CPU-时间的缩放仅略高于用于分散问题的未知数的线性。