Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

A Parallel-in-Time Implementation of the Numerov Method For Wave Equations

  • Published:
Journal of Scientific Computing Aims and scope Submit manuscript

A Correction to this article was published on 24 April 2022

This article has been updated

Abstract

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}}{{\varvec{u}}}={{\varvec{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 \({{\varvec{r}}}\), we can compute \({\mathscr {P}}_{\alpha }^{-1}{{\varvec{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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9

Similar content being viewed by others

Data Availability and Material

All data generated are included in the manuscript.

Change history

References

  1. Adam, Y.: Highly accurate compact implicit methods and boundary conditions. J. Comput. Phys. 24(1), 10–22 (1977)

    Article  MathSciNet  Google Scholar 

  2. Bertaccini, D., Ng, M.K.: Block \(\{\omega \}\)-circulant preconditioners for the systems of differential equations. CALCOLO 40(2), 71–90 (2003)

    Article  MathSciNet  Google Scholar 

  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, R.L., Hedstrom, G.W.: The distribution of the eigenvalues of the discrete Laplacian. BIT Numer. Math. 12(4), 475–488 (1972)

    Article  MathSciNet  Google Scholar 

  5. Chawla, M.M.: Unconditionally stable Numerov-type methods for second order differential equations. BIT Numer. Math. 23(4), 541–542 (1983)

    Article  Google Scholar 

  6. Chawla, M.M.: Numerov made explicit has better stability. BIT Numer. Math. 24(1), 117–118 (1984)

    Article  MathSciNet  Google Scholar 

  7. Chen, F., Hesthaven, J.S., Zhu, X.: On the use of reduced basis methods to accelerate and stabilize the parareal method. In: Quarteroni, A., Rozza, G. (eds.) Reduced Order Methods for Modeling and Computational Reduction, vol. 9, pp. 187–214. Springer, Cham (2014)

    MATH  Google Scholar 

  8. Cockburn, B., Fu, Z., Hungria, A., et al.: Stormer-Numerov HDG methods for acoustic waves. J. Sci. Comput. 75(2), 597–624 (2018)

    Article  MathSciNet  Google Scholar 

  9. Cocquet, P.H., Gander, M.J.: 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)

    Article  MathSciNet  Google Scholar 

  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)

    Article  MathSciNet  Google Scholar 

  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)

    Article  MathSciNet  Google Scholar 

  13. Eghbal, A., Gerber, A.G., Aubanel, E.: Acceleration of unsteady hydrodynamic simulations using the parareal algorithm. J. Comput. Sci. 19, 57–76 (2017)

    Article  Google Scholar 

  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)

    Article  MathSciNet  Google Scholar 

  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)

  16. Gander, M.J., Graham, I.G., Spence, E.A.: 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)

    Article  MathSciNet  Google Scholar 

  17. Gander, M.J., Halpern, L.: Time parallelization for nonlinear problems based on diagonalization. In: Domain Decomposition Methods in Science and Engineering XXIII, pp. 163–170. Springer, Cham (2017)

    Chapter  Google Scholar 

  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)

  19. Gander, M.J., 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)

    Article  MathSciNet  Google Scholar 

  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, M.J., Petcu, M.: Analysis of a modified parareal algorithm for second-order ordinary differential equations. AIP Conf. Proc. 936, 233–236 (2007)

    Article  Google Scholar 

  22. Gander, M.J., Wu, S.L.: Convergence analysis of a Periodic-Like waveform relaxation method for initial-value problems via the diagonalization technique. Numer. Math. 143, 489–527 (2019)

    Article  MathSciNet  Google Scholar 

  23. Gander, M.J., Wu, S.L.: A diagonalization-based parareal algorithm for dissipative and wave propagation problems. SIAM J. Numer. Anal. 58(5), 2981–3009 (2020)

    Article  MathSciNet  Google Scholar 

  24. Goddard, A., Wathen, A.: A note on parallel preconditioning for all-at-once evolutionary PDEs. Electron. Trans. Numer. Anal. 51, 135–150 (2019)

    Article  MathSciNet  Google Scholar 

  25. Graham, I., Spence, E., Vainikko, E.: Domain decomposition preconditioning for high-frequency Helmholtz problems with absorption. Math. Comp. 86, 2089–2127 (2017)

    Article  MathSciNet  Google Scholar 

  26. Gu, X.M., Wu, S.L.: A parallel-in-time iterative algorithm for volterra partial integro-differential problems with weakly singular kernel. J. Comput. Phys. 417, 109576 (2020)

    Article  MathSciNet  Google Scholar 

  27. Hairer, E.: Unconditionally stable methods for second order differential equations. Numer. Math. 32, 373–379 (1979)

    Article  MathSciNet  Google Scholar 

  28. Inda, M.A., Bisseling, R.H.: A simple and efficient parallel fft algorithm using the bsp model. Parallel Comput. 27, 1847–1878 (2001)

    Article  MathSciNet  Google Scholar 

  29. Larson, M.G., Bengzon, F.: The Finite Element Method: Theory, Implementation, and Applications, vol. 10. Springer Science & Business Media, Berlin (2013)

    Book  Google Scholar 

  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)

    Article  MathSciNet  Google Scholar 

  31. Liu, J., Wu, S.L.: A fast block \(\alpha \)-circulant preconditoner for all-at-once systems from wave equations. SIAM J. Matrix Anal. Appl. 41(4), 1912–1943 (2020)

    Article  MathSciNet  Google Scholar 

  32. Maday, Y., Rønquist, E.M.: Parallelization in time through tensor-product space-time solvers. Comptes Rendus Mathematique 346(1–2), 113–118 (2008)

    Article  MathSciNet  Google Scholar 

  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)

    Article  MathSciNet  Google Scholar 

  34. Meneguette, M.: Chawla-Numerov method revisited. J. Comput. Appl. Math. 36(2), 247–250 (1991)

    Article  MathSciNet  Google Scholar 

  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)

    MathSciNet  Google Scholar 

  36. Mossberg, E.: Higher order finite difference methods for wave propagation problems. Uppsala University Publications, Sweden (2002)

    Google Scholar 

  37. Nguyen, H., Tsai, R.: A stable parareal-like method for the second order wave equation. J. Comput. Phys. 405, 109156 (2020)

    Article  MathSciNet  Google Scholar 

  38. Ruprecht, D., Krause, R.: Explicit parallel-in-time integration of a linear acoustic-advection system. Comput. Fluids 59, 72–83 (2012)

    Article  MathSciNet  Google Scholar 

  39. Skeel, R.D., Zhang, G., Schlick, T.: A family of symplectic integrators: stability, accuracy, and molecular dynamics applications. SIAM J. Sci. Comput. 18(1), 203–222 (1997)

    Article  MathSciNet  Google Scholar 

  40. Størmer, C.: Méthode d’intégration numérique des équations différentielles ordinaires. É. Privat (1921)

  41. Wu, S.L.: Toward parallel coarse grid correction for the parareal algorithm. SIAM J. Sci. Comput. 40, A1446–A1472 (2018)

    Article  MathSciNet  Google Scholar 

  42. Wu, S.L., Zhang, H., Zhou, T.: Solving time-periodic fractional diffusion equations via diagonalization technique and multigrid. Numer. Linear Algebra Appl. 25, e2178 (2018)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

The authors sincerely appreciate the anonymous referees for their valuable comments and constructive suggestions that have greatly improved the original manuscript.

Funding

The first and the third authors are supported by NSFC-12071069, the National Key R&D Program of China (No. 2020YFA0714102), the Fundamental Research Funds for the Central Universities (No. JGPY202101) and the project of Jilin development and Reform Commission (No. 2020C017-3). The second author is supported by NSFC (Nos. 11771313, 12171080).

Author information

Authors and Affiliations

  1. School of Mathematics and Statistics, Northeast Normal University, Changchun, 130024, People’s Republic of China

    Yafei Sun, Shu-Lin Wu & Yingxiang Xu

Authors
  1. Yafei Sun
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Shu-Lin Wu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Yingxiang Xu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yingxiang Xu.

Ethics declarations

Conflict of interest

No conflicts of interest.

Code Availability

Codes can be provided per requirement.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Sun, Y., Wu, SL. & Xu, Y. A Parallel-in-Time Implementation of the Numerov Method For Wave Equations. J Sci Comput 90, 20 (2022). https://doi.org/10.1007/s10915-021-01701-x

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s10915-021-01701-x

Keywords

Mathematics Subject Classification

Search

Navigation