Basic HTML version of Foils prepared 5 October 98

Foil 12 Second two Solutions of O(N2) Computational Complexity

From Earthquake Prediction as Example of N Body Computations CPS615 INtroduction to Computational Science -- Fall Semester 1998. by Geoffrey C. Fox
3) Cutoff long range forces (common strategy in chemistry where Forces fall off faster (E.g. 1/r5) than in gravity)
  • This leads to a classic nearest neighbor O(N) algorithm with irregular geometry causes minor implementation issues
Use the new "fast multipole" algorithms which have been very successful in other related areas
  • Astrophysics
  • Computational Electromagnetic
  • Vortex approach to CFD
Instead of zeroing out contributions of far away particles, these methods do an ingenious multipole expansion of the contributions of far away regions

© 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 Apr 11 1999