The work of Perram et al. [39] was the first recognized method that reduced
the Ewald sum complexity without using approximation schemes.
In this method, Perram et al. utilized the linked-cell spatial decomposition technique
devised by Hockney and Eastwood [31]. It was shown that by properly dividing the potential
evaluation into a short-range interaction, which ordinarily grows as 
,
and a long-range interaction, that ordinarily grows as N, the Ewald sum can be performed with an overhead that grows as 
.
The argument is as follows.
Assume that the simulation box is spatially decomposed into 
sub-boxes.
Moreover, let 
be chosen such that the maximum term neglected in the real
sum is 
, where 
is some relative error constant.
Hence, 
is chosen such that 
.
Further, assume that 
and 
are the unit times to perform a unit force computation in
the direct (real) and reciprocal (Fourier) space respectively. Let 
denote the
time (on average) to compute the real-space sum and 
denote the time (on average) to evaluate the
reciprocal-space sum.
If 
is chosen large enough such that particle-interactions beyond one sub-box are neglected, i.e.
only interactions between particles within the nearest neighbor sub-boxes are considered,
then 
is proportional to the number of boxes
in the system times the average number of particles in each box and can be approximated by:
where 
is constant and 
.
Furthermore, from Eq.(16), 
is proportional to the number
of particles times the maximum number of reciprocal vectors 
, where K is an integer that
controls the range of reciprocal vectors, and is estimated by:
Note that 
and 
and 
are constants that depend on Ewald parameters
and the system dimensions.
The total time, therefore, for Ewald computation is 
. To minimize T, we treat
M as a variable and evaluate 
. Carrying out the derivative and solving
for M results in 
. Substituting in the above expression for T yields:
where 
are also constants.
The above equation shows that for 
, the overhead in computing the Ewald sum
grows as 
.
Fincham [25] offers another derivation to prove the above result.
In summary, the previous subsections offered an account of the traditional approaches to Ewald summation.
Among these methods, Perram's 
algorithm has probably the most useful
combination of speed and accuracy. Rycerz and Jacobs' approach is the least useful because it is system-dependent and requires extra experimentation to validate its use.
Most MD ``production'' codes that
perform Ewald summation use one (or more) of the approximation techniques
discussed in Sec.(3) to enhance their performance.