An Improved Fast Multipole Algorithm for Potential Fields

SIAM Journal on Scientific ComputingPublished 1 November 1998

Tomasz Hrycak, Vladimir Rokhlin

DOI10.1137/s106482759630989x

Source URL

Citations82

SJR quartileQ1

SJR score1.63

SNIP1.76

TL;DR

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.

Abstract

A new version of the fast multipole method (FMM) for potential fields is presented. We introduce a new representation of potentials, in which most translation operators are diagonal. As a result, for double precision calculations in two dimensions we obtain an improvement of a factor of two to four in speed, compared to previously published algorithms; the improvement is expected to be much greater in three dimensions. The performance of the method is illustrated with several numerical examples.

Keywords

EngineeringPhysics and Astronomy

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 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.

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.

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.

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.