×

A parallel-in-time implementation of the Numerov method for wave equations. (English) Zbl 1483.65056

J. Sci. Comput. 90, No. 1, Paper No. 20, 31 p. (2022); correction ibid. 91, No. 3, Paper No. 70, 3 p. (2022).
Summary: The Numerov method is a well-known 4th-order two-step numerical method for wave equations. It has optimal convergence order among the family of Störmer-Cowell methods and plays a key role in numerical wave propagation. In this paper, we aim to implement this method in a parallel-in-time (PinT) fashion via a diagonalization-based preconditioning technique. The idea lies in forming the difference equations at the \(N_t\) time points into an all-at-once system \(\mathscr{K}{\boldsymbol{u}}={\boldsymbol{b}}\) and then solving it via a fixed point iteration preconditioned by a block \(\alpha\)-circulant matrix \(\mathscr{P}_\alpha\), where \(\alpha \in (0,\frac{1}{2})\) is a parameter. For any input vector \(\boldsymbol{r}\), we can compute \(\mathscr{P}_{\alpha}^{-1}\boldsymbol{r}\) in a PinT fashion by a diagonalization procedure. To match the accuracy of the Numerov method, we use a 4th-order compact finite difference for spatial discretization. In this case, we show that the spectral radius of the preconditioned iteration matrix can be bounded by \(\frac{\alpha}{1-\alpha}\) provided that the spatial mesh size \(h\) and the time step size \(\tau\) satisfy certain restriction. Interestingly, this restriction on \(h\) and \(\tau\) coincides with the stability condition of the Numerov method. Furthermore, the convergence rate of the preconditioned fixed point iteration is mesh independent and depends only on \(\alpha\). We also find that even though the Numerov method itself is unstable, the preconditioned iteration of the corresponding all-at-once system still has a chance to converge, however, very slowly. We provide numerical results for both linear and nonlinear wave equations to illustrate our theoretical findings.

MSC:

65F10 Iterative numerical methods for linear systems
65F08 Preconditioners for iterative methods
65M22 Numerical solution of discretized equations for initial value and initial-boundary value problems involving PDEs
65L20 Stability and convergence of numerical methods for ordinary differential equations
65Y05 Parallel numerical computation
Full Text: DOI

References:

[1] Adam, Y., Highly accurate compact implicit methods and boundary conditions, J. Comput. Phys., 24, 1, 10-22 (1977) · Zbl 0357.65074 · doi:10.1016/0021-9991(77)90106-1
[2] Bertaccini, D.; Ng, MK, Block \(\{\omega \}\)-circulant preconditioners for the systems of differential equations, CALCOLO, 40, 2, 71-90 (2003) · Zbl 1072.65044 · doi:10.1007/s100920300004
[3] Biesel, O.D., V., I.D., Morrow, J.A., Shore, W.T.: Layered networks, the discrete laplacian, and a continued fraction identity. http://www.math.washington.edu/ reu/papers/current/william/layered.pdf (2008)
[4] Burden, RL; Hedstrom, GW, The distribution of the eigenvalues of the discrete Laplacian, BIT Numer. Math., 12, 4, 475-488 (1972) · Zbl 0258.65106 · doi:10.1007/BF01932957
[5] Chawla, MM, Unconditionally stable Numerov-type methods for second order differential equations, BIT Numer. Math., 23, 4, 541-542 (1983) · Zbl 0523.65055 · doi:10.1007/BF01933627
[6] Chawla, MM, Numerov made explicit has better stability, BIT Numer. Math., 24, 1, 117-118 (1984) · Zbl 0568.65042 · doi:10.1007/BF01934522
[7] Chen, F.; Hesthaven, JS; Zhu, X.; Quarteroni, A.; Rozza, G., On the use of reduced basis methods to accelerate and stabilize the parareal method, Reduced Order Methods for Modeling and Computational Reduction, 187-214 (2014), Cham: Springer, Cham · Zbl 1315.65079
[8] Cockburn, B.; Fu, Z.; Hungria, A., Stormer-Numerov HDG methods for acoustic waves, J. Sci. Comput., 75, 2, 597-624 (2018) · Zbl 1398.65248 · doi:10.1007/s10915-017-0547-z
[9] Cocquet, PH; Gander, MJ, How large a shift is needed in the shifted Helmholtz preconditioner for its effective inversion by multigrid?, SIAM J. Sci. Comput., 39, 2, A438-A478 (2017) · Zbl 1365.65269 · doi:10.1137/15M102085X
[10] Cowell, P.H., Crommelin, A.C.D.: Investigation of the motion of Halley’s comet from 1759 to 1910. In: Greenwich Observations in Astronomy, Magnetism and Meteorology made at the Royal Observatory, 2, vol. 71, pp. O1-O84 (1911)
[11] Dahlquist, G., On accuracy and unconditional stability of linear multistep methods for second order differential equations, BIT Numer. Math., 18, 2, 133-136 (1978) · Zbl 0378.65043 · doi:10.1007/BF01931689
[12] Dai, X.; Maday, Y., Stable parareal in time method for first- and second-order hyperbolic systems, SIAM J. Sci. Comput., 35, 1, A52-A78 (2013) · Zbl 1264.65136 · doi:10.1137/110861002
[13] Eghbal, A.; Gerber, AG; Aubanel, E., Acceleration of unsteady hydrodynamic simulations using the parareal algorithm, J. Comput. Sci., 19, 57-76 (2017) · doi:10.1016/j.jocs.2016.12.006
[14] Farhat, C.; Cortial, J.; Dastillung, C.; Bavestrello, H., Time-parallel implicit integrators for the near-real-time prediction of linear structural dynamic responses, Internat. J. Numer. Methods Engrg., 67, 5, 697-724 (2006) · Zbl 1113.74023 · doi:10.1002/nme.1653
[15] Gander, M.J.: 50 years of time parallel time integration. In: T. Carraro, M. Geiger, S. Ko \({\ddot{{\rm r}}}\) kel, R. Rannacher (eds.) Multiple Shooting and Time Domain Decomposition Methods, pp. 69-113. Springer (2015) · Zbl 1337.65127
[16] Gander, MJ; Graham, IG; Spence, EA, Applying GMRES to the Helmholtz equation with shifted Laplacian preconditioning: What is the largest shift for which wavenumber-independent convergence is guaranteed?, Numer. Math., 131, 567-614 (2015) · Zbl 1328.65238 · doi:10.1007/s00211-015-0700-2
[17] Gander, MJ; Halpern, L., Time parallelization for nonlinear problems based on diagonalization, Domain Decomposition Methods in Science and Engineering XXIII, 163-170 (2017), Cham: Springer, Cham · Zbl 1367.65118 · doi:10.1007/978-3-319-52389-7_15
[18] Gander, M.J., Halpern, L., Rannou, J., Ryan, J.: A direct solver for time parallelization. In: Domain Decomposition Methods in Science and Engineering XXII, pp. 491-499. Springer (2016) · Zbl 1339.65114
[19] Gander, MJ; Halpern, L.; Rannou, J.; Ryan, J., A direct time parallel solver by diagonalization for the wave equation, SIAM J. Sci. Comput., 41, A220-A245 (2019) · Zbl 1407.65175 · doi:10.1137/17M1148347
[20] Gander, M.J., Liu, J., Wu, S.L., Yue, X., Zhou, T.: Paradiag: Parallel-in-time algorithms based on the diagonalization technique. arXiv preprint arXiv:2005.09158 (2020)
[21] Gander, MJ; Petcu, M., Analysis of a modified parareal algorithm for second-order ordinary differential equations, AIP Conf. Proc., 936, 233-236 (2007) · Zbl 1152.65336 · doi:10.1063/1.2790116
[22] Gander, MJ; Wu, SL, Convergence analysis of a Periodic-Like waveform relaxation method for initial-value problems via the diagonalization technique, Numer. Math., 143, 489-527 (2019) · Zbl 1472.65083 · doi:10.1007/s00211-019-01060-8
[23] Gander, MJ; Wu, SL, A diagonalization-based parareal algorithm for dissipative and wave propagation problems, SIAM J. Numer. Anal., 58, 5, 2981-3009 (2020) · Zbl 1475.65098 · doi:10.1137/19M1271683
[24] Goddard, A.; Wathen, A., A note on parallel preconditioning for all-at-once evolutionary PDEs, Electron. Trans. Numer. Anal., 51, 135-150 (2019) · Zbl 1422.65232 · doi:10.1553/etna_vol51s135
[25] Graham, I.; Spence, E.; Vainikko, E., Domain decomposition preconditioning for high-frequency Helmholtz problems with absorption, Math. Comp., 86, 2089-2127 (2017) · Zbl 1368.65250 · doi:10.1090/mcom/3190
[26] Gu, XM; Wu, SL, A parallel-in-time iterative algorithm for volterra partial integro-differential problems with weakly singular kernel, J. Comput. Phys., 417, 109576 (2020) · Zbl 1437.65237 · doi:10.1016/j.jcp.2020.109576
[27] Hairer, E., Unconditionally stable methods for second order differential equations, Numer. Math., 32, 373-379 (1979) · Zbl 0393.65035 · doi:10.1007/BF01401041
[28] Inda, MA; Bisseling, RH, A simple and efficient parallel fft algorithm using the bsp model, Parallel Comput., 27, 1847-1878 (2001) · Zbl 0983.68248 · doi:10.1016/S0167-8191(01)00118-1
[29] Larson, MG; Bengzon, F., The Finite Element Method: Theory, Implementation, and Applications (2013), Berlin: Springer Science & Business Media, Berlin · Zbl 1263.65116 · doi:10.1007/978-3-642-33287-6
[30] Liao, W.; Yan, Y., Singly diagonally implicit Runge-Kutta method for time-dependent reaction-diffusion equation, Numer. Methods Partial Differ. Eq., 27, 6, 1423-1441 (2011) · Zbl 1243.65112 · doi:10.1002/num.20589
[31] Liu, J.; Wu, SL, A fast block \(\alpha \)-circulant preconditoner for all-at-once systems from wave equations, SIAM J. Matrix Anal. Appl., 41, 4, 1912-1943 (2020) · Zbl 1460.65102 · doi:10.1137/19M1309869
[32] Maday, Y.; Rønquist, EM, Parallelization in time through tensor-product space-time solvers, Comptes Rendus Mathematique, 346, 1-2, 113-118 (2008) · Zbl 1133.65066 · doi:10.1016/j.crma.2007.09.012
[33] McDonald, E.; Pestana, J.; Wathen, A., Preconditioning and iterative solution of all-at-once systems for evolutionary partial differential equations, SIAM J. Sci. Comput., 40, A1012-A1033 (2018) · Zbl 1392.65036 · doi:10.1137/16M1062016
[34] Meneguette, M., Chawla-Numerov method revisited, J. Comput. Appl. Math., 36, 2, 247-250 (1991) · Zbl 0751.65048 · doi:10.1016/0377-0427(91)90030-N
[35] Mohanty, R.; Singh, S., High accuracy Numerov type discretization for the solution of one-space dimensional non-linear wave equations with variable coefficients, J. Adv. Res. Sci. Comput., 3, 1, 53-66 (2011)
[36] Mossberg, E., Higher order finite difference methods for wave propagation problems (2002), Sweden: Uppsala University Publications, Sweden
[37] Nguyen, H.; Tsai, R., A stable parareal-like method for the second order wave equation, J. Comput. Phys., 405, 109156 (2020) · Zbl 1453.65275 · doi:10.1016/j.jcp.2019.109156
[38] Ruprecht, D.; Krause, R., Explicit parallel-in-time integration of a linear acoustic-advection system, Comput. Fluids, 59, 72-83 (2012) · Zbl 1365.76241 · doi:10.1016/j.compfluid.2012.02.015
[39] Skeel, RD; Zhang, G.; Schlick, T., A family of symplectic integrators: stability, accuracy, and molecular dynamics applications, SIAM J. Sci. Comput., 18, 1, 203-222 (1997) · Zbl 0868.65055 · doi:10.1137/S1064827595282350
[40] Størmer, C.: Méthode d’intégration numérique des équations différentielles ordinaires. É. Privat (1921) · JFM 48.0623.05
[41] Wu, SL, Toward parallel coarse grid correction for the parareal algorithm, SIAM J. Sci. Comput., 40, A1446-A1472 (2018) · Zbl 1398.65358 · doi:10.1137/17M1141102
[42] Wu, SL; Zhang, H.; Zhou, T., Solving time-periodic fractional diffusion equations via diagonalization technique and multigrid, Numer. Linear Algebra Appl., 25, e2178 (2018) · Zbl 1513.65347 · doi:10.1002/nla.2178
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.