zbMATH — the first resource for mathematics

An efficient numerical algorithm for the \(L^{2}\) optimal transport problem with periodic densities. (English) Zbl 1408.49022
Summary: We present an extension of the numerical method of G. Loeper and F. Rapetti [C. R., Math., Acad. Sci. Paris 340, No. 4, 319–324 (2005; Zbl 1067.65119)] for the Monge-Ampère equation to non-uniform target densities and adopt it to solve the optimal transport problem with quadratic cost. The method employs a damped Newton algorithm to solve the Monge-Ampère equation. We show that the algorithm converges for sufficiently large damping coefficients, for the case where the source and target densities are sufficiently smooth, periodic and bounded away from zero. At each Newton iteration, we solve a non-constant coefficient linear partial differential equation. To improve the efficiency of the procedure, we use an analytically preconditioned fast Fourier transform method coupled with GMRES ([J. Strain, Proc. Am. Math. Soc. 122, No. 3, 843–850 (1994; Zbl 0812.65099)]) to solve this equation, as opposed to a more straightforward approach based on a second-order finite-difference discretization combined with biconjugate gradient used in [Zbl 1067.65119]. Finally, we present some numerical experiments in image processing to demonstrate the efficiency of the method.

49M15 Newton-type methods
49M25 Discrete approximations in optimal control
65K10 Numerical optimization and variational techniques
65N06 Finite difference methods for boundary value problems involving PDEs
65H10 Numerical computation of solutions to systems of equations
65T50 Numerical methods for discrete and fast Fourier transforms
35J96 Monge-Ampère equations
35J60 Nonlinear elliptic equations
65N35 Spectral, collocation and related methods for boundary value problems involving PDEs
65F10 Iterative numerical methods for linear systems
Full Text: DOI arXiv