Space-time parallel algorithms for large scale simulation and optimization problems governed by partial differential equations

从4-24核的小型笔记本电脑到数万核的大型计算集群，并行计算机正变得越来越普遍。然而，要将这种巨大的计算能力转化为更好的预测和设计，仍然是一个巨大的挑战。本研究计划的总体目标是创建一套创新和有效的数值算法来解决涉及偏微分方程（PDEs）的模拟和优化问题。通过利用时间和空间上的并行性，我们的算法将能够充分利用现代的多核计算架构，因此只要有足够的处理器，就可以处理大型问题。我们研究项目的新颖之处在于它关注于时间上的并行化，也就是说，我们设计的算法使每个处理器在时域的不同部分上工作。这与传统方法不同，在传统方法中，不同的处理器处理空间中的不同区域。我们将在时间上考虑两种类型的并行：第一种是直接模拟，在这种情况下，人们试图根据已知的初始条件预测系统的未来状态。虽然时间演化过程看起来是完全顺序的，但如果使用两个精度不同的求解器，实际上可以完成有用的并行工作；较不精确（但更便宜）的方法可以用来快速找到粗略的轨迹，而较昂贵（但更准确）的方法可以在不同的时间间隔内并行运行以改进解决方案。在这里，我们建议以分层方式使用三个或更多的求解器，以进一步增加可以并行运行的进程的数量。我们还将通过整合允许同时运行多个迭代的自适应管道来提高一类时空并行算法（称为波形松弛方法）的效率。我们考虑的第二种时间并行性是在PDE约束下的优化问题；这里的主要障碍是前向发展的控制方程与后向发展的伴随PDE之间的紧密耦合。在这里，我们提出了时间范围的分解，以获得具有相同优化结构的更小的问题。然后，我们的新算法将基于局部最优块迭代地产生全局最优解。我们还将为局部优化问题设计有效的求解器。对于非线性问题，我们将研究一种新的预处理策略来提高求解器的鲁棒性和效率。所有算法都将伴随着严格的数学分析，以了解它们对模型问题的性能。将开发有效的实现，以在实际并行机上为重要的实际问题提供加速，例如弹性和多孔介质流。我们开发的工具将使研究人员和从业人员能够获得更高质量的模拟和优化结果。

Parallel computers are becoming increasingly ubiquitous, from small laptops with 4-24 cores, to massive computing clusters with tens of thousands of cores. To translate this immense computing power into better predictions and designs, however, remains a great challenge. The overall goal of this research program is to create a set of innovative and efficient numerical algorithms for solving simulation and optimization problems involving partial differential equations (PDEs). By exploiting parallelism both in time and in space, our algorithms will be able to fully utilize modern, many-core computing architectures, so that large problems remain tractable as long as there are enough processors. The novelty of our research program is its focus on parallelization in time, i.e., we design algorithms where each processor works on a different part of the time domain. This is unlike classical approaches, where different processors work on different regions in space. We will consider two types of parallelism in time: the first one is for direct simulation, where one seeks to predict the future state of a system based on known initial conditions. Although the time evolution process appears completely sequential, useful parallel work can in fact be done if one resorts to two solvers with different accuracies; the less accurate (but cheaper) one can be used to find the rough trajectory quickly, while the more expensive (but more accurate) one can be run in parallel on different time intervals to refine the solution. Here, we propose using three or more solvers in a hierarchical fashion to further increase the number of processes that can be run in parallel. We will also improve the efficiency of a class of space-time parallel algorithms, known as waveform relaxation methods, by incorporating an adaptive pipeline that allows multiple iterations to be run at the same time. The second type of parallelism in time we consider is for optimization problems under PDE constraints; the main hurdle here is the tight coupling between the forward-evolving governing equation, and the backward-evolving adjoint PDE that enforces optimality. Here, we propose a decomposition of the time horizon to obtain smaller problems with the same optimization structure. Our new algorithms will then produce the globally optimal solution iteratively, based on locally optimal pieces. We will also design efficient solvers for local optimization problems. For nonlinear problems, we will investigate a new preconditioning strategy to increase solver robustness and efficiency. All algorithms will be accompanied by rigorous mathematical analysis to understand their performance for model problems. Efficient implementations will be developed to deliver speedup on real parallel machines for important practical problems, such as elasticity and porous media flow. The tools we develop will enable researchers and practitioners to obtain higher quality simulations and optimization results.