Parallel one-step methods with minimal parallel stages Original Research Article

The computing time of one-step methods for the numerical solution of initial-value problems y′(x) = f(x,y); y(x0) = y0 is closely related to the order of the approximation and the number of evaluations of f per step (called stages). If parallel computers are used, the definition of stages has to be adapted, as many evaluations can be done simultaneously. For explicit Runge-Kutta (ERK) methods of order p, the minimal number of parallel stages sp is known to be sp = p. Here the result is generalized for any arbitrary type of explicit one-step method. For some important classes of implicit methods like implicit Runge-Kutta (IRK) methods, diagonally implicit Runge-Kutta (DIRK) methods, singly diagonally implicit Runge-Kutta (SDIRK) methods, semi-implicit Runge-Kutta (SIRK) methods and Rosenbrock-Wanner (ROW) methods, the same technique can be applied, which leads to lower bounds of the minimal sp. Finally, we show that for singly diagonal implicit ROW methods sp = p − 1 is optimal.