Sparse Diagonal Forms for Translation Operators for the Helmholtz Equation in TwoDimensions

摘要

In the design of Fast Multipole Methods (FMM) for the numerical solution ofscattering problems, a crucial step is the diagonalization of translation operators for the Helmholtz equation. These operators have analytically simple, physically transparent, and numerically stable diagonal forms. It has been obseryed by several researchers that for any given precision E, diagonal forms for the translation operators for the Helmholtz equation are not unique, and that some choices lead to more efficient FMM schemes than others. As is well-known, original single-stage FMM algorithms for the Helmholtz equation have asymptotic CPU time requirements of order O(n(exp 3/2)), where n is the number of nodes in the discretiza tion of the boundary of the scatterer; two-stage versions have CPU time estimates of order O(n(exp 4/3)); generally, k-stage versions have CPU time estimates of order O(n(exp (k+2)/(k+1))). However, there exist choices of diagonal forms leading to single-stage FMM algorithms with CPU time requirements of order O(n(exp 4/3)), two-stage schemes with CPU time requirements 0(n(exp 5/4)), etc. In this paper, we construct such diagonal forms in two dimensions. While the construction of this paper is in no sense optimal, it is rigorous and straightforward. Our numerical experiments indicate that it is within a factor of two of being optimal, in terms of the number of nodes required to discretize the translation operator to a specified precision E. The procedure is illustrated with several numerical examples.