Appendix B - Fast Multipole Methods for Three-Dimensional N-Body Problems

Summary

A fundamental issue in the use of vortex methods is the ability to use efficiently large numbers of computational elements for simulations of viscous and inviscid flows.

The traditional cost of the method scales as O(N²) as the N computational elements and particles induce velocities at each other, making the method unacceptable for simulations involving more than a few tens of thousands of particles. We reduce the computation cost of the method by making the observation that the effect of a cluster of particles at a certain distance may be approximated by a finite series expansion. When the space is subdivided in uniform boxes it is straightforward to construct an O(N^3/2) algorithm [189]. In the past decade faster methods have been developed that have operation counts of O(N log N) [17] or O(N) [91], depending on the details of the algorithm. In these algorithms the particle population is decomposed spatially into clusters of particles (see, for example, Figure B.1) and we build a hierarchy of clusters (a tree data structure) – smaller neighboring clusters combine to form a cluster of the next size up in the hierarchy and so on. The hierarchy allows one to determine efficiently where the multipole approximation of a certain cluster is valid.

The N-body problem appears in many fields of engineering and science ranging from astrophysics to micromagnetics and computer animation. In the past few years these N-body solvers have been implemented and applied in simulations involving vortex methods.