Periodic fast multipole method

Applications in electrostatics, magnetostatics, fluid mechanics, and elasticity often involve sources contained in a unit cell C, centered at the origin, on which periodic boundary condition are imposed. The free-space Green’s functions for many classical partial differential equations (PDE), such as the modified Helmholtz equation, are well-known. Among the existing schemes for imposing the periodicity, three common approaches are: direct discretization of the governing PDE including boundary conditions to yield a large sparse linear system of equations, spectral methods which solve the governing PDE using Fourier analysis, and the method of images based on tiling the plane with copies of the unit cell and computing the formal solution. In the method of images, the lattice of image cells is divided into a “near” region consisting of the unit source cell and its nearest images and an infinite “far” region covered by the remaining images. Recently, two new approaches were developed to carry out calculation of the free-space Green’s function over sources in the near region and correct for the lack of periodicity using an integral representation or a representation in terms of discrete auxiliary Green’s functions. Both of these approaches are effective even for unit cells of high aspect ratio, but require the solution of a possibly ill-conditioned linear system of equations in the correction step. In this dissertation, a new scheme is proposed to treat periodic boundary conditions within the framework of the fast multipole method (FMM). The scheme is based on an explicit, low-rank representation for the influence of all far images. It avoids the lattice sum/Taylor series formalism altogether and is insensitive to the aspect ratio of the unit cell. The periodizing operators are formulated with plane-wave factorizations that are valid for half spaces, leading to a simple fast algorithm. When the rank is large, a more elaborate algorithm using the Non-Uniform Fast Fourier Transform (NUFFT) can further reduce the computational cost. The computation for modified Helmholtz case is explained in detail. The Poisson equation is discussed, with charge neutrality as a necessary constraint. Both the Stokes problem and the modified Stokes problem are formulated and solved. The full scheme including the NUFFT acceleration is described in detail and the performance of the method is illustrated with extensive numerical examples. In the last chapter, another project about boundary integral equations is presented. Boundary integral equations and Nystrom discretization methods provide a powerful tool for computing the solution of Laplace and Helmholtz boundary value problems (BVP). Using the fundamental solution (free-space Green’s function) for these equations, such problems can be converted into boundary integral equations, thereby reducing the dimension of the problem by one. The resulting geometric simplicity and reduced dimensionality allow for high-order accurate numerical solutions with greater efficiency than standard finite-difference or finite-element discretizations. Integral equation methods require appropriate quadrature rules for evaluating the singular and nearly singular integrals involved. A standard approach uses a panel-based discretization of the curve and Generalized Gaussian Quadrature (GGQ) rules for treating singular and nearly-singular integrals separately, which correspond to a panel’s interaction with itself and its neighbors, respectively. In this dissertation, a new panel-based scheme is developed which circumvents the difficulties of the nearly-singular integrals. The resulting rule is more efficient than standard GGQ in terms of the number of required kernel evaluations