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 land 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. 1995 Academic Press, Inc.