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

JOURNAL OF COMPUTATIONAL PHYSICS

卷:347

Article

Owhadi, Houman¹  Zhang, Lei^2,3 

[1] CALTECH, Comp & Math Sci, MC 9-94, Pasadena, CA 91125 USA

[2] Shanghai Jiao Tong Univ, Sch Math Sci, Inst Nat Sci, Shanghai 200240, Peoples R China

[3] Shanghai Jiao Tong Univ, Minist Educ, Key Lab Sci & Engn Comp MOE LSC, Shanghai 200240, Peoples R China

关键词: Wavelets;    Multigrid;    Multi-resolution;    Implicit schemes;    Hyperbolic;    Parabolic;   

DOI  :  10.1016/j.jcp.2017.06.037

来源: Elsevier

【 摘 要 】

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 [62] 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. (C) 2017 Elsevier Inc. All rights reserved.

【 授权许可】

Free