  We study Benamou's domain decomposition algorithm for optimal transport in
the entropy regularized setting. The key observation is that the regularized
variant converges to the globally optimal solution under very mild assumptions.
We prove linear convergence of the algorithm with respect to the
Kullback--Leibler divergence and illustrate the (potentially very slow) rates
with numerical examples.
  On problems with sufficient geometric structure (such as Wasserstein
distances between images) we expect much faster convergence. We then discuss
important aspects of a computationally efficient implementation, such as
adaptive sparsity, a coarse-to-fine scheme and parallelization, paving the way
to numerically solving large-scale optimal transport problems. We demonstrate
efficient numerical performance for computing the Wasserstein-2 distance
between 2D images and observe that, even without parallelization, domain
decomposition compares favorably to applying a single efficient implementation
of the Sinkhorn algorithm in terms of runtime, memory and solution quality.
