The Fast Multipole Algorithm The X10 language

Evaluating the energy of a system of N bodies interacting via a pairwise potential is naïvely an O(N) problem. The Fast Multipole Method[1] uses truncated expansions in a hierarchical division of the simulation space to achieve an approximation to a specified level of accuracy in only O(N) time. A multipole expansion approximates the potential at the origin due to particles within a sphere centered at a distant point r. Expansions A local expansion approximates the potential due to distant particles, at any point r within a sphere centered at the origin. Hierarchical division of space 3D space is divided into an octree of cubic boxes. (Only 4 of 8 boxes shown here.) For the red box: • Multipole expansions are used for every box in the interaction list (dark blue) • Non-well-separated boxes (light blue) are evaluated at a lower level in the tree • More remote boxes (white) are evaluated at a higher level 1) Create the octree 2) Create multipole expansions for each box at the lowest level of octree 3) Combine expansions for child boxes into an expansion for each parent box (upward pass) 4) Transform multipole expansion for each box to local expansion for all boxes in interaction list; translate parent expansion to each child box (downward pass) 5) At lowest level, use local expansion for each box to calculate potential and force due to all remote particles; use direct pairwise evaluation for near particles Step