Fast convolution for non-reflecting boundary conditions

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_tlog 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.