# Using Fourier Transform to speed up calculation of forces following an inverse square law

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.

-
First hit on google: cs.montana.edu/courses/spring2005/580/papers/0906008.pdf –  Vít Tuček Apr 3 '13 at 17:15
This could be also a good starting point: en.wikipedia.org/wiki/… –  Vít Tuček Apr 3 '13 at 17:20

## 1 Answer

The FFT is an important part of the fast multipole method, which is probably what you would want to use.

-
NB. arxiv.org/abs/0911.4114 appears to describe a more manifestly Fourierish FMM. –  Steve Huntsman Apr 3 '13 at 17:15