تقرير
A well-conditioned direct PinT algorithm for first-and second-order evolutionary equations
العنوان: | A well-conditioned direct PinT algorithm for first-and second-order evolutionary equations |
---|---|
المؤلفون: | Liu, Jun, Wang, Xiang-Sheng, Wu, Shu-Lin, Zhou, Tao |
سنة النشر: | 2021 |
المجموعة: | Computer Science Mathematics |
مصطلحات موضوعية: | Mathematics - Numerical Analysis, 65Y05, 65F05 |
الوصف: | 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)=\mathcal{O}(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. Comment: 22 pages, 1 figure, 4 tables; accepted version to appear in Advances in Computational Mathematics |
نوع الوثيقة: | Working Paper |
URL الوصول: | http://arxiv.org/abs/2108.01716 |
رقم الأكسشن: | edsarx.2108.01716 |
قاعدة البيانات: | arXiv |
الوصف غير متاح. |