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

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.