Computational complexity of one-step methods for systems of differential equations
HTML articles powered by AMS MathViewer
- by Arthur G. Werschulz PDF
- Math. Comp. 34 (1980), 155-174 Request permission
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
- Allan Borodin and Ian Munro, The computational complexity of algebraic and numeric problems, Elsevier Computer Science Library: Theory of Computation Series, No. 1, American Elsevier Publishing Co., Inc., New York-London-Amsterdam, 1975. MR 0468309 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 and H. T. Kung, Fast algorithms for manipulating formal power series, J. Assoc. Comput. Mach. 25 (1978), no. 4, 581–595. MR 520733, DOI 10.1145/322092.322099
- J. C. Butcher, Implicit Runge-Kutta processes, Math. Comp. 18 (1964), 50–64. MR 159424, DOI 10.1090/S0025-5718-1964-0159424-9
- J. C. Butcher, An order bound for Runge-Kutta methods, SIAM J. Numer. Anal. 12 (1975), 304–315. MR 381315, DOI 10.1137/0712025
- 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. J. Cooper and J. H. Verner, Some explicit Runge-Kutta methods of high order, SIAM J. Numer. Anal. 9 (1972), 389–405. MR 317546, DOI 10.1137/0709037
- Avner Friedman, Partial differential equations, Holt, Rinehart and Winston, Inc., New York-Montreal, Que.-London, 1969. MR 0445088
- Peter Henrici, Discrete variable methods in ordinary differential equations, John Wiley & Sons, Inc., New York-London, 1962. MR 0135729 C. HINDMARSH [1974], Numerical Solution of Ordinary Differential Equations: Lecture Notes, Lawrence Livermore Laboratory Report No. UCID-16588, June, 1974. PÓLYA & G. SZEGÖ [1925], Aufgaben und Lehrsätze der Analysis, Vol. I, Springer-Verlag, Berlin, 1925.
- Louis B. Rall, Computational solution of nonlinear operator equations, John Wiley & Sons, Inc., New York-London-Sydney, 1969. With an appendix by Ramon E. Moore. MR 0240944
- Hans J. Stetter, Analysis of discretization methods for ordinary differential equations, Springer Tracts in Natural Philosophy, Vol. 23, Springer-Verlag, New York-Heidelberg, 1973. MR 0426438 SZEGÖ [1959], Orthogonal Polynomials, Amer. Math. Soc. Colloq. Publ., Vol. 23, Amer. Math. Soc., Providence, R. I., 1959. 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. G. WERSCHULZ [1976], Optimal Order and Minimal Complexity of One-Step Methods for Initial Value Problems, Computer Science Department Report, Carnegie-Mellon University, 1976.
Additional Information
- © Copyright 1980 American Mathematical Society
- Journal: Math. Comp. 34 (1980), 155-174
- MSC: Primary 65L05; Secondary 34A50, 68C25
- DOI: https://doi.org/10.1090/S0025-5718-1980-0551295-0
- MathSciNet review: 551295