# Convolution property of DFT

Started by June 29, 2010
```Hi, I'm trying fast convolution property but there seems to be some mistake
(with the answer).

Here is the Matlab code for it,

clear all; clc;

% Test Vector Convolution

a = [1 2 3 4 5];
b = [10 20 30 40 50];
c= conv(a,b)
A = [1 2 3 4 5 zeros(1,5)];
B = [10 20 30 40 50 zeros(1,5)];
d= ifft(fft(A) .* fft(B))
c - d(1:9)

The results are:

c =

10    40   100   200   350   440   460   400   250

d =

10.0000   40.0000  100.0000  200.0000  350.0000  440.0000  460.0000
400.0000  250.0000    0.0000

ans =  (for the difference b/w the two)

1.0e-012 *

-0.0906   -0.0497   -0.0284   -0.0284  0  0.1137  0  0  0

Shouldn't the result be smaller than eps (2.2204e-016)?

```
```On 6/29/10 12:26 PM, third_person wrote:
> Hi, I'm trying fast convolution property but there seems to be some mistake
> (with the answer).
>
> Here is the Matlab code for it,
>
> clear all; clc;
>
> % Test Vector Convolution
>
> a = [1 2 3 4 5];
> b = [10 20 30 40 50];
> c= conv(a,b)
> A = [1 2 3 4 5 zeros(1,5)];
> B = [10 20 30 40 50 zeros(1,5)];
> d= ifft(fft(A) .* fft(B))
> c - d(1:9)
>
> The results are:
>
> c =
>
>     10    40   100   200   350   440   460   400   250
>
> d =
>
>    10.0000   40.0000  100.0000  200.0000  350.0000  440.0000  460.0000
> 400.0000  250.0000    0.0000
>
> ans =  (for the difference b/w the two)
>
>   1.0e-012 *
>
>    -0.0906   -0.0497   -0.0284   -0.0284  0  0.1137  0  0  0
>
>
> Shouldn't the result be smaller than eps (2.2204e-016)?
>

Why do you think it should smaller than eps?  Do you think fft and ifft
have no roundoff?

I don't know what the actual roundoff should be but a difference of
1e-13 seems fairly reasonable.

Ray

```
```On Jun 29, 12:26&#4294967295;pm, "third_person"
<third_person@n_o_s_p_a_m.ymail.com> wrote:
> Hi, I'm trying fast convolution property but
> there seems to be some mistake
> (with the answer).
>
> Here is the Matlab code for it,
>
> clear all; clc;
>
> % Test Vector Convolution
>
> a = [1 2 3 4 5];
> b = [10 20 30 40 50];
> c= conv(a,b)
> A = [1 2 3 4 5 zeros(1,5)];
> B = [10 20 30 40 50 zeros(1,5)];
> d= ifft(fft(A) .* fft(B))
> c - d(1:9)
>
> The results are:
>
> c =
>
> &#4294967295; &#4294967295; 10 &#4294967295; &#4294967295;40 &#4294967295; 100 &#4294967295; 200 &#4294967295; 350 &#4294967295; 440 &#4294967295; 460 &#4294967295; 400 &#4294967295; 250
>
> d =
>
> &#4294967295; &#4294967295;10.0000 &#4294967295; 40.0000 &#4294967295;100.0000 &#4294967295;200.0000 &#4294967295;350.0000 &#4294967295;440.0000 &#4294967295;460.0000
> 400.0000 &#4294967295;250.0000 &#4294967295; &#4294967295;0.0000
>
> ans = &#4294967295;(for the difference b/w the two)
>
> &#4294967295; 1.0e-012 *
>
> &#4294967295; &#4294967295;-0.0906 &#4294967295; -0.0497 &#4294967295; -0.0284 &#4294967295; -0.0284 &#4294967295;0 &#4294967295;0.1137 &#4294967295;0 &#4294967295;0 &#4294967295;0
>
> Shouldn't the result be smaller than eps (2.2204e-016)?

Typically,
1. A and B are zeropadded to length(A)+length(B)-1
2. If A an B are real, d = real(ifft(fft(A) .* fft(B))
is used because ifft is notorious for creating
spurious imaginary roundoff error

However, the results I obtained below surprised me
(Note the change in notation)

clear all, clc

a = [1 2 3 4 5]';
b = [10 20 30 40 50]';
c= conv(a,b) ;
A = [1 2 3 4 5 zeros(1,4)]';
B = [10 20 30 40 50 zeros(1,4)]';
C = ifft(fft(A) .* fft(B));
D = [c C(1:9)]

% D =
%
%   10         10
%   40         40 +1.2632e-014i
%  100        100 -6.3159e-015i
%  200        200
%  350        350 -6.3159e-015i
%  440        440 -7.7816e-015i
%  460        460
%  400        400 -6.3159e-015i
%  250        250 +1.4097e-014i

A = [1 2 3 4 5 zeros(1,5)]';
B = [10 20 30 40 50 zeros(1,5)]';
C = ifft(fft(A) .* fft(B));
D = [c C(1:9)]

% D =
%
%    10           10
%    40           40
%   100          100
%   200          200
%   350          350
%   440          440
%   460          460
%   400          400
%   250          250

I can't explain it. Can someone else?

Greg
```
```On Jun 30, 9:53&#4294967295;am, Greg Heath <he...@alumni.brown.edu> wrote:
> On Jun 29, 12:26&#4294967295;pm, "third_person"
>
>
>
> <third_person@n_o_s_p_a_m.ymail.com> wrote:
> > Hi, I'm trying fast convolution property but
> > there seems to be some mistake
> > (with the answer).
>
> > Here is the Matlab code for it,
>
> > clear all; clc;
>
> > % Test Vector Convolution
>
> > a = [1 2 3 4 5];
> > b = [10 20 30 40 50];
> > c= conv(a,b)
> > A = [1 2 3 4 5 zeros(1,5)];
> > B = [10 20 30 40 50 zeros(1,5)];
> > d= ifft(fft(A) .* fft(B))
> > c - d(1:9)
>
> > The results are:
>
> > c =
>
> > &#4294967295; &#4294967295; 10 &#4294967295; &#4294967295;40 &#4294967295; 100 &#4294967295; 200 &#4294967295; 350 &#4294967295; 440 &#4294967295; 460 &#4294967295; 400 &#4294967295; 250
>
> > d =
>
> > &#4294967295; &#4294967295;10.0000 &#4294967295; 40.0000 &#4294967295;100.0000 &#4294967295;200.0000 &#4294967295;350.0000 &#4294967295;440.0000 &#4294967295;460.0000
> > 400.0000 &#4294967295;250.0000 &#4294967295; &#4294967295;0.0000
>
> > ans = &#4294967295;(for the difference b/w the two)
>
> > &#4294967295; 1.0e-012 *
>
> > &#4294967295; &#4294967295;-0.0906 &#4294967295; -0.0497 &#4294967295; -0.0284 &#4294967295; -0.0284 &#4294967295;0 &#4294967295;0.1137 &#4294967295;0 &#4294967295;0 &#4294967295;0
>
> > Shouldn't the result be smaller than eps (2.2204e-016)?
>
> Typically,
> 1. A and B are zeropadded to length(A)+length(B)-1
> 2. If A an B are real, d = real(ifft(fft(A) .* fft(B))
> is used because ifft is notorious for creating
> spurious imaginary roundoff error
>
> However, the results I obtained below surprised me
> (Note the change in notation)
>
> clear all, clc
>
> a = [1 2 3 4 5]';
> b = [10 20 30 40 50]';
> c= conv(a,b) ;
> A = [1 2 3 4 5 zeros(1,4)]';
> B = [10 20 30 40 50 zeros(1,4)]';
> C = ifft(fft(A) .* fft(B));
> D = [c C(1:9)]
>
> % D =
> %
> % &#4294967295; 10 &#4294967295; &#4294967295; &#4294967295; &#4294967295; 10
> % &#4294967295; 40 &#4294967295; &#4294967295; &#4294967295; &#4294967295; 40 +1.2632e-014i
> % &#4294967295;100 &#4294967295; &#4294967295; &#4294967295; &#4294967295;100 -6.3159e-015i
> % &#4294967295;200 &#4294967295; &#4294967295; &#4294967295; &#4294967295;200
> % &#4294967295;350 &#4294967295; &#4294967295; &#4294967295; &#4294967295;350 -6.3159e-015i
> % &#4294967295;440 &#4294967295; &#4294967295; &#4294967295; &#4294967295;440 -7.7816e-015i
> % &#4294967295;460 &#4294967295; &#4294967295; &#4294967295; &#4294967295;460
> % &#4294967295;400 &#4294967295; &#4294967295; &#4294967295; &#4294967295;400 -6.3159e-015i
> % &#4294967295;250 &#4294967295; &#4294967295; &#4294967295; &#4294967295;250 +1.4097e-014i
>
> A = [1 2 3 4 5 zeros(1,5)]';
> B = [10 20 30 40 50 zeros(1,5)]';
> C = ifft(fft(A) .* fft(B));
> D = [c C(1:9)]
>
> % D =
> %
> % &#4294967295; &#4294967295;10 &#4294967295; &#4294967295; &#4294967295; &#4294967295; &#4294967295; 10
> % &#4294967295; &#4294967295;40 &#4294967295; &#4294967295; &#4294967295; &#4294967295; &#4294967295; 40
> % &#4294967295; 100 &#4294967295; &#4294967295; &#4294967295; &#4294967295; &#4294967295;100
> % &#4294967295; 200 &#4294967295; &#4294967295; &#4294967295; &#4294967295; &#4294967295;200
> % &#4294967295; 350 &#4294967295; &#4294967295; &#4294967295; &#4294967295; &#4294967295;350
> % &#4294967295; 440 &#4294967295; &#4294967295; &#4294967295; &#4294967295; &#4294967295;440
> % &#4294967295; 460 &#4294967295; &#4294967295; &#4294967295; &#4294967295; &#4294967295;460
> % &#4294967295; 400 &#4294967295; &#4294967295; &#4294967295; &#4294967295; &#4294967295;400
> % &#4294967295; 250 &#4294967295; &#4294967295; &#4294967295; &#4294967295; &#4294967295;250
>
> I can't explain it. Can someone else?

i don't understand what's troubling you, Greg.  is it the extremely
tiny imaginary values that result (presumably from roundoff) when N=9
that don't when N=10?

r b-j

```
```On Jun 30, 12:03&#4294967295;pm, robert bristow-johnson
<r...@audioimagination.com> wrote:
> On Jun 30, 9:53&#4294967295;am, Greg Heath <he...@alumni.brown.edu> wrote:
>
>
>
>
>
> > On Jun 29, 12:26&#4294967295;pm, "third_person"
>
> > <third_person@n_o_s_p_a_m.ymail.com> wrote:
> > > Hi, I'm trying fast convolution property but
> > > there seems to be some mistake
> > > (with the answer).
>
> > > Here is the Matlab code for it,
>
> > > clear all; clc;
>
> > > % Test Vector Convolution
>
> > > a = [1 2 3 4 5];
> > > b = [10 20 30 40 50];
> > > c= conv(a,b)
> > > A = [1 2 3 4 5 zeros(1,5)];
> > > B = [10 20 30 40 50 zeros(1,5)];
> > > d= ifft(fft(A) .* fft(B))
> > > c - d(1:9)
>
> > > The results are:
>
> > > c =
>
> > > &#4294967295; &#4294967295; 10 &#4294967295; &#4294967295;40 &#4294967295; 100 &#4294967295; 200 &#4294967295; 350 &#4294967295; 440 &#4294967295; 460 &#4294967295; 400 &#4294967295; 250
>
> > > d =
>
> > > &#4294967295; &#4294967295;10.0000 &#4294967295; 40.0000 &#4294967295;100.0000 &#4294967295;200.0000 &#4294967295;350.0000 &#4294967295;440.0000 &#4294967295;460.0000
> > > 400.0000 &#4294967295;250.0000 &#4294967295; &#4294967295;0.0000
>
> > > ans = &#4294967295;(for the difference b/w the two)
>
> > > &#4294967295; 1.0e-012 *
>
> > > &#4294967295; &#4294967295;-0.0906 &#4294967295; -0.0497 &#4294967295; -0.0284 &#4294967295; -0.0284 &#4294967295;0 &#4294967295;0.1137 &#4294967295;0 &#4294967295;0 &#4294967295;0
>
> > > Shouldn't the result be smaller than eps (2.2204e-016)?
>
> > Typically,
> > 1. A and B are zeropadded to length(A)+length(B)-1
> > 2. If A an B are real, d = real(ifft(fft(A) .* fft(B))
> > is used because ifft is notorious for creating
> > spurious imaginary roundoff error
>
> > However, the results I obtained below surprised me
> > (Note the change in notation)
>
> > clear all, clc
>
> > a = [1 2 3 4 5]';
> > b = [10 20 30 40 50]';
> > c= conv(a,b) ;
> > A = [1 2 3 4 5 zeros(1,4)]';
> > B = [10 20 30 40 50 zeros(1,4)]';
> > C = ifft(fft(A) .* fft(B));
> > D = [c C(1:9)]
>
> > % D =
> > %
> > % &#4294967295; 10 &#4294967295; &#4294967295; &#4294967295; &#4294967295; 10
> > % &#4294967295; 40 &#4294967295; &#4294967295; &#4294967295; &#4294967295; 40 +1.2632e-014i
> > % &#4294967295;100 &#4294967295; &#4294967295; &#4294967295; &#4294967295;100 -6.3159e-015i
> > % &#4294967295;200 &#4294967295; &#4294967295; &#4294967295; &#4294967295;200
> > % &#4294967295;350 &#4294967295; &#4294967295; &#4294967295; &#4294967295;350 -6.3159e-015i
> > % &#4294967295;440 &#4294967295; &#4294967295; &#4294967295; &#4294967295;440 -7.7816e-015i
> > % &#4294967295;460 &#4294967295; &#4294967295; &#4294967295; &#4294967295;460
> > % &#4294967295;400 &#4294967295; &#4294967295; &#4294967295; &#4294967295;400 -6.3159e-015i
> > % &#4294967295;250 &#4294967295; &#4294967295; &#4294967295; &#4294967295;250 +1.4097e-014i
>
> > A = [1 2 3 4 5 zeros(1,5)]';
> > B = [10 20 30 40 50 zeros(1,5)]';
> > C = ifft(fft(A) .* fft(B));
> > D = [c C(1:9)]
>
> > % D =
> > %
> > % &#4294967295; &#4294967295;10 &#4294967295; &#4294967295; &#4294967295; &#4294967295; &#4294967295; 10
> > % &#4294967295; &#4294967295;40 &#4294967295; &#4294967295; &#4294967295; &#4294967295; &#4294967295; 40
> > % &#4294967295; 100 &#4294967295; &#4294967295; &#4294967295; &#4294967295; &#4294967295;100
> > % &#4294967295; 200 &#4294967295; &#4294967295; &#4294967295; &#4294967295; &#4294967295;200
> > % &#4294967295; 350 &#4294967295; &#4294967295; &#4294967295; &#4294967295; &#4294967295;350
> > % &#4294967295; 440 &#4294967295; &#4294967295; &#4294967295; &#4294967295; &#4294967295;440
> > % &#4294967295; 460 &#4294967295; &#4294967295; &#4294967295; &#4294967295; &#4294967295;460
> > % &#4294967295; 400 &#4294967295; &#4294967295; &#4294967295; &#4294967295; &#4294967295;400
> > % &#4294967295; 250 &#4294967295; &#4294967295; &#4294967295; &#4294967295; &#4294967295;250
>
> > I can't explain it. Can someone else?
>
> i don't understand what's troubling you, Greg. &#4294967295;is it the extremely
> tiny imaginary values that result (presumably from roundoff) when
> N=9 that don't when N=10?

I usually get imaginary valued roundoff when I use
ifft and the result should be real. I was intrigued
that, in contrast, the OP got purely real roundoff.

Then I noticed that he used one more zero than necessary
in the zeropadding. So, I removed the extra zero and
got purely imaginary roundoff.

Satisfied that my understanding was validated, I put
the extra zero back in to see if that was the cause of
the real valued roundoff...

Much to my surprise, my calculation resulted in no
roundoff error.

I find this puzzling, even intriguing, but certainly
not troublesome.

Greg
```