Multigrid Reduction in Time for Nonlinear Parabolic Problems

O'Neill, Ben

Graduate Thesis Or Dissertation

Multigrid Reduction in Time for Nonlinear Parabolic Problems Public Deposited

Analytics

Download PDF

Citations

Citeable URL: https://scholar.colorado.edu/concern/graduate_thesis_or_dissertations/b2773v68h

Abstract

The need for parallelism in the time dimension is being driven by changes in computer architectures, where recent performance increases are attributed to greater concurrency rather than faster clock speeds. Sequential time integration limits parallelism to the spatial domain, introducing a parallel scaling bottleneck. Multigrid Reduction in Time (MGRIT) is an iterative parallel-in-time algorithm that permits temporal concurrency by applying time-integration on a multilevel hierarchy of temporal grids. The overarching goal of this thesis is to maximize the accuracy per computational cost (APCC) of the MGRIT algorithm in the context of both linear and nonlinear parabolic partial differential equations (PDE's). The cost of the MGRIT algorithm is directly proportional to the cost of a time-integration step. For a linear problem with implicit time-stepping, each time step equates to solving one linear system. If an optimal spatial solver is used, the work required for a time-step evaluation is independent of the time-step size. For nonlinear problems, each time integration step involves an iterative nonlinear solve, the cost of which often increases with time-step size. This thesis develops a library of MGRIT optimizations, most importantly an alternate initial guess for the nonlinear time-step solver and delayed spatial coarsening, that reduce the cost of the algorithm for nonlinear parabolic problems. This allows nonlinear problems to be solved with parallel scaling behavior comparable to a corresponding linear problem. An alternative approach towards maximizing the APCC is to increase the accuracy of the method. MGRIT uses multigrid reduction techniques and a multilevel hierarchy of coarse time grids to ``parallelize'' the time dimension. Richardson extrapolation (RE) uses a similar multilevel hierarchy of time-grids to improve the accuracy of those same time-integration methods. In this thesis we develop the RE-MGRIT algorithm, a non-intrusive parallel-in-time algorithm that uses RE with MGRIT to improve the convergence order of the underlying time integration scheme, all with almost no extra cost when compared to the standard MGRIT algorithm. In addition to increasing the convergence order of the time integration scheme, RE can also be used as a means of temporal error estimation. This thesis introduces and tests a Richardson based estimate of the local truncation error. When used in conjunction with an adaptive RE-MGRIT based algorithm, these estimates, available for free at each time-point, allow for automatic error control without the requirement for an additional temporal error estimation procedure.

Creator