research-article

An Implementation of the Fast Multipole Method without Multipoles

Author:

Christopher R. AndersonAuthors Info & Claims

SIAM Journal on Scientific and Statistical Computing, Volume 13, Issue 4

Pages 923 - 947

https://doi.org/10.1137/0913055

Published: 01 July 1992 Publication History

Abstract

An implementation is presented of the fast multipole method, which uses approximations based on Poisson’s formula. Details for the implementation in both two and three dimensions are given. Also discussed is how the multigrid aspect of the fast multipole method can be exploited to yield efficient programming procedures. The issue of the selection of an appropriate refinement level for the method is addressed. Computational results are given that show the importance of good level selection. An efficient technique that can be used to determine an optimal level to choose for the method is presented.

References

[1]

C. R. Anderson, HELM2: A hierarchical element method in two dimensions, UCLA Report, CAM 90-15, Department of Mathematics, University of California, Los Angeles, CA, 1990

[2]

C. R. Anderson, HELMS: A hierarchical element method in three dimensions, UCLA Report, CAM 90-16, Department of Mathematics, University of California, Los Angeles, CA, 1990

[3]

J. Barnes, P. Hut, A hierarchical $O(N \log N)$ force-calculation algorithm, Nature, 324 (1986), 466–499

[4]

R. Courant, D. Hilbert, Methods of mathematical physics. Vol. I, Interscience Publishers, Inc., New York, N.Y., 1953xv+561

[5]

L. Greengard, V. Rokhlin, A fast algorithm for particle simulations, J. Comput. Phys., 73 (1987), 325–348

Digital Library

[6]

L. Greengard, V. Rokhlin, C. Anderson, C. Greengard, Fast methods in three dimensionsVortex Methods, Lecture Notes in Mathematics 1360, Springer-Verlag, Berlin, New York, 1988

[7]

L. Greengard, V. Rokhlin, On the efficient implementation o f the fast multiple algorithm, Report, 602, Department of Computer Science, Yale University, New Haven, CT, 1988

[8]

L. Hernquist, TREESPH: A Unification of SPH with The Hierarchical Tree Method, Astrophysical Journal Supp., 64 (1987), 715–

[9]

Jacob Katzenelson, Computational structure of the N-body problem, SIAM J. Sci. Statist. Comput., 10 (1989), 787–815

Digital Library

[10]

A. D. McLaren, Optimal numerical integration on a sphere, Math. Comp., 17 (1963), 361–383

[11]

Z. P. Nowak, J. Ballman, R. Eppler, W. Hackbusch, Panel clustering technique for lifting potential flows in the three space dimensionsPanel Methods in Mechanics, Notes in Numerical Fluid Mechanics, 1360, Vieweg-Verlag, Braunschewig, Wiesbaden, 1987

[12]

V. Rokhlin, Rapid solution of integral equations of scattering theory in two dimensions, J. Comput. Phys., 86 (1990), 414–439

Digital Library

[13]

A. H. Stroud, Approximate calculation of multiple integrals, Prentice-Hall Inc., Englewood Cliffs, N.J., 1971xiii+431

[14]

K. Stuben, U. Trottenberg, W. Hackbusch, U. Trottenberg, Multigrid methods: fundamental algorithms, model problem analysis and applicationsMultigrid methods (Cologne, 1981), Lecture Notes in Math., Vol. 960, Springer, Berlin, 1982, 1–176, New York

[15]

L. Van Dommelen, E. Rundensteiner, Fast adaptive summation of point forces in two-dimensional Poisson equations, J. Comp. Phys., 83 (1989), 126–147

Digital Library

Cited By

Börm S(2023)Distributed ℋ2-Matrices for Boundary Element MethodsACM Transactions on Mathematical Software10.1145/358249449:2(1-21)Online publication date: 15-Jun-2023
https://dl.acm.org/doi/10.1145/3582494
Chen D(2023)A hybrid stochastic interpolation and compression method for kernel matricesJournal of Computational Physics10.1016/j.jcp.2023.112491494:COnline publication date: 1-Dec-2023
https://dl.acm.org/doi/10.1016/j.jcp.2023.112491
Gortsas TTsinopoulos SPolyzos D(2022)An accelerated boundary element method via cross approximation of integral kernels for large‐scale cathodic protection problemsComputer-Aided Civil and Infrastructure Engineering10.1111/mice.1268737:7(848-863)Online publication date: 6-May-2022
https://dl.acm.org/doi/10.1111/mice.12687
Show More Cited By

Index Terms

An Implementation of the Fast Multipole Method without Multipoles

Index terms have been assigned to the content through auto-classification.

Recommendations

A New Fast-Multipole Accelerated Poisson Solver in Two Dimensions

We present an adaptive fast multipole method for solving the Poisson equation in two dimensions. The algorithm is direct, assumes that the source distribution is discretized using an adaptive quad-tree, and allows for Dirichlet, Neumann, periodic, and ...
Acceleration of Contour Dynamics Simulations with a Hierarchical-Element Method

This paper presents a so-called hierarchical-element method that can be used to accelerate complex contour dynamics simulations. The method is based on a modified fast multipole method where the multipole approximations are replaced by Poisson ...
A kernel-independent uniform fast multipole method based on barycentric rational interpolation
Abstract
A kernel-independent uniform fast multipole method (UFMM) is presented for fast summation of particle interactions, where the kernel is approximated by using the Floater-Hormann (FH) rational interpolant at the equispaced grids. The proposed UFMM ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image SIAM Journal on Scientific and Statistical Computing

SIAM Journal on Scientific and Statistical Computing Volume 13, Issue 4

Jul 1992

198 pages

ISSN:0196-5204

Issue’s Table of Contents

Copyright © 1992 Society for Industrial and Applied Mathematics.

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 July 1992

Author Tags

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

42
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Börm S(2023)Distributed ℋ2-Matrices for Boundary Element MethodsACM Transactions on Mathematical Software10.1145/358249449:2(1-21)Online publication date: 15-Jun-2023
https://dl.acm.org/doi/10.1145/3582494
Chen D(2023)A hybrid stochastic interpolation and compression method for kernel matricesJournal of Computational Physics10.1016/j.jcp.2023.112491494:COnline publication date: 1-Dec-2023
https://dl.acm.org/doi/10.1016/j.jcp.2023.112491
Gortsas TTsinopoulos SPolyzos D(2022)An accelerated boundary element method via cross approximation of integral kernels for large‐scale cathodic protection problemsComputer-Aided Civil and Infrastructure Engineering10.1111/mice.1268737:7(848-863)Online publication date: 6-May-2022
https://dl.acm.org/doi/10.1111/mice.12687
Rahola J(2022)Diagonal forms of the translation operators in the fast multipole algorithm for scattering problemsBIT10.1007/BF0173198736:2(333-358)Online publication date: 11-Mar-2022
https://dl.acm.org/doi/10.1007/BF01731987
Ramani RShkoller S(2020)A multiscale model for Rayleigh-Taylor and Richtmyer-Meshkov instabilitiesJournal of Computational Physics10.1016/j.jcp.2019.109177405:COnline publication date: 15-Mar-2020
https://dl.acm.org/doi/10.1016/j.jcp.2019.109177
Wala MKlöckner A(2020)Optimization of fast algorithms for global Quadrature by Expansion using target-specific expansionsJournal of Computational Physics10.1016/j.jcp.2019.108976403:COnline publication date: 15-Feb-2020
https://dl.acm.org/doi/10.1016/j.jcp.2019.108976
Börm SChristophersen S(2016)Approximation of integral operators by Green quadrature and nested cross approximationNumerische Mathematik10.1007/s00211-015-0757-y133:3(409-442)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1007/s00211-015-0757-y
Bebendorf MKuske CVenn R(2015)Wideband nested cross approximation for Helmholtz problemsNumerische Mathematik10.1007/s00211-014-0656-7130:1(1-34)Online publication date: 1-May-2015
https://dl.acm.org/doi/10.1007/s00211-014-0656-7
Gillman AMartinsson P(2014)A fast solver for Poisson problems on infinite regular latticesJournal of Computational and Applied Mathematics10.1016/j.cam.2013.09.003258(42-56)Online publication date: 1-Mar-2014
https://dl.acm.org/doi/10.1016/j.cam.2013.09.003
Börm SGördes J(2013)Low-rank approximation of integral operators by using the Green formula and quadratureNumerical Algorithms10.1007/s11075-012-9679-264:3(567-592)Online publication date: 1-Nov-2013
https://dl.acm.org/doi/10.1007/s11075-012-9679-2
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents