A nearly optimal multigrid method for general unstructured grids

Lars Grasedyck, Lu Wang, Jinchao XuNumerische Mathematik 2016 · DOI

TL;DR

This paper introduces a novel multigrid method for solving partial differential equations on general unstructured grids. It achieves nearly optimal complexity by constructing an auxiliary grid hierarchy using a cluster tree, leading to efficient preconditioning for finite element methods.

What Problem Does This Paper Address?

Solving partial differential equations (PDEs) often involves discretizing them into large systems of linear equations. Multigrid (MG) methods are highly efficient for these systems, but traditional geometric multigrid (GMG) relies on a hierarchy of nested grids, which is not always readily available for unstructured meshes. While algebraic multigrid (AMG) methods exist, they can lack solid theoretical guarantees. This paper addresses the challenge of developing an efficient and theoretically sound multigrid method for general shape-regular unstructured grids, where a natural grid hierarchy is not given. The goal is to achieve a nearly optimal complexity of O(N log N) for solving these systems.

Methods

The core of the proposed method is the construction of an auxiliary grid hierarchy. This is achieved by first building a "cluster tree" based on the geometric information of the original unstructured grid. This tree is then used to define a structured hierarchy of auxiliary grids. A key technique is the "auxiliary space preconditioning" approach, where a multigrid method is applied to these auxiliary grids. This auxiliary space is not necessarily a subspace of the original finite element space, but a suitable transfer operator connects them. The paper also details a "closure operation" to ensure the auxiliary grids are conforming and nested, and a "near boundary correction" to handle boundary approximation errors. The theoretical analysis relies on abstract multigrid theory, verifying assumptions related to smoother boundedness, transfer operator properties, and the optimality of the preconditioner on the auxiliary space.

Datasets

Not discussed in the paper. The paper focuses on a theoretical framework and numerical experiments on a model problem (Poisson equation on a unit square) and a more complex geometry (Baltic Sea).

Key Insights and Ideas

  • Cluster Tree for Hierarchy Construction: The paper introduces a novel way to generate a structured grid hierarchy from unstructured data using a cluster tree, which is crucial for applying multigrid principles.
  • Auxiliary Space Preconditioning: The method leverages auxiliary spaces that are not direct subspaces of the original finite element space, offering flexibility in constructing efficient preconditioners.
  • Bridging Geometric and Algebraic Ideas: The approach attempts to combine the theoretical rigor of geometric multigrid with the flexibility of handling unstructured grids, drawing inspiration from algebraic multigrid concepts.
  • Near Boundary Correction: The explicit inclusion of a near-boundary correction step highlights the importance of handling boundary effects accurately, especially when grid levels don't perfectly align with the domain boundary.

Key Results

The paper proves that the proposed multigrid method achieves a convergence rate of $1 - O(1/\log N)$ for elliptic PDEs. Numerical experiments confirm this theoretical bound, demonstrating a total complexity of $O(N \log N)$. For a benchmark problem (Poisson equation on the Baltic Sea with local refinement), the ASMG method shows competitive performance with geometric multigrid, with storage requirements increasing by at most a factor of 3 and solve times by at most a factor of 2.

Limitations and Future Work

The paper acknowledges that the construction of auxiliary grids might require more technical assumptions if Assumption 1 (regarding the algebraic grading of the grid) is not met. The authors suggest that the presented algorithm and theory can be generalized to three-dimensional cases by using octrees instead of quadtrees. Future work could explore the application of this method to a wider range of PDEs and more complex geometries.

Summary updated

BibTeX
@article{grasedyck2016nearly,
  author = {Lars Grasedyck and Lu Wang and Jinchao Xu},
  title = {{A nearly optimal multigrid method for general unstructured grids}},
  journal = {Numerische Mathematik},
  year = {2016},
  doi = {10.1007/s00211-015-0785-7},
}

Loading related content...

Figure