Fast convolutions with Helmholtz Green's functions and radially symmetric band-limited kernels

This thesis presents fast and accurate numerical algorithms for computing convolutions with the free space and quasi-periodic Helmholtz Green's function in two and three dimensions. Toward this end, we also construct a fast discrete Fourier transform from the square in the spatial domain to the disk in the Fourier domain, the adjoint and inverse transforms, and several polar grids. These tools are of interest by themselves and have their own applications.; Computation of volumetric convolutions with these Green's functions appears in many disciplines of engineering, physics, and applied mathematics. Examples include scattering problems for penetrable obstacles which may be repeated within a lattice. A mathematical challenge occurs when the scattering obstacle is discontinuous and requires application of the Green's function to a discontinuous function. Since straightforward discretization of the convolution leads to a dense matrix, the computational cost of applying it in dimension d is Ok2d , where kappa is the wave-number of the Green's function. Alternatively, applying the convolution as multiplication in the Fourier domain requires discretizing a large volume due to slow decay of the kernel and function. Part of the motivation for this thesis is to address this complexity and difficulties maintaining accuracy when convolving with discontinuous functions.; The key element of our approach is splitting the Green's function between the spatial and Fourier domains. We use a limiting procedure to define the Green's functions yielding the splitting. Such splitting results in approximations with exponential decay in both domains and we utilize fast algorithms for their application as operators. Specifically, a sum of well localized Gaussians provides the spatial approximation and a radially symmetric effectively band-limited kernel gives the approximation in the Fourier domain. The algorithms to apply the Green's functions are designed to maintain their performance when convolved with discontinuous compactly supported functions and have computational complexity Okd logk with minimal dependence on the desired accuracy.; A part of our approach is the development of quadratures in the disk which incorporate radially symmetric band-limited kernels as part of the measure. Such quadratures can be used in a variety of applications and allows us to construct a fast discrete Fourier transform from the square to the disk and its adjoint. As part of the algorithm to compute the inverse transform, we construct eigenfunctions of the operator which band-limits to the disk and space-limits to the square. Properties of the corresponding eigenvalues are similar to those of the one dimensional prolate spheroidal wave functions. We exploit these properties to construct a fast inverse transform.