1
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What a fantastic answer! So if the length of the data $x[n]$ is $M$, the length of $h[n]$ is $N$, and the length of $\hat{h}[n]$ is $Q$, then the length of $y_e$ and $y_o$ is $M/2 + Q - 1 = \frac{M + N - 1}{2}$ yes? Any caveats to the equality I wrote? $\endgroup$ – TheGrapeBeyond Aug 30 '13 at 15:35
  • $\begingroup$ Well, there may be edge effects that you need to account for and $Q-1$ might not equal $\frac{N-1}{2}$ as you have written. Also, if $M \gg N$, you might want to consider overlap-and-add or overlap-and-save instead of FFTs of length $M/2+Q-1$ or more. $\endgroup$ – Dilip Sarwate Aug 30 '13 at 19:18
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Sorry I am not understanding something. You say that sometimes "no FFT" is slower than time-domain conv for small N, but looking at your table this is never the case... can you please expand? Thanks. $\endgroup$ – TheGrapeBeyond Aug 29 '13 at 14:03
  • $\begingroup$ @TheGrapeBeyond IPP library in "no FFT" uses time-domain convolution only. I edited my answer to clarify. Thanks $\endgroup$ – SergV Aug 29 '13 at 14:34
  • $\begingroup$ Sergv, yes I see that, however it is never faster, yet you claim that time-domain is faster for small Ns. "noFFT" is never faster in your table, except for row4. $\endgroup$ – TheGrapeBeyond Aug 29 '13 at 14:35
  • $\begingroup$ @TheGrapeBeyond, I do not have another information now. I have data for "auto mode" and "no FFT" mode. "Auto mode" is clever algoritms. It uses time domain calculation for small N and FFT calculation for large N. So you see equal timing for both modes for small N. I can to run new tests with "time-domain" calculation but only tomorow $\endgroup$ – SergV Aug 29 '13 at 14:47
1
$\begingroup$

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(N2) time (actually 2N2 time, or in your case N2 time?).

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

enter image description here

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.

$\endgroup$
  • $\begingroup$ "It sounds like you're thinking that FFT halves the computation time." No no, what I mean is that the FFT is agnostic to whether or not you have 0s in your filter. If you have zeros every other sample in your filter, you just halved your convolution time. If however you chose to do it through FFT, it takes the same amount of time. $\endgroup$ – TheGrapeBeyond Aug 31 '13 at 15:45
  • $\begingroup$ @TheGrapeBeyond: Yes, but you understand that the FFT will still be far faster, right? $\endgroup$ – endolith Aug 31 '13 at 18:58
  • $\begingroup$ Let me ask this way: You have a filter of length $N$. Case(1): You perform the convolution via time-domain, and the convolution via FFT. FFT wins. Case(2). You take advantage of the fact that the filter has zeros every other sample. You perform the conv as before, in the half the time, the FFT takes the same amount of time as before. Now, does their exist an $N$, such that the conv wins out over the FFT in the case(2)? That is the question. I think the answer based on what you said is yes, if $N$ is small enough, although I am not sure how you would quantify that. $\endgroup$ – TheGrapeBeyond Aug 31 '13 at 19:08
  • $\begingroup$ @TheGrapeBeyond: Yes, there is always an N above which the FFT is faster. By halving the time of the direct convolution, you're moving that point upward to a higher N, but it still exists. In other words, for case 1, maybe at N=500 the direct is faster, and at N=501, the FFT is faster. For case 2, maybe direct is faster up to N=800, but then FFT gets faster at N=801. Those are just made up numbers, but you get it? $\endgroup$ – endolith Aug 31 '13 at 19:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.