Multigrid Reduction in Time for Chaotic and Hyperbolic Problems (Final Report)

Abstract

The coming massive parallelism of exascale computing presents a pressing challenge for the many DOE simulations of time-dependent partial differential equations (PDEs), which typically use traditional sequential time stepping methods. Since this traditional approach is inherently serial, it presents a sequential bottleneck when moving to exascale computing, because future performance gains will come through greater concurrency, not faster clock speeds. Thus, the goal of this work is to research parallelism in time, i.e., methods that compute multiple time values simultaneously, not sequentially. The focus will be on hyperbolic and chaotic problems of interest to DOE, with the goal of enabling scalable simulations of time-dependent hyperbolic and chaotic problems on future architectures. The chosen methodology for solving these problems parallel-in-time is multigrid, because multigrid (when it works) is a powerful, optimal, and scalable solver for discretized PDEs. Multigrid is already commonly used in many DOE simulations for scalably and optimally solving space-only PDE problems. The areas of hyperbolic and chaotic problems are chosen because of their relevance to problems of programmatic interest to DOE. However, these problems are also well-known to be difficult for parallel-in-time methods, with the most common method, parareal, diverging in many cases. The current state of-the-art for parallel-in-time at LLNL is the multigrid reduction in time (MGRIT) XBraid package, which also struggles for such problems, while still showing some improvement over parareal. In summary, new methods are needed for an efficient parallel-in-time scheme for hyperbolic and chaotic problems, and this work shall research promising new multigrid methods in this area. In particular, this work shall continue researching the directions from the current collaboration with Dr. Falgout, which are laid out in the work Toward Parallel in Time for Chaotic Dynamical Systems and showed the first known results of a parallel-in-time speedup for a chaotic problem. This work outlines two key improvements to XBraid for chaotic problems, the so-called “theta” and “delta-correction” methods. Here, these two improvements will be further researched and improved (including with a new relaxation method inspired by on Least Squares Shadowing (LSS)) and explored for more complicated problems.