Search

As a counterpoint to recent numerical methods for crystal surface evolution, which agree well with microscopic dynamics but suffer from significant stiffness that prevents simulation on fine spatial grids, we develop a new numerical method based on the macroscopic partial differential equation, leveraging its formal structure as the gradient flow of the total variation energy, with respect to a weighted H - 1 norm. This gradient flow structure relates to several metric space gradient flows of recent interest, including 2-Wasserstein flows and their generalizations to nonlinear mobilities. We develop a novel semi-implicit time discretization of the gradient flow, inspired by the classical minimizing movements scheme (known as the JKO scheme in the 2-Wasserstein case). We then use a primal dual hybrid gradient (PDHG) method to compute each element of the semi-implicit scheme. In one dimension, we prove convergence of the PDHG method to the semi-implicit scheme, under general integrability assumptions on the mobility and its reciprocal. Finally, by taking finite difference approximations of our PDHG method, we arrive at a fully discrete numerical algorithm, with iterations that converge at a rate independent of the spatial discretization: in particular, the convergence properties do not deteriorate as we refine our spatial grid. We close with several numerical examples illustrating the properties of our method, including facet formation at local maxima, pinning at local minima, and convergence as the spatial and temporal discretizations are refined. [ABSTRACT FROM AUTHOR]

We present a method to efficiently solve the optimal transportation problem for a general class of strictly convex costs. Given two probability measures supported on a discrete grid with n points we compute the optimal transport map between them in O (n log (n)) operations and O(n) storage space. Our approach allows us to solve optimal transportation problems on spatial grids as large as 4096 × 4096 and 384 × 384 × 384 in a matter of minutes. [ABSTRACT FROM AUTHOR]

We propose a variational finite volume scheme to approximate the solutions to Wasserstein gradient flows. The time discretization is based on an implicit linearization of the Wasserstein distance expressed thanks to Benamou–Brenier formula, whereas space discretization relies on upstream mobility two-point flux approximation finite volumes. The scheme is based on a first discretize then optimize approach in order to preserve the variational structure of the continuous model at the discrete level. It can be applied to a wide range of energies, guarantees non-negativity of the discrete solutions as well as decay of the energy. We show that the scheme admits a unique solution whatever the convex energy involved in the continuous problem, and we prove its convergence in the case of the linear Fokker–Planck equation with positive initial density. Numerical illustrations show that it is first order accurate in both time and space, and robust with respect to both the energy and the initial profile. [ABSTRACT FROM AUTHOR]

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 Γ -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 discrete transportation distance, which is known to coincide with underlying Markov semigroup, and test our results against a classical backward Euler discretization of this discrete heat flow. [ABSTRACT FROM AUTHOR]

We propose a primal-dual parallel proximal splitting method for solving domain decomposition problems for partial differential equations. The problem is formulated via minimization of energy functions on the subdomains with coupling constraints which model various properties of the solution at the interfaces. The proposed method can handle a wide range of linear and nonlinear problems, with flexible, possibly nonlinear, transmission conditions across the interfaces. Strong convergence in the energy spaces is established in this general setting, and without any additional assumption on the energy functions or the geometry of the problem. Several examples are presented. [ABSTRACT FROM AUTHOR]