Skip to main content
2 of 2
http -> https (the question was bumped anyway)
Martin Sleziak
  • 4.7k
  • 4
  • 35
  • 40

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.

dranxo
  • 817
  • 5
  • 13