Fast convolution quadrature for the wave equation in three dimensions

This work addresses the numerical solution of time-domain boundary integral equations arising from acoustic and electromagnetic scattering in three dimensions. The semidiscretization of the time-domain boundary integral equations by Runge–Kutta convolution quadrature leads to a lower triangular Toeplitz system of size N  . This system can be solved recursively in an almost linear time (O(Nlog2⁡N)O(Nlog2⁡N)), but requires the construction of O(N)O(N) dense spatial discretizations of the single layer boundary operator for the Helmholtz equation. This work introduces an improvement of this algorithm that allows to solve the scattering problem in an almost linear time.The new approach is based on two main ingredients: the near-field reuse and the application of data-sparse techniques. Exponential decay of Runge–Kutta convolution weights wnh(d) outside of a neighborhood of d≈nhd≈nh (where h   is a time step) allows to avoid constructing the near-field (i.e. singular and near-singular integrals) for most of the discretizations of the single layer boundary operators (near-field reuse). The far-field of these matrices is compressed with the help of data-sparse techniques, namely, HH-matrices and the high-frequency fast multipole method. Numerical experiments indicate the efficiency of the proposed approach compared to the conventional Runge–Kutta convolution quadrature algorithm.