Basic HTML version of Foils prepared April 7,1995

Foil 38 Large N-Body Calculations (Quinn, Salmon, Warren)

From Programming Paradigms B CRPC/MCNC Workshop -- April 10-13 1995. by Geoffrey C. Fox
Clustering algorithm (Appel, Barnes-Hut, Greengard)
Can replace M body force calculation by one using center of mass of cluster
  • Naive calculation has complexity 0.5 N2 t2 particle
  • Clustering has complexity (20-50) N log N t2 particle and is better when N >1000
Can do O(N=10,000) particles with O(N2) algorithm
Three orders of magnitude larger problem possible with clustering algorithm

Northeast Parallel Architectures Center, Syracuse University, npac@npac.syr.edu

If you have any comments about this server, send e-mail to webmaster@npac.syr.edu.

Page produced by wwwfoil on Sun Feb 22 1998