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)?
Convolution property of DFT
Started by ●June 29, 2010
Reply by ●June 29, 20102010-06-29
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
Reply by ●June 30, 20102010-06-30
On Jun 29, 12:26�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 = > > � � 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)?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
Reply by ●June 30, 20102010-06-30
On Jun 30, 9:53�am, Greg Heath <he...@alumni.brown.edu> wrote:> On Jun 29, 12:26�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 = > > > � � 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)? > > 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?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
Reply by ●June 30, 20102010-06-30
On Jun 30, 12:03�pm, robert bristow-johnson <r...@audioimagination.com> wrote:> On Jun 30, 9:53�am, Greg Heath <he...@alumni.brown.edu> wrote: > > > > > > > On Jun 29, 12:26�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 = > > > > � � 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)? > > > 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? > > 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?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