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 Free Access

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] BORODIN & I. MUNRO [1975], The Computational Complexity of Algebraic and Numeric Problems, American Elsevier, New York, 1975. MR 0468309 (57:8145)
  • [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] P. BRENT & H. T. KUNG [1978], "Fast algorithms for manipulating formal power series," J. Assoc. Comput. Mach., v. 25, 1978, pp. 581-595. MR 0520733 (58:25090)
  • [J] C. BUTCHER [1964], "Implicit Runge-Kutta processes," Math. Comp., v. 18, 1964, pp. 50-64. MR 0159424 (28:2641)
  • [J] C. BUTCHER [1975], "An order bound for Runge-Kutta methods," SIAM J. Numer. Anal., v. 12, 1975, pp. 304-315. MR 0381315 (52:2212)
  • [G] J. COOPER [1969], "Error bounds for some single-step methods," Conf. on the Numerical Solution of Differential Equations, Lecture Notes in Math., vol. 109, Springer-Verlag, Berlin, 1969, pp. 140-147. MR 0278525 (43:4255)
  • [G] J. COOPER &. J. H. VERNER [1972], "Some explicit Runge-Kutta methods of high order," SIAM J. Numer. Anal., v. 9, 1972, pp. 389-405. MR 0317546 (47:6093)
  • [A] FRIEDMAN [1969], Partial Differential Equations, Holt, Rinehart, and Winston, New York, 1969. MR 0445088 (56:3433)
  • [P] HENRICI [1962], Discrete Variable Methods in Ordinary Differential Equations, Wiley, New York, 1962. MR 0135729 (24:B1772)
  • [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] B. RALL [1969], Computational Solution of Nonlinear Operator Equations, Wiley, New York, 1969. MR 0240944 (39:2289)
  • [H] J. STETTER [1973], Analysis of Discretization Methods for Ordinary Differential Equations, Springer-Verlag, Berlin, 1972. MR 0426438 (54:14381)
  • [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

DOI: https://doi.org/10.1090/S0025-5718-1980-0551295-0
Article copyright: © Copyright 1980 American Mathematical Society