Fast Bellman algorithm for real Monge-Ampere equation
This work addresses a computational bottleneck in solving non-linear PDEs for researchers in numerical analysis and applied mathematics, offering a significant speed improvement over current methods.
The paper tackles the Dirichlet problem for the real Monge-Ampere equation by introducing a new numerical algorithm that represents the operator as an infimum of linear elliptic operators and uses Bellman's principle, resulting in faster running times by factors of 3-10 for smooth cases and 20-100 for degenerate ones compared to existing methods.
In this paper, we introduce a new numerical algorithm for solving the Dirichlet problem for the real Monge--Ampere equation. The idea is to represent the non-linear Monge--Ampere operator as an infimum of a class of linear elliptic operators and use Bellman's principle to construct a numeric scheme for approximating the operator attaining this infimum. Moreover, we prove convergence of the proposed algorithm (under suitable technical assumptions) and discuss its strengths and weaknesses. We also demonstrate the performance of the method on several examples with various degrees of regularity and degeneracy and compare the results to two existing methods. Our method runs considerably faster than the ones used for comparison, improving the running time by a factor of 3--10 for smooth, strictly convex examples, and by a factor of 20--100 or more for mildly degenerate examples.