Fast and accurate evaluation of nonlocal coulomb and dipole-dipole interactions via the nonuniform FFT

Shidong Jiang, Leslie Greengard, Weizhu Bao

Research output: Contribution to journalArticlepeer-review


We present a fast and accurate algorithm for the evaluation of nonlocal (longrange) Coulomb and dipole-dipole interactions in free space. The governing potential is simply the convolution of an interaction kernel ψ(x) and a density function ψ(x) = |ψ(x)|2 for some complexvalued wave function ψψ(x), permitting the formal use of Fourier methods. These are hampered by the fact that the Fourier transform of the interaction kernel ρ U(k) has a singularity and/or ρ(k) = 0 at the origin k = 0 in Fourier (phase) space. Thus, accuracy is lost when using a uniform Cartesian grid in k which would otherwise permit the use of the FFT for evaluating the convolution. Here, we make use of a high-order discretization of the Fourier integral, accelerated by the nonuniform fast Fourier transform (NUFFT). By adopting spherical and polar phase-space discretizations in three and two dimensions, respectively, the singularity in U (k) at the origin is canceled so that only a modest number of degrees of freedom are required to evaluate the Fourier integral, assuming that the density function (ρx) is smooth and decays sufficiently quickly as |x| → 8. More precisely, the calculation requires O(N logN) operations, where N is the total number of discretization points in the computational domain. Numerical examples are presented to demonstrate the performance of the algorithm.

Original languageEnglish (US)
Pages (from-to)B777-B794
JournalSIAM Journal on Scientific Computing
Issue number5
StatePublished - 2014


  • Coulomb interaction
  • Dipole-dipole interaction
  • Interaction energy
  • Nonlocal
  • Nonuniform FFT
  • Poisson equation

ASJC Scopus subject areas

  • Computational Mathematics
  • Applied Mathematics


Dive into the research topics of 'Fast and accurate evaluation of nonlocal coulomb and dipole-dipole interactions via the nonuniform FFT'. Together they form a unique fingerprint.

Cite this