Accession Number : ADA309451

Title :   Sparse Diagonal Forms for Translation Operators for the Helmholtz Equation in Two Dimensions,

Corporate Author : YALE UNIV NEW HAVEN CT DEPT OF COMPUTER SCIENCE

Personal Author(s) : Rokhlin, Vladimir

PDF Url : ADA309451

Report Date : 27 DEC 1995

Pagination or Media Count : 38

Abstract : In the design of Fast Multipole Methods (FMM) for the numerical solution of scattering 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.

Descriptors :   *ALGORITHMS, *MATHEMATICAL PROGRAMMING, *HELMHOLTZ EQUATIONS, MATHEMATICAL MODELS, OPTIMIZATION, TWO DIMENSIONAL, ELECTROMAGNETIC SCATTERING, FAR FIELD, APPROXIMATION(MATHEMATICS), OPERATORS(MATHEMATICS), NUMERICAL METHODS AND PROCEDURES, MULTIPOLARITY, BESSEL FUNCTIONS, FOURIER SERIES.

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE