Title: Computation of Optimal Transport on Discrete Metric Measure Spaces,
Abstract: In this paper we investigate the numerical approximation of an analogue of
the Wasserstein distance for optimal transport on graphs that is defined via a
discrete modification of the Benamou--Brenier formula. This approach involves
the logarithmic mean of measure densities on adjacent nodes of the graph. For
this model a variational time discretization of the probability densities on
graph nodes and the momenta on graph edges is proposed. A robust descent
algorithm for the action functional is derived, which in particular uses a
proximal splitting with an edgewise nonlinear projection on the convex subgraph
of the logarithmic mean. Thereby, suitable chosen slack variables avoid a
global coupling of probability densities on all graph nodes in the projection
step. For the time discrete action functional $\Gamma$--convergence to the time
continuous action is established. Numerical results for a selection of test
cases show qualitative and quantitative properties of the optimal transport on
graphs. Finally, we use our algorithm to implement a JKO scheme for the
gradient flow of the entropy in the discrete transportation distance, which is
known to coincide with the underlying Markov semigroup, and test our results
against a classical backward Euler discretization of this discrete heat flow.