A new version of the Fast Multipole Method for the Laplace equation in three dimensions
Acta NumericaPublished 1 January 1997
Leslie Greengard, Vladimir Rokhlin
Citations884
SJR quartileQ1
SJR score6.61
SNIP9.03
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A new version of the Fast Multipole Method for the evaluation of potential fields in three dimensions is introduced based on a new diagonal form for translation operators and yields high accuracy at a reasonable cost.
Abstract
We introduce a new version of the Fast Multipole Method for the evaluation of potential fields in three dimensions. It is based on a new diagonal form for translation operators and yields high accuracy at a reasonable cost.
Keywords
EngineeringPhysics and Astronomy
American Journal of PhysicsMethods of Theoretical Physics
13,257 Citations1954Philip Μ. Morse, Herman Feshbach +1 more
American Mathematical MonthlyA Treatise on the Theory of Bessel Functions.
9,555 Citations1923Matthew Porter, G. N. Watson
Journal of Computational PhysicsA fast algorithm for particle simulations
4,917 Citations1987Leslie Greengard, Vladimir Rokhlin
An algorithm is presented for the rapid evaluation of the potential and force fields in systems involving large numbers of particles whose interactions are Coulombic or gravitational in nature, making it considerably more practical for large-scale problems encountered in plasma physics, fluid dynamics, molecular dynamics, and celestial mechanics.
Journal of the Franklin InstituteMethods of theoretical physics
4,823 Citations1954Caterina Domenicali
NatureA hierarchical O(N log N) force-calculation algorithm
3,685 Citations1986Josh Barnes, Piet Hut
A novel method of directly calculating the force on N bodies that grows only as N log N is described, using a tree-structured hierarchical subdivision of space into cubic cells, each is recursively divided into eight subcells whenever more than one particle is found to occupy the same cell.
Computer Simulation Using Particles
2,126 Citations1988R. W. Hockney, J.W. Eastwood
Communications on Pure and Applied MathematicsFast wavelet transforms and numerical algorithms I
1,777 Citations1991Gregory Beylkin, Ronald R. Coifman +1 more
The algorithms presented here are based on the recently developed theory of wavelets and are applicable to all Calderon-Zygmund and pseudo-differential operators, and indicate that many previously intractable problems become manageable with the techniques presented here.
IEEE Antennas and Propagation MagazineThe fast multipole method for the wave equation: a pedestrian prescription
1,474 Citations1993Ronald R. Coifman, Vladimir Rokhlin +1 more
The FMM provides an efficient mechanism for the numerical convolution of the Green's function for the Helmholtz equation with a source distribution and can be used to radically accelerate the iterative solution of boundary-integral equations.
Journal of Computational PhysicsRapid solution of integral equations of classical potential theory
1,398 Citations1985Vladimir Rokhlin
An algorithm is described for rapid solution of classical boundary value problems (Dirichlet an Neumann) for the Laplace equation based on iteratively solving integral equations of potential theory using CPUs proportional to n.
The MIT Press eBooksThe Rapid Evaluation of Potential Fields in Particle Systems
1,059 Citations1988Leslie Greengard
IEEE Transactions on Computer-Aided Design of Integrated Circuits and SystemsFastCap: a multipole accelerated 3-D capacitance extraction program
905 Citations1991K. Nabors, Jacob White
Performance comparisons on integrated circuit bus crossing problems show that for problems with as few as 12 conductors the multipole accelerated boundary element method can be nearly 500 times faster than Gaussian-elimination-based algorithms, and five to ten times slower than the iterative method alone, depending on required accuracy.
Microwave and Optical Technology LettersMultilevel fast‐multipole algorithm for solving combined field integral equations of electromagnetic scattering
857 Citations1995Jiming Song, Weng Cho Chew
The fast multipole method has been implemented to speed up the matrix-vector multiply when an iterative method is used to solve the combined field integral equation (CFIE).
Journal of Computational PhysicsRapid solution of integral equations of scattering theory in two dimensions
825 Citations1990Vladimir Rokhlin
An algorithm for rapid solution of boundary value problems for the Helmholtz equation in two dimensions based on iteratively solving integral equations of scattering theory is described.
SIAM Journal on Scientific and Statistical ComputingA Fast Adaptive Multipole Algorithm for Particle Simulations
614 Citations1988Jean‐François Carrier, Leslie Greengard +1 more
An algorithm for the rapid evaluation of the potential and force fields in systems involving large numbers of particles whose interactions are described by Coulomb's law, which has an asymptotic CPU time estimate of $O(N)$ and does not depend on the statistics of the distribution for its efficient performance.
Numerische MathematikOn the fast matrix multiplication in the boundary element method by panel clustering
578 Citations1989Wolfgang Hackbusch, Zenon P. Nowak
A method for the approximate matrix-vector multiplication is described which requires much less arithmetical work and the storage requirements are strongly reduced.
SIAM Journal on Scientific and Statistical ComputingAn Efficient Program for Many-Body Simulation
535 Citations1985Andrew W. Appel
This paper describes both the particular program and the methodology underlying such speedups that reduced the running time of a large problem $(N = 10,000)$ by a factor of four hundred.
SIAM Journal on Scientific and Statistical ComputingThe Fast Gauss Transform
498 Citations1991Leslie Greengard, John Strain
An algorithm is presented which evaluates the sum of N Gaussians at M arbitrarily distributed points in $C \cdot (N + M)$ work, where C depends only on the precision required.
Angular Momentum in Quantum Physics: Theory and Application
490 Citations1984L. C. Biedenharn, James D. Louck
Journal of Computational PhysicsMultilevel matrix multiplication and fast solution of integral equations
438 Citations1990Achi Brandt, A.A. Lubrecht
It is shown that the complexity of this calculation can be reduced from O(n2) to O(sn), provided the kernel K is sufficiently smooth, and Corresponding integral equations can be solved to a similar accuracy in basically the same amount of work.
The Journal of Chemical PhysicsAtomic level simulations on a million particles: The cell multipole method for Coulomb and London nonbond interactions
418 Citations1992Hong-Qiang Ding, Naoki Karasawa +1 more
Applied and Computational Harmonic AnalysisDiagonal Forms of Translation Operators for the Helmholtz Equation in Three Dimensions
415 Citations1993Vladimir Rokhlin
SIAM Journal on Scientific ComputingWavelet-Like Bases for the Fast Solution of Second-Kind Integral Equations
407 Citations1993Bradley K. Alpert, Gregory Beylkin +2 more
A class of vector-space bases is introduced for the sparse representation of discretizations of integral operators possessing a smooth, nonoscillatory kernel possessing a finite number of singularities in each row or column as a sparse matrix, to high precision.
SIAM Journal on Scientific ComputingMultipole Translation Theory for the Three-Dimensional Laplace and Helmholtz Equations
278 Citations1995Michael A. Epton, B. Dembart
The mathematical theory of multipole translation operators for the three-dimensional Laplace and Helmholtz equations is summarized and extended and an elementary proof of the inner-to-inner translation theorem is proved.
Computer Physics CommunicationsMultilevel computations of integral transforms and particle interactions with oscillatory kernels
232 Citations1991Achi Brandt
Algorithms for performing dense-matrix multiplication for n×n matrices representing the interaction of n particles or the discretization of integral transforms on n gridpoints are described.
SIAM Journal on Matrix Analysis and ApplicationsA Divide-and-Conquer Algorithm for the Symmetric Tridiagonal Eigenproblem
229 Citations1995Ming Gu, Stanley C. Eisenstat
A new, stable method for finding the spectral decomposition of a symmetric arrowhead matrix and a new implementation of deflation are presented, which are competitive with bisection with inverse iteration, Cuppen's divide-and-conquer algorithm, and the QR algorithm for solving the symmetric tridiagonal eigenproblem.
SIAM Journal on Scientific and Statistical ComputingA Fast Algorithm for the Evaluation of Legendre Expansions
218 Citations1991Bradley K. Alpert, Vladimir Rokhlin
An algorithm is presented for the rapid calculation of the values and coefficients of finite Legendre series and admits far-reaching generalizations and is currently being applied to several other problems.
IEEE Transactions on Antennas and PropagationA study of wavelets for the solution of electromagnetic integral equations
214 Citations1995Robert Wagner, Weng Cho Chew
The use of wavelet basis functions for the efficient solution of electromagnetic integral equations is studied and the effect is examined and analyzed in terms of the radiation/receiving characteristics of the wavelets basis functions.
Chemical Physics LettersAccelerated molecular dynamics simulation with the parallel fast multipole algorithm
192 Citations1992John A. Board, Jeffrey W. Causey +3 more
The fast multipole algorithm of Greengard and Rokhlin is implemented and incorporated into the molecular dynamics program MD, allowing rapid computation of the non-bonded forces acting in dynamical protein systems without truncation or other corruption of the Coulomb force.
SIAM Journal on Scientific ComputingPreconditioned, Adaptive, Multipole-Accelerated Iterative Methods for Three-Dimensional First-Kind Integral Equations of Potential Theory
185 Citations1994K. Nabors, F. T. Korsmeyer +2 more
This paper presents a preconditioned, Krylov-subspace iterative algorithm, where a modified multipole algorithm with a novel adaptation scheme is used to compute the iterates for solving dense matrix problems generated by Galerkin or collocation schemes applied to three-dimensional, first-kind, integral equations that arise in potential theory.
Comptes rendus de l'Académie des sciences. Série 1, MathématiqueRemarques sur l'analyse de Fourier à fenêtre
171 Citations1991Ronald R. Coifman, Yves Meyer
Lecture notes in mathematicsThe rapid evaluation of potential fields in three dimensions
161 Citations1988L. Grengard, Vladimir Rokhlin
Journal of Computational PhysicsLaplace's Equation and the Dirichlet-Neumann Map in Multiply Connected Domains
160 Citations1993Anne Greenbaum, Leslie Greengard +1 more
SIAM Journal on Scientific ComputingGeneralized Gaussian Quadratures and Singular Value Decompositions of Integral Operators
158 Citations1998Norman Yarvin, Vladimir Rokhlin
The approach of Ma et al. is modified, improving the stability of the scheme and extending its range of applicability, and results indicate that such quadratures dramatically reduce the computational cost of the evaluation of integrals under certain conditions.
IEEE Transactions on Circuits and Systems I Fundamental Theory and ApplicationsMultipole-accelerated capacitance extraction algorithms for 3-D structures with multiple dielectrics
150 Citations1992K. Nabors, Jacob White
The authors describe how to extend the multiple-accelerated boundary-element method for 3-D capacitance computation to the case where conductors are embedded in an arbitrary piecewise-constant dielectric medium.
American Journal of PhysicsMathematical Analysis of Physical Problems
129 Citations1973Philip R. Wallace, William C. Davidon
Journal of Computational PhysicsA method of local corrections for computing the velocity field due to a distribution of vortex blobs
128 Citations1986Christopher R. Anderson
A computationally efficient method for computing the velocity field due to a distribution of vortex blobs is presented, which requires fewer calculations than the straightforward vortex method velocity procedure and does not sacrifice the higher- order accuracy which can be achieved using higher-order vortex core functions.
IEEE Transactions on Antennas and PropagationImproved impedance matrix localization method (EM problems)
125 Citations1993F.X. Canning
Journal of Computational PhysicsIntegral Equation Methods for Stokes Flow and Isotropic Elasticity in the Plane
123 Citations1996Leslie Greengard, Mary Catherine A. Kropinski +1 more
Transactions of the American Mathematical SocietyFast algorithms for multiple evaluations of the Riemann zeta function
123 Citations1988Andrew Odlyzko, Arnold Schönhage
SIAM Journal on Scientific ComputingFast Fourier Transform Accelerated Fast Multipole Algorithm
121 Citations1996William D. Elliott, John A. Board
A new block decomposition of the multipole expansion data that provides numerical stability and efficient computation in the Fourier domain using the fast Fourier transform (FFT) is described.
Microwave and Optical Technology LettersA ray‐propagation fast multipole algorithm
95 Citations1994Robert Wagner, Weng Cho Chew
A nonnested, ray-propagation approach is used to compute a matrix-vector multiply in O(N4/3) operations, where N is the number of unknowns in the discretized integral equation.
Computers in PhysicsThe Numerical Solution of the <i>N</i>-Body Problem
88 Citations1990Leslie Greengard
A steering column for absorbing impact energy comprising a steering shaft mounted for rotation in a vehicle by an upper bearing which collapses under a predetermined load if the vehicle is impacted so that the steering wheel remains in position and so that impact energy is absorbed.
Journal of Computational PhysicsA Direct Adaptive Poisson Solver of Arbitrary Order Accuracy
86 Citations1996Leslie Greengard, June‐Yub Lee
A direct, adaptive solver for the Poisson equation which can achieve any prescribed order of accuracy is presented, based on a domain decomposition approach using local spectral approximation, as well as potential theory and the fast multipole method.
SIAM Journal on Scientific ComputingAn Improved Fast Multipole Algorithm for Potential Fields
82 Citations1998Tomasz Hrycak, Vladimir Rokhlin
A new version of the fast multipole method (FMM) for potential fields is presented, in which most translation operators are diagonal, resulting in an improvement of a factor of two to four in speed, compared to previously published algorithms.
Acta NumericaOn the numerical evaluation of electrostatic fields in composite materials
76 Citations1994Leslie Greengard, Monique Moura
Journal of Computational PhysicsFast, adaptive summation of point forces in the two-dimensional Poisson equation
76 Citations1989Leon van Dommelen, Elke A. Rundensteiner
A relatively simple procedure is outlined which significantly reduces the number of operations by replacing selected partial sums by asymptotic series, corresponding to a ''fast'' solver.
SIAM Journal on Scientific and Statistical ComputingThe Fast Gauss Transform with Variable Scales
59 Citations1991John Strain
This algorithm evaluates the sum of N Gaussians at M arbitrarily distributed points in C(N + M) work, where C depends only on the precision required and the essential minimum of the scales.
The Journal of Chemical PhysicsAn efficient fast-multipole algorithm based on an expansion in the solid harmonics
56 Citations1996H. Y. Wang, R. LeSar
Journal of ComplexityA fast algorithm for the discrete laplace transformation
51 Citations1988Vladimir Rokhlin
An algorithm for the rapid evaluation of expressions of the form ∑ j=1 m α j ·e −β j ·x at multiple points is presented, and its performance is demonstrated by numerical examples.
SIAM Journal on Scientific and Statistical ComputingSparse Approximation for Solving Integral Equations with Oscillatory Kernels
44 Citations1992F.X. Canning
An integral equation formulation of Helmholtz’s equation is considered as an example of a problem with an oscillatory kernel that allows directional radiation patterns to be produced by using a phase cancellation when constructing “extended” sources.
Computers & Mathematics with ApplicationsEnd-point corrected trapezoidal quadrature rules for singular functions
44 Citations1990Vladimir Rokhlin
On the Efficient Implementation of the Fast Multipole Algorithm.
40 Citations1988Leslie Greengard, Rokhlin
A procedure permitting translation operators to be applied to p to the 4th power degree expansions for a cost proportional to p is described, which speeds up the execution of two-dimensional single precision codes and three-dimensional codes by roughly a factor of eight.
Proceedings of the Royal Society of London Series A Mathematical and Physical SciencesError estimates for the fast multipole method. I. The two-dimensional case
30 Citations1995Henrik Gordon Petersen, D. Soelvason +2 more
What the error actually is for the two-dimensional case of the Greengard-Rokhlin algorithm is illustrated, and an estimate has a simple analytic form which will allow its use in tuning the algorithm for best efficiency.
SIAM Journal on Scientific ComputingGrid-Multipole Calculations
30 Citations1995C.L. Berman
New high-order, momentum conserving methods for spreading charge to and interpolating potential from the mesh allow efficient grid-based algorithms to be used in high- order accurate n-body particle codes such as the fast multipole algorithm of Greengard and Rokhlin.
Applied and Computational Harmonic AnalysisFast Numerical Computations of Oscillatory Integrals Related to Acoustic Scattering, I
29 Citations1993Brian Bradie, Ronald R. Coifman +1 more
Proceedings of the Royal Society of London Series A Mathematical and Physical SciencesError estimates for the fast multipole method. II. The three-dimensional case
25 Citations1995Henrik Gordon Petersen, E.R. Smith +1 more
An explicit though complicated form for the error in the three dimensional case of the fast multipole method is developed, and an estimate is derived which will allow its use in tuning the method for best efficiency and for comparison of the method with other methods at the same accuracy.
Mathematics of ComputationA fast Laplace transform based on Laguerre functions
21 Citations1992John Strain
A Fast Laplae Transform Based on Laguerre Funtions y John Strain Courant Institute of Mathematial Sienes 251 Merer Street New York, NY 10012 January 13, 2000.
Electronics LettersReducing moment method storage from order <i>N</i> <sup>2</sup> to order <i>N</i>
9 Citations1989F.X. Canning
Microwave and Optical Technology LettersVariational formulation of electromagnetic boundaryvalue problems involving anisotropic media
6 Citations1994Jian‐Ming Jin, Weng Cho Chew