When I ask Matlab for a zero-padded FFT, does it (or FFTW) ever explicitly create a zero-padded input vector?

Question

If I have a length $N$ signal and ask Matlab for an $M$-point FFT, $M \gg N$, of course the computer has to allocate memory for $M$ output samples, but my question is if it ever has to allocate memory for $M$ input and fill it with the input vector along with zeros? Or are FFT algorithms capable of generating the $M$-point result without having to explicitly store the $M$-length padded input?

(Motivation I have a library that can automatically give me zero-padded data (or unpadded data), which I then perform FFTs on. Assume everything before the result of this library call has already happened, and we only care about what we do once those results (padded or unpadded) are available. If Matlab or FFTW don't need to explicitly allocate $M$-long zero-padded inputs to the FFT, then I'd be wasting memory by asking the library to zero-pad for me, and should just ask it for unpadded data.)

Answer 1

There is an FFT trick to perform a $2N$-point FFT on $2N$ real-only input samples using a single complex $N$-point FFT operation. But I've never heard of performing an $M$-point FFT on $N$ input samples without zero padding the input sequence out to length $M$. Ahmed, if you can develop a way to do that you would become famous and someone would write a song about you.

Answer 2

After reviewing the butterfly structure employed in FFT, it looks like explicit zero-padding or increasing the memory allocation at the input is required. For example, in zero-padding a N-point FFT to a M-point FFT, say N=6 and M=8. As shown in the FFT algorithm with the basic butterfly computation below.

We will need to explicitly zero-padded the sequence as shown in the figure. Despite x(6) and x(7) are just zeros (the zero-padded coefficients), their memory locations will eventually be used to hold X(3) and X(7) respectively, and they will become non-zero quickly after the first stage (assuming x(2) & x(3) are both non-zero). My assumption is, the output of the FFT overwrites the input though.

Answer 3

The first rule of optimization: check that your assumptions are correct. It is tempting to assume that «saving memory» or «reducing operations» will make code faster, but a smart compiler (or just-in-time engine) could do smart stuff (or silly stuff) that invalidates your assumption. Or you could be right, but the difference might make up for 0.1% of the total execution time.

Thus the second rule of optimization: don’t do it. Rather, write code that actually works, that is protected by tests and that is readable by others or yourself in 6 months. Avoid doing obviously stupid things for performance, but follow conventions and what makes sense for the language and functionality.

Only after the two first are checked does it make sense to «optimize».

Various FFT implementations may be «in-place» or «out-of-place» meaning that the input buffer either is or is not reused throughout the algorithm. If it is reused, then it logically needs to be allocated to the maximum of input size and output size. If it is not reused, then potentially a FFT algorithm could work on a 60-sample input to produce a 64-sample output to avoid a re-allocation/memcopy with the assumption that missing input samples are to be assumed to be zero.

When using the Matlab mex C interface, it seems that you have to allocate arrays on both input and output anyways (?). I don’t know if Mathworks use a similar API for their internal functions. If you check the FFTW API perhaps they have special previsions for «FFTs that are to be zero-padded»? If so, perhaps Matlab extend those, as the zero-padding parameter is exposed in the Matlab function.