Fast Eigenpairs Computation with Operator Adapted Wavelets and Hierarchical Subspace Correction

Hehu Xie, Lei Zhang, Houman Owhadi

TL;DR

This paper introduces a novel algorithm for the fast computation of eigenvalues and eigenvectors (eigenpairs) of complex, multiscale operators. By combining "gamblets"—operator-adapted wavelets derived from game theory—with a hierarchical subspace correction method, the authors achieve near-linear computational complexity even for challenging problems like elliptic PDEs with extremely rough or oscillatory coefficients.

What Problem Does This Paper Address?

Solving large-scale eigenvalue problems is a cornerstone of modern science, from quantum mechanics to structural engineering. However, when the underlying operator has "rough" coefficients (i.e., properties that change rapidly or unpredictably across different scales), standard numerical methods often hit a wall.

Traditional solvers like Krylov subspace methods or standard multigrid iterations rely on certain "regularity" assumptions—essentially, that the solution is smooth enough. When these assumptions fail due to multiscale features (like the complex porous structures in oil reservoirs or disordered potentials in physics), convergence slows to a crawl. The challenge is to find a way to decompose these complex operators into a hierarchy of simpler problems without losing the essential multiscale information.

Methods

The authors propose a two-part strategy:

  1. Gamblet Decomposition: They use "gamblets" (operator-adapted wavelets). Unlike standard wavelets, gamblets are constructed using a game-theoretic approach to "know" about the specific operator $\mathcal{L}$. They provide a multiresolution decomposition that is scale-orthogonal and well-conditioned. This allows the operator to be represented as a series of sparse, block-diagonal matrices, effectively "untangling" the coupled scales.
  2. Hierarchical Subspace Correction: Instead of solving the massive eigenvalue problem all at once, the algorithm starts by solving a small, coarse-scale version of the problem. It then "corrects" these initial estimates by moving up a hierarchy of finer gamblet subspaces. At each step, the non-linear eigenvalue problem is approximated by solving a sequence of linear systems using a gamblet-based multigrid solver.

This approach effectively transforms a difficult global eigenvalue problem into a series of much easier, localized linear solves.

Datasets

The method was evaluated on several high-contrast, multiscale benchmarks:

  • SPE10 Benchmark: A standard dataset from the Society of Petroleum Engineers used to model highly heterogeneous oil reservoirs. It features a contrast ratio (the ratio between highest and lowest permeability) of $10^6$.
  • Random Checkerboard: A synthetic problem where coefficients vary randomly between 20 and 1/20 at a very small scale, creating a highly oscillatory environment.
  • Anderson Localization: A problem involving the Schrödinger operator with a disordered potential, used to study how waves localize in random media.

Key Insights and Ideas

  • Operator Adaptation is Key: Standard basis functions (like sines/cosines or standard finite elements) don't "see" the rough coefficients of the PDE. Gamblets are built from the operator, meaning they naturally capture the multiscale physics.
  • Linearizing the Eigenvalue Problem: The hierarchical correction method shows that you don't need to solve a full eigenvalue problem at every scale. Solving linear systems (which is much faster) is sufficient to "correct" the coarse eigenpairs as you move to finer resolutions.
  • Near-Linear Complexity: The authors prove that the total cost scales as $O(N \text{polylog } N)$, where $N$ is the number of degrees of freedom. This is the "gold standard" for efficiency in numerical analysis.

Key Results

  • Speedup: In the SPE10 test, the gamblet-based method achieved a ten-fold acceleration in CPU time compared to ARPACK (a standard industry-strength solver).
  • Precision: The method successfully converged to a relative error of $10^{-14}$ for the first 12 eigenvalues within just 70 outer iterations. In contrast, geometric multigrid methods failed to reach this level of accuracy even after 800 iterations.
  • Robustness: The algorithm remained stable and efficient across all tested scenarios, including those with extreme coefficient contrasts and high oscillations where traditional preconditioning often fails.

Limitations and Future Work

  • Precomputation Cost: The "offline" phase (constructing the gamblets) can be computationally expensive. While the "online" phase (solving for eigenpairs) is incredibly fast, the total time is only advantageous if the operator is reused or if the problem is sufficiently large.
  • Implementation Complexity: Constructing gamblets is mathematically and algorithmically more involved than using standard finite elements or wavelets.
  • Future Directions: The authors suggest extending this framework to non-symmetric operators and exploring its application in real-time structural health monitoring and more complex quantum chemistry simulations.

Summary updated

Abstract

We present a method for the fast computation of the eigenpairs of a bijective positive symmetric linear operator $\mathcal{L}$. The method is based on a combination of operator adapted wavelets (gamblets) with hierarchical subspace correction. First, gamblets provide a raw but fast approximation of the eigensubspaces of $\mathcal{L}$ by block-diagonalizing $\mathcal{L}$ into sparse and well-conditioned blocks. Next, the hierarchical subspace correction method computes the eigenpairs associated with the Galerkin restriction of $\mathcal{L}$ to a coarse (low-dimensional) gamblet subspace and then corrects those eigenpairs by solving a hierarchy of linear problems in the finer gamblet subspaces (from coarse to fine, using multigrid iteration). The proposed algorithm is robust to the presence of multiple (a continuum of) scales and is shown to be of near-linear complexity when $\mathcal{L}$ is an (arbitrary local, e.g., differential) operator mapping $\mathcal{H}^s_0(\Omega)$ to $\mathcal{H}^{-s}(\Omega)$ (e.g., an elliptic PDE with rough coefficients).
BibTeX
@article{xie2019fast,
  author = {Hehu Xie and Lei Zhang and Houman Owhadi},
  title = {{Fast Eigenpairs Computation with Operator Adapted Wavelets and Hierarchical Subspace Correction}},
  journal = {SIAM J. Numer. Anal.},
  year = {2019},
  url = {https://openreview.net/forum?id=IymIXhVmX_},
}

Loading related content...

Figure