A fast algorithm for particle simulations

L. Greengard, V. Rokhlin

Research output: Contribution to journalArticlepeer-review


An algorithm is presented for the rapid evaluation of the potential and force fields in systems involving large numbers of particles whose interactions are Coulombic or gravitational in nature. For a system ofNparticles, an amount of work of the orderO(N2) has traditionally been required to evaluate all pairwise interactions, unless some approximation or truncation method is used. The algorithm of the present paper requires an amount of work proportional toNto evaluate all interactions to within roundoff error, making it considerably more practical for large-scale problems encountered in plasma physics, fluid dynamics, molecular dynamics, and celestial mechanics.

Original languageEnglish (US)
Pages (from-to)280-292
Number of pages13
JournalJournal of Computational Physics
Issue number2
StatePublished - Aug 1997

ASJC Scopus subject areas

  • Numerical Analysis
  • Modeling and Simulation
  • Physics and Astronomy (miscellaneous)
  • General Physics and Astronomy
  • Computer Science Applications
  • Computational Mathematics
  • Applied Mathematics


Dive into the research topics of 'A fast algorithm for particle simulations'. Together they form a unique fingerprint.

Cite this