On the Theory of Parallel Runge—Kutta Methods

The purpose of this paper is to create a theoretical framework for parallelization of Runge-Kutta methods. We investigate the inherent potential for parallelism by considering digraphs of Runge-Kutta matrices. By highlighting the important role of the underlying sparsity pattern, this approach narrows the field down to certain types of methods. These are further investigated by two techniques: perturbed collocation and elementary differentials. Our analysis leads to singly diagonally implicit fourth-order L-stable methods that can be implemented on two processors (in MIMD architecture) with computational cost of two ‘conventional’ stages. We also debate local error control and present a technique that can be used to this end.