Parallel Multigrid Solvers in Space and Time for Future Architectures

Abstract:

Multigrid solvers are popular and effective approaches for solving large sparse systems of equations, which often come from discretized partial differential equations.
While multigrid is effective over a broad class of problems, the massive parallelism posed by exascale computing presents pressing challenges. This work will address some of these issues. The first challenge is posed by the serial time integration bottleneck, which is caused by the fact that future growth in high-performance computing is coming from more cores, not faster clock speeds. Previously, faster clock speeds decreased the runtime per time step, and thus allowed for either faster simulations or for more time steps while not increasing the overall runtime. However, clock speeds are now stagnate, leading to the bottleneck. The proposed approach utilizes multigrid to simultaneously compute multiple time steps in parallel and has the potential to dramatically decrease overall time to solution for time stepping. Several application areas for this multigrid in time approach will be considered, e.g., parabolic probl ems, fluid dynamics, optimization, and neural network training.
The second challenge regards spatial multigrid methods and the need to reduce communication for parallel algebraic multigrid (AMG). The efficiency of AMG relies on its multilevel structure of successively coarser representations of the problem; however, these coarse grids suffer from fill-in and associated communication. Moreover, as the problem size increases, more levels are constructed, leading to increased fill-in and possible scalability issues at exascale. The proposed approach reduces this fill-in and associated communication by eliminating unnecessary entries in coarse grid matrices, while preserving spectral equivalence with the original coarse grid. The third challenge concerns the generality of AMG, and the need to extend AMG beyond traditional restrictions to certain subclasses of symmetric positive definite (SPD) matrices. A generalized approach to algebraic coarsening and interpolation will be presented that  ;allows AMG to be applied to areas such as high-order discontinuous  Galerkin discretizations, neutron transport, and the indefinite Helmholtz problem.

Biography:

Jacob Schroder is a computational mathematician at the Center for Applied Scientific Computing (CASC) at Lawrence Livermore National Laboratory. The core direction of his research is numerical analysis and scientific computing. His specific focus is on highperformance computing, iterative solvers for large sparse (non)linear systems, their associated preconditioning, and numerical PDEs. He approaches his research both from a software perspective centered on providing new methods to the broader community and also from a theoretical perspective centered on the development of new methods. His research has resulted in new classical spatial multigrid solvers for areas such as Helmholtz problems, high-order discontinuous Galerkin discretizations, and neutron transport. He has also developed new parallel-in-time methods using a multigrid reduction strategy that have been applied in a variety of settings, e. g., elasticity, fluid dynamics and optimization. He is a member of the Scalable Linear Solvers (hypre) project and the leader for the Parallel Time Integration with Multigrid (XBraid) project.
Jacob earned his Ph.D. in computer science from the University of Illinois at Urbana-Champaign under the direction of Prof. Luke Olson. His dissertation resulted in new methods for smoothed aggregation-based algebraic multigrid (AMG), which proved effective for a variety of problems, e.g., anisotropic diffusion, Helmholtz, elasticity and Euler flow. Next, he joined University of Colorado at Boulder for one year as a postdoc under Profs. Thomas Manteuffel and Stephen McCormick. Jacob joined Lawrence Livermore in September 2011.