Robust fast solvers for the Poisson equation have generally been limit
ed to regular geometries, where direct methods, based on Fourier analy
sis or cyclic reduction, and multigrid methods can be used. While mult
igrid methods can be applied in irregular domains (and to a broader cl
ass of partial differential equations), they are difficult to implemen
t 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 th
eory rather than on direct discretization of the partial differential
equation. Our method combines fast algorithms for computing volume int
egrals 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 rectangula
r domain in which the problem domain can be embedded, independent of t
he complexity of the geometry. (c) 1995 Academic Press, Inc.