Abstract: Traditionally, time-dependent partial differential equations (PDEs) are simulated via the procedure of sequential time-stepping. However, it is also possible to solve these PDEs in a parallel-in-time fashion. To date, many successful parallel-in-time strategies have been developed, particularly for diffusion-dominated PDE problems. There has been much less success in this area for hyperbolic problems.

 

We consider solving linear hyperbolic PDEs using the iterative, multilevel parallel-in-time method known as multigrid reduction-in-time (MGRIT). The key to efficient time integration with MGRIT is the use of a coarse-grid problem which should both closely approximate the original discretized (fine-grid) problem and be less expensive to solve than it. We discuss the development of new coarse-grid problems that derive from optimization techniques and semi-Lagrangian discretization methods. These coarse-grid problems lead to dramatically improved MGRIT convergence relative to existing approaches. Furthermore, we demonstrate that they lead to an MGRIT method capable of solving problems in a faster wall-clock time than sequential time-stepping.