A novel algorithm for computing forces in N-body simulations is presented. This algorithm constructs a hierarchical tree data structure and uses multipole expansions for the inverse square law. It can be considered as a multipole-based variant of Barnes-Hut algorithm [2]. The key idea here is the representation of forces (gravitational or electrostatic) through a multipole series by using the relationship between ultraspherical and Legendre polynomials. The primary advantage of this algorithm is the accuracy it offers along with the ease of coding. This method can be used in the simulation of star clusters in astrophysical applications in which higher order moments are expensive and difficult to construct. This method can also be used in molecular dynamics simulations as an alternative to particle-mesh and Ewald Summation methods which suffer from large errors due to various differentiation schemes. Our algorithm has O(p3Nlog N) complexity where p is typically a small constant.
['Kasthuri Srinivasan', 'Vivek Sarin']
A treecode for accurate force calculations