Hierarchical Particle-Mesh: an FFT-accelerated Fast Multipole Method
arXiv:1906.10734 · doi:10.3847/1538-4365/ab2d24
Abstract
I describe a modification to the original Fast Multipole Method (FMM) of Greengard & Rokhlin that approximates the gravitation field of an FMM cell as a small uniform grid (a "gridlet") of effective masses. The effective masses on a gridlet are set from the requirement that the multipole moments of the FMM cells are reproduced exactly, hence preserving the accuracy of the gravitational field representation. The calculation of the gravitational field from a multipole expansion can then be computed for all multipole orders simultaneously, with a single Fast Fourier Transform, significantly reducing the computational cost at a given value of the required accuracy. The described approach belongs to the class of "kernel independent" variants of the FMM method and works with any Green function.
arXiv commentAccepted for publication in the ApJ
References in corpus (6)
- Enforcing the Courant-Friedrichs-Lewy Condition in Explicitly Conservative Local Time Stepping Schemes
- Yet another fast multipole method without multipoles --- Pseudo-particle multipole method
- A parallel fast multipole method for elliptic difference equations
- Pseudoparticle Multipole Method: A Simple Method to Implement High-Accuracy Treecode
- Grommet: an N-body code for high-resolution simulations of individual galaxies
- Real-space quadrature: a convenient, efficient representation for multipole expansions