ALgorithms for Large-scale Optimization of WAve Propagation Problems – ALLOWAPP

The goal of the ALLOWAPP project is to design space-time parallel algorithms for optimization problems that arise when modelling wave phenomena. Such problems occur in geophysical applications such as seismic inversion, in data assimilation, and also in medical applications such as brain imaging. To make the optimization tractable, parallel computers must be used to cope with the large amounts of data and intensive computation inherent to these problems. In the last decade, parallel-in-time methods have made enormous progress: for parabolic problems, a near-optimal scaling with respect to the number of processors has been achieved (scalability). For wave propagation, there has been no such success.

In this project, we will design innovative, space-time parallel methods for solving optimization problems with wave constraints. We will consider three interrelated aspects. The first aspect is the direct simulation of hyperbolic systems, which must be done recurrently over the course of the optimization. Here, we propose using an optimized Schwarz waveform relaxation method with many subdomains in space, and adaptive pipelining in time. This allows us to increase the scalability of the overall algorithm by solving the problem not only over many subdomains, but also many time steps. We will also consider parallelization in time by direct methods.

The second aspect is the optimization over bounded time horizons, which is at the heart of both data assimilation and wave localization problems. Here, our approach is to split the full optimality system into many subsystems in time and in space, and to use transmission conditions to ensure consistency with the global solution. We will then exploit the control structure and use the discrete Hilbert Uniqueness Method to derive optimal transmission conditions. Approximating these conditions by local, easy-to-implement conditions will then lead to highly efficient methods, when combined with specially designed schemes to handle high frequencies, such as bi-grid filtering or regularization.

The third aspect concerns the assimilation of infinite streams of data, where one cannot benefit from adjoint techniques. We will tackle this problem by combining parallel simulation with observer approaches, so that the time integration benefits from the space-time parallel methods mentioned above. Our idea is to group the observed data by time blocks, process them sequentially according to their order of arrival using a Luenberger-type observer that is parallelized in time. Our goal is to make the acceleration factor independent of the observer used. The analysis will greatly benefit from the two other parts.

Our methods will be used to tackle two concrete problems, namely wave localization in complex geometries and data assimilation in geophysical and environmental systems. Thanks to the established expertise at partner institutions to which the consortium members belong, we will be able to work alongside recognized experts in these two areas. The former has important applications in telecommunications, cordless charging and medical imaging, while the latter will lead to improvements in air quality prediction and geophysical hazard management.


In recent years, the groups involved in our consortium have developed novel mathematical and numerical tools, including optimized Schwarz methods, coarse-grid preconditioners for space-time problems and parareal algorithms. This work has enabled us to acquire expertise in the field of time parallelization, and places us in an ideal position to address the new problems in this proposal. These complementary competences, combined with the teams' know-how in the areas of domain decomposition, wave phenomena, data assimilation (French team) and time parallelization, inverse problems and applications (Hong Kong team), guarantee the production of new high-performance algorithms that are robust enough to tackle a wide range of problems with real-world applications.