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 ).
When your function is sampled over a nonuniform grid fast multipole methods or Barnes-Hut style algorithms can help.