Fast, high-order methods for scattering by inhomogeneous media

In this thesis, we introduce a new, fast, high-order method for scattering by inhomogeneous media in three dimensions. As in previously existing methods, the low ($O$(N log N)) complexity of our integral equation method is obtained through extensive use of the fast Fourier transform (FFT) in evaluating the required convolutions. Unlike previous FFT-based methods, however, this method yields high-order accuracy, even for scatterers containing geometric singularities such as discontinuities, corners, and cusps.; We begin our discussion with a thorough theoretical analysis of an efficient, high-order method recently introduced by Bruno and Sei (IEEE Trans. in Antenn. Propag., 2000), which motivated the present work. This two-dimensional method is based on a Fourier approximation of the integral equation in polar coordinates and a related, generally low-order, Fourier smoothing of the scatterer. The claim that use of this low-order approximation of the scatterer leads to a high-order accurate numerical method generated considerable controversy. Our proofs establish that this method indeed yields high-order accurate solutions. We also introduce several substantial improvements to the numerical implementation of this two-dimensional algorithm, which lead to increased numerical stability with decreased computational cost.; We then present our new, fast, high-order method in three dimensions. An immediate generalization of the polar coordinate approach in two dimensions to a spherical coordinate approach in three dimensions appears less advantageous than our chosen approach: Fourier approximation and integration in Cartesian coordinates. To obtain smooth and periodic functions (which are approximated to high-order via Fourier series), we (1) decompose the Green's function into a smooth part with infinite support and a singular part with compact support; and (2) replace, as in the two-dimensional approach, the (possibly discontinuous) scatterer with its truncated Cartesian Fourier series.; The accuracy of our three-dimensional method is approximately equal to that of the two-dimensional method mentioned above and, interestingly, is actually much simpler than the two-dimensional approach. In addition to our theoretical discussion of these high-order methods, we present a parallel implementation of our three-dimensional Cartesian approach. The efficiency, high-order accuracy, and overall performance of both the polar and Cartesian methods are demonstrated through several computational examples.