I want to compute the $K$ sums: $$ f_k = \sum_{j=0}^{N-1} a_j e^{i \frac{2 \pi j k}{K}} $$ for $f_0,f_1,...f_{K-1}$. Now if $K = N$, then this is the usual DFT, but in my application $K \ne N$, as I have a different number of coefficients $a_j$ than grid points $k$. In other words the DFT matrix here is not square.

Now if $K > N$ it seems that I can expand the sum to $$ f_k = \sum_{j=0}^{K-1} a_j e^{i \frac{2 \pi j k}{K}} $$ and set $a_N,...,a_{K-1} = 0$ (i.e., zero-pad the coefficients $a_j$ to make the DFT matrix square). But this is inefficient since it will add unnecessary operations to the FFT by adding zero terms to the sums.

Also, if $N > K$ I don't see an easy way to turn this into a standard DFT problem. Does anyone know of any tricks?

  • $\begingroup$ Possible duplicate. Check this link: math.stackexchange.com/questions/77118/non-power-of-2-ffts $\endgroup$ – onetimething Aug 10 '17 at 0:22
  • $\begingroup$ The $O(n\log(n))$ complexity of the FFT often makes the 0 padding worth while in comparison with direct summation. $\endgroup$ – Brian Borchers Aug 10 '17 at 0:23
  • $\begingroup$ If $N>K$ can't you just compute the $N$ DFT modes and throw away all but the first $K$? $\endgroup$ – Rahul Aug 10 '17 at 0:29

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.