Parallel methods for ordinary differential equations

Remarkably few methods have been proposed for the parallel integration of ordinary differential equations (ODEs). In part this is because the problems do not have much natural parallelism (unless they are virtually uncoupled systems of equations, in which case the method is obvious). In part it is because the subproblems arising in the solution of ODEs (for example, the solution of linear equations) are the ones that have provided the challenges for parallelism. This paper surveys some of the methods that have been proposed, and suggests some additional methods that are suitable for special cases, such as linear problems. It then looks at the possible application of large-scale parallelism, particularly across the method. If efficiency is of no concern (that is, if there is an arbitrary number of proceessors) there are some ways in which the solution of stiff equations can be done more rapidly; in fact, a speed up from a parallel time of 0(N ²) to 0(logN) for N equations might be possible if communication time is ignored. This is obtained by trying to perform as much as possible of the matrix arithmetic associated with the solution of the linear equations at each step in advance of that step and in parallel with the integration of earlier steps.