×

Efficient implementation of symplectic implicit Runge-Kutta schemes with simplified Newton iterations. (English) Zbl 1433.65131

Summary: 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 \(d\)-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 \(sd \times sd\) 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.

MSC:

65L06 Multistep, Runge-Kutta and extrapolation methods for ordinary differential equations
65L05 Numerical methods for initial value problems involving ordinary differential equations
65L04 Numerical methods for stiff equations

Software:

ITER-REF; mctoolbox

References:

[1] 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) · Zbl 1380.65416
[2] 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 · Zbl 1197.65240 · doi:10.1016/j.cpc.2008.11.005
[3] 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 · Zbl 0368.65037 · doi:10.1137/0714069
[4] 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 · Zbl 1291.65357 · doi:10.1007/s11075-014-9825-0
[5] Butcher, J. C.: On the implementation of implicit Runge-Kutta methods. BIT Numer. Math. 16(3), 237-240 (1976). doi:10.1007/BF01932265 · Zbl 0336.65037 · doi:10.1007/BF01932265
[6] 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) · Zbl 1094.65125
[7] Hairer, E., Wanner, G.: Solving ordinary differential equations, 2nd edn., vol. II. Springer, Berlin (1996). doi:10.1007/978-3-642-05221-7 · Zbl 0859.65067
[8] 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 · Zbl 1148.65058 · doi:10.1007/s10543-008-0170-3
[9] 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 · Zbl 0816.65043 · doi:10.1007/BF01935017
[10] Higham, N. J.: Accuracy and stability of numerical algorithms. Siam. doi:10.1137/1.9780898718027 (2002) · Zbl 1011.65010
[11] Jay, L. O.: Preconditioning of implicit Runge-Kutta methods. Scalable Computing: Practice and Experience. 10 (2009) · Zbl 1148.65058
[12] Kahan, W.: Further remarks on reducing truncation errors. Commun. ACM 8(1), 40 (1965) · doi:10.1145/363707.363723
[13] 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 · Zbl 0187.11003 · doi:10.1137/0707002
[14] 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) · Zbl 1197.65001
[15] Saad, Y.: Iterative methods for sparse linear systems. SIAM. doi:10.1137/1.9780898718003.bm (2003) · Zbl 1031.65046
[16] Sanz Serna, J., Calvo, M.: Numerical Hamiltonian problems. Chapman and Hall (1994) · Zbl 0816.65042
[17] Xie, D.: A new numerical algorithm for efficiently implementing implicit Runge-Kutta methods. Department of Mathematical Sciences. University of Wisconsin, Milwaukee, Wisconsin USA (2009) · Zbl 0187.11003
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.