基于Parareal算法和高阶动态模式分解的时间并行方法及其在流体模拟中的应用

《Computer Physics Communications》：A parallel-in-time method based on the Parareal algorithm and High-Order Dynamic Mode Decomposition with applications to fluid simulations

　　

摘要
顺序时间积分的高成本是限制 Parareal 等时间并行算法加速比的一个主要制约因素，因为在刚性数值问题中难以对时间步长进行粗化。为了应对这一挑战，我们开发了一种基于 Parareal 算法的时间并行方法，其中我们采用基于动态模态分解（DMD）的数据驱动方法构建了一种新颖的粗求解器，以取代经典的时间推进格式。所提出的求解器并行地使用两种不同精度的数值格式来计算粗解，并应用高阶动态模态分解（HODMD）进行高效近似，以降低顺序成本。与原始 Parareal 算法相比，所提出的方法允许在许多复杂的刚性问题上构建成本更低的粗求解器。我们通过流体力学中的若干数值算例表明，所提出的方法能有效降低串行计算成本，并提高刚性、高时间复杂度数值模拟的并行加速比，而这些模拟使用原始 Parareal 算法很难实现加速。

引言
用于求解时间相关问题时步方法的传统方法是本质顺序的，这可能会成为某些大规模模拟的瓶颈。时间并行方法是一类旨在通过利用时间维度上的并行性来加速时间相关问题数值解的算法。这些方法旨在通过将计算分布在时间维度上的多个处理器上来克服这一局限。由于其在减少大规模模拟计算时间方面的潜力，尤其是当空间并行化的并行加速比趋于饱和时，这些方法近年来引起了越来越多的关注。Gander 将时间并行方法分为四个主要类别，包括多重射击法、基于域分解和波形松弛的方法、时空多重网格方法以及直接时间并行方法[1]。Parareal 算法是一种常用的时间并行方法，由 Lions 等人[2]开发。该算法采用一个细求解器和一个粗求解器，通过在细求解器和粗求解器之间交替迭代来修正解。自提出以来，该算法已被广泛用于加速流体问题[3]、[4]、[5]，基于神经网络偏微分方程（PDE）求解器[6]，线性开关系统[7]，哈密顿系统[8]等。时间多重网格（MGRIT）是将多重网格方法扩展到时间维度的另一个非侵入式时间并行方法，它将 Parareal 时间积分解释为一种两级缩减方法[9]。MGRIT 已被用于求解非线性双曲方程[10]、空间分数阶扩散方程[11]，以及 Stokes 和 Oseen 问题[12]等。其他时间并行方法包括波形松弛[13]、时空全近似方案（PFASST）[14]，以及现有时间推进方法的直接并行化[15]。

Parareal 算法顺序计算的高成本可能会显著阻碍该算法的并行加速比和效率。为解决这一问题，许多 Parareal 算法的变体已被开发。Legoll 等人提出了一种微观-宏观 Parareal 算法，该算法假设变量可以分离为慢变和快变分量，并使用粗传播子来近似慢变分量的宏观模型[16]。由于消除了快变量并有可能使用大得多的时间步长，该算法拥有一个低成本的粗求解器。GParareal 是另一种基于 Parareal 的算法，它使用高斯过程模拟器替代原始 Parareal 算法中的修正项[17]。该算法使用先前迭代的数据来训练模拟器，并已被证明在低维常微分方程上取得了更好的收敛性、运行时间和精度。然而，其在高维系统上的可扩展性仍然受限。为解决这一问题，最近邻 GParareal（nnGParareal）被提出，该方法通过数据缩减来增强可扩展性[18]。该方法将模型复杂度从三次降低到对数线性，并在有限数量的计算机核心上解决低维常微分方程方面表现出色。近年来，深度学习方法的发展取得了显著进展。在该不断增长领域中一个突出的方向是将深度学习技术集成到 Parareal 算法中。例如，Ibrahim 等人开发了一种利用物理信息神经网络（PINN）作为粗传播子的 Parareal 算法[19]。这种基于 PINN 的粗求解器通过同时利用 CPU 和 GPU，在异构架构上降低了顺序成本并增强了计算效率。[20]引入了一种 RandNet-Parareal 框架，该框架利用随机神经网络（RandNet）来学习 Parareal 算法中粗解和细解之间的差异，以提高 PDE 在高分辨率空间网格上的加速比。此外，基于神经算子的代理模型也被开发出来构建粗求解器，如应用于双资产 Black-Scholes 方程和 MHD 模拟[21]、[22]。其他粗求解器的构建方法包括使用优化[23]、概率预测[24]和卷积神经网络[25]等。在[23]中，开发了一种基于优化的策略来设计 Parareal 算法中的粗传播子，以克服收敛阶的障碍。在[24]中，提出了 Prob-GParareal，即 GParareal 算法的概率扩展，以将不确定性量化带入微分方程的时间并行解。该方法通过采用高斯过程来对 Parareal 修正函数进行建模，将数值不确定性跨时间传播，从而得到系统演化的概率预测。为应对使用 Parareal 算法求解时间相关 PDE 的挑战，[25]使用卷积神经网络（CNN）作为粗传播子，该 CNN 专门训练用于学习常规数值细求解器完全离散的时间推进算子，并在 Allen-Cahn 方程中进行了应用演示。

在 Parareal 框架中，在时间维度上使用粗网格对于实现并行计算的高加速比和并行效率至关重要。然而，对于刚性问题的长时间模拟，主要挑战之一和瓶颈在于，问题的刚性不允许在经典时间推进数值格式中对时间步长进行大幅放松。Parareal 加速比的上限主要取决于粗求解器的计算成本，而粗求解器本质上是顺序的。由于刚性问题对时间步长有严格要求，因此基于时间离散自然粗化的粗求解器通常是难以承受的，这显著限制了像 Parareal 算法这样的时间并行算法的加速比。为解决使用更大时间步长的困难并提高算法在此类场景下的并行加速比，我们提出了一种基于 Parareal 算法和高阶动态模态分解（HODMD）的新颖时间并行方法。具体而言，我们提出并行地应用高精度和低精度两种数值格式来构建粗求解器。在更精确但更昂贵的数值格式中，我们仅在每个划分时间间隔的子集上计算解，并计算两种格式给出的解之间的差异。然后对差异应用 HODMD[29]以预测每个间隔端点的解。我们将此预测与较低精度数值格式给出的解结合，以获得 Parareal 算法粗传播子的近似值。所提出的粗求解器提供了一种新的方法来构建刚性微分方程的粗近似，与经典粗求解器相比计算成本更低。所提出的求解器嵌入在 Parareal 迭代内部时，降低了 Parareal 算法的顺序成本，并能够在某些使用传统经典求解器的 Parareal 算法难以加速的刚性问题上实现更高的加速比。

在本工作中，我们关注一些具有严格时间步长限制的复杂流体力学问题的数值模拟，包括浸没在不可压缩粘性流体中的动态结构的运动以及图案基底上薄液膜液滴的去润湿。时间并行方法此前已被用于流体模拟的时间并行化[4]、[30]、[31]、[32]、[33]。然而，在某些流体模拟中，如[4]，由于数值正则化参数和所涉物理参数导致的问题稳定性要求，为构建廉价的粗传播子带来了挑战。在本工作中，我们将所提出的新颖粗求解器应用于时间步长受限的此类生物流体问题，并通过若干数值算例表明，与原始 Parareal 方法相比，所提出的方法能有效减少总计算时间并提高某些长时间数值模拟的并行效率。

本文其余部分组织如下。在第2节中，我们回顾了 Parareal 算法。在第3节中，我们回顾了包括 HODMD 在内的 DMD 概念和变体。在第4节中，我们描述了新颖粗求解器的构建以及如何将 HODMD 集成到 Parareal 迭代中的粗求解器里。在第5节中，我们将所提出的算法应用于各种数值实验，包括杆状微游泳器、弹性球和去润湿薄液膜的模拟。我们通过呈现和分析所提出的方法应用于上述数值算例的精度、加速比和可扩展性来展示该方法的效率。我们在第7节中总结全文。

第2节 Parareal 算法
Parareal 算法是一种在[2]中引入的时间并行算法。该算法旨在通过并行化解的时间域来求解时间相关问题。考虑以下形式的初值问题（IVP）：
dx/dt = u(t, x)，对于 t ∈ (0, T]，且 x(0) = x?
假设有 Nc 个核心。Parareal 算法将时间域 [0, T] 均匀地划分为 Nc 个子区间，长度为 ΔT = T/Nc，并令 Tn = nΔT，对于 n = 0, 1, 2, …, Nc。该算法通过以下方式并行化计算

第3节 动态模态分解
动态模态分解（DMD）是一种用于序列数据的降维技术，已被用于分析动力学系统，特别是那些表现出复杂行为的系统。基于 Koopman 分析理论，DMD 寻求将系统的动力学分解为一组模态。该方法起源于流体力学领域，此后已被广泛应用于电力系统[34]、金融[35]、医学影像分析[36]等领域的复杂问题。

第4节 基于高阶动态模态分解的新颖 Parareal 算法
限制 Parareal 算法加速比的一个主要问题是粗求解器中涉及顺序计算的高成本。然而，对于具有严格稳定性要求的复杂问题，通常难以通过直接粗化时间网格来构建粗求解器。为此，我们提出了一种带有新颖粗求解器的改进 Parareal 算法，该算法通过采用 HODMD 产生此类问题的粗近似。我们提出对两大方面进行修改

第5节 数值算例
在本节中，我们呈现算法1应用于不同流体模拟的数值结果，包括不同构型的微游泳器的流固相互作用问题和固体基底上薄液膜的动态。具体而言，我们在两种场景下测试该算法，一种采用拉格朗日描述，使用显式时间推进格式求解流体问题，在每步具有固定空间复杂度；另一种采用欧拉描述

讨论
本研究中呈现的数值实验表明，与原始 Parareal 方法相比，Parareal-HODMD 算法在加速求解若干刚性流体问题时能取得显著的加速比。基于实验结果，我们发现所提出方法的性能和效率受到松弛序列{γi}、目标精度和问题固有刚性之间复杂交互作用的支配。

结论
为了提高高时间复杂度数值模拟的计算效率，通常需要应用某种时间并行方法，如 Parareal 算法。对于许多刚性问题，通常禁止使用大时间步长，导致 Parareal 方法粗传播子的计算极其昂贵。因此，粗求解器的高成本和顺序特性可能会显著限制 Parareal 算法的并行效率。在本工作中，

数据可用性
本工作中所呈现数值算例的代码可在 Github 上获取。

仓库链接：https://github.com/weifan-liu/parareal_hodmd

CRediT 作者贡献声明

Weifan Liu：稿件审阅与编辑、原稿撰写、可视化、验证、资源支持、项目管理、方法论、调查研究、经费筹措、形式化分析、数据管理、概念构思。

利益冲突声明

作者声明不存在已知的竞争性经济利益或可能对本研究产生影响的个人关系。

Weifan Liu