A Parallel Adaptive Fast Multipole algorithm for N-body problems

We describe the design and implementation of a parallel adaptive fast multipole algorithm (AFMA) for N-body problems. Our AFMA algorithm can organize particles in cells of arbitrary shape. This simplifies its parallelization, so that good locality and load balance are both easily achieved. We describe a tighter well-separatedness criterion, and improved techniques for constructing the AFMA tree. We describe how to avoid redundant computation of pair-wise interactions while maintaining load balance, using a fast edge-partitioning algorithm. The AFMA algorithm is designed in an object oriented, message-driven manner, allowing latency tolerance by overlapping computation and communication easily. It also incorporates several optimizations for message prioritization and communication reduction. Preliminary performance results of our implementation using the Charm++ parallel programming system are presented.

Sanjeev Krishnan and L. V. Kale, "A Parallel Adaptive Fast Multipole Algorithm 
for N-Body Problems", Proceedings of the International Conference on Parallel 
Processing, August 1995, pp. III 46 - III 50.

@inproceedings{FastMultipoleICPP95,
  author = "Sanjeev Krishnan and L. V. Kale",
  title = "A Parallel Adaptive Fast Multipole Algorithm for N-Body Problems",
  booktitle = "Proceedings of the International Conference on
               Parallel Processing",
  pages = "III 46 - III 50",
  year = "1995",
  month = "August",
}