Fast Fourier Transform of a zero vector

This is a short post about FFT of zero vectors and as a result show why FFTW does not check if the argument is a zero vector.

I could argue that zero vectors are a very rare occurance. Now, taking the Fourier Transform of the zero vector is an even more rare occurance, but actually not really. For instance, 2d linear convolution, which is used everywhere, requires zero padding and therefore FFT of zero vectors. Alot of them.

If we implement 2d FFT using the row-column method, we would perform many unnecessary FFT of zero vectors, which are themselves just zero vectors. So in these rows and columns we could simply skip the calculations altogether. But what about making fft better by wrapping it in a function checking if the argument is zero. If we check the argument if it is a zero vector and return zeros must be faster than to calculate the FFT, right? How much would we gain if we do this?

My first version looks like this:

function res = fftzero1(a)
if all(a==0*a) %the test
    res = 0*a %return zero vector
    return;
else
    res = fft(a); %otherwise we just calculate the fft
end

If we run this code a couple of times

n = 2^13; 
B = zeros(n,1);  
A = zeros(n,1); 
tic; for i=1:n; B = fftzero1(A); end; toc

This version takes 0.38 s for a zero vector and 0.76 s for a non-zero vector on a quad core Intel Sandy Bridge i5-2500K 3.3GHz.
Compared to only performing FFT of the vector without tests, which takes 0.47. So, clearly this wrapper isn’t providing us with much speedup for the zero case, but more importantly, the test introduce too much overhead for the random FFT call. So, I will try to minimize this overhead.

Let’s try to compare the argument with a zero vector:

function res = fftzero2(a)
if all(a == zeros(size(a)))
    res = a*0;
    return;
else
    res = fft(a);
end

This speeds up the code marginally, but still an improvement.
From 0.38 to 0.33 s (zero argument)
0.67-0.71 s (for non-zero vectors, so no difference from before)

The next speedup is very obvious when you think about it, we already know a is a zero vector, so why don’t we just return it and avoid allocating memory?

function res = fftzero3(a)
if all(a == zeros(size(a)))
    res = a;
    return;
else
    res = fft(a);
end

The code now takes 0.26 s for the zero vector, 0.65 s for random vectors.

We could use in-place variables:

function a = fftzero4(a)
if all(a == zeros(size(a)) )
    return;
else
    a = fft(a);
end

This takes 0.6 s for a random vector and 0.15 s for zero vector compared to 0.4 s for a random vector and 0.47 s for a zero vector by simply using FFT directly.

We sped up the zero vector test by 2.5 times and the random vector FFT by 1.26. The random vector FFT is still 1.5 times slower than the ordinary call to FFT.

There are several cases where FFT of a vector is very simple, for instance a vector of ones is simply zeros with it’s DC component being n, the size of the vector.
The best way to deal with zero vectors is to just handle them separately, because of the overhead in the calls.