In our talk we will present and analyse a new fast method for the numerical solution of the time domain boundary integral formulations of the wave equation. We employ Lubich's convolution quadrature method for the time discretization and a Galerkin boundary element method for the spatial discretization. The coefficient matrix of the arising system of linear equations is a triangular block Toeplitz matrix. In the literature two approaches for its solution have been proposed: (a) By using FFT techniques the computational complexity is reduced substantially while the storage cost stays unchanged and is, typically, very high. (b) By using panel-clustering techniques the gain is reversed: the computational cost stays (approximately) unchanged while the storage cost is reduced substantially.
In our talk, we will present a new fast method which combines the advantages of the two approaches: First, the discrete convolution (related to the block Toeplitz system) is transformed to the (discrete) Fourier image and, then, a new panel-clustering method is applied to the transformed system. This requires efficient (H- and H2-matrix) representations of integral operators related to Helmholtz-type equations for a large range of complex wave numbers.
In our talk, we will focus on the methodolical approach and the convergence analysis while the sparse approximations of the Helmholtz-type integral operators for complex wave numbers will be presented by L. Banjai in the second part of this talk.