High performance implementations of the fast multipole algorithm
Implementations of a fast algorithm for the solution of the N body problem on two parallel computers are described. The recent fast multipole algorithm of Greengard and Rokhlin which solves the N body problem in order N time is implemented on two commercial parallel computers (BBN ButterflyTM and IN-MOS Transputer TM). Speedup and timing results for the two-dimensional version of the algorithm are reported and compared; work is in progress on three-dimensional implementations. This algorithm comprises the computational heart of molecular dynamics (MD) simulation codes for many condensed materials; these codes can be used to investigate the thermal behavior 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.