Computational complexity of onestep methods for systems of differential equations
Author:
Arthur G. Werschulz
Journal:
Math. Comp. 34 (1980), 155174
MSC:
Primary 65L05; Secondary 34A50, 68C25
MathSciNet review:
551295
Fulltext 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 pthorder Taylor series method requiring only arithmetic operations per step as . (Moreover, we show that any such algorithm requires at least operations per step.) We compute the order which minimizes the complexity bounds for Taylor series and linear RungeKutta methods and show that in all cases this optimal order increases as the error criterion decreases, tending to infinity as tends to zero. Finally, we show that if certain derivatives are easy to evaluate, then Taylor series methods are asymptotically better than linear RungeKutta methods for problems of small dimension N.
 [A]
Allan
Borodin and Ian
Munro, The computational complexity of algebraic and numeric
problems, American Elsevier Publishing Co., Inc., New
YorkLondonAmsterdam, 1975. Elsevier Computer Science Library; Theory of
Computation Series, No. 1. 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, CarnegieMellon 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
(58 #25090)
 [J]
J.
C. Butcher, Implicit RungeKutta
processes, Math. Comp. 18 (1964), 50–64. MR 0159424
(28 #2641), http://dx.doi.org/10.1090/S00255718196401594249
 [J]
J.
C. Butcher, An order bound for RungeKutta methods, SIAM J.
Numer. Anal. 12 (1975), 304–315. MR 0381315
(52 #2212)
 [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
(43 #4255)
 [G]
G.
J. Cooper and J.
H. Verner, Some explicit RungeKutta methods of high order,
SIAM J. Numer. Anal. 9 (1972), 389–405. MR 0317546
(47 #6093)
 [A]
Avner
Friedman, Partial differential equations, Holt, Rinehart and
Winston, Inc., New YorkMontreal, Que.London, 1969. MR 0445088
(56 #3433)
 [P]
Peter
Henrici, Discrete variable methods in ordinary differential
equations, John Wiley & Sons, Inc., New YorkLondon, 1962. MR 0135729
(24 #B1772)
 [A]
C. HINDMARSH [1974], Numerical Solution of Ordinary Differential Equations: Lecture Notes, Lawrence Livermore Laboratory Report No. UCID16588, June, 1974.
 [G]
PÓLYA & G. SZEGÖ [1925], Aufgaben und Lehrsätze der Analysis, Vol. I, SpringerVerlag, Berlin, 1925.
 [L]
Louis
B. Rall, Computational solution of nonlinear operator
equations, With an appendix by Ramon E. Moore, John Wiley & Sons,
Inc., New YorkLondonSydney, 1969. MR 0240944
(39 #2289)
 [H]
Hans
J. Stetter, Analysis of discretization methods for ordinary
differential equations, SpringerVerlag, New YorkHeidelberg, 1973.
Springer Tracts in Natural Philosophy, Vol. 23. 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 OneStep Methods for Initial Value Problems, Computer Science Department Report, CarnegieMellon University, 1976.
 [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, CarnegieMellon University, 1974.
 [R]
 P. BRENT & H. T. KUNG [1978], "Fast algorithms for manipulating formal power series," J. Assoc. Comput. Mach., v. 25, 1978, pp. 581595. MR 0520733 (58:25090)
 [J]
 C. BUTCHER [1964], "Implicit RungeKutta processes," Math. Comp., v. 18, 1964, pp. 5064. MR 0159424 (28:2641)
 [J]
 C. BUTCHER [1975], "An order bound for RungeKutta methods," SIAM J. Numer. Anal., v. 12, 1975, pp. 304315. MR 0381315 (52:2212)
 [G]
 J. COOPER [1969], "Error bounds for some singlestep methods," Conf. on the Numerical Solution of Differential Equations, Lecture Notes in Math., vol. 109, SpringerVerlag, Berlin, 1969, pp. 140147. MR 0278525 (43:4255)
 [G]
 J. COOPER &. J. H. VERNER [1972], "Some explicit RungeKutta methods of high order," SIAM J. Numer. Anal., v. 9, 1972, pp. 389405. 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. UCID16588, June, 1974.
 [G]
 PÓLYA & G. SZEGÖ [1925], Aufgaben und Lehrsätze der Analysis, Vol. I, SpringerVerlag, 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, SpringerVerlag, 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 OneStep Methods for Initial Value Problems, Computer Science Department Report, CarnegieMellon 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:
http://dx.doi.org/10.1090/S00255718198005512950
PII:
S 00255718(1980)05512950
Article copyright:
© Copyright 1980
American Mathematical Society
