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.
翻译:近几十年来,偏差方程(PDEs)的平行时间计算方法一直受到密集发展,特别是扩散占主导地位的问题。文献中广泛报道,许多这些方法对于消化占主导地位的问题效果很差。这里我们分析的是用于恒定波速度线性平流问题离散的多电网减少实时(MGRIT)超常平行计算法(MGRIT)的特殊迭代平行时间算法。我们侧重于使用时空和Runge-Kutta方法上风有限差异的离散通用方法。我们利用我们在以往工作中开发的趋同框架,证明这些方法中的许多分解方法在消化方面效果很差。我们用一种分类的子类方法证明,如果在粗差电网中采用重新分解微电网问题的标准方法,则不可能使MGRRIT与C-速度线数和粗化因素的高度趋同。这种趋同和不易变异的分解方法,至少部分是由于对被称为特性组成部分的平滑四面模式进行不完全的整形校正校正。我们建议一种替代的离性混合的混合方法,包括以前的圆性平流法,以显示以前的混合的平流法的平流法。