A free-space adaptive fmm-based pde solver in three dimensions

M. Harper Langston, Leslie Greengard, Denis Zorin

Research output: Contribution to journalArticlepeer-review


We present a kernel-independent, adaptive fast multipole method (FMM) of arbitrary order accuracy for solving elliptic PDEs in three dimensions with radiation and periodic boundary conditions. The algorithm requires only the ability to evaluate the Green's function for the governing equation and a representation of the source distribution (the right-hand side) that can be evaluated at arbitrary points. The performance is accelerated in three ways. First, we construct a piecewise polynomial approximation of the right-hand side and compute far-field expansions in the FMM from the coefficients of this approximation. Second, we precompute tables of quadratures to handle the near-field interactions on adaptive octree data structures, keeping the total storage requirements in check through the exploitation of symmetries. Third, we employ shared-memory parallelization methods and load-balancing techniques to accelerate the major algorithmic loops of the FMM.We present numerical examples for the Laplace, modified Helmholtz and Stokes equations.

Original languageEnglish (US)
Pages (from-to)79-122
Number of pages44
JournalCommunications in Applied Mathematics and Computational Science
Issue number1
StatePublished - 2011


  • Adaptive methods
  • Fast multipole method
  • Kernel-independent fast multipole method
  • Poisson solver
  • Volume integrals

ASJC Scopus subject areas

  • Computer Science Applications
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'A free-space adaptive fmm-based pde solver in three dimensions'. Together they form a unique fingerprint.

Cite this