Christian Lubich (Tuebingen. Germany)

Fast convolution for non-reflecting boundary conditions

Abstract

Non-reflecting boundary conditions for problems of wave propagation are non-local  in space and time. While the non-locality in space can be efficiently handled by Fourier or spherical expansions in special geometries, the arising temporal convolutions still form a computational bottleneck. In the present talk, a new algorithm for the evaluation of these convolution integrals is proposed. To compute a temporal convolution over $N_t$ successive time steps, the algorithm requires $O(N_t \log N_t)$ operations and $O(\log N_t)$ active memory. In the numerical examples, this algorithm is used to discretize the Dirichlet-to-Neumann and Neumann-to-Dirichlet operators arising from the formulation of non-reflecting boundary conditions in rectangular geometries for Schrödinger and wave equations.