Search

The formal representation of the quasi-periodic Helmholtz Green's function obtained by the method of images is only conditionally convergent and, thus, requires an appropriate summation convention for its evaluation. Instead of using this formal sum, we derive a candidate Green's function as a sum of two rapidly convergent series, one to be applied in the spatial domain and the other in the Fourier domain (as in Ewald's method). We prove that this representation of Green's function satisfies the Helmholtz equation with the quasi-periodic condition and, furthermore, leads to a fast algorithm for its application as an operator.We approximate the spatial series by a short sum of separable functions given by Gaussians in each variable. For the series in the Fourier domain, we exploit the exponential decay of its terms to truncate it. We use fast and accurate algorithms for convolving functions with this approximation of the quasi-periodic Green's function. The resulting method yields a fast solver for the Helmholtz equation with the quasi-periodic boundary condition. The algorithm is adaptive in the spatial domain and its performance does not significantly deteriorate when Green's function is applied to discontinuous functions or potentials with singularities. We also construct Helmholtz Green's functions with Dirichlet, Neumann or mixed boundary conditions on simple domains and use a modification of the fast algorithm for the quasi-periodic Green's function to apply them.The complexity, in dimension d≥2, of these algorithms is O(κdlogκ+C(logϵ−1)d), where ϵ is the desired accuracy, κ is proportional to the number of wavelengths contained in the computational domain and C is a constant. We illustrate our approach with examples. [ABSTRACT FROM AUTHOR]

We develop fast discrete Fourier transforms (and their adjoints) from a square in space to a disk in the Fourier domain. Since our new transforms are not unitary, we develop a fast inversion algorithm and derive corresponding estimates that allow us to avoid iterative methods typically used for inversion. We consider the eigenfunctions of the corresponding band-limiting and space-limiting operator to describe spaces on which these new transforms can be inverted and made useful. In the process, we construct polar grids which provide quadratures and interpolation with controlled accuracy for functions band-limited within a disk. For rapid computation of the involved trigonometric sums we use the unequally spaced fast Fourier transform, thus yielding fast algorithms for all new transforms. We also introduce polar grids motivated by linearized scattering problems which are obtained by discretizing a family of circles. These circles are generated by using a single circle passing through the origin and rotating this circle with the origin as a pivot. For such grids, we provide a fast algorithm for interpolation to a near optimal grid in the disk, yielding an accurate adjoint transform and inversion algorithm. [ABSTRACT FROM AUTHOR]