A parallel fast multipole method for elliptic difference equations

Abstract

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.

Corrected typos; changed output format

Cited by in corpus (10)

• A fast immersed boundary method for external incompressible viscous flows using lattice Green's functions
• A fast lattice Green's function method for solving viscous incompressible flows on unbounded domains
• FLUPS: a Fourier-based Library of Unbounded Poisson Solvers
• Velocity gradient analysis of a head-on vortex ring collision
• A fast multi-resolution lattice Green's function method for elliptic difference equations
• Hierarchical Particle-Mesh: an FFT-accelerated Fast Multipole Method
• Planar potential flow on Cartesian grids
• Dynamics and decay of a spherical region of turbulence in free space
• Computation of Volume Potentials on Structured Grids Using the Method of Local Corrections
• Lattice Green's Functions for High Order Finite Difference Stencils