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 [special characters omitted], where κ 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 [special characters omitted] 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.
|Commitee:||Alpert, Bradley, Julien, Keith, Martinsson, Per-Gunnar, Meyer, Francois|
|School:||University of Colorado at Boulder|
|School Location:||United States -- Colorado|
|Source:||DAI-B 69/03, Dissertation Abstracts International|
|Keywords:||Band-limited kernels, Fast convolutions, Green's functions, Lattice sums, Polar grid, Quadratures, Quasi-periodic, Separated representations, Unequally spaced FFT|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be