MiS Preprint Repository

In this work the question of efficient solution of an external boundary value problem for the wave equation in three dimensions is addressed. The problem is reformulated in terms of time domain boundary integral equations; the corresponding convolution equations are discretized with the help of Runge-Kutta convolution quadrature. The resulting lower triangular Toeplitz system of size $N$ is solved recursively, constructing $O(N)$ discretizations of boundary single-layer operator of Helmholtz equation.

Since the problem is posed in odd dimension, Huygens principle holds true and convolution weights of Runge-Kutta convolution quadrature $w_n^h(d)$ exhibit exponential decay outside of a neighborhood of the diagonal $d\approx nh$, where $h$ is a time step. Therefore, only a constant number of discretizations of boundary integral operators has to contain the near-field and for the rest only the far-field can be constructed. We combine this property with a use of data-sparse techniques, namely $\mathcal{H}$-matrices and high-frequency fast multipole method, to design an efficient recursive algorithm. Issues specific to the application of data-sparse techniques to the convolution quadrature are also addressed. Numerical experiments indicate the efficiency of the proposed approach.