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 (www.arxiv.org) 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
67/2012
Fast Convolution Quadrature for Wave Equation in Three Dimensions
Lehel Banjai and Maryna Kachanovska
Abstract
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.
