Time-Parallel Solution of Structural Dynamics
Figure 1: First time-parallel strategy for large-scale systems and reduced-order models.
This project involves the developement and the practical implementation of methods relying on computing the solution of an evolution PDE concurrently at several time-levels. Numerical experiments demonstrate the potential speedup of this approach for both linear and nonlinear structural dynamics.

For more information:
Julien Cortial

The parallelization of the time-loop of a partial differential equation solver, or time-parallelism, has in general received little attention in the literature compared to the parallelization of its space-loop. This is because time-parallelism --- where the solution is computed simultaneously at different time-instances --- is harder to achieve efficiently than space-parallelism, due to the inherently sequential nature of the time-integration process. However, time-parallelism can be of paramount importance to many applications. These include those time-dependent problems where the underlying computational models have either very few spatial degrees of freedom (dof) to enable any significant amount of space-parallelism, or not enough spatial dof to efficiently exploit a given large number of processors. Problems in robotics and protein folding, and more generally, time-dependent problems arising from reduced-order models usually fall in the first category. Many structural dynamics problems, even those with hundreds of thousands of dof, can fall in the second category when massively parallel computations are desired. Accelerating the time-to-solution of the first category of problems is crucial for real-time or near-real-time applications, and time-parallelism can be a key factor for achieving this objective. With the advent of massively parallel systems with thousands of cores, time-parallelism also provides a venue for reducing the time-to-solution of fixed size problems of the second category below the minimum attainable using space-parallelism alone on such systems.

To achieve the aforementioned objective, the Parallel-In-Time Algorithm (or PITA) relies on classical domain decomposition principles that are usually applied to the spatial component of a PDE. The time-domain is first divided into time-slices to be processed independently. This decomposition can also be seen as defining a coarse time-grid as opposed to the underlying fine time-grid, chosen such as to allow convergence with the sought-after accuracy. Starting with initial approximate seed values defined on the coarse time-grid, the system evolution is then independently computed on each time-slice using a classical time-stepping integrator. This solution exhibits discontinuities or jumps at the time-slice boundaries if the initial guess is not accurate enough. Applying a Newton-like approach to the global time-dependent equation, a correction function is then computed so that its values on the coarse time-grid are added to the current seeds to improve their accuracy. The solution can thus be iteratively refined until convergence, which can be monitored by the reduction of the jumps.

While most steps of this iteration process are naturally parallel, the key challenge is to perform efficiently the sequential correction computation. For structural dynamics the best strategy consists in propagating only a relevant part of the jump on the fine time-grid while retaining an acceptable computational efficiency. Typically speed-up factors of 3 or more can be achieved for both linear and non-linear dynamics problems.  

Figure 2: Second time-parallel strategy for large-scale systems and reduced-order models.