×

A uniform spectral analysis for a preconditioned all-at-once system from first-order and second-order evolutionary problems. (English) Zbl 1496.65152

Summary: Solving evolutionary equations in a parallel-in-time manner is an attractive topic. The iterative algorithm based on the block \(\alpha\)-circulant preconditioning technique has shown promising advantages, especially for hyperbolic problems. By fast Fourier transform for factorizing the involved circulant matrices, the preconditioned iteration can be computed efficiently via the so-called diagonalization technique, which yields a direct parallel implementation across all time levels. In recent years, considerable efforts have been devoted to exploring the spectral property of the iteration matrix arising from the used time-integrator, which leads to many case-by-case studies. Denoting by \(\mathcal{K}\) and \(\mathcal{P}_\alpha\) the all-at-once matrix of the evolutionary PDEs and the corresponding block \(\alpha\)-circulant preconditioner, we will present a systematic spectral analysis for the matrix \(\mathcal{P}_\alpha^{-1}\mathcal{K}\) for both the first-order and second-order evolutionary problems. For the first-order problems our analysis works for all stable single-step time-integrators, while for the second-order problems our analysis works for a large class of symmetric two-step methods which could be arbitrarily high-order. Illustrative numerical experiments are presented to complement our theory.

MSC:

65M55 Multigrid methods; domain decomposition for initial value and initial-boundary value problems involving PDEs
65M12 Stability and convergence of numerical methods for initial value and initial-boundary value problems involving PDEs
65M15 Error bounds for initial value and initial-boundary value problems involving PDEs
65Y05 Parallel numerical computation
65L06 Multistep, Runge-Kutta and extrapolation methods for ordinary differential equations
65T50 Numerical methods for discrete and fast Fourier transforms
Full Text: DOI

References:

[1] D. Bini, G. Latouche, and B. Meini, Numerical Methods for Structured Markov Chains, Oxford University Press, New York, 2005. · Zbl 1076.60002
[2] M. M. Chawla, Unconditionally stable Numerov-type methods for second order differential equations, BIT, 23 (1983), pp. 541-542. · Zbl 0523.65055
[3] F. Chen, J. S. Hesthaven, and X. Zhu, On the use of reduced basis methods to accelerate and stabilize the Parareal method, in Reduced Order Methods for Modeling and Computational Reduction, MS&A. Model. Simul. Appl. 9, A. Quarteroni and G. Rozza, eds., Springer, Berlin, 2014, pp. 187-214. · Zbl 1315.65079
[4] J. P. Coleman, Order conditions for a class of two-step methods for \(y''=f(x,y)\), IMA J. Numer. Anal., 23 (2003), pp. 197-220. · Zbl 1022.65080
[5] J. Cortial and C. Farhat, A time-parallel implicit method for accelerating the solution of non-linear structural dynamics problems, Internat. J. Numer. Methods Engrg., 77 (2009), pp. 451-470. · Zbl 1155.74428
[6] G. Dahlquist, On accuracy and unconditional stability of linear multistep methods for second order differential equations, BIT, 18 (1978), pp. 133-136. · Zbl 0378.65043
[7] X. Dai and Y. Maday, Stable parareal in time method for first- and second-order hyperbolic systems, SIAM J. Sci. Comput., 35 (2013), pp. A52-A78. · Zbl 1264.65136
[8] F. Danieli and A. J. Wathen, All-at-once solution of linear wave equations, Numer. Linear Algebra Appl. 28 (2021), e2386. · Zbl 07478618
[9] V. A. Dobrev, Tz. V. Kolev, N. A. Petersson, and J. B. Schroder, Two-level convergence theory for multigrid reduction in time (MGRIT), SIAM J. Sci. Comput., 39 (2017), pp. S501-S527. · Zbl 1416.65329
[10] M. Emmett and M. L. Minion, Toward an efficient parallel in time method for partial differential equations, Commun. Appl. Math. Comput. Sci., 7 (2012), pp. 105-132. · Zbl 1248.65106
[11] C. Farhat and M. Chandesris, Time-decomposed parallel time-integrators: Theory and feasibility studies for fluid, structure, and fluid-structure applications, Internat. J. Numer. Methods Engrg., 58 (2003), pp. 1397-1434. · Zbl 1032.74701
[12] C. Farhat, J. Cortial, C. Dastillung, and H. Bavestrello, Time-parallel implicit integrators for the near-real-time prediction of linear structural dynamic responses, Internat. J. Numer. Methods Engrg., 67 (2006), pp. 697-724. · Zbl 1113.74023
[13] R. D. Falgout, S. Friedhoff, T.Kolev, S. P. MacLachlan, and J. B. Schroder, Parallel time integration with multigrid, SIAM J. Sci. Comput., 36 (2014), pp. C635-C661. · Zbl 1310.65115
[14] M. J. Gander and M. Petcu, Analysis of a modified parareal algorithm for second-order ordinary differential equations, AIP Conf. Proc., 936 (2007), pp. 233-236. · Zbl 1152.65336
[15] M. J. Gander and M. Petcu, Analysis of a Krylov subspace enhanced parareal algorithm for linear problems, ESAIM Proc., 25 (2008), pp. 114-129. · Zbl 1156.65322
[16] M. J. Gander and S. Vandewalle, Analysis of the parareal time-parallel time-integration method, SIAM J. Sci. Comput., 29 (2007), pp. 556-578. · Zbl 1141.65064
[17] M. J. Gander, J. Liu, S. L. Wu, X. Yue, and T. Zhou, ParaDiag: Parallel-in-Time Algorithms Based on the Diagonalization Technique, preprint, arXiv:2005.09158, 2021, https://arxiv.org/abs/2005.09158.
[18] M. Gander, L. Halpern, J. Ryan, and T. Tran, A direct solver for time parallelization, in Proceedings of the Domain Decomposition Methods in Science and Engineering XXII, Lect. Notes Comput. Sci. Eng. 104, Springer, Cham, 2016, pp. 491-499. · Zbl 1339.65114
[19] M.J. Gander and L. Halpern, Time parallelization for nonlinear problems based on diagonalization, in Proceedings of the Domain Decomposition Methods in Science and Engineering XXIII, Lect. Note Comput. Sci. Eng. 116, Springer Chaim, 2017, pp. 163-178. · Zbl 1367.65118
[20] M. J. Gander and S. L. Wu, Convergence analysis of a periodic-like waveform relaxation method for initial-value problems via the diagonalization technique, Numer. Math., 143 (2019), pp. 489-527. · Zbl 1472.65083
[21] A. Goddard and A. Wathen, A note on parallel preconditioning for all-at-once evolutionary PDEs, Electron. Trans. Numer. Anal., 51 (2019), pp. 135-150. · Zbl 1422.65232
[22] E. Lelarasmee, A. E. Ruehli, and A. L. Sangiovanni-Vincentelli, The waveform relaxation method for time-domain analysis of large scale integrated circuits, IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 1 (1982), pp. 131-145.
[23] B. Li, K. Wang and Z. Zhou, Long-time accurate symmetrized implicit-explicit BDF methods for a class of parabolic equations with non-self-adjoint operators, SIAM J. Numer. Anal., 58 (2020), pp. 189-210. · Zbl 07154062
[24] J. Liu and S. L. Wu, A fast block \(\alpha \)-circulant preconditioner for all-at-once systems from wave equations, SIAM J. Math. Anal. Appl., 41 (2020), pp. 1912-1943. · Zbl 1460.65102
[25] J. L. Lions, Y. Maday, and G. Turinici, A“parareal” in time discretization of PDEs, C. R. Acad. Sci. Paris, 332 (2001), pp. 661-668. · Zbl 0984.65085
[26] X.-L. Lin and M. Ng, An all-at-once preconditioner for evolutionary partial differential equations, SIAM J. Sci. Comput., 43 (2021), pp. A2766-A2784. · Zbl 07379636
[27] X. Lin, M. Ng, and H. Sun, Efficient preconditioner of one-sided space fractional diffusion equation, BIT, 58 (2018), pp. 729-748. · Zbl 1404.65136
[28] E. McDonald, J. Pestana, and A. Wathen, Preconditioning and iterative solution of all-at-once systems for evolutionary partial differential equations, SIAM J. Sci. Comput., 40 (2018), pp. A1012-A1033. · Zbl 1392.65036
[29] Y. Maday and E. M. R \(\ddot{\rm o}\) nquist, Parallelization in time through tensor-product space-time solvers, C. R. Math. Acad. Sci. Paris, 346 (2008), pp. 113-118. · Zbl 1133.65066
[30] H. Nguyen and R. Tsai, A stable parareal-like method for the second order wave equation, J. Comput. Phys., 405 (2020), 109156. · Zbl 1453.65275
[31] B. W. Ong and J. B. Schroder, Applications of time parallelization, Comput. Vis. Sci., 23 (2020), 11. · Zbl 07704915
[32] D. Ruprecht and R. Krause, Explicit parallel-in-time integration of a linear acoustic-advection system, Comput. & Fluids, 59 (2012), pp. 72-83. · Zbl 1365.76241
[33] D. Ruprecht, Wave propagation characteristics of Parareal, Comput. Vis. Sci., 19 (2018), pp. 1-17. · Zbl 1398.65374
[34] B. S. Southworth, Necessary conditions and tight two-level convergence bounds for parareal and multigrid reduction in time, SIAM J. Matrix Anal. Appl., 40 (2019), pp. 564-608. · Zbl 1420.65039
[35] R. Speck, D. Ruprecht, R. Krause, M. Emmett, M. L. Minion, M. Winkel, and P. Gibbon, A massively space-time parallel N-body solver, in Proceedings of the International Conference on High Performance Computing, Networking, Storage, and Analysis, Los Alamitos, CA, IEEE, 92 (2012), pp. 1-11. · Zbl 1443.76185
[36] H. D. Sterck, R. D. Falgout, S. Friedhoff, O. A. Krzysik, and S. P. MacLachlan, Optimizing multigrid reduction-in-time and parareal coarse-grid operators for linear advection, Numer. Linear Algebra Appl., 2021; e2367. · Zbl 07396250
[37] S. Vandewalle, Parallel multigrid waveform relaxation for parabolic problems, Vieweg + Teubner Verlag, Stuttgart, Germany, 1993. · Zbl 0816.65057
[38] A. J. Wathen, Preconditioning, Acta Numer., 24 (2015), pp. 329-376. · Zbl 1316.65039
[39] A. Wathen, Some observations on preconditioning for non-self-adjoint and time-dependent problems, Comput. Math. Appl., in press, https://doi.org/10.1016/j.camwa.2021.05.037. · Zbl 1524.65155
[40] S. Wu and Z. Zhou, A parallel-in-time algorithm for high-order BDF methods for diffusion and subdiffusion equations, SIAM J. Sci. Comput., 43 (2021), pp. A3627-A3656. · Zbl 1491.65084
[41] S. L. Wu and T. Zhou, Convergence analysis for three parareal solvers, SIAM J. Sci. Comput., 37 (2015), pp. A970-A992. · Zbl 1328.65157
[42] S. L. Wu, Convergence analysis of the parareal-Euler algorithm for systems of ODEs with complex eigenvalues, J. Sci. Comput., 67 (2016), pp. 644-668. · Zbl 1339.65095
[43] S. L. Wu, Toward parallel coarse grid correction for the parareal algorithm, SIAM J. Sci. Comput., 40 (2018), pp. A1446-A1472. · Zbl 1398.65358
[44] S. L. Wu and T. Zhou, Acceleration of the two-level MGRIT algorithm via the diagonalization technique, SIAM J. Sci. Comput., 41 (2019), pp. A3421-A3448. · Zbl 1425.65104
[45] S. L. Wu and T. Zhou, Parallel implementation for the two-stage SDIRK methods via diagonalization, J. Comput. Phys., 428 (2021), 110076. · Zbl 07511430
[46] J. Yang, Z. Yuan, and Z. Zhou, Robust Convergence of Parareal Algorithms With Arbitrarily High-Order Fine Propagators, preprint, arXiv:2019.05203, 2021, https://arxiv.org/abs/2109.05203.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.