  We propose a Fast Fourier Transform based Periodic Interpolation Method
(FFT-PIM), a flexible and computationally efficient approach for computing the
scalar potential given by a superposition sum in a unit cell of an infinitely
periodic array. Under the same umbrella, FFT-PIM allows computing the potential
for 1D, 2D, and 3D periodicities for dynamic and static problems, including
problems with and without a periodic phase shift. The computational complexity
of the FFT-PIM is of $O(N \log N)$ for $N$ spatially coinciding sources and
observer points. The FFT-PIM uses rapidly converging series representations of
the Green's function serving as a kernel in the superposition sum. Based on
these representations, the FFT-PIM splits the potential into its near-zone
component, which includes a small number of images surrounding the unit cell of
interest, and far-zone component, which includes the rest of an infinite number
of images. The far-zone component is evaluated by projecting the non-uniform
sources onto a sparse uniform grid, performing superposition sums on this
sparse grid, and interpolating the potential from the uniform grid to the
non-uniform observation points. The near-zone component is evaluated using an
FFT-based method, which is adapted to efficiently handle non-uniform
source-observer distributions within the periodic unit cell. The FFT-PIM can be
used for a broad range of applications, such as periodic problems involving
integral equations in computational electromagnetic and acoustic, micromagnetic
solvers, and density functional theory solvers.
