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

doi:10.1007/s42967-024-00428-4

Communications on Applied Mathematics and Computation ›› 2026, Vol. 8 ›› Issue (1): 248-268.doi: 10.1007/s42967-024-00428-4

• ORIGINAL PAPERS • Previous Articles Next Articles

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

Ke Chen¹, Daniel Appelö², Tracy Babb³, Per-Gunnar Martinsson⁴

1. Department of Mathematics, University of Maryland, 4176 Campus Drive, College Park, 20742, MD, USA;
2. Department of Mathematics, Virginia Tech., 225 Stanger Street, Blacksburg, 24061, VA, USA;
3. Department of Applied Mathematics, University of Colorado Boulder, 2300 Colorado Avenue, Boulder, 80309, CO, USA;
4. Department of Mathematics, University of Texas at Austin, 2515 Speedway, Austin, 78712, TX, USA

Received:2023-06-06 Revised:2024-04-03 Online:2026-02-20 Published:2026-02-11
Contact: Ke Chen,E-mail:kechen@umd.edu,kechen@udel.edu E-mail:kechen@umd.edu,kechen@udel.edu
Supported by:
This work was supported in part by the NSF Grants DMS-2208164, DMS-2210286 (DA) and DMS-1952735, DMS-2012606 (PGM). The work of PGM was also supported by the Office of Naval Research (N00014-18-1-2354) and by the Department of Energy ASCR (DE-SC0022251).

Abstract

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}\left(N^{1.5}\right)$ for the precomputation where the solution operator to the elliptic problems is built, and then $\mathcal{O}(N \log N)$ 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.

Key words: Explicit singly diagonally implicit Runge-Kutta (ESDIRK), Parabolic, Direct solver, High-order, Hierarchical

CLC Number:

Ke Chen, Daniel Appelö, Tracy Babb, Per-Gunnar Martinsson. Fast and High-Order Approximation of Parabolic Equations Using Hierarchical Direct Solvers and Implicit Runge-Kutta Methods[J]. Communications on Applied Mathematics and Computation, 2026, 8(1): 248-268.

TrendMD

References

[1] Babb, T., Gillman, A., Hao, S., Martinsson, P.-G.: An accelerated Poisson solver based on multidomain spectral discretization. BIT Numer. Math. 58(4), 851-879 (2018)
[2] Babb, T., Martinsson, P.-G., Appelo, D.: HPS accelerated spectral solvers for time dependent problems. arXiv:1811.04555, 155 (2018)
[3] Davis, T.A.: Direct Methods for Sparse Linear Systems. Society for Industrial and Applied Mathematics, Philadelphia (2006)
[4] George, A.: Nested dissection of a regular finite element mesh. SIAM J. Numer. Anal. 10(2), 345-363 (1973)
[5] Gillman, A., Barnett, A.H., Martinsson, P.-G.: A spectrally accurate direct solution technique for frequency-domain scattering problems with variable media. BIT Numer. Math. 55(1), 141-170 (2015)
[6] Gillman, A., Martinsson, P.-G.: A direct solver with

\begin{document}$ O $\end{document}

(

\begin{document}$ N $\end{document}

) complexity for variable coefficient elliptic PDEs discretized via a high-order composite spectral collocation method. SIAM J. Sci. Comput. 36(4), 2023-2046 (2014). https://doi.org/10.1137/130918988
[7] Gottlieb, D., Lustman, L.: The spectrum of the Chebyshev collocation operator for the heat equation. SIAM J. Numer. Anal. 20(5), 909-921 (1983). https://doi.org/10.1137/0720063
[8] Gottlieb, S., Ketcheson, D.I., Shu, C.-W.: Strong Stability Preserving Runge-Kutta and Multistep Time Discretizations. World Scientific, Singapore (2011)
[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. 308, 419-434 (2016)
[10] Hu, J., Shu, R., Zhang, X.: Asymptotic-preserving and positivity-preserving implicit-explicit schemes for the stiff BGK equation. SIAM J. Numer. Anal. 56(2), 942-973 (2018)
[11] Kennedy, C.A., Carpenter, M.H.: Additive Runge-Kutta schemes for convection-diffusion-reaction equations. Appl. Numer. Math. 44(1/2), 139-181 (2003)
[12] Lushnikov, P.M., Vladimirova, N.: Non-Gaussian statistics of multiple filamentation. Opt. Lett. 35(12), 1965-1967 (2010)
[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. Society for Industrial and Applied Mathematics, Philadelphia (2019)
[16] Pazner, W., Kolev, T., Dohrmann, C.: Low-order preconditioning for the high-order finite element de Rham complex. SIAM J. Sci. Comput. 45(2), 675-702 (2023)
[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, L.N.: The eigenvalues of second-order spectral differentiation matrices. SIAM J. Numer. Anal. 25(6), 1279-1298 (1988)

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	Guangyao Zhu, Yan Jiang, Mengping Zhang. Inverse Lax-Wendroff Boundary Treatment for Solving Conservation Laws with Finite Volume Methods [J]. Communications on Applied Mathematics and Computation, 2025, 7(3): 885-909.
[2]	Daniel Appel?, Thomas Hagstrom, Yann-Meing Law. Energy-Conserving Hermite Methods for Maxwell’s Equations [J]. Communications on Applied Mathematics and Computation, 2025, 7(3): 1146-1173.
[3]	Yihui Tu, Zhenli Xu, Haizhao Yang. Hierarchical Interpolative Factorization for Self Green’s Function in 3D Modified Poisson-Boltzmann Equations [J]. Communications on Applied Mathematics and Computation, 2025, 7(2): 536-561.
[4]	Lei Yang, Shun Li, Yan Jiang, Chi-Wang Shu, Mengping Zhang. Inverse Lax-Wendroff Boundary Treatment of Discontinuous Galerkin Method for 1D Conservation Laws [J]. Communications on Applied Mathematics and Computation, 2025, 7(2): 796-826.
[5]	Laura Río-Martín, Michael Dumbser. High-Order ADER Discontinuous Galerkin Schemes for a Symmetric Hyperbolic Model of Compressible Barotropic Two-Fluid Flows [J]. Communications on Applied Mathematics and Computation, 2024, 6(4): 2119-2154.
[6]	Michel Bergmann, Afaf Bouharguane, Angelo Iollo, Alexis Tardieu. High Order ADER-IPDG Methods for the Unsteady Advection-Diffusion Equation [J]. Communications on Applied Mathematics and Computation, 2024, 6(3): 1954-1977.
[7]	Baiying Dong, Zhilin Li, Juan Ruiz-álvarez. A Stable FE-FD Method for Anisotropic Parabolic PDEs with Moving Interfaces [J]. Communications on Applied Mathematics and Computation, 2024, 6(2): 992-1012.
[8]	Ruihan Guo, Yinhua Xia. Arbitrary High-Order Fully-Decoupled Numerical Schemes for Phase-Field Models of Two-Phase Incompressible Flows [J]. Communications on Applied Mathematics and Computation, 2024, 6(1): 625-657.
[9]	Wei Guo, Jannatul Ferdous Ema, Jing-Mei Qiu. A Local Macroscopic Conservative (LoMaC) Low Rank Tensor Method with the Discontinuous Galerkin Method for the Vlasov Dynamics [J]. Communications on Applied Mathematics and Computation, 2024, 6(1): 550-575.
[10]	Jean-Luc Guermond, Bojan Popov, Laura Saavedra. Second-Order Invariant Domain Preserving ALE Approximation of Euler Equations [J]. Communications on Applied Mathematics and Computation, 2023, 5(2): 923-945.
[11]	Eleuterio F. Toro, Andrea Santacá, Gino I. Montecinos, Morena Celant, Lucas O. Müller. AENO: a Novel Reconstruction Method in Conjunction with ADER Schemes for Hyperbolic Equations [J]. Communications on Applied Mathematics and Computation, 2023, 5(2): 776-852.
[12]	Johannes Markert, Gregor Gassner, Stefanie Walch. A Sub-element Adaptive Shock Capturing Approach for Discontinuous Galerkin Methods [J]. Communications on Applied Mathematics and Computation, 2023, 5(2): 679-721.
[13]	M. Semplice, E. Travaglia, G. Puppo. One- and Multi-dimensional CWENOZ Reconstructions for Implementing Boundary Conditions Without Ghost Cells [J]. Communications on Applied Mathematics and Computation, 2023, 5(1): 143-169.
[14]	Andrew Christlieb, Matthew Link, Hyoseon Yang, Ruimeng Chang. High-Order Semi-Lagrangian WENO Schemes Based on Non-polynomial Space for the Vlasov Equation [J]. Communications on Applied Mathematics and Computation, 2023, 5(1): 116-142.
[15]	Lorenzo Botti, Daniele A. Di Pietro. p-Multilevel Preconditioners for HHO Discretizations of the Stokes Equations with Static Condensation [J]. Communications on Applied Mathematics and Computation, 2022, 4(3): 783-822.