Adaptive Pipelining Methods for Parallel-in-Time Integration

The parallel numerical solution of time-dependent partial differential equations (PDEs) has long been the focus of the high performance computing community. In order to effectively utilize the large number of available processors in modern computing clusters, the classical approach is to apply a semi-discretization in time to the time-dependent PDE, and then apply domain decomposition (DD) in space. For highly refined models however, accuracy or stability constraints often limit the size of the time step; the time stepping process, because of its sequential nature, often becomes the bottleneck. Consequently, parallelization in the time direction has become an increasingly pressing issue.

In this project, we will design new time-parallelization schemes based on waveform relaxation (WR), which are methods of the space-time domain decomposition type. Our new methods are competitive with sequential time-stepping in terms of total number of floating point operations required, and their convergence does not deteriorate with the length of the time horizon. The key idea is to eliminate computations that do not contribute to fast convergence of the overall solution. The resulting methods are mathematically different from standard WR methods, and a key part of this project is to analyze their convergence. Preliminary results show that our approach works well with advection-dominated problems and is able to multiply the overall speedup numbers by about an order of magnitude.

In order to accommodate iterative solvers other than DD, we propose reformulating WR as an abstract fixed point iteration involving the unknown solution, the solution at the previous time step, and interface data coming from the previous WR iteration. The resulting framework is general enough to convert any iterative method for elliptic problems into an efficiently implemented WR-like method. Crucially, we will produce a customizable, easy-to-use code base in C++/MPI for time-parallel integration, which will be shared with the research community. This will allow engineers and researchers to add time parallelism into their codes easily, and to effectively utilize tera-scale computing resources to speed up or increase the resolution of their simulations.

To ensure that our framework also works well for realistic applications, we will apply it to the simulation of unsaturated porous media flow modelled by the Richards equation. To solve this equation, we will design a WR version of the nonlinear Robin-Robin method. We will analyze its behaviour theoretically and perform a numerical comparison of its convergence rate and parallel efficiency against standard time-stepping and/or parareal approaches.