A fast solver for Poisson problems on infinite regular lattices
This provides a more efficient method for solving elliptic difference equations on infinite lattices, particularly beneficial when the number of loaded points is much smaller than the bounding box.
The paper presents a fast solver for Poisson problems on infinite regular lattices, achieving O(N_source) complexity compared to O(N_Ω log N_Ω) for FFT-based methods, where N_source is the number of loaded points.
The Fast Multipole Method (FMM) provides a highly efficient computational tool for solving constant coefficient partial differential equations (e.g. the Poisson equation) on infinite domains. The solution to such an equation is given as the convolution between a fundamental solution and the given data function, and the FMM is used to rapidly evaluate the sum resulting upon discretization of the integral. This paper describes an analogous procedure for rapidly solving elliptic \textit{difference} equations on infinite lattices. In particular, a fast summation technique for a discrete equivalent of the continuum fundamental solution is constructed. The asymptotic complexity of the proposed method is $O(N_{\rm source})$, where $N_{\rm source}$ is the number of points subject to body loads. This is in contrast to FFT based methods which solve a lattice Poisson problem at a cost $O(N_Ω\log N_Ω)$ independent of $N_{\rm source}$, where $Ω$ is an artificial rectangular box containing the loaded points and $N_Ω$ is the number of points in $Ω$.