Optimizing FE-Multigrid Methods for Convection-Diffusion Equations via Space-Time Parallelization
Please login to view abstract download link
We present an innovative approach to optimizing multigrid methods for singularly perturbed convection-diffusion equations employing space and time parallelization techniques. We discretize in space and time using continuous linear finite elements and linear one-step methods, respectively. This yields a global linear system of equations spanning all time steps. A geometric multigrid method with temporal coarsening is applied to this global system. Our approach subdivides the time domain into intervals, allowing independent smoothing for each subinterval. For smoothing purposes, the degrees of freedom are sophisticatedly arranged such that the time steps are blocked for each spatial unknown within these subintervals. The resulting spatial problems are solved numerically using the time-simultaneous multigrid method with space-only coarsening [1] closely related to multigrid waveform relaxation [2]. Utilizing this technique additionally enables a high degree of parallelization in space. In numerical experiments, we optimize both space and time parallelization strategies to efficiently solve the global problem. The advantages of both multigrid methods are exploited by choosing the subintervals and thus the number of blocked time steps. This approach achieves a high degree of parallelization in both space and time, akin to space-time multigrid algorithms [3] in its most refined state. [1] W. Drews, S. Turek and C. Lohmann, Numerical Analysis of a Time–Simultaneous Multigrid Solver for Stabilized Convection–Dominated Transport Problems in 1D. Ergebnisberichte des Instituts für Angewandte Mathematik, Fakultät für Mathematik, TU Dortmund, Vol. 668, 2023. [2] J. Janssen, S. Vandewalle, Multigrid Waveform Relaxation on Spatial Finite Element Meshes: The Continuous-Time Case. SIAM J. Numer. Anal., Vol. 33.2, pp. 456–474, 1996. [3] M. J. Gander and M. Neumüller, Analysis of a New Space-Time Parallel Multigrid Algorithm for Parabolic Problems. SIAM J. Sci. Comput., Vol. 38.4, pp. A2173- A2208, 2016.