A fast Poisson solver for complex geometries

A. McKenney, L. Greengard, A. Mayo

Research output: Contribution to journalArticlepeer-review


Robust fast solvers for the Poisson equation have generally been limited to regular geometries, where direct methods, based on Fourier analysis or cyclic reduction, and multigrid methods can be used. While multigrid methods can be applied in irregular domains (and to a broader class of partial differential equations), they are difficult to implement in a robust fashion, since they require an appropriate hierarchy of coarse grids, which are not provided in many practical situations. In this paper, we present a new fast Poisson solver based on potential theory rather than on direct discretization of the partial differential equation. Our method combines fast algorithms for computing volume integrals and evaluating layer potentials on a grid with a fast multipole accelerated integral equation solver. The amount of work required is O (m log m + N), where m is the number of interior grid points and N is the number of points on the boundary. Asymptotically, the cost of our method is just twice that of a standard Poisson solver on a rectangular domain in which the problem domain can be embedded, independent of the complexity of the geometry.

Original languageEnglish (US)
Pages (from-to)348-355
Number of pages8
JournalJournal of Computational Physics
Issue number2
StatePublished - May 1995

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 fast Poisson solver for complex geometries'. Together they form a unique fingerprint.

Cite this