Fast Iterative Solution of the Optimal Transport Problem on Graphs

DOI10.1137/20M137015XOpenAlexW3175662620MaRDI QIDQ4997404

Enrico Facca, Michele Benzi

Publication date: 29 June 2021

Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2009.13478

zbMATH Keywords

saddle point problemgradient descentoptimal transport problemalgebraic multigrid methodsimplicit time stepping scheme

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Transportation, logistics and supply chain management (90B06) Iterative numerical methods for linear systems (65F10) Flows in graphs (05C21)

Related Items (4)

Computing the cut locus of a Riemannian manifoldviaoptimal transport ⋮ AI‐enhanced iterative solvers for accelerating the solution of large‐scale parametrized systems ⋮ Randomized methods for computing optimal transport without regularization and their convergence analysis ⋮ Efficient preconditioners for solving dynamical optimal transport via interior point methods

Uses Software

• Unnamed Item
• LAMG
• GraphRicciCurvature
• Wasserstein GAN

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computational Optimal Transport: With Applications to Data Science
• Ricci curvature of graphs
• Introductory lectures on convex optimization. A basic course.
• A Laplacian approach to \(\ell_1\)-norm minimization
• Numerical solution of Monge-Kantorovich equations via a dynamic formulation
• A mathematical model for adaptive transport network in path finding by true slime mold
• Convergence of the non-uniform directed physarum model
• Optimal transport for applied mathematicians. Calculus of variations, PDEs, and modeling
• Spectral preconditioners for the efficient numerical solution of a continuous branched transport model
• Optimal mass transport for registration and warping
• \textit{Physarum} can compute shortest paths
• On the Translocation of Masses
• An optimal transport approach for seismic tomography: application to 3D full waveform inversion
• Multilevel Algorithms for Large-Scale Interior Point Methods
• Emergence of Scaling in Random Networks
• Aggregation-Based Algebraic Multigrid for Convection-Diffusion Equations
• Lean Algebraic Multigrid (LAMG): Fast Graph Laplacian Linear Solver
• Quadratically Regularized Optimal Transport on Graphs
• Numerical solution of saddle point problems
• Towards a Stationary Monge--Kantorovich Dynamics: The Physarum Polycephalum Experience
• An Introduction to Numerical Analysis
• Imaging with Kantorovich--Rubinstein Discrepancy
• Solving Basis Pursuit
• A Flexible Inner-Outer Preconditioned GMRES Algorithm
• Collective dynamics of ‘small-world’ networks
• Block Preconditioners Based on Approximate Commutators
• The Differentiation of Pseudo-Inverses and Nonlinear Least Squares Problems Whose Variables Separate
• Optimal Transport

This page was built for publication: Fast Iterative Solution of the Optimal Transport Problem on Graphs