text: In this paper we investigate the computational complexity of solving ordinary differential equations (ODEs) y ' = p ( y ) over unbounded time domains, where p is a vector of polynomials. Contrarily to the bounded (compact) time case, this problem has not been well-studied, apparently due to the "intuition" that it can always be reduced to the bounded case by using rescaling techniques. However, as we show in this paper, rescaling techniques do not seem to provide meaningful insights on the complexity of this problem, since the use of such techniques introduces a dependence on parameters which are hard to compute.We present algorithms which numerically solve these ODEs over unbounded time domains. These algorithms have guaranteed accuracy, i.e. given some arbitrarily large time t and error bound e as input, they will output a value y ? which satisfies ? y ( t ) - y ? ? ? e . We analyze the complexity of these algorithms and show that they compute y ? in time polynomial in several quantities including the time t, the accuracy of the output e and the length of the curve y from 0 to t, assuming it exists until time t. We consider both algebraic complexity and bit complexity.
  @cite_7: 
  @cite_1: Abstract This paper discusses several examples of ordinary differential equation (ODE) applications that are difficult to solve numerically using conventional techniques, but which can be solved successfully using the Taylor series method. These results are hard to obtain using other methods such as Runge–Kutta or similar schemes; indeed, in some cases these other schemes are not able to solve such systems at all. In particular, we explore the use of the high-precision arithmetic in the Taylor series method for numerically integrating ODEs. We show how to compute the partial derivatives, how to propagate sets of initial conditions, and, finally, how to achieve the Brouwer’s Law limit in the propagation of errors in long-time simulations. The TIDES software that we use for this work is freely available from a website.
  @cite_17: In this paper we analyze the problem of adaptivity for one-step numerical methods for solving ODEs, both IVPs and BVPs, with a view to generating grids of minimal computational cost for which the local error is below a prescribed tolerance (optimal grids). The grids are generated by introducing an auxiliary independent variable τ and finding a grid deformation map, t=Θ(τ), that maps an equidistant grid τj to a non-equidistant grid in the original independent variable, tj . An optimal deformation map Θ is determined by a variational approach. Finally, we investigate the cost of the solution procedure and compare it to the cost of using equidistant grids. We show that if the principal error function is non-constant, an adaptive method is always more efficient than a non-adaptive method.
  @cite_3: Abstract “Church’s thesis” is at the foundation of computer science. We point out that with any particular set of physical laws, Church’s thesis need not merely be postulated, in fact it may be decidable. Trying to do so is valuable. In Newton’s laws of physics with point masses, we outline a proof that Church’s thesis is false; physics is unsimulable. But with certain more realistic laws of motion, incorporating some relativistic effects, the extended Church’s thesis is true. Along the way we prove a useful theorem: a wide class of ordinary differential equations may be integrated with “polynomial slowdown”. Warning: we cannot give careful definitions and caveats in this abstract–you must read the full text—and interpreting our results is not trivial.
  @cite_6: This article introduces the software package TIDES and revisits the use of the Taylor series method for the numerical integration of ODEs. The package TIDES provides an easy-to-use interface for standard double precision integrations, but also for quadruple precision and multiple precision integrations. The motivation for the development of this package is that more and more scientific disciplines need very high precision solution of ODEs, and a standard ODE method is not able to reach these precision levels. The TIDES package combines a preprocessor step in M athematica that generates Fortran or C programs with a library in C. Another capability of TIDES is the direct solution of sensitivities of the solution of ODE systems, which means that we can compute the solution of variational equations up to any order without formulating them explicitly. Different options of the software are discussed, and finally it is compared with other well-known available methods, as well as with different options of TIDES. From the numerical tests, TIDES is competitive, both in speed and accuracy, with standard methods, but it also provides new capabilities.
  @cite_16: This paper revisits the Taylor method for the numerical integration of initial value problems of Ordinary Differential Equations (ODEs). The main goal is to present a computer program that outputs a specific numerical integrator for a given set of ODEs. The generated code includes a function to compute the jet of derivatives of the solution up to a given order plus adaptive selection of order and step size at run time. The package provides support for several extended precision arithmetics, including user-defined types. The paper discusses the performance of the resulting integrator in some examples, showing that it is very competitive in many situations. This is especially true for integrations that require extended precision arithmetic. The main drawback is that the Taylor method is an explicit method, so it has all the limitations of these kind of schemes. For instance, it is not suitable for stiff systems.
  @cite_20: The problem is to calculate an approximate solution of an initial value problem for a scalar autonomous differential equation. A generalized notion of a nonlinear Runge-Kutta (NRK) method is defined. We show that the order of anys-stage NRK method cannot exceed 2s−1; hence, the family of NRK methods due to Brent has the maximal order possible. Using this result, we derive complexity bounds on the problem of finding an approximate solution with error not exceeding e. We also compute the order which minimizes these bounds, and show that this optimal order increases as e decreases, tending to infinity as e tends to zero.
  @cite_11: The cost of solving an initial value problem for ordinary differential equations to accuracy 2 is polynomial in ln e. Adaptive step-size control is never theoretically more costly than fixed step-size control, and can be an unbounded factor less costly. These results contradict the standard theory, but are based on more realistic assumptions.
summary: Finally, this problem has been widely studied in Numerical Analysis but the point of view is usually different and more focused on practically fast algorithms rather than asymptotically efficient algorithms. Some work @cite_17 @cite_11 @cite_20 @cite_3 suggests that any polynomial time algorithm must have variable order, and that adaptive algorithms are theoretically superior to non-adaptive ones This is in contrast with classical results which state the contrary but under usually unrealistic hypothesis, see @cite_11 . While adaptive algorithms have been widely studied, high-order algorithms are not mainstream because they are expensive in practice. Variable order methods have been used in @cite_7 , @cite_16 , @cite_3 , @cite_1 , @cite_6 and some polynomial time algorithms have been obtained over compact domains or over arbitrary domains but with stronger hypothesis.