The Cluster Multipole Algorithm for Far-Field Computations

Computer simulations of N-body systems are beneficial to study the overall behavior of a number of physical systems in fields such as astrophysics, molecular dynamics, and computational fluid dynamics. A new approach for computer simulations of N-body systems is proposed in this research. The new algorithm is called the Cluster Multipole Algorithm (CMA). The goals of the new algorithm are to improve the applicability to non-point sources and to provide more control on the accuracy over current algorithms. The algorithm is targeted to applications that do not require rebuilding the data structure about the system every time step due to current limitations in the construction of the data structure. Examples of slowly changing systems can be found in molecular dynamics, capacitance, and computational fluid dynamics simulations. As the data structure development is improved, the new algorithm will be applicable to a wider range of applications. The CMA exhibits the flexibility of both Appel\u27s algorithm and the Fast Multipole Method (FMM) without sacrificing the order of computation (O(N)) for well structured clusters. The CMA provides more control on the accuracy of computations as compared to both the FMM and Appel\u27s algorithm resulting in enhanced performance. A set of requirements are imposed on the data structures which are applicable, to maintain O(N) computation. However, the algorithm is capable of handling a wide range of data structures beyond the FMM