A Bootstrap Multigrid Eigensolver

James J. Brannick, Shuhao CaoSIAM J. Matrix Anal. Appl 2015 · OpenReview

TL;DR

This paper introduces a novel "bootstrap multigrid" (BMG) method for efficiently solving eigenvalue problems that arise from discretizing partial differential equations, particularly focusing on the challenging Laplace-Beltrami operator on surfaces. The BMG approach adapts existing algebraic multigrid ideas to a geometric setting, enabling accurate computation of eigenvalues with large multiplicity and interior eigenvalues, which are often difficult for traditional methods.

What Problem Does This Paper Address?

Solving eigenvalue problems derived from discretizing partial differential equations (PDEs) is a fundamental task in many scientific and engineering fields. However, these problems can become computationally intractable, especially when dealing with:

  • Large multiplicities: Eigenvalues can have many corresponding eigenfunctions, making it hard to capture the entire eigenspace.
  • Interior eigenvalues: Finding eigenvalues that are not at the extreme ends of the spectrum (smallest or largest) is particularly challenging.
  • Complex geometries: Discretizing problems on curved surfaces (like the Laplace-Beltrami operator on a sphere) introduces geometric complexities and non-nested meshes, complicating standard multigrid approaches.

Existing methods like standard two-grid solvers can suffer from a "loss of spectra" or require excessively fine coarse meshes to accurately capture these challenging eigenvalues. This paper aims to bridge this gap by developing a more robust and efficient multigrid eigensolver.

Methods

The core of this paper is the development of a Bootstrap Multigrid (BMG) eigensolver. This method is inspired by the Bootstrap Algebraic Multigrid (BAMG) framework but adapted for a geometric setting. Key aspects include:

  • Geometric Multigrid Foundation: The approach leverages the structure of the discretized PDE and the underlying geometry, unlike purely algebraic methods.
  • Enriched Coarse Spaces: The BMG method iteratively enriches the coarse spaces with approximations of eigenfunctions computed on finer meshes. This "bootstrap" process allows the coarse space to adapt and better represent the solution.
  • Adaptation of BAMG: The paper simplifies the BAMG setup algorithm by explicitly using the finite element discretization to define the multilevel structure, including interpolation and restriction operators.
  • Two-Grid and Multigrid Variants: The paper presents both a two-grid BMG algorithm and a full multigrid V-cycle variant.
  • Shifted and Indefinite Systems: The method is designed to handle shifted and indefinite eigenvalue problems, which are crucial for finding interior eigenvalues.
  • Surface Finite Element Method (SFEM): The Laplace-Beltrami eigenvalue problem on a 2-sphere is used as a model problem, employing SFEM for discretization.

Datasets

Not discussed in the paper. The paper focuses on a theoretical framework and numerical experiments using a standard benchmark problem (Laplace-Beltrami operator on a 2-sphere).

Key Insights and Ideas

  • Enrichment is Key: The core idea is that enriching the coarse space with approximations of eigenfunctions from finer levels is crucial for accurately capturing eigenvalues with large multiplicity and interior eigenvalues. This adaptive enrichment allows the coarse space to "learn" the relevant solution modes.
  • Geometric Structure Matters: By explicitly using the geometric information from the PDE discretization, the BMG method can be more efficient and robust than purely algebraic approaches, especially for problems with complex geometries.
  • Simplification of BAMG: Adapting the BAMG framework to a geometric setting simplifies its implementation and allows for a more direct use of finite element structures.
  • Handling Interior Eigenvalues: The BMG approach, particularly with the use of shifts, provides a viable strategy for computing interior eigenvalues, which are notoriously difficult for standard multigrid eigensolvers.
  • Relaxation Suffices for Source Problems: The paper demonstrates that for the auxiliary "source" problems that arise in the BMG framework, using a few sweeps of a relaxation method (like Kaczmarz or Gauss-Seidel) is often sufficient, rather than requiring a full direct solve, significantly reducing computational cost.

Key Results

  • Accurate Eigenvalue Recovery: The BMG method successfully recovers eigenvalues with large multiplicity and interior eigenvalues, overcoming the "spectra loss" phenomenon observed in standard two-grid methods.
  • Optimal Convergence Rates: Numerical experiments show that the BMG approach achieves nearly optimal convergence rates, often close to O(h), for both eigenfunctions and eigenvalues, comparable to direct solvers but with significantly reduced computational cost.
  • Efficiency Gains: By replacing direct solves of auxiliary problems with iterative smoothers, the BMG method achieves substantial computational savings.
  • Robustness on Surfaces: The method is demonstrated to be effective for the Laplace-Beltrami eigenvalue problem on a 2-sphere, a challenging problem due to its geometry and high eigenvalue multiplicity.

Limitations and Future Work

  • Mesh Dependence: While the method is designed to be efficient, the convergence rates still depend on the mesh refinement strategy and the relationship between mesh sizes across levels (e.g., H ≤ h¹/⁴).
  • Choice of Enrichment Space: The dimension and selection of the enrichment space can influence performance. While the paper provides guidance, optimal choices might still require some tuning based on the problem's spectrum.
  • Future Work: The authors suggest that the BMG framework is applicable to a wider range of PDE eigenvalue problems beyond the Laplace-Beltrami operator. Further exploration of optimal strategies for selecting shifts and enrichment spaces for different problem types would be beneficial. The paper also hints at the potential for applying the BMG approach to symmetric indefinite problems like the Helmholtz equation.

Summary updated

Abstract

This paper introduces bootstrap multigrid methods for solving eigenvalue problems arising from the discretization of partial differential equations. Inspired by the full bootstrap algebraic multigrid setup algorithm that includes an AMG eigensolver, we illustrate how the algorithm can be simplified for the case of a discretized partial differential equation, thereby developing a bootstrap geometric multigrid (BMG) approach. We illustrate numerically the efficacy of the BMG method for (1) recovering eigenvalues having large multiplicity, (2) computing interior eigenvalues, and (3) approximating shifted indefinite eigenvalue problems. Numerical experiments are presented to illustrate the basic components and ideas behind the success of the overall bootstrap multigrid approach. For completeness, we present a simplified error analysis of a two-grid bootstrap algorithm for the Laplace–Beltrami eigenvalue problem.
BibTeX
@article{brannick2015bootstrap,
  author = {James J. Brannick and Shuhao Cao},
  title = {{A Bootstrap Multigrid Eigensolver}},
  journal = {SIAM J. Matrix Anal. Appl},
  year = {2015},
  url = {https://openreview.net/forum?id=4tVA7VGGEm},
}
Figure