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

点击翻译按钮获取中文摘要

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.