A parallel version of the fast multipole method

L. Greengard; W. D. Gropp

doi:10.1016/0898-1221(90)90349-O

A parallel version of the fast multipole method

L. Greengard, W. D. Gropp

Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

This paper presents a parallel version of the fast multipole method (FMM). The FMM is a recently developed scheme for the evaluation of the potential and force fields in systems of particles whose interactions are Coulombic or gravitational in nature. The sequential method requires O(N) operations to obtain the fields due to N charges, rather than the O(N²) operations required by the direct calculation. Here, we describe the modifications necessary for implementation of the method on parallel architectures and show that the expected time requirements grow as log N when using N processors. Numerical results are given for a shared memory machine (the Encore Multimax 320).

Original language	English (US)
Pages (from-to)	63-71
Number of pages	9
Journal	Computers and Mathematics with Applications
Volume	20
Issue number	7
DOIs	https://doi.org/10.1016/0898-1221(90)90349-O
State	Published - 1990

ASJC Scopus subject areas

Modeling and Simulation
Computational Theory and Mathematics
Computational Mathematics

Access to Document

10.1016/0898-1221(90)90349-O

Cite this

@article{413416a1a3654d35848a8e2ac652b835,

title = "A parallel version of the fast multipole method",

abstract = "This paper presents a parallel version of the fast multipole method (FMM). The FMM is a recently developed scheme for the evaluation of the potential and force fields in systems of particles whose interactions are Coulombic or gravitational in nature. The sequential method requires O(N) operations to obtain the fields due to N charges, rather than the O(N2) operations required by the direct calculation. Here, we describe the modifications necessary for implementation of the method on parallel architectures and show that the expected time requirements grow as log N when using N processors. Numerical results are given for a shared memory machine (the Encore Multimax 320).",

author = "L. Greengard and Gropp, {W. D.}",

note = "Funding Information: Acknowledgements--The work by the first author was supported in part by the Office of Naval Research under Contract No. N00014-86-K-0310 and by a National Science Foundation Postdoctoral Fellowship. The work of the second author was supported in part by the Office of Naval Research under Contract No. N00014-86-K-0310 and the National Science Foundation under Contract No. DCR 8521451.",

year = "1990",

doi = "10.1016/0898-1221(90)90349-O",

language = "English (US)",

volume = "20",

pages = "63--71",

journal = "Computers and Mathematics with Applications",

issn = "0898-1221",

publisher = "Elsevier Limited",

number = "7",

}

TY - JOUR

T1 - A parallel version of the fast multipole method

AU - Greengard, L.

AU - Gropp, W. D.

N1 - Funding Information: Acknowledgements--The work by the first author was supported in part by the Office of Naval Research under Contract No. N00014-86-K-0310 and by a National Science Foundation Postdoctoral Fellowship. The work of the second author was supported in part by the Office of Naval Research under Contract No. N00014-86-K-0310 and the National Science Foundation under Contract No. DCR 8521451.

PY - 1990

Y1 - 1990

N2 - This paper presents a parallel version of the fast multipole method (FMM). The FMM is a recently developed scheme for the evaluation of the potential and force fields in systems of particles whose interactions are Coulombic or gravitational in nature. The sequential method requires O(N) operations to obtain the fields due to N charges, rather than the O(N2) operations required by the direct calculation. Here, we describe the modifications necessary for implementation of the method on parallel architectures and show that the expected time requirements grow as log N when using N processors. Numerical results are given for a shared memory machine (the Encore Multimax 320).

AB - This paper presents a parallel version of the fast multipole method (FMM). The FMM is a recently developed scheme for the evaluation of the potential and force fields in systems of particles whose interactions are Coulombic or gravitational in nature. The sequential method requires O(N) operations to obtain the fields due to N charges, rather than the O(N2) operations required by the direct calculation. Here, we describe the modifications necessary for implementation of the method on parallel architectures and show that the expected time requirements grow as log N when using N processors. Numerical results are given for a shared memory machine (the Encore Multimax 320).

UR - http://www.scopus.com/inward/record.url?scp=0002897633&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0002897633&partnerID=8YFLogxK

U2 - 10.1016/0898-1221(90)90349-O

DO - 10.1016/0898-1221(90)90349-O

M3 - Article

AN - SCOPUS:0002897633

SN - 0898-1221

VL - 20

SP - 63

EP - 71

JO - Computers and Mathematics with Applications

JF - Computers and Mathematics with Applications

IS - 7

ER -

A parallel version of the fast multipole method

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this