TreeSweeps.pdf

Illustration of the components in a fast multipole method (FMM), with the upward sweep depicted on the left side of the tree, and the downward sweep depicted on the right side of the tree. In the FMM, multipole expansions are created at the leaf level of the tree (P2M operation), they are then translated upwards to the center of the parent cells in the multipole-to-multipole (M2M) translation, then transformed to a local expansion in the multipole-to-local (M2L) operation for the siblings at all levels deeper than level 1. The local expansions are translated downward to children cells in the local-to-local (L2L) operation and finally, the local expansions are added at the leaf level and evaluated in the local-to-particle (L2P) operation. This figure appeared in the following paper, under (c) 2011 The Authors. “A tuned and scalable fast multipole method as a preeminent algorithm for exascale systems”, Rio Yokota, L A Barba. Int. J. High-perf. Comput. (2011) Preprint arXiv:1106.2176 - doi:10.1177/1094342011429952 The figure is here shared under CC-BY.