MiS Preprint Repository

We have decided to discontinue the publication of preprints on our preprint server as of 1 March 2024. The publication culture within mathematics has changed so much due to the rise of repositories such as ArXiV ( that we are encouraging all institute members to make their preprints available there. An institute's repository in its previous form is, therefore, unnecessary. The preprints published to date will remain available here, but we will not add any new preprints here.

MiS Preprint

Fast Convolution Quadrature for Wave Equation in Three Dimensions

Lehel Banjai and Maryna Kachanovska


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.

MSC Codes:
65M38, 35L05
data-sparse techniques, wave equation, time-domain boundary integral equations, Runge-Kutta convolution quadrature

Related publications

2014 Repository Open Access
Lehel Banjai and Maryna Kachanovska

Fast convolution quadrature for wave equation in three dimensions

In: Journal of computational physics, 279 (2014), pp. 103-126