A simple O(N log N) algorithm for the rapid evaluation of particle-particle interactions

Journal Article (Journal Article)

Exact simulations of huge systems of charged particles are impossible in practice, because their cost proportional to N2, where N is the number of particles. We present an approximate and simple O(N log N) algorithm based upon the idea of recursive bisection of the set of particles. A small fraction of the particle-particle interactions is evaluated exactly by direct summation, while the rest is approximated via multipole expansions. Our algorithm is easy to program (in particular, in parallel, which is trivial), and it is well suited for system with a non-uniform distribution of particles. For uniform systems, its accuracy and execution time are comparable to other fast methods such as tree codes and the fast multipole method. © 1995.

Full Text

Duke Authors

Cited Authors

  • Pérez-Jordá, JM; Yang, W

Published Date

  • December 29, 1995

Published In

Volume / Issue

  • 247 / 4-6

Start / End Page

  • 484 - 490

International Standard Serial Number (ISSN)

  • 0009-2614

Digital Object Identifier (DOI)

  • 10.1016/S0009-2614(95)01235-4

Citation Source

  • Scopus