Fast Convolution Quadrature for Wave Equation in Three Dimensions
Lehel Banjai and Maryna Kachanovska
Contact the author: Please use for correspondence this email.
Submission date: 09. Nov. 2012 (revised version: December 2013)
published in: Journal of computational physics, 279 (2014), p. 103-126
DOI number (of the published article): 10.1016/j.jcp.2014.08.049
MSC-Numbers: 65M38, 35L05
Keywords and phrases: data-sparse techniques, wave equation, time-domain boundary integral equations, Runge-Kutta convolution quadrature
Download full preprint: PDF (1798 kB)
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 wnh(d) exhibit exponential decay outside of a neighborhood of the diagonal d ≈ 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 -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.