SPARSE DIAGONAL FORMS FOR TRANSLATION OPERATORS FOR THE HELMHOLTZ-EQUATION IN 2 DIMENSIONS

In the design of fast multipole methods (FMM) for the numerical soluti on of scattering problems, a crucial step is the diagonalization of tr anslation operators for the Helmholtz equation. These operators have a nalytically simple, physically transparent, and numerically stable dia gonal forms. It has been observed by several researchers that for any given precision epsilon, 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(3/2)), where n is the number of no des in the discretization of the boundary of the scatterer; two-stage versions have CPU time estimates of order O(n(4/3)); generally, k-stag e versions have CPU time estimates of order O(n((k+2)/(k+1))). However , there exist choices of diagonal forms leading to single-stage FMM al gorithms with CPU time requirements of order O(n(4/3)), two-stage sche mes with CPU time requirements O(n(5/4)), etc. In this paper. we const ruct 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 nudes required to discreti ze the translation operator to a specified precision epsilon. The proc edure is illustrated with several numerical examples. (C) 1998 Academi c Press.