Suppose I have $n$ electric point charges in, say, two dimensions. Is there any algorithm (and I have a hunch that it might be related to the Fourier transform) to compute the net forces that act on each point charge in less than $O(n^2)$, preferably something like $O(n \log n)$? Thanks!


An approximation might be good enough for my use case.



Using Fourier Transform to speed up calculation of forces following an inverse square law
The FFT is an important part of the [fast multipole method](http://en.wikipedia.org/wiki/Fast_multipole_method), which is probably what you would want to use.


