# FFT with nonsquare matrix

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?

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