The fast multipole algorithm on Transputer networks
The authors describe an implementation of a fast algorithm for the solution of the N body problem on a Transputer network of P processors with a run time complexity that approaches O(N/P). The recent serial fast multipole algorithm of Greengard and Rokhlin which solves the N body problem in order N time is the basis of this work; their parallel version is a straightforward extension of that work. Results for the two-dimensional version of the algorithm are reported; work is in progress on the three-dimensional version. This algorithm comprises the computational heart of molecular dynamics simulation codes for many materials; these codes can be used to investigate the thermal and statistical mechanical properties of matter from consideration of appropriate ensemble averages over particle trajectories in phase space. Use of the new algorithm on high performance computers will allow simulation study of far larger systems than has been possible to date
