Hierarchical matrix techniques for low- and high-frequency Helmholtz problems

In this paper, we discuss the application of hierarchical matrix techniques to the solution of Helmholtz problems with large wave number kappa in 2D. We consider the Brakhage-Werner integral formulation of the problem discretized by the Galerkin boundary-element method. The dense n x n Galerkin matrix arising from this approach is represented by a sum of an and an Eta-matrix and an Eta(2)-matrix, two different hierarchical matrix formats. A well-known multipole expansion is used to construct the Eta(2)-matrix. We present a new approach to dealing with the numerical instability problems of this expansion: the parts of the matrix that can cause problems are approximated in a stable way by an Eta-matrix. Algebraic recompression methods are used to reduce the storage and the complexity of arithmetical operations of the . Further, an approximate LU decomposition of such a recompressed Eta-matrix is an effective preconditioner. We prove that the construction of the matrices as well as the matrix-vector product can be performed in almost linear time in the number of unknowns. Numerical experiments for scattering problems in 2D are presented, where the linear systems are solved by a preconditioned iterative method.