Fast convolution for non-reflecting boundary conditions

  • Christian Lubich (Universität Tübingen)
G3 10 (Lecture hall)


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 Nt successive time steps, the algorithm requires O(Ntlog Nt) operations and O(log Nt) 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.