用于数据驱动问题和现代分支的混合PDE解算器

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

英文标题：
《Hybrid PDE solver for data-driven problems and modern branching》
---
作者：
Francisco Bernal and Gon\\c{c}alo dos Reis and Greig Smith
---
最新提交年份：
2017
---
英文摘要：
  The numerical solution of large-scale PDEs, such as those occurring in data-driven applications, unavoidably require powerful parallel computers and tailored parallel algorithms to make the best possible use of them. In fact, considerations about the parallelization and scalability of realistic problems are often critical enough to warrant acknowledgement in the modelling phase. The purpose of this paper is to spread awareness of the Probabilistic Domain Decomposition (PDD) method, a fresh approach to the parallelization of PDEs with excellent scalability properties. The idea exploits the stochastic representation of the PDE and its approximation via Monte Carlo in combination with deterministic high-performance PDE solvers. We describe the ingredients of PDD and its applicability in the scope of data science. In particular, we highlight recent advances in stochastic representations for nonlinear PDEs using branching diffusions, which have significantly broadened the scope of PDD.   We envision this work as a dictionary giving large-scale PDE practitioners references on the very latest algorithms and techniques of a non-standard, yet highly parallelizable, methodology at the interface of deterministic and probabilistic numerical methods. We close this work with an invitation to the fully nonlinear case and open research questions.
---
中文摘要：
大规模偏微分方程的数值解，例如发生在数据驱动应用中的偏微分方程，不可避免地需要强大的并行计算机和定制的并行算法来尽可能充分地利用它们。事实上，对现实问题的并行化和可伸缩性的考虑通常非常关键，足以保证在建模阶段得到承认。本文的目的是推广概率区域分解（PDD）方法，这是一种新的PDE并行化方法，具有良好的可扩展性。该思想利用了PDE的随机表示及其通过蒙特卡罗逼近，并结合确定性高性能PDE解算器。我们描述了PDD的组成及其在数据科学领域的适用性。特别是，我们强调了使用分支扩散的非线性偏微分方程随机表示的最新进展，这大大拓宽了偏微分方程的范围。我们设想这项工作是一本词典，为大规模PDE从业者提供关于确定性和概率数值方法界面上非标准但高度并行的方法学的最新算法和技术的参考。在结束这项工作时，我们邀请大家讨论完全非线性的案例和开放的研究问题。
---
分类信息：

一级分类：Mathematics        数学
二级分类：Numerical Analysis        数值分析
分类描述：Numerical algorithms for problems in analysis and algebra, scientific computation
分析和代数问题的数值算法，科学计算
--
一级分类：Mathematics        数学
二级分类：Probability        概率
分类描述：Theory and applications of probability and stochastic processes: e.g. central limit theorems, large deviations, stochastic differential equations, models from statistical mechanics, queuing theory
概率论与随机过程的理论与应用：例如中心极限定理，大偏差，随机微分方程，统计力学模型，排队论
--
一级分类：Quantitative Finance        数量金融学
二级分类：Computational Finance        计算金融学
分类描述：Computational methods, including Monte Carlo, PDE, lattice and other numerical methods with applications to financial modeling
计算方法，包括蒙特卡罗，偏微分方程，格子和其他数值方法，并应用于金融建模
--

---
PDF下载：
--> Hybrid_PDE_solver_for_data-driven_problems_and_modern_branching.pdf (943.18 KB)

2022-5-31 12:24:29 上传

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：PDE Applications Presentation Practitioner Quantitative

发表在《欧洲应用数学杂志》（EJAM）-（这是SMUR的最终版本）数据驱动问题的混合PDE解算器和现代分支Francisco Bernal、Goncalo dos Reis2,3和Greig Smith2,4地图-数学材料中心贴花、Ecole Polytechnique、Route de Saclay、91128 Palaiseau Cedex、FR.email:Francisco。Bernal@polytechnique.eduUniversity爱丁堡大学数学学院，爱丁堡，EH9 3FD，英国。电子邮件：G。dosReis@ed.ac.ukCentrode Matemática e Aplicacoes（CMA），FCT，UNL，PT。英国爱丁堡爱丁堡大学麦克斯韦研究所分析及其应用研究生院（MIGSAA）。电子邮件：G.Smith-13@sms.ed.ac.uk（2017年5月11日-2017年4月18日接受出版）大规模偏微分方程的数值解，例如发生在数据驱动应用中的偏微分方程，不可避免地需要强大的并行计算机和定制的并行算法，以尽可能充分利用它们。事实上，对现实问题的并行化和可伸缩性的考虑通常非常关键，足以保证在建模阶段得到承认。本文旨在推广概率域分解（ProbabilisticDomain Decomposition，PDD）方法，这是一种新的pde并行化方法，具有良好的可扩展性。该思想利用了PDean的随机表示及其通过蒙特卡罗与确定性高性能PDE解算器相结合的近似。我们描述了PDD的组成及其在数据科学领域的适用性。

特别是，我们强调了使用分支扩散对非线性模型进行随机表示的最新进展，这显著拓宽了PDD的范围。我们设想这项工作是一本词典，为大规模PDE从业者提供关于确定性和概率数值方法界面上非标准但高度并行的方法学的最新算法和技术的参考。在结束这项工作时，我们邀请大家讨论完全非线性的案例和开放的研究问题。关键词：概率区域分解、高性能并行计算、可扩展性、非线性偏微分方程、显著分支扩散、混合偏微分方程求解器、蒙特卡罗方法。2010年AMS主题分类：主要：65C05、65C30、次要：65N55、60H35、91-XX、35CXX1简介偏微分方程（PDE）在建模中无处不在，出现在图像分析和处理、反问题、形状分析和优化、过滤、数据同化和优化控制中。它们在数学生物学中被用来模拟肿瘤竞争或生长的种群动态；或者模拟2 F.Bernal等人的复杂动力学。人群中的人员移动，或者模拟（ir）玩家在游戏中的理性决策，以及数学金融中许多复杂问题的特征。所有这些应用的基础是在有界或无界域中数值求解此类方程的必要性。确定性区域分解。边值问题（BVP）的标准示例是具有Dirichlet边界条件（BCs）的拉普拉斯方程：如果x，则u（x）=0∈ Ohm  Rd，u（x）=g（x），如果x∈ Ohm.

（1.1）实际应用中涉及的大型数据集几乎总是意味着（1.1）等BVP的离散化会导致代数方程组，这些方程组只能在具有大量（例如p>>1）处理器的并行计算机上求解。并行化不仅需要多个处理器，还需要并行算法。classicalSchwarz的交替方法是第一种，并且仍然是这种算法的范例，我们称之为“确定性区域分解”（DDD）[58]。虽然最先进的DDD算法在各个方面都优于Schwarz的交替方法，但后者仍然可以说明它们都面临的关键困难。施瓦兹算法的思想是分割Ohm 使处理器j=1，····，p解决PDE对子域的限制，OhmJSE见图1.1。图1.1：。任意区域上的区域分解Ohm, 分成四个重叠的子域OhmSchwarz交替法需要ias。子域Ohmishighlighted。由于解决方案一开始还未知，BCs在Ohmjare也是未知的，因此，为了给processorj一个适定（但不正确）的问题，必须进行初步猜测。沿Ohmjarethen以迭代的方式更新了周围子域的解决方案，直到收敛。处理器间通信和DDD的可扩展性限制。由于DDD更新过程中涉及的处理器间通信本质上是顺序的，因此它根据众所周知的阿姆达尔定律将alimit设置为算法的可伸缩性。下面是一个简单的示例。如果处理器数量增加一倍，则完全可扩展的算法将需要一半的时间（例如T/2）才能运行。

如果有一个分数ν<1的算法是连续的，那么完成时间将不会低于wtν，无论添加了多少个处理器。例如，在Schwarz的方法中，如果等待数据驱动问题的混合PDE解算器和现代分支3人工BCs准备就绪，一个给定处理器的执行时间损失了5%（即ν=.05），那么执行时间最多可以缩短20倍（处理器数量非常多；大约19倍就已经占用了1000多个处理器）。换句话说，Schwarz的交替算法或任何DDD算法都无法充分利用并行计算机的全部功能，因为在（基本的）通信中浪费了空闲时间。我们通过借用David Keyes的一个例子来进一步强调这一点。戈登·贝尔奖每年颁发给在解决实际问题时在性能上取得突破的数值格式。1999年，其中一个问题是模拟飞机机翼周围的可压缩Navier-Stokes方程。有128个处理器，获胜的代码花了43分钟来完成任务。另一方面，对于3072个处理器，它需要2.5分钟，而不是像完全并行化算法那样需要1.79分钟。剩下的28%的计算机时间都浪费在了处理器间的通信上。此时，添加更多处理器将导致更快的可扩展性损失。概率区域分解（PDD）方法。Acebron等人基于Renato Spigler之前未发表的想法，通过PDD方法（或者更确切地说，PDD框架）实现了概念上的突破。PDD是唯一一种可能不需要通信的区域分解方法，因此具有完全可扩展性。

它通过将模拟分为两个单独的阶段来实现，第一阶段将BVP重新设定为随机公式（通过所谓的费曼-卡克公式），从而计算特定时间/空间点的PDE解。因此，我们可以计算DDD的实际接口的“真实”解决方案值Ohm因此，以前未知的活动边界现在已知了！因此，子域现在彼此完全独立，第二阶段涉及以完全并行的方式求解子域上的解。PDD计算将受到两个独立的数值误差源的影响：子域解算器和蒙特卡罗模拟的统计误差。目前，人们对线性情况下的PDD有很好的理解，尽管最近在随机表示方面的进展为将PDD用于非线性PDE打开了大门。一类强服从PDD的非线性偏微分方程，其解可由所谓的分支过程表示，如【61】、【57】、【51】所述，并由【43】和【42】进行了扩展。这种方法避免了反向回归，即所谓的“蒙特卡罗模拟的蒙特卡罗”问题，见下文第4节或[41，第3.1节]。为了说明PDD中分支的潜力，第3节给出了数值例子。对于一般的轻度非线性偏微分方程，线性化和求解每个线性迭代的直接（通常有效）方法可以很容易地用PDD实现，而无需借助非线性表示。据我们所知，非线性二阶抛物型/椭圆型偏微分方程或完全非线性偏微分方程组的一般情况尚未在PDD框架中解决。

这些类型的偏微分方程承认前向后向SDE的概率表示（FBSDE【28】），FBSDE的数值方法目前是广泛研究的主题。看见http://www.mcs.anl.gov/research/projects/petsc-fun3d/Talks/bellTalk.ppt4F.Bernal等人。论文的其余部分组织如下：第2节是PDD概述。我们说明了线性情况下随机和BVP之间的联系，并为所需的数值方法提供了指针。我们强调平衡PDD各个方面的概念，以加速整个算法。本节以PDD报告结果的调查结束在第3节中，讨论了可以用分支过程概率表示的非线性方程，并介绍了最近的发展。我们使用分支给出了令人信服的数值测试示例第4节是对新的、比目前所解决的问题更具挑战性的问题的邀请。特别地，简要地讨论了具有前后向随机微分方程（FBSDEs）的非线性抛物方程组的随机表示。我们强调openresearch的问题。2概率域分解概述PDD方法[1]、[2]是确定性方法的一种替代方法，其专门设计用于解决DDD的可扩展性问题。首先，域名Ohm 正在考虑的被划分为不重叠的子域。（而不是重叠的，比如施瓦茨的交替算法。）然后，PDD包括两个阶段，首先，通过使用蒙特卡罗方法求解BVP的随机表示，使用所谓的Feynman-Kac表示，仅在沿人工界面的一组界面节点上计算解。随机表示是PDD的关键，可以是高度非平凡的。

尽管如此，它也可以非常简单，例如在（1.1）中，众所周知（见[45]）解u可以表示为asu（x）=Ex，0g（Xτ）（2.1）其中X是t的最简单随机微分方程（SDE）的解≥ 0 dXt=dWt，X=X∈ 研发部<=> Xt=x+Wt（2.2），其中（Wt）t≥0是d维布朗运动；Xτ是上的点Ohm 其中，下一条直线首先到达边界，X从X的t=0开始；最后，E[·]是常用的期望算子（在（2.1）中），Ex，0[·]强调扩散（Xt）t≥0startsat时间t=从位置x开始的0。）见图2.1。通过蒙特卡罗方法（SDE（2.2）的多个独立实现的平均值，可以完全并行的方式进行），引入一些统计误差来近似上述期望值。需要一个数值格式来解决SDE，我们将其称为“随机数字”【46】。通过使用随机表示（2.1），可以计算艺术边界上每个点的方程解Ohm我∩ Ohmj、 然后，可以（近似地）重构接口上的解（例如，用切比雪夫多项式插值接口节点处的值），从而使PDE限制到每个子域，现在处于适定状态。现在，每个p子域上的p拉普拉斯方程都是独立的问题，并且可以“确定性地”独立求解，这是DD的第二阶段。请注意，PDD中的两个阶段在结构上都是令人尴尬的平行。WeHybrid PDE solver for data-driven Problem and modern branching 5图2.1。PDD两个阶段的图示。（左）首先，通过数值求解适当的SDE，在子域之间的每个接口节点（黑圈）上计算解决方案，该SDE涉及来自同一接口节点的许多独立实现。

两个这样的实现是红色显示的轨迹。（右）节点解已知后，通过插值为人工界面（绿色段）提供Dirichlet BC，并解耦各子域上的BVP。然后，可以使用确定性方法（如FEM（所示网格））相互独立地求解它们。强调这只有通过偏微分方程的随机表示在域的孤立点（时空）解BVP的独特能力才能实现。另一方面，DDD方法是基于矩阵的，可以在任何地方提供解决方案；但这样做必然会影响信息的传播。备注2.1（其他特征：容错和边界设计）PDD的另一个特征是，从结构上讲，它是容错的：单个处理器的中断不会对整个模拟造成实质性的（更不用说致命的）损坏。鉴于现代并行计算机拥有数百万个处理器，这是一个独特的优势（与DDD算法形成鲜明对比）。最后，由用户选择艺术边界。这些可以通过这样的方式来选择，以减少数字中的扭结和锐角的影响。例如，通过更好地与随机表示和蒙特卡罗模拟提供的解决方案进行交互。2.1 PDDPDD的组成部分需要四个组成部分：插值器、子域解算器、手头PDE的随机表示，以及利用蒙特卡罗方法利用后者的有效数值方法。让我们对它们进行简要的评论。 插值器方案将界面节点处的（近似）解（用蒙特卡罗计算）连接起来，以便在整个界面上生成（近似）Dirichlet BC。

（我们注意到，在与时间相关的问题中，接口沿着时间组件以及空间组件运行。）RBF插值是一种非常适合PDD的灵活而精确的插值模式——见[12]及其参考文献。We6 F.Bernal等人注意到，也可以采用比插值更不严格的近似方案，例如“去噪”样条曲线或最小二乘法。 子域解算器是在有限域上求解PDE（ora BVP）的任何最先进的数值格式，无需并行化。它将插值器提供的边界上的解近似为Dirichlet BCs，并在子域内的任何地方产生解。所有子域解随后“粘合在一起”，以生成大规模原始问题的完整解。解算器的常见示例有有限差分、有限元素和无网格方法。 PDE的随机（或概率）表示，如（2.1）中所述，是将PDE（平稳或时间相关）的解的逐点表征为随机微分方程系统（SDE）泛函的预期值。随机表示的范例是众所周知的费曼-卡克公式。更多详情将在第2.2节中介绍。 利用随机表示的有效随机数值方法。使用蒙特卡罗方法，在接口节点处产生解的期望值近似为许多独立样本的平均值，并且必须对每个接口节点重复该值。与确定性方法相反，在随机设置中，误差是双重的，由时间离散化和样本平均值替代期望值引起。