GPU accelerated fast multipole methods for vortex particle simulation

Many physics based simulations can be efficiently and accurately performed using particle methods which focus computational resources at the location of sources or discontinuities (particles), and evaluation of relevant fields at locations of interest. These particle methods result in the so-called N-body problem. The N-body problem also arises in interpolation using implicit functions, in simulation of molecular and stellar dynamics, and other areas. Fast and accurate N-body simulations are the goal of this paper. The Fast Multipole Method (FMM) has been proposed for these. In this paper we provide efficient data-structures implemented on Graphical Processing Units (GPUs), and a novel parallel formulation of the FMM on GPUs to address this problem. As an example application, we simulate the interactions between vortex rings. Except for initial setup, our approach processes all the computations and updates on GPU. Further, we provide interactive visualization of the simulation as it proceeds. Where the cost of direct simulation of the interaction of vortices and particles is O(n2 + nm) per time step, where n is number of vortex elements and m is the number of particles, our algorithm reduces it to O(n + m) cost.