TY - JOUR
T1 - The fast multipole method for gridless particle simulation
AU - Ambrosiano, John
AU - Greengard, Leslie
AU - Rokhlin, Vladimir
PY - 1988/1
Y1 - 1988/1
N2 - The numerical solution to N-body problems in gravitation or electrostatics has traditionally been obtained via particle-in-cell methods (PIC) since direct evaluation of all pairwise interparticle forces, requiring O(N2) operations, is too expensive. Recently, hierarchical solvers, which use tree data structures and lumped-force approximations, have made gridless simulations feasible in O(N log N) operations. In this paper, we explore the use of the fast multipole method (FMM) - a highly accurate order O(N) algorithm - in particle simulations. We briefly describe the FMM and its relation to other methods. Technical considerations of gridless simulations such as discrete particle fluctuations, sampling errors and boundary conditions are discussed and compared with PIC methodology. Examples of electrostatic simulations in plasma physics are presented.
AB - The numerical solution to N-body problems in gravitation or electrostatics has traditionally been obtained via particle-in-cell methods (PIC) since direct evaluation of all pairwise interparticle forces, requiring O(N2) operations, is too expensive. Recently, hierarchical solvers, which use tree data structures and lumped-force approximations, have made gridless simulations feasible in O(N log N) operations. In this paper, we explore the use of the fast multipole method (FMM) - a highly accurate order O(N) algorithm - in particle simulations. We briefly describe the FMM and its relation to other methods. Technical considerations of gridless simulations such as discrete particle fluctuations, sampling errors and boundary conditions are discussed and compared with PIC methodology. Examples of electrostatic simulations in plasma physics are presented.
UR - http://www.scopus.com/inward/record.url?scp=0023166090&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0023166090&partnerID=8YFLogxK
U2 - 10.1016/0010-4655(88)90029-X
DO - 10.1016/0010-4655(88)90029-X
M3 - Article
AN - SCOPUS:0023166090
SN - 0010-4655
VL - 48
SP - 117
EP - 125
JO - Computer Physics Communications
JF - Computer Physics Communications
IS - 1
ER -