Gamblets for opening the complexity-bottleneck of implicit schemes for hyperbolic and parabolic ODEs/PDEs with rough coefficients

Lei Zhang, Houman Owhadi, Lei Zhang 0027

Abstract

Implicit numerical schemes are essential for stable simulations of partial differential equations (PDEs), but they often face a computational bottleneck when dealing with rough coefficients, requiring the solution of massive linear systems at each time step. This paper presents a generalization of gamblets—operator-adapted multiresolution basis functions—to overcome this challenge. By leveraging a game-theoretic approach to numerical analysis, gamblets provide near-linear complexity ($O(N \text{polylog } N)$) for solving these systems. The framework is extended to handle complex-valued matrices for higher-order schemes and incorporates multi-time-stepping to further enhance efficiency.

Introduction

In many physical simulations, such as seismic wave propagation or heat transfer in composite materials, the underlying coefficients (e.g., wave speed or thermal conductivity) vary wildly across different scales. These "rough coefficients" pose a significant challenge for standard numerical methods. While implicit schemes are preferred for their numerical stability, they require solving a large linear system at every time step. Standard acceleration methods like classical multigrid or wavelets often fail in this context because they are not "aware" of the small-scale physics captured by the rough coefficients. This creates a complexity bottleneck where computational costs become prohibitive as resolution increases.

Methods

The authors address this bottleneck using Gamblets, which are derived from a Game Theoretic approach to Numerical Analysis. Unlike standard, fixed wavelets, gamblets are adapted to the specific PDE operator and time-step of the simulation.

  1. Operator-Adapted Basis: Gamblets are defined as the "optimal bet" (in a Bayesian sense) for the solution given limited information. This ensures the basis naturally captures the stiffness and multiscale nature of the PDE.
  2. Multiresolution Decomposition: The solution space is broken into a hierarchy of sub-bands. Because gamblets are scale-orthogonal with respect to the energy norm of the PDE, the resulting stiffness matrices are block-diagonal, allowing different frequency bands to be computed independently.
  3. Localization: A critical feature is that gamblets decay exponentially in space. This allows the truncation of computations to local subdomains, which is the key to achieving near-linear complexity.
  4. Complex Gamblets: For higher-order implicit schemes (like Radau IIA), the framework is extended to handle complex-valued matrices, maintaining localization and stability properties.
  5. Multi-time-stepping: The algorithm can utilize different time steps for different multiresolution sub-bands, further optimizing temporal computation.
Multiresolution decomposition using gamblets, showing the hierarchy of basis functions and transition matrices across different scales.

Key Insights and Results

The fundamental realization of this work is that the multiresolution decomposition induced by gamblets behaves similarly to an eigenspace decomposition, where the operator becomes diagonal. While a true eigenspace decomposition is computationally expensive, gamblets provide a "near-eigenspace" that can be computed in near-linear time.

Complexity and Accuracy

Numerical tests confirm the theoretical near-linear scaling. The pre-computation of gamblets scales at $O(N \ln^{3d} N)$, and the propagation of the solution at each time step scales at $O(N \ln^{d+1} N)$. The method provides rigorous a-priori error bounds, achieving "grid-size accuracy" in the energy norm.

Stability and Efficiency

The errors remain stable over long simulation times for both hyperbolic (wave) and parabolic (heat) equations. Furthermore, the multi-time-stepping approach demonstrated significant efficiency gains; in one experiment, it achieved a target $H^1$ error with a time step five times larger than what was required by a uniform time-stepping scheme.

Conclusion

The gamblet framework successfully bypasses the traditional complexity bottleneck for PDEs with rough coefficients by providing a physics-aware, localized basis. While currently focused on linear operators, the robustness of the localization property suggests broad applicability. Future work will focus on extending these principles to non-linear PDEs and further optimizing implementation for high-performance computing environments.

Summary updated

BibTeX
@article{zhang2017gamblets,
  author = {Lei Zhang and Houman Owhadi and Lei Zhang},
  title = {{Gamblets for opening the complexity-bottleneck of implicit schemes for hyperbolic and parabolic ODEs/PDEs with rough coefficients}},
  journal = {Journal of Computational Physics},
  year = {2017},
  doi = {10.1016/j.jcp.2017.06.037},
}
Figure