Mapping the adaptive fast multipole algorithm onto MIMD systems
The adaptive fast multipole algorithm (AFMA) is an algorithm developed by Greengard and Rohklin (Yale Univ., Dept. of Comp. Sci., Res. rep., RR 602, 1988) for evaluating potential fields in nonuniformly distributed particle systems (N-body problems). The AFMA evaluates the fields resulting from the interaction of N charges (or masses) in O(N) time. However, when parallelizing the algorithm on fixed topology, distributed memory systems, the unstructured nature of the problem generates communication problems. To account for that, a new parallel adaptive fast multipole algorithm (PAFMA) has been developed for certain classes of nonuniform problems. It utilizes the fast multipole algorithm (FMA), also developed by Greengard and Rohklin for use on uniformly distributed particle systems. The PAFMA subdivides the problem into regions on which the FMA, which takes advantage of regular communication patterns, can be used
