Fixed versus variable order Runge-Kutta

ABSTRACT

Popular codes for the numerical solution of nonstiff ordinary differential equations (ODEs) are based on a (fixed order) Runge-Kutta method, a variable order Adams method, or an extrapolation method. Extrapolation can be viewed as a variable order Runge-Kutta method. It is plausible that variation of order could lead to a much more efficient Runge-Kutta code, but numerical comparisons have been contradictory. We reconcile previous comparisons by exposing differences in testing methodology and incompatibilities of the implementations tested. An experimental Runge-Kutta code is compared to a state-of-the-art extrapolation code. With some qualifications, the extrapolation code shows no advantage. Extrapolation does not appear to be a particularly effective way to vary the order of Runge-Kutta methods. Although an acceptable way to solve nonstiff problems, our tests raise the question as to whether there is any point in pursuing it as a separate method.

REFERENCES

• 1: BAUER, H. J. Entwicklung leistungsffihiger extrapolationscodes. Diplomarbeit, Inst. f. Ang. Math., Univ. of Heidelberg, F.R.G., 1983.
• 2: BETTIS, D.G. Efficient embedded Runge-Kutta methods, In Numerical Treatment of Differential Equations, R. Bulirsch, Ed. Lecture Notes in Math. No. 631, Springer, New York, 1978, pp 9-18.
• 3: BULIRSCH R., AND STOER, J. Numerical treatment of ordinary differential equations by extrapolation methods. Numer. Math. 8 {1966) 1-13.
• 4: CLARK, N.W. A study of some numerical methods for the integration of systems of first-order ordinary differential equations. Rep. ANL-7428, Argonne National Laboratories, Argonne, II., 1968.
• 5: DEUFLHARD, P. Order and stepsize control in extrapolation methods. Numer. Math. 41 {1983) 399-422.
• 6: DEUFLHARD, P. Recent progress in extrapolation methods for ordinary differential equations. Rep. 224, SFB 123, University of Heidelberg, F.R.G., 1983.
• 7: DIEKHOFF, H.-J., LORY, P., OBERLE, H. J., PESCH, H.-J., RENTROP, P., AND SEYDEL, R. Comparing routines for the numerical solution of initial value problems of ordinary differential equations in multiple shooting. Numer. Math. 27 (1977) 449-469. Also Rep. 7520, Inst. f. Math., Technical University of Munich, F.R.G.
• 8: ENRIGHT, W. H., AND HULL, rl'. E. Test results on initial value methods for non-stiff ordinary differential equations. SIAM J. Numer. Anal. 13 (1976) 944-961.
• 9: FRAZHO, D. B., POWERS, W. F., AND CANALE, R.P. Numerical integration aspects of a nutrient utilization ecological problem. In Proceedings of the Conference on Numerical Solution of ODEs, Lecture Notes in Mathematics, No. 362, D.G. Bettis, Ed. Springer-Verlag, New York, 1974, pp. 167-182.
• 10: G. K. Gupta, A Note About Overhead Costs in ODE Solvers, ACM Transactions on Mathematical Software (TOMS), v.6 n.3, p.319-326, Sept. 1980 [doi>10.1145/355900.355904]
• 11: HULL, T. E., ENRIGHT, W. H., FELLEN, B. M., AND SEDGWICK, A.E. Comparing numerical methods for ordinary differential equations. SIAM J. Numer. Anal. 9 (1972) 603-637.
• 12: HUSSELS, H. G. Schrittweitensteuerung bei der Integration gewShnlicher Differentialgleichungen mit Extrapolationsverfahren. Diplomarbeit, Mathematisches institiit, Universitat Cologne, F.R.G., 1973.
• 13: INGRAM, H.L. A comparison of digital computer programs for the numerical solution of ordinary differential equations. Rep. NASA TMX-64781, Marshall Space Flight Center, Alabama, 1973.
• 14: Fred T. Krogh, On Testing a Subroutine for the Numerical Integration of Ordinary Differential Equations, Journal of the ACM (JACM), v.20 n.4, p.545-562, Oct. 1973 [doi>10.1145/321784.321786]
• 15: PRINCE, P. J., AND DORMAND, J.R. High order embedded Runge-Kutta formulae. J. Comp. Appl. Math. 7 {1981) 67-75.
• 16: SHAMPINE, L.F. Limiting precision in differential equation solvers. Math. Comp. 28 (1974) 141-144.
• 17: SHAMPINE, L.F. Stiffness and non-stiff differential equation solvers. In Numerische Behandlung yon Dif{erentialgleichungen, R. Ansorge et al. Eds. Birkh~iuser, Basel, 1975.
• 18: SHAMPINE, L.F. The quality of Runge-Kutta formulas. Rep. SAND76-0370, Sandia National Laboratories, Albuquerque, New Mexico, 1976.
• 19: L. F. Shampine, Storage Reduction for Runge-Kutta Codes, ACM Transactions on Mathematical Software (TOMS), v.5 n.3, p.245-250, Sept. 1979 [doi>10.1145/355841.355842]
• 20: SHAMPINE, L.F. The step sizes used by one-step codes for ODEs. Appl. Numer. Math. 1 (1985) 95-106.
• 21: SHAMPINE, L.F. Interpolation for Runge-Kutta methods. SIAM J. Numer. Anal. 5 {1985), 1014-1027.
• 22: SHAMPINE, L. F., AND BACA, L.S. Fixed vs. variable order Runge-Kutta, Rep. SAND84-1410, Sandia National Laboratories, Albuquerque, New Mexico, 1984.
• 23: SHAMPINE, L. F., AND GORDON, M.K. Computer Solution of Ordinary Differential Equations: The Initial Value Problem. Freeman, San Francisco, 1975.
• 24: SHAMPINE, L. F., AND WATTS, H.A. The art of writing a Runge-Kutta code, II. Appl. Math. Comput. 5 {1979) 93-121.
• 25: SHAMPINE, L. F., BACA, L. S., AND BAUER, H.-J. Output in extrapolation codes. Comp. & Maths. with Appls. 9 (1983) 245-255.
• 26: SHAMPINE, L. F., GORDON, M. K., AND WISNIEWSKI, J.A. Variable order Runge-Kutta codes. In Computational Techniques for Ordinary Differential Equations, I. Gladwell and D. K. Sayers, Eds. Academic Press, New York, 1980.
• 27: SHAMPINE, L. F., WATTS, H. A., AND DAVENPORT, S.M. Solving non-stiff ordinary differential equations--the state of the art. SIAM Rev. 18 (1976) 376-411.
• 28: STOER, J. Extrapolation methods for the solution of initial value problems and their practical realization. In Proceedings of the Conference on Numerical Solution of ODEs, Lecture Notes in Math., No. 362, D. G. Bettis, Ed. Springer-Verlag, New York, 1974, pp 1-21.
• 29: VERNER, J.H. Families of imbedded Runge-Kutta methods. SIAM J. Numer. Anal. 16 (1979) 857-875.
• 30: WATTS, H.A. Starting step size for an ODE solver. J. Comp. Appl. Math. 9 (1983) 177-191.
• 31: WATTS, H.A. Step size control in ODE solvers. Trans. Soc. Comput. Sim. I (1984) 15-25.

INDEX TERMS

Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.7 Ordinary Differential Equations
          Subjects: Initial value problems; One-step (single step) methods
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis; Efficiency

General Terms:
Algorithms, Measurement, Performance