Local multilevel preconditioners for elliptic equations with jump coefficients on bisection grids

Long Chen, Michael Holst, Jinchao Xu, Yunrong Zhu

TL;DR

This paper introduces novel local multilevel preconditioners for solving elliptic partial differential equations with highly discontinuous coefficients on adaptively refined grids (specifically, bisection grids). These new methods achieve nearly optimal computational complexity by ensuring that the convergence rate of the preconditioned conjugate gradient method is largely independent of the coefficient jumps and only logarithmically dependent on the mesh size.

What Problem Does This Paper Address?

Solving elliptic partial differential equations (PDEs) with highly discontinuous coefficients (e.g., material properties that change drastically across interfaces) is a significant challenge in scientific computing. These discontinuities lead to ill-conditioned systems when discretized using finite element methods, severely degrading the performance of standard iterative solvers and multilevel methods. This problem is common in various applications like groundwater flow, electromagnetics, and semiconductor modeling. While methods for uniform grids exist, adapting them to locally refined grids (which are often necessary for capturing complex solution features efficiently) introduces further difficulties, particularly in maintaining optimal computational complexity. This paper aims to bridge this gap by developing robust and efficient multilevel preconditioners for these challenging problems on adaptively refined bisection grids.

Methods

The core of this work lies in the design and analysis of "local multilevel preconditioners." Unlike traditional global methods, these preconditioners employ local smoothing operations, focusing only on newly added nodes and their immediate neighbors in the bisection refinement process. This local approach is crucial for maintaining efficiency on adaptively refined grids where the structure of nested meshes can become complex.

Key techniques include:

  • Local Quasi-Interpolation: A novel local interpolation operator is introduced to analyze the approximation and stability properties of the finite element space on these locally refined grids. This operator is designed to be stable and robust with respect to coefficient jumps, unlike global projections.
  • Stable Space Decomposition: A hierarchical decomposition of the finite element space is established, which is essential for the analysis of the multilevel preconditioners. This decomposition is shown to be stable and allows for the separation of "high-frequency" components related to local refinements.
  • BPX and Multigrid V-cycle Preconditioners: The paper constructs and analyzes two types of local multilevel preconditioners: an additive BPX preconditioner and a multiplicative V-cycle multigrid preconditioner. These are built upon the local interpolation and space decomposition.
  • Eigenvalue Analysis: A rigorous analysis of the eigenvalue distribution of the preconditioned systems is performed. This analysis demonstrates that only a small, fixed number of eigenvalues are significantly affected by the coefficient jumps and mesh size, while the majority remain well-behaved.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and numerical experiments on model problems.

Key Insights and Ideas

  • Locality is Key for Adaptivity: The paper strongly emphasizes that for adaptive mesh refinement, local operations are paramount. Global operations, while effective on uniform grids, break down or lose efficiency on complex, locally refined meshes.
  • Controlled Eigenvalue Degradation: The most significant insight is that despite large coefficient jumps and local mesh refinement, the "bad" eigenvalues (those that slow down convergence) are limited in number. This is a crucial theoretical result that underpins the robustness of the proposed methods.
  • Bridging Uniform and Local Refinement: The work successfully extends the theory of robust multilevel methods from uniform grids to the more challenging setting of locally refined bisection grids, a significant step for practical adaptive finite element methods.
  • Logarithmic Dependence on Mesh Size is Acceptable: While perfect uniformity with respect to mesh size is not achieved, a logarithmic dependence is considered a near-optimal outcome, especially given the complexity of the problem.

Key Results

  • Robust Convergence: The proposed local multilevel preconditioners (BPX and V-cycle) lead to preconditioned conjugate gradient (PCG) algorithms whose convergence rate is independent of the magnitude of coefficient jumps and only logarithmically dependent on the mesh size.
  • Nearly Optimal Complexity: The overall computational complexity of the proposed methods is shown to be nearly optimal, meaning it scales efficiently with the problem size.
  • Theoretical Guarantees: The paper provides theoretical proofs for the approximation and stability properties of the local interpolation operator and the stable space decomposition, which are foundational for the convergence analysis.
  • Numerical Validation: Numerical experiments demonstrate that the proposed methods (TPSMGCG and TPSBPXCG) exhibit robust convergence behavior, with the number of iterations growing much slower than traditional methods as the mesh is refined or coefficient jumps increase.

Limitations and Future Work

  • "Worst-Case" Estimates: The paper notes that the derived estimates are for the "worst case." In specific scenarios (e.g., "edge type" or "quasi-monotone" coefficients), the convergence can be further improved.
  • 3D Challenges: While the theory is presented for both 2D and 3D, the paper acknowledges that 3D problems with discontinuous coefficients are significantly more challenging, and the hierarchical basis methods can deteriorate rapidly. The proposed local methods aim to mitigate this, but the analysis for 3D might still be more complex.
  • Future Work: The paper suggests that further improvements might be possible by modifying the decomposition or smoothers for specific coefficient distributions, as hinted at by Remark 5.3. The numerical experiments also suggest that the constant factors in the convergence estimates can be improved, which could be a direction for future research.

Summary updated

Abstract

The goal of this paper is to design optimal multilevel solvers for the finite element approximation of second order linear elliptic problems with piecewise constant coefficients on bisection grids. Local multigrid and BPX preconditioners are constructed based on local smoothing only at the newest vertices and their immediate neighbors. The analysis of eigenvalue distributions for these local multilevel preconditioned systems shows that there are only a fixed number of eigenvalues which are deteriorated by the large jump. The remaining eigenvalues are bounded uniformly with respect to the coefficients and the meshsize. Therefore, the resulting preconditioned conjugate gradient algorithm will converge with an asymptotic rate independent of the coefficients and logarithmically with respect to the meshsize. As a result, the overall computational complexity is nearly optimal.
BibTeX
@inproceedings{chen2012local,
  author = {Long Chen and Michael Holst and Jinchao Xu and Yunrong Zhu},
  title = {{Local multilevel preconditioners for elliptic equations with jump coefficients on bisection grids}},
  booktitle = {Comput. Vis. Sci},
  year = {2012},
  url = {https://openreview.net/forum?id=BteAUhZEHJ},
}
Figure