Parallel adaptive fast multipole method

We present parallel versions of a representative N-body application that uses Greengard and Roklin's adaptive Fast Multipole Method (FMM), While paralell implementations of the uniform FMM are straightforward and have been developed on different architectures, the adaptive version complicates the task of obtaining effective parallel performance owing to the nonuniform and dynamically changing nature of the problem domains to which it is applied. We propose and evaluate two techniques for providing load balancing and data locality, both of which take advantage of key insights into the method and its typical applications.