I do a lot of 2D discrete FFT in python using np.fft.fftshift(np.fft.fft2(y)), then throw away 90% or more of the array, keeping only the central low-frequency area.

I understand that there's .rfft2() for cases where the input is real.

I'm wondering if there are significantly faster ways than numpy's fft to do this, especially if I can specify the low frequency range of interest.

I have heard of FFTW (as pyFFTW) and its ability to choose the best algorithm for a given input, but don't know if there's any extra benefit available for a limited frequency ROI.

Example of full FT and my ROI:

enter image description here

enter image description here

  • 1
    $\begingroup$ See a discussion below on "pruned FFTs", where in only a subset of outputs are needed. The author of FFTW concedes that this procedure is not worth it unless you are throwing away at least 99% of your output. Your use case is close, but don't expect huge gains. fftw.org/pruned.html $\endgroup$
    – Charlie S
    Oct 20 at 14:12
  • $\begingroup$ @CharlieS I see. In my case the time spent learning how to implement pruned FFTs will be orders of magnitude larger than any time saved getting the job done with a faster algorithm. I have a hunch that this will turn out to be the best answer to my question, please feel free to post as such. $\endgroup$
    – uhoh
    Oct 20 at 23:47
  • $\begingroup$ @CharlieS though starting from your link and doing some more searching, I do see something called "chirped" or "zoomed" or Chirp Z-transform (1, 2, 3) which seems possibly helpful. My understanding so far (I'm still pre-coffee this morning) is that if you only want to go up to say 1/4 of the maximum frequency, you can use can filter/interpolate/smooth and then sub-sample... $\endgroup$
    – uhoh
    Oct 20 at 23:54
  • $\begingroup$ ... say by [::4, ::4] then apply the same DFT you'd planned on. Of course whether that actually saves computation or human time is an open question. Perhaps more complicated than that, for some techniques there seems to be a frequency shifting transform involved as well. $\endgroup$
    – uhoh
    Oct 21 at 0:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.