1

I have an equation that can be expressed in a somewhat Fourier transform-like expression. (I can't find a way to write in latex format so I am trying to write in c code format). For a function f in a grid of M points, I evaluate a function on a kind of different grid. So my expression looks like

F[n] = np.sum( np.exp(-2j * np.pi * k * n / N) * f[k])

with k = np.linspace(0, M-1, M), i.e. k ranges from 0 to M with M < N. Because of this, if I want to evaluate the above expression in a Fourier-transformed way, I rewrite the above expression as

F[n] = np.sum( np.exp(-2j * np.pi * (k*M/N) * n / M) * f[k])

So now as you can see, my effective index is now (kM/N) which is no longer an integer. I can do a manual Fourier transform by writing my own code for each n index.

For now, I am creating an NxM matrix containing the exponential term and multiplying this with my vector (M elements) to get another vector of N elements. The current implementation looks more like,

F = np.exp(-2j * np.pi * np.outer(n, k) / N) @ f[k]

with k = np.linspace(0, M-1, M) and n = np.linspace(0, N-1, N). This gets very expensive (both computation time and from memory perspective) for very large matrices and so I want to use the existing FFT functionality in Numpy or Scipy and do not see a way to input my manual frequency axis as an argument inside the np.fft.fft function. Also, I am unclear about how to convert this into an FFT kind of problem. Another question I have is how do I perform FFT for a single frequency input point using np.fft.fft (or from Scipy)?

Md Elious Ali Mondal
  • 11
  • 3
  • That sounds like a [Goertzel filter](https://stackoverflow.com/questions/13499852/scipy-fourier-transform-of-a-few-selected-frequencies). – Nick ODell Aug 18 '23 at 18:04
  • 2
    The FFT is a fast algorithm for computing the DFT. You can evaluate the DFT for one frequency, and you could even evaluate that summation for a non-integer frequency. But the FFT is fast because it computes all the frequencies at the same time, you cannot get that time saving if you compute a single frequency. So "how do I perform FFT for a single frequency input point" makes no sense -- you want to compute the DFT, and you cannot use the FFT algorithm for that unless you compute all frequencies at once and discard the ones you don't need. – Cris Luengo Aug 18 '23 at 19:01
  • 1
    @NickODell, Goertzel filter works good on only specific frequencies which is the case of integer k and if you look at my expression, I specifically need my k values to be a specific non-integer. Thanks for the suggestion. I will update in case I find something new – Md Elious Ali Mondal Aug 18 '23 at 19:53
  • @CrisLuengo thanks for pointing this out, I rewrote my expressions in a code format to better express it. As you can read now, I am looking for something like the Goertzel filter DFT at a single frequency (not an actual FFT for a single frequency) or an FFT where the range of the two indices is different. Let me know if the question is better readable now and whether you have some suggestions to use FFT to compute the above expression instead of explicitly making a NxM matrix – Md Elious Ali Mondal Aug 18 '23 at 19:56

0 Answers0