  A new fast multipole formulation for solving elliptic difference equations on
unbounded domains and its parallel implementation are presented. These
difference equations can arise directly in the description of physical systems,
e.g. crystal structures, or indirectly through the discretization of PDEs. In
the analog to solving continuous inhomogeneous differential equations using
Green's functions, the proposed method uses the fundamental solution of the
discrete operator on an infinite grid, or lattice Green's function. Fast
solutions $\mathcal{O}(N)$ are achieved by using a kernel-independent
interpolation-based fast multipole method. Unlike other fast multipole
algorithms, our approach exploits the regularity of the underlying Cartesian
grid and the efficiency of FFTs to reduce the computation time. Our parallel
implementation allows communications and computations to be overlapped and
requires minimal global synchronization. The accuracy, efficiency, and parallel
performance of the method are demonstrated through numerical experiments on the
discrete 3D Poisson equation.
