Grant: Discovery Grants Program - Individual
Université Laval
$18,000.00
Space-time parallel algorithms for large scale simulation and optimization problems governed by partial differential equations
FY 2022-23
Summary
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.
Program
Discovery Grants Program - Individual
Recipient
Location
Quebec, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2021-02595
Name nom
Kwok, Wing Hong Felix
Department département
Mathématiques et statistique - Mathématiques et statistique
Organization id
51
Institution établissement
Université Laval
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2022
Competition year année de concours
2021
Award amount
18000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1508
Committee name en
Mathematics and Statistics
Committee name fr
Mathématiques et statistique
Area of application code
1205
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Mathematical sciences
Area of application fr
Sciences mathématiques
Research subject code
2950
Research subject group en
Applied mathematics
Research subject group fr
Mathématiques appliquées
Research subject en
Applied mathematics
Research subject fr
Mathématiques appliquées
Installment
inst:2
Partie
1
Nb partie
5
Application title
Space-time parallel algorithms for large scale simulation and optimization problems governed by partial differential equations
Application summary
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.