Fast numerical methods for wave propagation problems

Overview

The Department of Mathematics at the Royal Institute of Technology seeks applications to a Ph.D student position in Applied and Computational Mathematics within a project on fast numerical methods for wave propagation problems. This is a fundamental problem in many branches of science and engineering involving waves of different kinds, for instance electromagnetics, acoustics, optics and seismology. The project will primarily consider iterative methods for wave propagation problems in the frequency domain, modeled by the Helmholtz equation. In particular it will concern a new type of methods which are constructed around the more fundamental time domain wave equation. Those methods can more easily exploit the power of high-performance computers, which allows the solution of bigger problems. The main goals of the project are to develop algorithms where the iterations converge faster, to obtain a better theoretical understanding of the convergence rate and to apply the methods in applications.

The doctoral student is expected to develop his/her own ideas and communicate scientific results both orally and in writing. The work will include both theoretical analysis and implementation of the methods.

The project will be in co-operation with the group of Prof. Daniel Appelö at Virginia Tech, US. Some longer research visits to VT during the PhD are expected.

Deadline for applications is 2024-01-31.

Practical and administrative information, including how to apply, is available here.

Project

Iterative methods for Helmholtz equation

The Helmholtz equation,

is a time-independent linear partial differential equation. The unknown u(x) represents the amplitude of a wave with angular frequency ω that propagates in a medium with wave speed c(x) and source f(x). The equation is used extensively to model different types of wave propagation problems, but also wave functions in quantum mechanics.

When solving Helmholtz equation, computational costs and memory requirements increase rapidly with the frequency ω. To maintain a fixed accuracy with a p-th order method at frequency ω the number of grid points per wavelength must scale as ω1/p due to the pollution errors. The total number of degrees of freedom is then proportional to ωd(1+1/p) in d dimensions. At high frequencies this leads to very large scale problems that are difficult to solve with direct methods, such as gaussian elimination. In practice, iterative methods and parallel high-performance computers must be used. It is thus important that solver implementations work well on such platforms. Moreover, solvers should be based on high order accurate methods, or the extra penalty ωd/p due to pollution errors can become prohibitive, in particular in 3D.

Designing efficient iterative solvers for the Helmholtz equation is a challenging problem, in particular when the frequency is high. The main difficulties stem from the resolution requirements and the highly indefinite character of the discretized problem. For detailed reviews see the articles by Ernst, Gander and Zhang in the reference section below.

As discretizations of Helmholtz give rise to indefinite linear systems, the conjugate gradient (CG) method cannot be used and the method of necessity becomes the generalized minimal residual method (GMRES). Without preconditioning, the convergence is, however, very slow and the iteration typically stagnates. Efficient preconditioners tailored to the Helmholtz equation must be used to accelerate the convergence. Many such preconditioners have been developed in the past two decades, for instance the analytic incomplete LU, shifted laplacian and sweeping to mention a few. Specialized, and efficient, preconditioners give faster convergence, but they are hard to reconcile with the need for high order implementations that can use high performance computers to good advantage.

Time-domain methods

Iterative methods for the Helmholtz equation is a long standing "hard" problem in numerical analysis and it is still a very active field. In this project we will use a rather different, and less studied, type of iteration by constructing the method around the more fundamental time domain equation,

The difficulties encountered for Helmholtz equation have counter parts in the time domain and can be easier to deal with there. The exploration of the problem through the time domain lens offers new insights and avenues for progress in the area.

There are many advantages to solving the time dependent wave equation rather than the Helmholtz equation. Algorithms for solving the wave equation are memory lean. They are easy to parallelize and scale well. There are also many provably stable and high order accurate methods available. Compared to discretizations of Helmholtz, time domain methods can therefore more easily deal with large scale high-frequency problems.

In the simplest time-domain method one runs the wave equation for a long time to get a Helmholtz solution. The theoretical underpinning of this approach is the limiting amplitude principle which says that every solution to the wave equation with an oscillatory forcing, in the exterior of a domain with reflecting boundary conditions tends to the Helmholtz solution. However, this method generally does not work for interior problems and becomes very slow for problems with trapping waves.

The WaveHoltz and the Controllability Method are two more efficient time-domain approaches. They are based on finding the time-periodic solution of the wave equation, which corresponds to the Helmholtz solution. The basic iteration step includes the solution of the wave-equation over one time-period, followed by some filtering and convergence acceleration, e.g. a conjugate gradient step.

Tasks

The project will focus on the WaveHoltz method. For Dirichlet and Neumann problems it leads to a positive definite linear system that can be solved with CG or other Krylov methods. The method is described in the references below. Some tentative project directions are:

Examples

To give an idea of the types of problem that we aim to solve, here are a few examples of numerical solutions obtained by the WaveHoltz method.

References

General iterative methods for Helmholtz

Time-domain methods