Abstract
We are concerned with the efficient implementation of symplectic implicit Runge-Kutta (IRK) methods applied to systems of Hamiltonian ordinary differential equations by means of Newton-like iterations. We pay particular attention to time-symmetric symplectic IRK schemes (such as collocation methods with Gaussian nodes). For an s-stage IRK scheme used to integrate a \(\dim \)-dimensional system of ordinary differential equations, the application of simplified versions of Newton iterations requires solving at each step several linear systems (one per iteration) with the same \(s\dim \times s\dim \) real coefficient matrix. We propose a technique that takes advantage of the symplecticity of the IRK scheme to reduce the cost of methods based on diagonalization of the IRK coefficient matrix. This is achieved by rewriting one step of the method centered at the midpoint on the integration subinterval and observing that the resulting coefficient matrix becomes similar to a skew-symmetric matrix. In addition, we propose a C implementation (based on Newton-like iterations) of Runge-Kutta collocation methods with Gaussian nodes that make use of such a rewriting of the linear system and that takes special care in reducing the effect of round-off errors. We report some numerical experiments that demonstrate the reduced round-off error propagation of our implementation.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Antoñana, M., Makazaga, J., Murua, A.: Reducing and monitoring round-off error propagation for symplectic implicit Runge-Kutta schemes. Numerical Algorithms 1–20. doi:10.1007/s11075-017-0287-z (2017)
Baboulin, M., Buttari, A., Dongarra, J., Kurzak, J., Langou, J., Langou, J., Luszczek, P., Tomov, S.: Accelerating scientific computations with mixed precision algorithms. Comput. Phys. Commun. 180(12), 2526–2533 (2009). doi:10.1016/j.cpc.2008.11.005
Bickart, T. A.: An efficient solution process for implicit Runge-Kutta methods. SIAM J. Numer. Anal. 14(6), 1022–1027 (1977). doi:10.1137/0714069
Brugnano, L., Caccia, G. F., Iavernaro, F.: Efficient implementation of Gauss collocation and Hamiltonian boundary value methods. Numerical Algorithms 65(3), 633–650 (2014). doi:10.1007/s11075-014-9825-0
Butcher, J. C.: On the implementation of implicit Runge-Kutta methods. BIT Numer. Math. 16(3), 237–240 (1976). doi:10.1007/BF01932265
Hairer, E., Lubich, C., Wanner, G.: Geometric numerical integration: structure-preserving algorithms for ordinary differential equations, vol. 31. Springer Science & Business Media. doi:10.1007/3-540-30666-8 (2006)
Hairer, E., Wanner, G.: Solving ordinary differential equations, 2nd edn., vol. II. Springer, Berlin (1996). doi:10.1007/978-3-642-05221-7
Hairer, E., McLachlan, R. I., Razakarivony, A.: Achieving Brouwer’s law with implicit Runge-Kutta methods. BIT Numer. Math. 48(2), 231–243 (2008). doi:10.1007/s10543-008-0170-3
Hairer, E., Murua, A., Sanz-Serna, J. M.: The non-existence of symplectic multi-derivative Runge-Kutta methods. BIT Numer. Math. 34(1), 80–87 (1994). doi:10.1007/BF01935017
Higham, N. J.: Accuracy and stability of numerical algorithms. Siam. doi:10.1137/1.9780898718027 (2002)
Jay, L. O.: Preconditioning of implicit Runge-Kutta methods. Scalable Computing: Practice and Experience. 10 (2009)
Kahan, W.: Further remarks on reducing truncation errors. Commun. ACM 8(1), 40 (1965)
Liniger, W., Willoughby, R. A.: Efficient integration methods for stiff systems of ordinary differential equations. SIAM J. Numer. Anal. 7(1), 47–66 (1970). doi:10.1137/0707002
Muller, J., Brisebarre, N., De Dinechin, F., Jeannerod, C., Lefevre, V., Melquiond, G., Revol, N., Stehlé, D., Torres, S.: Handbook of floating-point arithmetic. Springer Science & Business Media. doi:10.1007/978-0-8176-4705-6 (2009)
Saad, Y.: Iterative methods for sparse linear systems. SIAM. doi:10.1137/1.9780898718003.bm (2003)
Sanz Serna, J., Calvo, M.: Numerical Hamiltonian problems. Chapman and Hall (1994)
Xie, D.: A new numerical algorithm for efficiently implementing implicit Runge-Kutta methods. Department of Mathematical Sciences. University of Wisconsin, Milwaukee, Wisconsin USA (2009)
Acknowledgements
M. Antoñana, J. Makazaga, and A. Murua have received funding from the Project of the Spanish Ministry of Economy and Competitiveness with reference MTM2016-76329-R (AEI/FEDER, EU), from the project MTM2013-46553-C3-2-P from Spanish Ministry of Economy and Trade, and as part of the Consolidated Research Group IT649-13 by the Basque Government.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Antoñana, M., Makazaga, J. & Murua, A. Efficient implementation of symplectic implicit Runge-Kutta schemes with simplified Newton iterations. Numer Algor 78, 63–86 (2018). https://doi.org/10.1007/s11075-017-0367-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11075-017-0367-0