Limits of parallelism in explicit ODE methods (Q1200540)

The authors present the technical details and proofs of theses formulated in their earlier paper [in: Proc. IMA Conf. on Computational ODEs. J. R. Cash and I. Gladwell (eds.), Oxford University Press (to appear)]. They consider explicit general-purpose numerical methods for solving the system of ordinary differential equations \(y'(t) = f(y(t))\), \(t_ 0 \leq t \leq t_{out}\), \(y(t_ 0) = \eta\). They assert that, for the model problem \(y' = \lambda y\), one-step and multistep methods have no parallelism but that true multivalue methods have some parallelism, the degree of parallelism limited by the ``number of saved values''; there is absolutely no benefit in having the degree of parallelism (number of processors) to exceed the number of saved values. The authors conclude that dramatic speedups are not possible in general when using parallelization of the computational process for such problems, including nonlinear ones.