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

Wolfgang Hackbusch ^{In this paper, we discuss the application of hierarchical matrixtechniques to the solution of Helmholtz problems with largewave number in 2D. We consider the Brakhage–Werner integralformulation of the problem discretized by the Galerkin boundary-elementmethod. The dense n x n Galerkin matrix arising from this approachis represented by a sum of an -matrix and an 2-matrix, two different hierarchical matrix formats.A well-known multipole expansion is used to construct the 2-matrix. We present a new approach to dealingwith the numerical instability problems of this expansion: theparts of the matrix that can cause problems are approximatedin a stable way by an -matrix. Algebraic recompression methods are used to reducethe storage and the complexity of arithmetical operations ofthe -matrix.Further, an approximate LU decomposition of such a recompressed-matrix is aneffective preconditioner. We prove that the construction ofthe matrices as well as the matrix-vector product can be performedin almost linear time in the number of unknowns. Numerical experimentsfor scattering problems in 2D are presented, where the linearsystems are solved by a preconditioned iterative method.}