Abstract
This paper presents a novel numerical framework for the efficient computation of eigenpairs of bijective positive symmetric linear operators $\mathcal{L}$. The core of the approach lies in the synergy between operator-adapted wavelets, termed "gamblets," and a hierarchical subspace correction strategy. Gamblets facilitate a multiresolution decomposition that effectively block-diagonalizes the operator into sparse, well-conditioned segments. The hierarchical correction then solves the eigenvalue problem on a coarse gamblet subspace and iteratively refines the solution across finer scales using multigrid-like linear solves. This method demonstrates near-linear complexity $O(N \text{polylog } N)$ and maintains robustness even in the presence of highly heterogeneous or rough coefficients, such as those found in elliptic PDEs with multiscale features.
The Challenge of Multiscale Eigenvalue Problems
Large-scale eigenvalue problems are fundamental to diverse fields, including quantum chemistry, structural mechanics, and geophysics. However, standard numerical solvers often struggle when the underlying operator $\mathcal{L}$ possesses "rough" coefficients—properties that vary significantly across multiple spatial scales.
Traditional methods like Krylov subspace iterations or geometric multigrid rely on regularity assumptions that are violated by such multiscale features. In these scenarios, convergence rates typically deteriorate, leading to prohibitive computational costs. The challenge is to find a way to decompose these complex operators into a hierarchy of simpler problems without losing essential multiscale information. The goal is a solver that remains efficient and robust regardless of the coefficient contrast or the complexity of the scales.
Methods: Gamblets and Hierarchical Correction
The proposed algorithm addresses these challenges through two primary components: Gamblet Decomposition and Hierarchical Subspace Correction.
1. Gamblet Decomposition
Gamblets are operator-adapted wavelets constructed through a game-theoretic framework. Unlike standard wavelets (e.g., Daubechies), gamblets are intrinsically linked to the operator $\mathcal{L}$. They provide a multiresolution decomposition of the solution space that is scale-orthogonal with respect to the energy norm induced by $\mathcal{L}$. This adaptation ensures that the operator, when represented in the gamblet basis, becomes nearly block-diagonal with sparse and well-conditioned blocks. This "untangling" of scales is crucial for handling rough coefficients.
2. Hierarchical Subspace Correction
The algorithm avoids solving the full, high-dimensional eigenvalue problem directly. Instead, it employs a hierarchical approach:
- Coarse Solve: The problem is first solved on a low-dimensional coarse gamblet subspace to obtain initial eigenpair estimates.
- Fine Correction: These estimates are then corrected by moving up the hierarchy to finer subspaces. At each level, the non-linear eigenvalue problem is approximated by solving a sequence of linear systems. These linear systems are solved efficiently using a gamblet-based multigrid iteration.
This strategy transforms a global, non-linear eigenvalue problem into a series of localized, linear sub-problems, significantly reducing the computational burden.
Key Results and Benchmarks
The effectiveness of the method was demonstrated on several challenging benchmarks:
- SPE10 Reservoir Model: A highly heterogeneous dataset with a permeability contrast of $10^6$. The gamblet-based method achieved a ten-fold acceleration in CPU time compared to ARPACK, a standard industry-strength solver.
- Random Checkerboard: A synthetic test with high-frequency oscillations. The method reached a relative error of $10^{-14}$ in just 70 outer iterations, while geometric multigrid failed to reach this level of accuracy even after 800 iterations.
- Anderson Localization: The algorithm successfully captured localized modes in Schrödinger operators with disordered potentials, demonstrating stability where traditional preconditioning often fails.
Conclusion and Future Work
By integrating operator-adapted wavelets with hierarchical correction, this research provides a powerful tool for multiscale eigenvalue problems. The near-linear complexity and robustness to high-contrast coefficients make it a promising candidate for large-scale scientific simulations. While the precomputation cost of constructing gamblets is a factor, the speedup in the solution phase is substantial for large problems. Future work will focus on extending the method to non-symmetric operators and exploring applications in real-time structural health monitoring.
Summary updated