Does convolution done via the FFT _undo_ computational gains when signal has zeros every other sample?

Question

Suppose we have filter $h[n]$, length $N$. If I use it to do convolution in the time domain, then there will be $N$ multiplications each time during the sliding. (Ignore border conditions for now). However if say $h[n]$ had zeros every other sample, then there would be half that number of multiplications, so ostensibly I save in computational load, since I have half the number of multiplies to do.

So then in conclusion the speed of convolution in the time domain is related to the number of zeros.

Now suppose I did this convolution via the multiplication in the frequency domain using the FFT instead. It seems that I would undo any gains I could have had, zeros or no zeros, because when we do it via the FFT method, it is agnostic to the actual values of the samples of the signal and filter.

Is this a correct assessment? If so, might there then be cases where a good old fashioned convolution in the time domain is in fact much faster than an FFT?

Answer 1

If you know ahead of time that your filter pulse response has zeroes in alternation, then you can use a different FFT routine to speed up the convolution. On the other hand, if you simply pass the filter input and the pulse response to a generic computational subroutine that will spit out the filter output given $x[n]$ and $h[n]$, then yes, the zeroes will be handled no differently than any other inputs and will not save any computation at all.

Example:
Suppose that the (FIR) filter pulse response is $\mathbf h = 1 \quad 0 \quad 1 \quad 0 \quad 1$. Then, the filter output is

$$y[n] = x[n] + x[n-2] + x[n-4]$$

and so the filter output is alternately the sum of three successive even-numbered inputs and the sum of three successive odd-numbered inputs. So, knowing that $\mathbf h$ has alternate zeroes, we could proceed as follows.

1. Create a filter $\hat{\mathbf h}$ by decimating $\mathbf h$ (or downsampling) by a factor of $2$. Thus, $\hat{\mathbf h} = 1 \quad 1 \quad 1$ in the example.
2. Decimate $\mathbf x$ to create two input streams $$\mathbf x_e = x[0]\quad x[2]\quad x[4] \quad \cdots ~~\text{and}~~ x_o = x[1]\quad x[3]\quad x[5] \quad \cdots$$
3. Apply $\hat{\mathbf h}$ to the two streams to get $\mathbf y_e$ and $\mathbf y_o$.
4. Recombine $\mathbf y_e$ and $\mathbf y_o$ to get $\mathbf y$.

If FFTs are used anywhere in doing the needed convolutions, note that the FFT of $\hat{\mathbf h}$ needs to be computed only once, and various tricks such as overlap-and-add etc will have to be applied separately to the two data streams. Note also that the FFTs can be shorter (though we have to do two of them), and a crude comparison says that $$2\left[\frac{N}{2}\log_2\left(\frac{N}{2}\right)\right] = N\log_2\left(\frac{N}{2}\right) < N\log_2 N.$$ More exact comparisons with actual numbers may reveal a different tradeoff.

Answer 2

Is this a correct assessment? If so, might there then be cases where a good old fashioned convolution in the time domain is in fact much faster than an FFT?

You're right. Convolution in the time domain with small N is always faster than FFT convolution. I researched this issue for Intel IPP library. I run calculation of convolution in 3 mode:

• auto - select the optimal algorithm automatically.
• direct - use direct algorithm
• FFT - use FFT-based algorithm implementation.

In “auto” mode IPP uses a convolution in the time domain for small N and a FFT convolution for large N. In table below: N - size of filter, M - size of data array. Data type was float32. Processor - Intel i5-2500.

+------+------+------+--------+------+  
|   M  |   N  |         time         |   
|      |      | auto | direct |  FFT |  
|------+------+------+--------+------|  
| 1024 |  15  |  6.2 |   6.2  |  8.4 |  
| 1024 |  65  |  9.9 |  10.2  | 10.2 |  
| 1024 | 319  | 24.5 |  28.8  | 25.1 |  
| 8192 |  15  | 48.4 |  48.1  | 62.0 |  
| 8192 |  65  | 60.5 |  77.8  | 60.8 |  
| 8192 | 319  | 82.2 | 257.   | 82.8 |  
+------+------+------+--------+------+  

So if N is small then use calculation in time domain. You can get an extra boost if your filter has some additional properties which you can use in time domain (symmetry, a lot of zeros, etc.).

EDIT

I wrote the experimental data above. There is a simple and well known theoretical explanation. The number of operations for time-domain convolution is O (M * N). A number of operations for FFT convolution is O ((M + N) * log (M + N)). It is easy to check that the FFT convolution better only for sufficiently large M, N. For IPP library, this boundary is located in the N ~ 50 for M=1024

EDIT 2

Add timing for time-domain convolution

Answer 3

If so, might there then be cases where a good old fashioned convolution in the time domain is in fact much faster than an FFT?

Yes. Direct convolution is always faster when N is small.

If you can halve the computation time for half zeros, then that changes the point at which N becomes "small", but the FFT method will always be faster for "large N" and slower for "small N", no matter how many zeros there are or other shortcuts you take, since the FFT takes O(N log N) (actually 8N log 2N?) time and the direct convolution takes O(N²) time (actually 2N² time, or in your case N² time?).

Here's a graph of number of operations vs N. The numbers are arbitrary, but they scale correctly:

So at N = 40, the FFT convolution is faster than the direct convolution, but the direct convolution with halved time because of zeros is faster than the FFT. At some N the FFT always wins, though.

It seems that I would undo any gains I could have had

It sounds like you're thinking that FFT halves the computation time. It doesn't. It does far better than halving. For a crude example, at N = 10000, yours takes something like 100,000,000 operations, while the original would take 200,000,000 operations, saving half the time. Meanwhile, the FFT takes something like 344,082 operations, orders of magnitude less.

At some N, the FFT will always become faster, but there are certainly cases where direct is faster.