A kernel-independent adaptive fast multipole algorithm in two and three dimensions

Lexing Ying, George Biros, Denis Zorin

Research output: Contribution to journalArticlepeer-review


We present a new fast multipole method for particle simulations. The main feature of our algorithm is that it does not require the implementation of multipole expansions of the underlying kernel, and it is based only on kernel evaluations. Instead of using analytic expansions to represent the potential generated by sources inside a box of the hierarchical FMM tree, we use a continuous distribution of an equivalent density on a surface enclosing the box. To find this equivalent density, we match its potential to the potential of the original sources at a surface, in the far field, by solving local Dirichlet-type boundary value problems. The far-field evaluations are sparsified with singular value decomposition in 2D or fast Fourier transforms in 3D. We have tested the new method on the single and double layer operators for the Laplacian, the modified Laplacian, the Stokes, the modified Stokes, the Navier, and the modified Navier operators in two and three dimensions. Our numerical results indicate that our method compares very well with the best known implementations of the analytic FMM method for both the Laplacian and modified Laplacian kernels. Its advantage is the (relative) simplicity of the implementation and its immediate extension to more general kernels.

Original languageEnglish (US)
Pages (from-to)591-626
Number of pages36
JournalJournal of Computational Physics
Issue number2
StatePublished - May 20 2004


  • Double-layer potential
  • Fast multipole methods
  • Fast solvers
  • Integral equations
  • N-body problems
  • Particle methods
  • Single-layer potential

ASJC Scopus subject areas

  • Numerical Analysis
  • Modeling and Simulation
  • Physics and Astronomy (miscellaneous)
  • General Physics and Astronomy
  • Computer Science Applications
  • Computational Mathematics
  • Applied Mathematics


Dive into the research topics of 'A kernel-independent adaptive fast multipole algorithm in two and three dimensions'. Together they form a unique fingerprint.

Cite this