IMA Journal of Numerical Analysis Advance Access originally published online on April 18, 2007
IMA Journal of Numerical Analysis 2008 28(1):46-79; doi:10.1093/imanum/drm001
| ||||||||||||||||||||||||||||||||||||||||||||||||||
Hierarchical matrix techniques for low- and high-frequency Helmholtz problems
Mathematical Institute, University of Zurich, Zurich, Switzerland
Max-Planck Institute for Mathematics in the Sciences, Leipzig, Germany
Email: lehelb{at}math.unizh.ch
Corresponding author. Email: wh{at}mis.mpg.de
Received on 4 March 2005. Revised on 13 December 2006.
 |
Abstract |
|---|
In this paper, we discuss the application of hierarchical matrix techniques to the solution of Helmholtz problems with large wave number 
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 
-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 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 -matrix. Algebraic recompression methods are used to reduce the storage and the complexity of arithmetical operations of the -matrix. Further, an approximate LU decomposition of such a recompressed -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.
Key Words: Helmholtz equation; boundary element method; hierarchical matrices