Abstract We present a scalable Poisson solver with O (N) complexity based on the fast multipole method (FMM) implemented in RAMSES. Our FMM constructs a hierarchy of FMM grids on top of the pre-existing Cartesian grid which is used to compute the force for hydrodynamics or particle–mesh simulations. In contrast to the O (N) multigrid solver (MG) — an iterative method that requires multiple V-cycles through a multi-resolution hierarchy of Cartesian grids — the FMM algorithm performs just one upward pass through the same hierarchy, during which multipole expansions are accumulated and shifted, followed by a single downward pass, in which local expansions are propagated. Numerical tests indicate that FMM attains accuracy comparable to that of MG for smooth potentials and is particularly well-suited for problems with isolated boundary conditions, since it avoids the approximate Dirichlet boundary conditions required by MG schemes. Although in theory FMM requires around 30 times more floating-point operations than MG, its higher arithmetic intensity leads to comparable performance and better scalability relative to MG.
Lee et al. (Sat,) studied this question.