The KWIK Algorithm

While CFMM is a linear method, the authors consider it an expensive O(N) technique and believe that there will someday be a faster method. In 1996 Dombroski et al. [188] introduced the KWIK algorithm, which may become an alternative to the CFMM.

The KWIK algorithm begins by examining the Coulomb operator, which contains a singularity at the origin and exhibits very slowly decaying long range behaviour. It was thought that separating these two characteristics would allow easier approximation. Thus the separation into short- and long-range operators,
$$\begin{align}\frac{1}{r} \equiv \frac{f(r)}{r} + \frac{1-f(r)}{r} \end{align}$$
was introduced. The short-range operator should have only O(N) significant interactions. The long-range operator is transformed into Fourier Space where it decays rapidly, and interactions are calculated in O(N) work via summation over Fourier coefficients and particles.

A separator function f(r), which produces a rapidly decaying short-range function and a long-range function whose Fourier Transform decays rapidly (so that the summation required converges quickly) is desired. Dombroski tried several forms for the separator function [189] including $\exp(-\omega r)$, $\exp(-\omega r^{2})$, $\tanh(\omega r)$ and $\erfc(\omega r)$. The decay parameter $\omega$ was introduced so that the amount of short- to long-range work could be tuned. Of these functions only $\erfc(\omega r)$ decays Gaussianly and has a Fourier transform which decays Gaussianly.

In an attempt to find a more appropriate separator function, Lee et al. [190] defined the ultimate separator as the one which minimizes the decay in real and Fourier space. The solution is a rather complex function, expressed as either modified Bessel, Hermite or parabolic cylinder functions. This function decays asymptotically as $r^{-1/2} \exp(-r^{2}/2)$, slightly faster than the Gaussian decay of $\erfc(\omega r)$. For practical reasons however, the $\erfc(\omega r)$ separator is preferred over the Lee separator as the decay speed difference between the two is small and the error function is far simpler to implement and optimize [191].

The KWIK algorithm has shown promising behaviour for point charges, yet the extension to continuous charges is still under development. Problems exist in calculating the long range energy accurately; however, it should be stressed that KWIK is still a young algorithm, requiring much more research.