Title: Multigrid Methods in Space and Time

Abstract: Multigrid methods are popular and effective approaches for solving large sparse systems of equations, often arising from discretized partial differential equations (PDEs). In this talk, we examine Dr. Schroder’s contributions to multigrid methods in three areas: parallel-in-time methods, machine learning, and algebraic multigrid (AMG).  

The emerging field of parallel-in-time is being driven by changes in computer architectures, where future speedups will be available through greater concurrency (i.e., more cores), not faster clock speeds, which are stagnant. This leads to the serial time integration bottleneck, which can only be avoided by exploiting parallel-in-time.  Here, we examine the multigrid reduction in time (MGRIT) method, which simultaneously computes multiple time steps in parallel and has the ability to dramatically decrease overall time to solution.  Several application areas for this multigrid in time approach will be considered, e.g., parabolic problems, fluid dynamics, and PDE-constrained optimization. The parallel-in-time optimization work leads to the next topic, machine learning, where MGRIT is applied to the training of deep neural networks (DNNs).  Training times for DNNs are expensive, often taking days, weeks, or longer. This is caused, in part, by the serial nature of forward and backward propagation, where many sequential passes through all network layers are required.  However, one can connect ordinary differential equations to the network layer dimension and apply MGRIT to forward and backward training passes, evaluating network layers simultaneously in parallel.  Through a joint code with Sandia, TorchBraid, we have successfully applied MGRIT to convolutional and transformer DNNs, showing training speedups over the layer dimension with multigrid. 

Lastly, we examine AMG, which is a popular and effective approach for solving the large sparse linear systems resulting from spatially discretized PDEs. The optimality and efficiency of AMG rests on the complementary relationship between relaxation (e.g., Gauss-Seidel) and coarse-grid correction.  While AMG is a relatively mature field compared to parallel-in-time or DNNs, a number of important matrix classes (e.g., nonsymmetric and indefinite) remain problematic for AMG and motivate much of this research.  We will present novel coarsening and interpolation approaches for generalizing AMG to nonsymmetric and indefinite problems, by relying first on energy-minimization and then on approximate Schur complement concepts.