My Summary of the Chapter: A Time-Parallel Implicit Methodology for the Near-Real-Time Solution of Systems of Linear Oscillators

• Scenarios where parallelization in time is of paramount importance:

  • When space parallelism is not feasible or cannot exploit all the compute cores available.
  • For real-time computation, parallelizing in both space and time might be required.
  • When the problem is too small to be parallelized in space (infeasible) such as in protein folding and robotics.
  • Used in ROM.

• Parallelization in time based on waveform relaxation does not work well for hyperbolic problems. For parabolic problems, the parallel efficiency was the focus of most of the available studies. However, no or little information about the performance compared to the serial version (the non-iterative one) is available.

• A second approach for parallelization was to convert the initial value problem to a boundary value problem. The drawback is that the solver for the original problem is different from that of the new problem.

• The third approach that is adopted in this work is parallelization through time domain decomposition.

• (In a previous work by Farhat et al) The Parareal algorithm framework was extended to the case of multistage ODE solvers and applied to a new family of time-parallel implicit ODE solvers named PITA.

• PITA worked well for parabolic and first-order hyperbolic problems, but it was not efficient for second order hyperbolic problems. In the later case, a parasitic beating phenomenon was generated by the PITA framework. This resulted in severe restriction on the time step to maintain stability.

• The goal of this paper is to present a new framework for parallel time integration that maintains the stability properties of the original solver, even for second-order hyperbolic problems. The focus here will be on the linear case only.

• For linear problems, parareal and PITA algorithms are equivalent.

• For the nonlinear case, the difference between parareal and PITA is in the way they propagate the jumps on the coarse time grid. PITA adopts newtons method for this propose while parareal allows the user to choose the preferred coarse propagator.

• PITA has significant potential for speeding up solving first-order hyperbolic problems (exemplified by gas dynamics) on massively parallel machines.

• For second-order nonlinear or linearized hyperbolic problems, PITA generates beating phenomena which severely limits the stability time step (exemplified by linear or linearized structural dynamics applications). This is true for parareal algorithm as well. Artificial dissipation was suggested to be introduced to restore the stability in parareal algorithm, however, artificial dissipation might harm accuracy and is not commonly used in structural dynamics.

• The paper presents a new parallel time integrator (which is the main contribution of this paper) that is based on the concept of parareal and PITA but differs in the way of propagating the jumps (that occurred between the coarse (seed) of a time interval and the final fine solver solution of the previous time interval). The advantages of this new framework are that it maintains the stability properties of the ODE solver (by filtering out the beating source using specifically designed projector) and preserves the order of accuracy of the chosen implicit coarse solver.

• Parareal and the original PITA propagate the jumps on the coarse grid only (to avoid cost of propagating the jumps on the fine grid). However, the suggested algorithm propagates the jumps on both grids but uses special projector to filter the source of the beating phenomenon in the jump and to reduce the cost of propagating the jump in the fine grid.

• Two experiments were presented, the first one (free vibration of a 3D structure) is a perfect candidate for parallelization in time as it has 348 dofs only. For this experiment, the suggested method converged in two iterations. The other experiment is for dynamic responses of an F-16 fighter aircraft with 168,799 dofs. The method converged in about 4 iterations. Both examples had 24 time subdomains.