As I said, if you use the padding option in Matlab or Python’s fft functions, it is just zero padding and computing the same thing as the “manual” 2-line Julia padding code above.
But this is not something you want to do blindly because it changes the transform you are computing (much more than a trivial change in normalization).
I am not into the Mathematical definitions.
You have to define mathematically what transform you want. There are infinitely many ways to have DFT-like functions with N inputs and M outputs, such as zero-padding the input (if M > N) or doing some other sampling in the frequency domain (as in a “Zoom FFT”).
Typically, what people do corresponds to a discrete-time Fourier transform (DTFT) with some window function implied for the input and some sampling in frequency domain for the output, but the choices of windowing and frequency-sampling matter a lot (and determine what algorithms are applicable)!
You may not be “into” it, but not understanding what you are doing is a good way to get incorrect results.
I do understand it deeply. This is what I do.
I meant in the context of this thread I thought it is obvious that we’re talking about what’s people usually mean.
If you want it more rigorously, I’d define it by the DFT Matrix as this is what usually people mean when they says the case of N \to M .
I was under the impression FFT Libraries have optimized code path for those cases as well.
Since not every day we have a chance to ask an expert like you in the field I was wondering if there is something I miss in FFTW’s documentation about this.
Specifically I was almost sure that the “easy” case (Where M > N ) has a special treatment,
The DFT matrix is square (as in the Wikipedia article you linked). A non-square transform is not a DFT in any sense (regardless of normalization). I guess you mean a zero-padded DFT (i.e. the first N columns of an MxM DFT), but if that is what you want you need to say so. There are infinitely many possible non-square Fourier-like transforms and they can all be represented as matrices. e.g. a chirp-z transform is also a very common and useful choice.
Nope, not typically.
See my comments/links above. A pruned FFT is theoretically possible, but only becomes practically beneficial (for 1d transforms) when you zero pad by a lot (multiplying the length by a large factor, typically 100x or more), and if you are doing this probably a “Zoom FFT” is better for you anyway (but is a different beast because you have to specify the desired frequency sampling).
OK, In order to be exact I meant the matrix form of:
X \left[ k \right] = \sum_{n = 0}^{N - 1} x \left[ n \right] {e}^{-j 2 \pi \frac{k n}{M} }, \; k \in \left\{ 0, 1, 2, \ldots, M - 1 \right\}
OK, I was under the impression (With little knowledge about how it’s implemented) that it would be easy to tell the FFT algorithm how to “extrapolate” M - N zeros without actually having them in the array.
The MATLAB FFT implementation uses the FFTW library. With default
settings, FFTW is highly efficient for data lengths of the form
N = 2^a3^b5^c7^d11^e*13^f, where e + f = 0 or 1, and the rest
of the exponents are arbitrary.
So that’s what it does, finds the next N that satisfies that expression. I wonder if that statement is actually accurate!
As for how the zero-padding is actually accomplished (after having found an efficient length), for me it’s less about performance, and more about having a convenient interface. That’s why I enjoy having the padding length as part of the interface.
(BTW: Julia’s nextprod is 50 times faster than the Matlab function, naturally )
FWIW this (including 7 as well) is how DSP.nextfastfft is implemented (here). If there’s a better heuristic that would be a good place to make the improvement.
)