The trick to making the FFT work is factoring out a complex exponential from the sum over odd terms. For this to happen your function needs to be sampled across a uniform grid. Greengard refers to this property as "brittle" (cf [math.nyu.edu/faculty/greengar/shortcourse_fmm.pdf][1] ).

When your function is sampled over a nonuniform grid fast multipole methods or Barnes-Hut style algorithms can help.


  [1]: http://math.nyu.edu/faculty/greengar/shortcourse_fmm.pdf