Given a large input array x, let's say length N=2**16, I want the Fourier coefficients only for a small number of frequencies, lets say an interval of length [100: 200]. Is there a library that can do this efficiently? Current libraries I find do not have this functionality and compute the full Fourier transform, which is far more work than is necessary in my case. Of course I could implement my own fast Fourier transform algorithm, but something "off the shelf" would be ideal. As a benchmark I computed the fast Fourier transform using Scipy and then sliced to get the frequencies of interest y = scipy.fft.fft(x) z = y[100: 200] On my machine this takes 0.65 seconds. A more efficient way is to use the definition of the DFT and compute it only for the frequencies of interest z = np.zeros(100) index = 0 for k in range(100, 200): z[index] = np.sum(x * np.exp(-2j*np.pi*k*np.arange(N)/N)) index += 1 On my machine this takes 0.38 seconds. Presumably this can be improved far more, and I am wondering if this has already been done somewhere to save me the effort. Continue reading...
