Source-linked AI summary
Convergent finite difference solvers for viscosity solutions of the elliptic Monge-Ampère equation in dimensions two and higher
Brittany D. Froese, Adam M. Oberman
TL;DR
The paper addresses numerical solution of the elliptic Monge-Ampère equation when singular solutions make standard methods unreliable. It introduces a monotone wide-stencil discretization with Newton’s method, proves convergence, and evaluates the solver in two and three dimensions on solutions ranging from smooth to non-differentiable.
Problem
Singular Monge-Ampère solutions can cause standard numerical methods to become unstable, poorly conditioned, or select non-convex solutions.
Method
The paper combines a monotone wide-stencil finite-difference discretization with Newton’s method and proves convergence of both the scheme and the nonlinear solver.
Results
The solver is presented for two- and three-dimensional exact solutions spanning smooth to non-differentiable regularity, with reported improvements in solution time and stability.
Takeaways & Limitations
The resulting solver applies in general dimensions to both regular and singular solutions, with slightly better accuracy on singular solutions but lower accuracy than standard finite differences on smooth solutions.
Takeaways & Limitations
For highly singular solutions, directional-resolution error from the wide stencil can dominate the accuracy.
Abstract
from arXiv · showhide
The elliptic Monge-Ampère equation is a fully nonlinear Partial Differential Equation that originated in geometric surface theory and has been applied in dynamic meteorology, elasticity, geometric optics, image processing and image registration. Solutions can be singular, in which case standard numerical approaches fail. Novel solution methods are required for stability and convergence to the weak (viscosity) solution. In this article we build a wide stencil finite difference discretization for the \MA equation. The scheme is monotone, so the Barles-Souganidis theory allows us to prove that the solution of the scheme converges to the unique viscosity solution of the equation. Solutions of the scheme are found using a damped Newton's method. We prove convergence of Newton's method and provide a systematic method to determine a starting point for the Newton iteration. Computational results are presented in two and three dimensions, which demonstrates the speed and accuracy of the method on a number of exact solutions, which range in regularity from smooth to non-differentiable.
1. Introduction
The paper develops a monotone finite-difference discretization for the elliptic Monge-Ampère equation, targeting singular solutions through viscosity-solution theory. It addresses the limitations of existing numerical methods while covering general dimensions and several applications.
- The paper introduces a monotone discretization valid in arbitrary dimensions and proves convergence to the viscosity solution.The equation is fully nonlinear, and the discretization is designed for the Dirichlet setting considered in the paper.
- Convexity is required for ellipticity, uniqueness, stability, and selecting the physically relevant solution.The paper builds the convexity selection principle into the discretization or solution method.
- Singular Monge-Ampère solutions require weak-solution concepts and specialized discretizations because standard numerical methods can become unstable, poorly conditioned, or select non-convex solutions.The paper focuses on viscosity solutions and incorporates convexity into the numerical approach.
- The equation has applications in geometric problems, optimal transport, dynamic meteorology, elasticity, geometric optics, image registration, mesh generation, reflector design, and astrophysics.In optimal transport, the optimal mapping is represented as g = ∇u with convex u satisfying the Monge-Ampère equation.
- Existing numerical methods vary by boundary condition and often perform best for regular solutions, while methods for singular solutions were previously restricted to two dimensions.The paper distinguishes standard Dirichlet problems from optimal-transport-type, periodic, and other boundary conditions.
2. Analysis and weak solutions
The paper reviews classical and weak solution concepts for the elliptic Monge–Ampère equation, emphasizing convexity, regularity loss, and viscosity/Aleksandrov formulations. It also relates ellipticity and linearization to convexity.
- Regularity: Classical C2,α solvability requires a strictly convex domain, C2,α boundary data, and strictly positive f.
- Regularity: When f vanishes identically, solutions may lose boundary continuity and interior differentiability.
- Viscosity solutions: A viscosity solution is both a viscosity subsolution and supersolution, defined using convex C2 test functions.
- Viscosity solutions: The paper’s example is a viscosity solution but not a classical C2 solution, with verification focused where the solution is nonsmooth.
- Aleksandrov solutions: Aleksandrov solutions allow f to be a nonnegative measure and are characterized by equality between the associated Monge–Ampère measure and that measure.
- Convexity and ellipticity: Convexity is necessary for uniqueness and ellipticity; the linearized operator is elliptic for strictly convex u but may become degenerate or unstable otherwise.
3. Convergent discretization of the Monge-Amp`ere equation
The paper constructs a monotone wide-stencil discretization valid in two and higher dimensions, regularizes it for Newton solves, and proves convergence to the viscosity solution. Directional resolution and singular solutions govern important accuracy limitations.
- Contributions: The proposed discretization extends monotone Monge–Ampère schemes to arbitrary dimensions and supports convergence proofs for both the scheme and Newton’s method.
- Motivation: Standard finite differences can produce multiple solutions, instability, and non-convex selections because they do not enforce convexity.
- Wide-stencil construction: A determinant characterization using orthogonal directions enables a monotone wide-stencil discretization in higher dimensions.
- Wide-stencil construction: The scheme approximates second directional derivatives with centered differences over grid directions, using interpolation near boundaries when stencil points are unavailable.
- Accuracy: Directional resolution error decreases with wider stencils but can dominate for singular solutions.
- Regularization and convergence: Regularizing max and min produces a differentiable, monotone operator suitable for Newton’s method while preserving convergence as h, dθ, and δ approach zero.
4. A semi-implicit solution method
The paper develops iterative solvers for the nonlinear discrete system, using explicit and semi-implicit schemes to obtain an initial value for Newton’s method. Explicit iterations are simple but constrained by a small stability-limited time step.
- Newton initialization: Newton’s method requires a good initial value, motivating a semi-implicit iteration for initialization.
- Explicit method: The explicit fixed-point iteration is an ℓ∞ contraction when dt is sufficiently small and corresponds to forward Euler time stepping.
- Explicit method: The explicit method is slow because stability requires dt = O(h2), so the time step decreases with spatial resolution.
- Semi-implicit method: The semi-implicit method solves a Poisson equation at each iteration.
- Semi-implicit method: A higher-dimensional semi-implicit scheme is derived by expressing the Laplacian through Hessian eigenvalues and expanding its d-th power.
5. Newton’s method
The paper regularizes a monotone Monge–Ampère discretization so damped Newton iteration remains usable for singular solutions. Under stated assumptions, the regularized scheme has an invertible Jacobian and Newton’s method converges quadratically, with a low-cost initialization strategy.
- The regularized scheme is designed so that Newton’s method can compute even singular solutions.
- Newton’s method for the regularized discretized system converges quadratically when the PDE has a unique viscosity solution.
- The proof uses smoothness, Lipschitz continuity of the Jacobian, and nonsingularity at the solution to invoke the standard Newton convergence result.
- The monotone operator yields positive definite coefficient matrices, making the Jacobian negative definite and invertible.
- Initialization combines one semi-implicit step, consistent boundary conditions, and optional convexification on a coarse grid before interpolation.
- Regularizing second directional derivatives ensures a strictly negative definite linear operator without changing Newton fixed points.The computations use ϵ = 1/2 dx^2 × 10^-8.
6. Computational results in two dimensions.
Two-dimensional experiments test the monotone scheme and Newton solver on exact solutions ranging from smooth to Lipschitz continuous. Newton is faster than the compared iterations, while accuracy depends on regularity and stencil width.
- Newton’s solver is faster in absolute solution time than the Gauss-Seidel and Poisson methods for every representative example.
- The experiments use four representative exact solutions spanning smooth, C1, boundary-gradient-singular, and Lipschitz-continuous cases.
- The computed gradient maps agree with those obtained from the exact solution gradients.
- Newton’s solution-time order is independent of solution regularity and is roughly O(M^1.3).
- Wider stencils and finer grids improve monotone-scheme accuracy by reducing directional-resolution and spatial-discretization errors.
- Standard finite differences are more accurate on the two regular examples, whereas monotone finite differences are slightly more accurate on the two singular examples.
7. Computational results in three dimensions
Three-dimensional experiments evaluate the method with a 19-point stencil on exact solutions of varying regularity. The two-dimensional comparison methods are unavailable in three dimensions, so the section reports standalone computation-time and accuracy results.
- The three-dimensional computations use a 19-point stencil on an N^3 grid over [0,1]^3.
- The Gauss-Seidel and Poisson methods cannot provide a three-dimensional comparison because the referenced methods were restricted to two dimensions.
- Three representative exact solutions include C2, C1, and boundary-gradient-singular cases.
- Computation times and accuracy results are reported for the three-dimensional examples.
8. Conclusions
The paper presents a fast, convergent finite difference solver for the elliptic Monge–Ampère equation, with a monotone discretization valid in arbitrary dimensions and convergence guarantees. Numerical tests cover exact solutions from smooth to non-differentiable regularity, while the solver improves speed and stability across regular and singular cases.
- A monotone discretization valid in arbitrary dimensions converges to the unique viscosity solution.
- The discretized equations are solved with Newton’s method, whose convergence is proved and whose observed complexity is O(M 1.3).M denotes the number of data points.
- A low-cost initialization procedure combines one step of a previously established method with the convex envelope as needed.
- The solver is significantly faster and more stable than existing methods for both regular and singular solutions.
- Accuracy is lower than standard finite differences on smooth solutions but slightly better on singular solutions.