Multigrid methods are known to solve the 3-dimensional Poisson equation in O(N) complexity. The idea is to descritize the system with an equi-spaced grid and to smear the partial charges of the particles with a specified interpolation onto the grid. Dirichlet boundary conditions are calculated by a multipole expansion scheme, which has complexity O(N). Applying the multigrid technique offers a solution of the the global potential surface in overall complexity O(N). In order to calculate the interaction energy between particles in the system, the energy surface has to be corrected for the self contribution of each particle. This is performed by subtracting the grid based calculated and charge weighted Green's function at each charge location. An accurate near-field part is calculated by subtracting the potential at a charges' location due to nearby particles and in calculating exact particle-particle interactions in this region.


References: