Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Computational complexity of one-step methods for systems of differential equations

Author: Arthur G. Werschulz
Journal: Math. Comp. 34 (1980), 155-174
MSC: Primary 65L05; Secondary 34A50, 68C25
MathSciNet review: 551295
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The problem is to calculate an approximate solution of an initial value problem for an autonomous system of N ordinary differential equations. Using fast power series techniques, we exhibit an algorithm for the pth-order Taylor series method requiring only $ O({p^N}\ln p)$ arithmetic operations per step as $ p \to + \infty $. (Moreover, we show that any such algorithm requires at least $ O({p^N})$ operations per step.) We compute the order which minimizes the complexity bounds for Taylor series and linear Runge-Kutta methods and show that in all cases this optimal order increases as the error criterion $ \varepsilon $ decreases, tending to infinity as $ \varepsilon $ tends to zero. Finally, we show that if certain derivatives are easy to evaluate, then Taylor series methods are asymptotically better than linear Runge-Kutta methods for problems of small dimension N.

References [Enhancements On Off] (What's this?)

  • [A] Allan Borodin and Ian Munro, The computational complexity of algebraic and numeric problems, American Elsevier Publishing Co., Inc., New York-London-Amsterdam, 1975. Elsevier Computer Science Library; Theory of Computation Series, No. 1. MR 0468309
  • [R] P. BRENT [1974], Efficient Methods for Finding Zeros of Functions Whose Derivatives are Easy to Evaluate, Computer Science Department Report, Carnegie-Mellon University, 1974.
  • [R] R. P. Brent and H. T. Kung, Fast algorithms for manipulating formal power series, J. Assoc. Comput. Mach. 25 (1978), no. 4, 581–595. MR 0520733,
  • [J] J. C. Butcher, Implicit Runge-Kutta processes, Math. Comp. 18 (1964), 50–64. MR 0159424,
  • [J] J. C. Butcher, An order bound for Runge-Kutta methods, SIAM J. Numer. Anal. 12 (1975), 304–315. MR 0381315,
  • [G] G. J. Cooper, Error bounds for some single step methods, Conf. on Numerical Solution of Differential Equations (Dundee, 1969) Springer, Berlin, 1969, pp. 140–147. MR 0278525
  • [G] G. J. Cooper and J. H. Verner, Some explicit Runge-Kutta methods of high order, SIAM J. Numer. Anal. 9 (1972), 389–405. MR 0317546,
  • [A] Avner Friedman, Partial differential equations, Holt, Rinehart and Winston, Inc., New York-Montreal, Que.-London, 1969. MR 0445088
  • [P] Peter Henrici, Discrete variable methods in ordinary differential equations, John Wiley & Sons, Inc., New York-London, 1962. MR 0135729
  • [A] C. HINDMARSH [1974], Numerical Solution of Ordinary Differential Equations: Lecture Notes, Lawrence Livermore Laboratory Report No. UCID-16588, June, 1974.
  • [G] PÓLYA & G. SZEGÖ [1925], Aufgaben und Lehrsätze der Analysis, Vol. I, Springer-Verlag, Berlin, 1925.
  • [L] Louis B. Rall, Computational solution of nonlinear operator equations, With an appendix by Ramon E. Moore, John Wiley & Sons, Inc., New York-London-Sydney, 1969. MR 0240944
  • [H] Hans J. Stetter, Analysis of discretization methods for ordinary differential equations, Springer-Verlag, New York-Heidelberg, 1973. Springer Tracts in Natural Philosophy, Vol. 23. MR 0426438
  • [G] SZEGÖ [1959], Orthogonal Polynomials, Amer. Math. Soc. Colloq. Publ., Vol. 23, Amer. Math. Soc., Providence, R. I., 1959.
  • [J] F. TRAUB & H. WOŹNIAKOWSKI [1976], "Strict lower and upper bounds on iterative complexity," in Analytic Computational Complexity (J. F. Traub, Ed.), Academic Press, New York, 1976.
  • [A] G. WERSCHULZ [1976], Optimal Order and Minimal Complexity of One-Step Methods for Initial Value Problems, Computer Science Department Report, Carnegie-Mellon University, 1976.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65L05, 34A50, 68C25

Retrieve articles in all journals with MSC: 65L05, 34A50, 68C25

Additional Information

Article copyright: © Copyright 1980 American Mathematical Society

American Mathematical Society