A multigrid scheme for 3D Monge-Ampère equations

Jun Liu, Brittany D. Froese, Adam M. Oberman, Mingqing XiaoInt. J. Comput. Math 2017 · OpenReview

TL;DR

This paper introduces a novel multigrid algorithm for efficiently solving the 3D Monge-Ampère equation, a challenging nonlinear PDE crucial in fields like medical imaging and optimal transport. Their method combines a specialized nonlinear Gauss-Seidel smoother with a Full Approximation Scheme (FAS) multigrid framework, achieving linear time complexity and outperforming existing solvers.

What Problem Does This Paper Address?

The Monge-Ampère equation, a fully nonlinear elliptic partial differential equation, is gaining traction in various scientific and engineering applications. However, solving it in three dimensions, especially for smooth solutions, has been computationally demanding, lacking fast and scalable solvers. Existing methods often struggle with the equation's nonlinearity and the crucial constraint of ensuring a convex solution, which is necessary for uniqueness. This paper aims to bridge this gap by developing an efficient, fast, and scalable multigrid solver for the 3D Monge-Ampère equation.

Methods

The core of this work is a nonlinear Full Approximation Scheme (FAS) multigrid method. The key innovations lie in:

  • Second-order Finite Difference Discretization: A standard centered finite difference scheme is used to discretize the Monge-Ampère equation.
  • Nonlinear Gauss-Seidel Smoother with Convexity Selection: A crucial component is a nonlinear Gauss-Seidel iteration that explicitly addresses the challenge of selecting the correct, convex solution. This is achieved by solving a cubic equation at each grid point and selecting the smallest real root, which is proven to correspond to the discretely convex solution. This is a significant improvement over methods that might converge to non-convex solutions.
  • FAS Multigrid Framework: The nonlinear Gauss-Seidel smoother is integrated into a standard FAS multigrid algorithm. This framework efficiently handles the nonlinearities by using coarse grids for correction and a recursive V-cycle structure.
  • Full Multigrid (FMG) Initialization: For further efficiency, a Full Multigrid (FMG) approach is employed to generate a good initial guess for the finest grid problem, reducing the number of V-cycle iterations needed for convergence.

Datasets

Not discussed in the paper. The paper focuses on numerical methods and uses synthetic examples with known analytical solutions for testing.

Key Insights and Ideas

  • Convexity is Key: The paper highlights that enforcing convexity is not just a theoretical requirement but a practical necessity for obtaining the correct, unique solution to the Monge-Ampère equation, especially at the discrete level.
  • Cubic Root Selection for Convexity: The novel approach of solving a cubic equation and selecting the smallest real root is a clever way to ensure discrete convexity, a challenge that simpler quadratic root selection (used in 2D) doesn't directly address in 3D.
  • Gauss-Seidel as a Powerful Smoother: The nonlinear Gauss-Seidel iteration, while slow as a standalone solver, proves to be an excellent smoother for the FAS multigrid method, effectively damping high-frequency errors.
  • FMG-FAS for Efficiency: Combining FMG initialization with the FAS V-cycle significantly boosts computational efficiency, leading to a method that scales well with problem size.

Key Results

  • Linear Time Complexity: The proposed FMG-FAS multigrid method demonstrates a computational cost that scales approximately linearly with the number of grid points.
  • Speedup: For a 128³ grid, the method achieves solutions in under three minutes on a laptop, a significant improvement over previous approaches.
  • Accuracy: The method achieves second-order accuracy for smooth solutions, comparable to existing methods, and shows reasonable accuracy even for mildly singular solutions.
  • Robustness: The algorithm is shown to be effective across various examples, including those with singularities, and consistently outperforms standalone Gauss-Seidel solvers.

Limitations and Future Work

  • Degenerate Cases: The current method breaks down for degenerate cases where the right-hand side function $f(x) = 0$, as this leads to a loss of uniform ellipticity and requires wide-stencil finite difference methods for guaranteed convergence to weak solutions.
  • Singular Solutions: While the method shows reasonable accuracy for mildly singular solutions, more complex singular cases might require further refinement or alternative approaches.
  • Future Directions: The authors suggest extending the method to filtered almost-monotone finite difference schemes to handle singular solutions more robustly. They also propose applying the method to the Optimal Transportation problem and parameter identification problems.

Summary updated

Abstract

The elliptic Monge–Ampère equation is a fully nonlinear partial differential equation which has been the focus of increasing attention from the scientific computing community. Fast three-dimensiona...
BibTeX
@article{liu2017multigrid,
  author = {Jun Liu and Brittany D. Froese and Adam M. Oberman and Mingqing Xiao},
  title = {{A multigrid scheme for 3D Monge-Ampère equations}},
  journal = {Int. J. Comput. Math.},
  year = {2017},
  url = {https://openreview.net/forum?id=9FQw26qzyS},
}
Figure