Gamblets for opening the complexity-bottleneck of implicit schemes for hyperbolic and parabolic ODEs/PDEs with rough coefficients
arXiv:1606.07686 · doi:10.1016/j.jcp.2017.06.037
Abstract
Implicit schemes are popular methods for the integration of time dependent PDEs such as hyperbolic and parabolic PDEs. However the necessity to solve corresponding linear systems at each time step constitutes a complexity bottleneck in their application to PDEs with rough coefficients. We present a generalization of gamblets introduced in \cite{OwhadiMultigrid:2015} enabling the resolution of these implicit systems in near-linear complexity and provide rigorous a-priori error bounds on the resulting numerical approximations of hyperbolic and parabolic PDEs. These generalized gamblets induce a multiresolution decomposition of the solution space that is adapted to both the underlying (hyperbolic and parabolic) PDE (and the system of ODEs resulting from space discretization) and to the time-steps of the numerical scheme.
arXiv comment55 pages. 26 figures
References in corpus (16)
- Maximally localized Wannier functions: Theory and applications
- Inferring solutions of differential equations using noisy multi-fidelity data
- Polyharmonic homogenization, rough polyharmonic splines and sparse super-localization
- Flux norm approach to finite dimensional homogenization approximations with non-separated scales and high contrast
- High-Order Implicit Time-Marching Methods Based on Generalized Summation-By-Parts Operators
- Non-intrusive and structure preserving multiscale integration of stiff ODEs, SDEs and Hamiltonian systems with hidden slow dynamics via flow averaging
- Probability Measures for Numerical Solutions of Differential Equations
- On the Brittleness of Bayesian Inference
- Probabilistic ODE Solvers with Runge-Kutta Means
- Averaging versus Chaos in Turbulent Transport?
- Brittleness of Bayesian Inference Under Finite Information in a Continuous World
- Localized bases for finite dimensional homogenization approximations with non-separated scales and high-contrast
- Universal Scalable Robust Solvers from Computational Information Games and fast eigenspace adapted Multiresolution Analysis
- Adaptive methods for PDE's: wavelets or mesh refinement?
- Towards Machine Wald
- Optimal Local Multi-scale Basis Functions for Linear Elliptic Equations with Rough Coefficient
Cited by in corpus (9)
- A Modern Retrospective on Probabilistic Numerics
- Universal Scalable Robust Solvers from Computational Information Games and fast eigenspace adapted Multiresolution Analysis
- Solving and Learning Nonlinear PDEs with Gaussian Processes
- A probabilistic finite element method based on random meshes: Error estimators and Bayesian inverse problems
- Numerical upscaling of perturbed diffusion problems
- Randomised one-step time integration methods for deterministic operator differential equations
- Fast eigenpairs computation with operator adapted wavelets and hierarchical subspace correction
- Sparse operator compression of higher-order elliptic operators with rough coefficients
- Sampling Methods for Bayesian Inference Involving Convergent Noisy Approximations of Forward Maps