Scalable variants of multipolebased algorithms for molecular dynamics applications
Abstract
Multipolebased algorithms allow for reduction in the effort required to solve the Nbody problem of electrostatics or graviation from O(N{sup 2}) to O(N log N) or even O(N) in the number of interacting bodies N. We consider serial and parallel implementations of variants of the algorithms of Barnes and Hut, and of Greengard and Rokhlin, as well as a hybrid algorithm. Coupled with other optimizations such as a Fourierdomain computation of multipole series translations, we find the hybrid algorithm to be most efficient over a wide range of accuracy and system sizes relevant to molecular dynamics. The algorithms have been demonstrated to scale to 64 processors, and we expect them to be valid out to at least 512 processors on large (1 million particle) problems.
 Authors:

 Duke Univ., Durham, NC (United States)
 Publication Date:
 OSTI Identifier:
 125521
 Report Number(s):
 CONF950212
CNN: Grant ASC9318159;Grant CDR8622201;Grant RR0810201; TRN: 95:0057680065
 Resource Type:
 Conference
 Resource Relation:
 Conference: 7. Society for Industrial and Applied Mathematics (SIAM) conference on parallel processing for scientific computing, San Francisco, CA (United States), 1517 Feb 1995; Other Information: PBD: 1995; Related Information: Is Part Of Proceedings of the seventh SIAM conference on parallel processing for scientific computing; Bailey, D.H.; Bjorstad, P.E.; Gilbert, J.R. [eds.] [and others]; PB: 894 p.
 Country of Publication:
 United States
 Language:
 English
 Subject:
 66 PHYSICS; 99 MATHEMATICS, COMPUTERS, INFORMATION SCIENCE, MANAGEMENT, LAW, MISCELLANEOUS; PARALLEL PROCESSING; ALGORITHMS; MOLECULAR CLUSTERS; COMPUTERIZED SIMULATION
Citation Formats
Board, Jr, J A, Hakura, Z S, and Elliott, W D. Scalable variants of multipolebased algorithms for molecular dynamics applications. United States: N. p., 1995.
Web.
Board, Jr, J A, Hakura, Z S, & Elliott, W D. Scalable variants of multipolebased algorithms for molecular dynamics applications. United States.
Board, Jr, J A, Hakura, Z S, and Elliott, W D. 1995.
"Scalable variants of multipolebased algorithms for molecular dynamics applications". United States.
@article{osti_125521,
title = {Scalable variants of multipolebased algorithms for molecular dynamics applications},
author = {Board, Jr, J A and Hakura, Z S and Elliott, W D},
abstractNote = {Multipolebased algorithms allow for reduction in the effort required to solve the Nbody problem of electrostatics or graviation from O(N{sup 2}) to O(N log N) or even O(N) in the number of interacting bodies N. We consider serial and parallel implementations of variants of the algorithms of Barnes and Hut, and of Greengard and Rokhlin, as well as a hybrid algorithm. Coupled with other optimizations such as a Fourierdomain computation of multipole series translations, we find the hybrid algorithm to be most efficient over a wide range of accuracy and system sizes relevant to molecular dynamics. The algorithms have been demonstrated to scale to 64 processors, and we expect them to be valid out to at least 512 processors on large (1 million particle) problems.},
doi = {},
url = {https://www.osti.gov/biblio/125521},
journal = {},
number = ,
volume = ,
place = {United States},
year = {1995},
month = {12}
}