A well-conditioned direct PinT algorithm for first-and second-order evolutionary equations

DOI10.1007/S10444-022-09928-4MaRDI QIDQ6374444arXivFDO

Authors Jun Liu, Xiang-Sheng Wang, Shulin Wu, Tao Zhou

Publication date 3 August 2021

Published in arXiv

Full work available at URL https://doi.org/10.1007/S10444-022-09928-4

Mathematics Subject Classification ID

Toeplitz, Cauchy, and related matrices (15B05) Iterative numerical methods for linear systems (65F10) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Numerical methods for low-rank matrix approximation; matrix compression (65F55) Numerical computation of solutions to systems of equations (65H10) Numerical methods for initial value problems involving ordinary differential equations (65L05) Finite difference methods for initial value and initial-boundary value problems involving PDEs (65M06) Stability and convergence of numerical methods for initial value and initial-boundary value problems involving PDEs (65M12) Error bounds for initial value and initial-boundary value problems involving PDEs (65M15) Multigrid methods; domain decomposition for initial value and initial-boundary value problems involving PDEs (65M55) Finite difference methods for boundary value problems involving PDEs (65N06) Parallel numerical computation (65Y05)

arXiv classification

cs.NAmath.NA

Abstract: In this paper, we propose a direct parallel-in-time (PinT) algorithm for time-dependent problems with first- or second-order derivative. We use a second-order boundary value method as the time integrator that leads to a tridiagonal time discretization matrix. Instead of solving the corresponding all-at-once system iteratively, we diagonalize the time discretization matrix, which yields a direct parallel implementation across all time levels. A crucial issue on this methodology is how the condition number of the eigenvector matrix $V$ grows as $n$ is increased, where $n$ is the number of time levels. A large condition number leads to large roundoff error in the diagonalization procedure, which could seriously pollute the numerical accuracy. Based on a novel connection between the characteristic equation and the Chebyshev polynomials, we present explicit formulas for computing $V$ and $V^{-1}$, by which we prove that $mathrm{Cond}_2(V)=mathcalO(n^2)$. This implies that the diagonalization process is well-conditioned and the roundoff error only increases moderately as $n$ grows and thus, compared to other direct PinT algorithms, a much larger $n$ can be used to yield satisfactory parallelism. Numerical results on parallel machine are given to support our findings, where over 60 times speedup is achieved with 256 cores.

This page was built for publication: A well-conditioned direct PinT algorithm for first-and second-order evolutionary equations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6374444)