Wavelets and convolution quadrature for the efficient solution of a 2D space-time BIE for the wave equation

We consider a wave propagation problem in 2D, reformulated in terms of a Boundary In- tegral Equation (BIE) in the space-time domain. For its solution, we propose a numeri- cal scheme based on a convolution quadrature formula by Lubich for the discretization in time, and on a Galerkin method in space. It is known that the main advantage of Lubich's formulas is the use of the FFT algorithm to retrieve discrete time integral operators with a computational complexity of order R log R, R being twice the total number of time steps performed. Since the discretization in space leads in general to a quadratic complexity, the global computational complexity is of order M2 R log R and the working storage required is M2R/2, where M is the number of grid points on the domain boundary. To reduce the complexity in space, we consider here approximant functions of wavelet type. By virtue of the properties of wavelet bases, the discrete integral operators have a rapid decay to zero with respect to time, and the overwhelming majority of the associated matrix entries assume negligible values. Based on an a priori estimate of the decaying behaviour in time of the matrix entries, we devise a time downsampling strategy that al- lows to compute only those elements which are significant with respect to a prescribed tolerance. Such an approach allows to retrieve the temporal history of each entry e (corre- sponding to a fixed couple of wavelet basis functions), via a Fast Fourier Transform, with computational complexity of order Re logRe. The parameter Re depends on the two basis functions, and it satisfies Re << R for a relevant percentage of matrix entries, percentage which increases significantly as time and/or space discretization are refined. Globally, the numerical tests show that the computational complexity and memory storage of the over- all procedure are linear in space and time for small velocities of the wave propagation, and even sub-linear for high velocities.