Mapping the adaptive fast multipole algorithm onto MIMD systems

Journal Article (Academic article)

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

Duke Authors

Cited Authors

  • Leathrum, ; F, J; Jr, ; Board, ; A, J

Published Date

  • 1992

Published In

  • Unstructured Scientific Computation on Scalable Multiprocessors

Start / End Page

  • 161 - 177

Conference Location

  • Nags Head, NC, USA