Skip to navigation

Spreading

View as Markdown

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 Ω\Omega of volume VV, the point-charge density is

ρ(r)=∑i=1Nqi δper(r−ri).\rho(\mathbf r) =\sum_{i=1}^{N}q_i\,\delta_{\mathrm{per}}(\mathbf r-\mathbf r_i).

Choose a real, even, periodic assignment window WW with unit integral:

∫ΩW(r) d3r=1.\int_\Omega W(\mathbf r)\,d^3r=1.

It is usually constructed by periodically repeating a compact local window. Convolving this window with the point-charge density gives a smooth density:

ρW(r)=(W∗ρ)(r)=∫ΩW(r−r′)ρ(r′) d3r′=∑i=1NqiW(r−ri).\rho_W(\mathbf r) =(W*\rho)(\mathbf r) =\int_\Omega W(\mathbf r-\mathbf r')\rho(\mathbf r')\,d^3r' =\sum_{i=1}^{N}q_i W(\mathbf r-\mathbf r_i).

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 WW has unit integral.

From density to grid charges

Let rg\mathbf r_g be a grid point and ΔV\Delta V the volume per grid point. Multiplying the sampled density by ΔV\Delta V gives the grid charges:

Qg=ΔV ρW(rg)=∑i=1Nqiwg(ri),wg(r)=ΔV W(rg−r).Q_g=\Delta V\,\rho_W(\mathbf r_g) =\sum_{i=1}^{N}q_i w_g(\mathbf r_i), \qquad w_g(\mathbf r)=\Delta V\,W(\mathbf r_g-\mathbf r).

The weights wgw_g are dimensionless. For a cubic mesh of spacing hh, ΔV=h3\Delta V=h^3. A compact window supported on pp grid points per axis touches at most p3p^3 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 QgQ_g directly from the particle positions and charges.

If the sampled weights obey a partition of unity,

∑gwg(r)=1,\sum_g w_g(\mathbf r)=1,

then spreading conserves the total charge exactly, up to roundoff:

∑gQg=∑iqi.\sum_g Q_g=\sum_i q_i.

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 C2C^2, giving a mesh energy that is C2C^2 in particle positions and C1C^1 analytical forces for a fixed box and mesh.

What the grid FFT computes

Use the cell Fourier convention

f^(k)=∫Ωf(r)e−ik⋅r d3r,f(r)=1V∑kf^(k)eik⋅r,\widehat f(\mathbf k) =\int_\Omega f(\mathbf r)e^{-i\mathbf k\cdot\mathbf r}\,d^3r, \qquad f(\mathbf r)=\frac{1}{V}\sum_{\mathbf k} \widehat f(\mathbf k)e^{i\mathbf k\cdot\mathbf r},

where k\mathbf k runs over reciprocal lattice vectors. Define the window’s transfer function and the particles’ structure factor as

T(k)=W^(k),S(k)=ρ^(k)=∑iqie−ik⋅ri.T(\mathbf k)=\widehat W(\mathbf k), \qquad S(\mathbf k)=\widehat\rho(\mathbf k) =\sum_i q_i e^{-i\mathbf k\cdot\mathbf r_i}.

The convolution theorem gives an exact relation for the continuous density:

ρW^(k)=T(k)S(k).\widehat{\rho_W}(\mathbf k)=T(\mathbf k)S(\mathbf k).

The unnormalized forward FFT of grid charges approximates these coefficients:

A(k)=∑gQge−ik⋅rg≈T(k)S(k).A(\mathbf k)=\sum_g Q_g e^{-i\mathbf k\cdot\mathbf r_g} \approx T(\mathbf k)S(\mathbf k).

Sampling folds higher frequencies onto the retained grid modes. These aliasing terms account for the difference between AA and TSTS and limit how accurately the window’s effect can be removed.

Computing MM structure factors directly costs O(NM)O(NM). With MM grid points, local spreading followed by one FFT reduces this cost to O(Np3+Mlog⁡M)O(Np^3+M\log M).

Deconvolution in Fourier space

The long-range potential is the convolution ϕlr=ulrper∗ρ\phi_{\mathrm{lr}}=u_{\mathrm{lr}}^{\mathrm{per}}*\rho, where ulrperu_{\mathrm{lr}}^{\mathrm{per}} is the periodized long-range kernel defined by the splitting. Its Fourier coefficients are KlrSK_{\mathrm{lr}}S, with Klr=ulrper^K_{\mathrm{lr}}=\widehat{u_{\mathrm{lr}}^{\mathrm{per}}}. Applying the physical kernel to the spread density instead gives

ulrper∗(W∗ρ)⟷KlrTS.u_{\mathrm{lr}}^{\mathrm{per}}*(W*\rho) \quad\longleftrightarrow\quad K_{\mathrm{lr}}T S.

Deconvolution compensates the smoothing introduced by spreading. Where T≠0T\ne0, dividing by TT recovers the desired coefficient:

KlrT(TS)=KlrS.\frac{K_{\mathrm{lr}}}{T}(T S)=K_{\mathrm{lr}}S.

After grid sampling, the actual DFT is A≈TSA\approx TS, so the corresponding operation is only approximate:

ϕ^grid(k)=Klr(k)T(k)A(k)≈Klr(k)S(k).\widehat\phi_{\mathrm{grid}}(\mathbf k) =\frac{K_{\mathrm{lr}}(\mathbf k)}{T(\mathbf k)}A(\mathbf k) \approx K_{\mathrm{lr}}(\mathbf k)S(\mathbf k).

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 KlrTSK_{\mathrm{lr}}TS becomes KlrAK_{\mathrm{lr}}A on the sampled grid.

Gathering reuses the spreading weights

After the inverse FFT, gather the auxiliary mesh field bgb_g at each particle using the same weights wg(ri)w_g(\mathbf r_i) that spread its charge onto the mesh:

ϕmesh(ri)=∑gwg(ri)bg.\phi_{\mathrm{mesh}}(\mathbf r_i)=\sum_g w_g(\mathbf r_i)b_g.

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 TT and its complex conjugate T∗T^*, respectively. Their combined factor is T∗T=∣T∣2T^*T=|T|^2, so the full influence function compensates both applications:

G(k)=Klr(k)B(k),Bideal(k)=1∣T(k)∣2,G(\mathbf k)=K_{\mathrm{lr}}(\mathbf k)B(\mathbf k), \qquad B_{\mathrm{ideal}}(\mathbf k)=\frac{1}{|T(\mathbf k)|^2},

because

T∗Klr∣T∣2TS=KlrS.T^*\frac{K_{\mathrm{lr}}}{|T|^2}T S=K_{\mathrm{lr}}S.

For a real, even window, TT is real and the denominator is T2T^2. The correction 1/T1/T compensates spreading alone; 1/∣T∣21/|T|^2 compensates spreading and gathering together, using the same window in both steps.

The complete mesh calculation

With K\mathcal K the retained grid modes and the chosen Coulomb zero mode excluded, the pipeline is

{qi,ri}→spreadQg→FFTA(k)→×KlrBb^(k)→inverse FFTbg→gatherϕmesh(ri).\{q_i,\mathbf r_i\} \xrightarrow{\mathrm{spread}}Q_g \xrightarrow{\mathrm{FFT}}A(\mathbf k) \xrightarrow{\times K_{\mathrm{lr}}B}\widehat b(\mathbf k) \xrightarrow{\mathrm{inverse\ FFT}}b_g \xrightarrow{\mathrm{gather}}\phi_{\mathrm{mesh}}(\mathbf r_i).

In the cell convention used here,

bg=1V∑k∈KKlr(k)B(k)A(k)eik⋅rg.b_g=\frac1V\sum_{\mathbf k\in\mathcal K} K_{\mathrm{lr}}(\mathbf k)B(\mathbf k)A(\mathbf k) e^{i\mathbf k\cdot\mathbf r_g}.

An FFT library may normalize its inverse differently. For an inverse FFT containing 1/M1/M, where MM is the total number of mesh points, this expression is (M/V)IFFT⁡(KlrBA)(M/V)\operatorname{IFFT}(K_{\mathrm{lr}}BA). With an unnormalized inverse, the prefactor is 1/V1/V.

The matching mesh energy has three equivalent forms:

Emesh=12∑iqiϕmesh(ri)=12∑gQgbg=12V∑k∈KKlr(k)B(k)∣A(k)∣2.E_{\mathrm{mesh}} =\frac12\sum_iq_i\phi_{\mathrm{mesh}}(\mathbf r_i) =\frac12\sum_g Q_gb_g =\frac{1}{2V}\sum_{\mathbf k\in\mathcal K} K_{\mathrm{lr}}(\mathbf k)B(\mathbf k)|A(\mathbf k)|^2.

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

Fimesh=−qi∑gbg∇riwg(ri).\mathbf F_i^{\mathrm{mesh}}=-q_i\sum_g b_g\nabla_{\mathbf r_i}w_g(\mathbf r_i).

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 hh with origin zero, its DFT contains aliases of the form

A(k)=∑n∈Z3T ⁣(k+2πhn)S ⁣(k+2πhn).A(\mathbf k)=\sum_{\mathbf n\in\mathbb Z^3} T\!\left(\mathbf k+\frac{2\pi}{h}\mathbf n\right) S\!\left(\mathbf k+\frac{2\pi}{h}\mathbf n\right).

Dividing by the base-mode T(k)T(\mathbf k) does not separate those folded terms. It also cannot recover omitted modes, and small values of TT 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 1/∣T∣21/|T|^2.

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.