2021/08/03 by Jun Liu, Xiangsheng Wang, Liu, Jun +5 · 2 citations
Computer Science · Mathematics · Physics and Astronomy · #65F05 #65Y05 #FOS: Mathematics #Metaheuristic Optimization Algorithms Research #Model Reduction and Neural Networks #Numerical Analysis (math.NA) #Numerical methods for differential equations
paper · pdf · doi:10.48550/arxiv.2108.01716
openalex publication_date 2021/08/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 Cond2(V)=O(n2). 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.