Fast and High-Order Approximation of Parabolic Equations Using Hierarchical Direct Solvers and Implicit Runge-Kutta Methods

Abstract

A stable and high-order accurate solver for linear and nonlinear parabolic equations is presented. An additive Runge-Kutta method is used for the time stepping, which integrates the linear stiff terms by an explicit singly diagonally implicit Runge-Kutta (ESDIRK) method and the nonlinear terms by an explicit Runge-Kutta (ERK) method. In each time step, the implicit solution is performed by the recently developed Hierarchical Poincaré-Steklov (HPS) method. This is a fast direct solver for elliptic equations that decomposes the space domain into a hierarchical tree of subdomains and builds spectral collocation solvers locally on the subdomains. These ideas are naturally combined in the presented method since the singly diagonal coefficient in ESDIRK and a fixed time step ensures that the coefficient matrix in the implicit solution of HPS remains the same for all time stages. This means that the precomputed inverse can be efficiently reused, leading to a scheme with complexity (in two dimensions)

\mathcal{O}(N^{1.5})

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$${\mathcal {O}}(N^{1.5})$$\end{document}

for the precomputation where the solution operator to the elliptic problems is built, and then

\mathcal{O}(NlogN)

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$${\mathcal {O}}(N \log N)$$\end{document}

for the solution in each time step. The stability of the method is proved for first order in time and any order in space, and numerical evidence substantiates a claim of the stability for a much broader class of time discretization methods. Numerical experiments supporting the accuracy of the efficiency of the method in one and two dimensions are presented.

Keywords

Explicit singly diagonally implicit Runge-Kutta (ESDIRK) / Parabolic / Direct solver / High-order / Hierarchical / 65M22 / 65M55

References

[1] Babb T, Gillman A, Hao S, Martinsson P-G. An accelerated Poisson solver based on multidomain spectral discretization. BIT Numer. Math., 2018, 58(4): 851-879

[2] Babb, T., Martinsson, P.-G., Appelo, D.: HPS accelerated spectral solvers for time dependent problems. arXiv:1811.04555, 155 (2018)

[3] Davis TA. Direct Methods for Sparse Linear Systems, 2006, Philadelphia, Society for Industrial and Applied Mathematics

[4] George A. Nested dissection of a regular finite element mesh. SIAM J. Numer. Anal., 1973, 10(2): 345-363

[5] Gillman A, Barnett AH, Martinsson P-G. A spectrally accurate direct solution technique for frequency-domain scattering problems with variable media. BIT Numer. Math., 2015, 55(1): 141-170

[6] Gillman A, Martinsson P-G. A direct solver with O\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$O$$\end{document}(N\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$N$$\end{document}) complexity for variable coefficient elliptic PDEs discretized via a high-order composite spectral collocation method. SIAM J. Sci. Comput., 2014, 36(4): 2023-2046

[7] Gottlieb D, Lustman L. The spectrum of the Chebyshev collocation operator for the heat equation. SIAM J. Numer. Anal., 1983, 20(5): 909-921

[8] Gottlieb S, Ketcheson DI, Shu C-W. Strong Stability Preserving Runge-Kutta and Multistep Time Discretizations, 2011, Singapore, World Scientific

[9] Hao S, Martinsson P-G. A direct solver for elliptic PDEs in three dimensions based on hierarchical merging of Poincaré-Steklov operators. J. Comput. Appl. Math., 2016, 308: 419-434

[10] Hu J, Shu R, Zhang X. Asymptotic-preserving and positivity-preserving implicit-explicit schemes for the stiff BGK equation. SIAM J. Numer. Anal., 2018, 56(2): 942-973

[11] Kennedy CA, Carpenter MH. Additive Runge-Kutta schemes for convection-diffusion-reaction equations. Appl. Numer. Math., 2003, 44(1/2): 139-181

[12] Lushnikov PM, Vladimirova N. Non-Gaussian statistics of multiple filamentation. Opt. Lett., 2010, 35(12): 1965-1967

[13] Martinsson, P.-G.: A composite spectral scheme for variable coefficient Helmholtz problems. arXiv: 1206.4136 (2012)

[14] Martinsson, P.-G.: A direct solver for variable coefficient elliptic PDEs discretized via a composite spectral collocation method. J. Comput. Phys. 242, 460–479 (2013) https://doi.org/10.1016/j.jcp.2013.02.019

[15] Martinsson P-G. Fast Direct Solvers for Elliptic PDEs, 2019, Philadelphia, Society for Industrial and Applied Mathematics

[16] Pazner W, Kolev T, Dohrmann C. Low-order preconditioning for the high-order finite element de Rham complex. SIAM J. Sci. Comput., 2023, 45(2): 675-702

[17] Rosales, R., Seibold, B., Shirokoff, D., Zhou, D.: Order reduction in high-order Runge-Kutta methods for initial boundary value problems. arXiv:1712.00897 (2017)

[18] Weideman J, Trefethen LN. The eigenvalues of second-order spectral differentiation matrices. SIAM J. Numer. Anal., 1988, 25(6): 1279-1298

Funding

National Science Foundation(DMS-2208164)

Office of Naval Research(N00014-18-1-2354)

Department of Energy(ASCR DE-SC0022251)

RIGHTS & PERMISSIONS

Shanghai University