Spreading
Spreading deposits charges from particles in continuous space onto a discrete, regular grid so that long-range interactions can be evaluated using FFTs. An assignment window determines how each particle’s charge is distributed among nearby grid points.
Gathering uses the same assignment weights to interpolate the resulting grid potential back to the particles. Deconvolution compensates in Fourier space for the smoothing introduced by spreading and gathering.
For the nonuniform FFT formulation of these steps, see Barnett, Magland, and af Klinteberg, A Parallel Nonuniform Fast Fourier Transform Library Based on an “Exponential of Semicircle” Kernel, SIAM Journal on Scientific Computing 41(5), C479–C504 (2019).
The spreading window
In a periodic cell of volume , the point-charge density is
Choose a real, even, periodic assignment window with unit integral:
It is usually constructed by periodically repeating a compact local window. Convolving this window with the point-charge density gives a smooth density:
Each delta function becomes a translated copy of the window, scaled by the particle’s charge. Positive and negative particles contribute with their original signs. The continuous density retains the total charge because has unit integral.
From density to grid charges
Let be a grid point and the volume per grid point. Multiplying the sampled density by gives the grid charges:
The weights are dimensionless. For a cubic mesh of spacing , . A compact window supported on grid points per axis touches at most nodes for each particle in three dimensions. Indices wrap across periodic cell boundaries.
Spreading is a direct real-space sum: evaluate the local weights and accumulate charge at neighboring nodes. The continuous density is a useful mathematical description; the implementation computes directly from the particle positions and charges.
If the sampled weights obey a partition of unity,
then spreading conserves the total charge exactly, up to roundoff:
Unit integral of the continuous window alone does not guarantee this discrete property. It must hold for the chosen sampled assignment rule.
Production spline: C2O3
With C2 Prolate splitting, cuPotential uses the C2O3 spreading spline, which has approximation order 3. Its assignment weights use four grid points per axis and are , giving a mesh energy that is in particle positions and analytical forces for a fixed box and mesh.
What the grid FFT computes
Use the cell Fourier convention
where runs over reciprocal lattice vectors. Define the window’s transfer function and the particles’ structure factor as
The convolution theorem gives an exact relation for the continuous density:
The unnormalized forward FFT of grid charges approximates these coefficients:
Sampling folds higher frequencies onto the retained grid modes. These aliasing terms account for the difference between and and limit how accurately the window’s effect can be removed.
Computing structure factors directly costs . With grid points, local spreading followed by one FFT reduces this cost to .
Deconvolution in Fourier space
The long-range potential is the convolution , where is the periodized long-range kernel defined by the splitting. Its Fourier coefficients are , with . Applying the physical kernel to the spread density instead gives
Deconvolution compensates the smoothing introduced by spreading. Where , dividing by recovers the desired coefficient:
After grid sampling, the actual DFT is , so the corresponding operation is only approximate:
The inverse transform gives an approximate potential at grid nodes, corrected for the smoothing introduced by spreading. The full particle calculation also accounts for gathering, which reuses the assignment weights.
The Fourier relations describe continuous functions. Spreading on the grid is a local real-space sum; the FFT follows that sum. The exact continuous coefficient becomes on the sampled grid.
Gathering reuses the spreading weights
After the inverse FFT, gather the auxiliary mesh field at each particle using the same weights that spread its charge onto the mesh:
Spreading sends a particle value to nearby grid points; gathering collects nearby grid values at a particle. Using the same real weights makes these discrete operations transposes of each other. A partition-of-unity window reproduces a constant grid field exactly.
The same weights are applied twice: once to spread charge onto the mesh and once to interpolate the mesh field back to the particles. In the continuum model without aliases, these operations contribute and its complex conjugate , respectively. Their combined factor is , so the full influence function compensates both applications:
because
For a real, even window, is real and the denominator is . The correction compensates spreading alone; compensates spreading and gathering together, using the same window in both steps.
The complete mesh calculation
With the retained grid modes and the chosen Coulomb zero mode excluded, the pipeline is
In the cell convention used here,
An FFT library may normalize its inverse differently. For an inverse FFT containing , where is the total number of mesh points, this expression is . With an unnormalized inverse, the prefactor is .
The matching mesh energy has three equivalent forms:
This is the smooth mesh contribution, before the self and other physical corrections. An energy-only evaluation can use the spectral sum directly. For a fixed box and a symmetric influence operator, differentiating this mesh energy gives
Potential gathering uses the assignment weights; this analytical force gather uses their derivatives with respect to the particle position.
What deconvolution cannot undo
Sampling folds unresolved frequencies into resolved ones. For a cubic mesh of spacing with origin zero, its DFT contains aliases of the form
Dividing by the base-mode does not separate those folded terms. It also cannot recover omitted modes, and small values of can amplify numerical error. Mesh resolution, assignment support, the physical splitting, and the chosen influence function must therefore be considered together.
In cuPotential’s current KSpace path, the correction uses discrete stencil power to match the assignment on the grid. The Ewald B-spline path uses squared stencil DFT amplitudes with a treatment for near-zero values; the C2-order-3 (C2O3) path uses stencil power averaged over fractional particle positions within a grid cell. The three-dimensional denominator is the product of the per-axis powers. These discrete corrections take the place of the continuous model’s .
See Error Analysis for the combined effect on energy and force errors, and Deserno and Holm’s particle-mesh analysis for assignment, aliasing, and influence functions.