Parallel-in-time methods for partial differential equations (PDEs) have been the subject of intense development over recent decades, particularly for diffusion-dominated problems. It has been widely reported in the literature, however, that many of these methods perform quite poorly for advection-dominated problems. Here we analyze the particular iterative parallel-in-time algorithm of multigrid reduction-in-time (MGRIT) for discretizations of constant-wave-speed linear advection problems. We focus on common method-of-lines discretizations that employ upwind finite differences in space and Runge-Kutta methods in time. Using a convergence framework we developed in previous work, we prove for a subclass of these discretizations that, if using the standard approach of rediscretizing the fine-grid problem on the coarse grid, robust MGRIT convergence with respect to CFL number and coarsening factor is not possible. This poor convergence and non-robustness is caused, at least in part, by an inadequate coarse-grid correction for smooth Fourier modes known as characteristic components.We propose an alternative coarse-grid that provides a better correction of these modes. This coarse-grid operator is related to previous work and uses a semi-Lagrangian discretization combined with an implicitly treated truncation error correction. Theory and numerical experiments show the coarse-grid operator yields fast MGRIT convergence for many of the method-of-lines discretizations considered, including for both implicit and explicit discretizations of high order. Parallel results demonstrate substantial speed-up over sequential time-stepping.
翻译:过去几十年,针对偏微分方程(PDE)的并行时间方法得到了广泛的发展,尤其是在扩散主导问题中被广泛应用。然而,文献中广泛报道许多这些方法对于对流主导问题表现非常糟糕。本文分析了多重网格时间缩减(MGRIT)的特定迭代并行时间算法与常数波速线性对流问题的离散化。我们关注使用空间上弱格式差分和时间上龙格-库塔方法的常见方法离散化。使用我们在之前工作中开发的收敛框架,我们证明对于这些离散化的一个子类,如果使用标准方法在粗网格上进行细网格问题的重新离散化,是无法实现关于CFL数和加粗系数的强大MGRIT收敛的。这种劣质收敛和不够健壮性部分是由平滑傅里叶模式未得到适当的粗网格校正所致,称为特征分量。我们提出了一种替代的粗网格算子,为这些模式提供更好的校正。这个粗网格算子与以前的工作有关,并使用半拉格朗日离散化与隐式处理的截断误差校正相结合。理论和数值实验表明,这个粗网格算子对于许多方法离散化,包括高阶隐式和显式离散化,都具有快速的MGRIT收敛。并行结果表明,在串行时间步进上实现了巨大的加速。