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

并行计算机正变得越来越普遍，从具有4-24个核心的小型笔记本电脑到具有数万个核心的大型计算集群。然而，将这种巨大的计算能力转化为更好的预测和设计仍然是一个巨大的挑战。该研究计划的总体目标是创建一套创新和高效的数值算法，用于解决涉及偏微分方程（PDE）的模拟和优化问题。通过利用时间和空间上的并行性，我们的算法将能够充分利用现代的众核计算架构，因此只要有足够的处理器，大型问题就可以处理。我们的研究计划的新奇之处在于它专注于时间上的并行化，即，我们设计算法，其中每个处理器在时域的不同部分上工作。这与经典方法不同，在经典方法中，不同的处理器在空间的不同区域工作。我们将考虑两种类型的时间并行：第一种是直接模拟，其中一个试图预测系统的未来状态的基础上已知的初始条件。虽然时间演化过程看起来是完全连续的，但如果使用两个精度不同的求解器，实际上可以进行有用的并行工作;精度较低（但较便宜）的求解器可以用于快速找到粗略的轨迹，而更昂贵（但更准确）的求解器可以在不同的时间间隔上并行运行以改进解决方案。在这里，我们建议以分层方式使用三个或更多求解器，以进一步增加可以并行运行的进程数量。我们还将提高一类时空并行算法的效率，称为波形松弛方法，通过引入自适应流水线，允许同时运行多个迭代。我们考虑的第二种类型的并行时间是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.