Exploiting limited access distance of ODE systems for parallelism and locality in explicit methods

Abstract

The solution of initial value problems of large systems of ordinary dierential equations (ODEs) is computationally intensive and demands for ecient parallel solution techniques that take into account the complex architectures of modern parallel computer systems. This article discusses implementation techniques suitable for ODE systems with a special coupling structure, called limited access distance, which typically arises from the discretization of systems of partial differential equations (PDEs) by the method of lines. It describes how these techniques can be applied to dierent explicit ODE methods, namely embedded Runge{Kutta (RK) methods, iterated RK methods, extrapolation methods, and Adams{Bashforth (AB) methods. Runtime experiments performed on parallel computer systems with dierent architectures show that these techniques can signicantly improve runtime and scalability. By example of Euler's method it is demonstrated that these techniques can also be applied to devise high-performance GPU implementations.