IFFT taking orders of magnitude more than FFT

Question

I'm trying to resample a 1-D signal using an FFT method (basically, the one from scipy.signal). However, the code is taking forever to run, even though my input signal is a power of two in length. After looking at profiling, I found the root of the problem.

Basically, this method takes an FFT, then removes part of the fourier spectrum, then takes an IFFT to bring it back to the time domain at a lower sampling rate.

The problem is that that the IFFT is taking far longer to run than the FFT:

ncalls tottime percall cumtime percall filename:lineno(function) 1 6263.996 6263.996 6263.996 6263.996 basic.py:272(ifft) 1 1.076 1.076 1.076 1.076 basic.py:169(fft)

I assume that this has something to do with the amount of fourier points remaining after the cutoff. That said, this is an incredible slowdown so I want to make sure that:

A. This behavior is semi-reasonable and isn't definitely a bug. B. What could I do to avoid this problem and still downsample effectively.

Right now I can pad my input signal to a power of two in order to make the FFT run really quickly, but not sure how to do the same kind of thing for the reverse operation. I didn't even realize that this was an issue for IFFTs :P

What is the number points in the IFFT? If it is, for example, a prime number, it will take a long time. FFT and IFFT use the same algorithm. — Warren Weckesser
Yeah, I think that's the problem. My original length is 13648384, which has several factors but the first couple are [1, 2, 4, 8, 16, 19, 23, 32]. On the other hand, I'm sampling from 22050Hz to 1200Hz, so the new length would be 742769 with only three factors: [1, 151, 4919]. So I guess the problem is that the second length has very few factors, but I'm not sure how to solve this without messing up the sampling rate conversion... — choldgraf
There are FFT algos that are much better with this than the one numpy can ship (license stuff). So you could try FFTW for which python wrappers exist. — seberg

hotpaw2 hotpaw2 · Accepted Answer · 2014-05-18T00:15:10

If your IFFT's length is different from that of the FFT, and the length of the IFFT isn't composed of only very small prime factors (2,3,etc.), then the efficiency can drop off significantly.

Thus, this method of resampling is only efficient if the two sample rates are different by ratios with small prime factors, such as 2, 3 and 7 (hint).

IFFT taking orders of magnitude more than FFT

1 Answers