convolution product with FFT

boy · March 11th, 2006, 7:35 am

Hi all, I'm new to evaluating integral with FFT but one has suggested me to use FFT since my integral (jump diffusion of Andersen) is in convolution form. My understanding of it is that if I need to evaluate int{f(x+y)g(y)dy}, I do Y = [-100:100] ifft(fft(f(Y)) .* conj(fft(g(Y)))) Am I right?? What I don't see is how does x come into play? I tried to read Numerical Recipes, but no clue what's going on.. Thanks!- boy

CB · March 11th, 2006, 7:49 am

QuoteOriginally posted by: boyHi all, I'm new to evaluating integral with FFT but one has suggested me to use FFT since my integral (jump diffusion of Andersen) is in convolution form. My understanding of it is that if I need to evaluate int{f(x+y)g(y)dy}, I do Y = [-100:100] ifft(fft(f(Y)) .* conj(fft(g(Y)))) Am I right?? What I don't see is how does x come into play? I tried to read Numerical Recipes, but no clue what's going on.. Thanks!- boyWhat is jump diffusion of Anderson? Is English your first language?

figaro · March 11th, 2006, 11:41 am

Type "fourier transform" into google and look up the properties, that will explain how it works. I think there is a page on wikipedia with most relevant properties.Practically, you will find that FFT is very unstable for what you are trying to do and that you are much better off approximating the integral on the grid.

WannaBeDude · March 13th, 2006, 4:17 pm

figaro,why do you say that fft is very unstable for convolution ? thanks.

figaro · March 14th, 2006, 5:44 am

My comments are based on my attempts to do deconvolution rather than convolution, so this may not be 100% applicable.FFT methods depend on discretising the convolution integral to get a convolution of discrete sequences, which you then pass through the FFT. Original ref here. Very unstable in practice. Much better (although slower) to just do the Fourier integral numerically (as in, using numerical integration), or set the problem up on the grid and do the (de)convolution directly.Hope this helps.

ZmeiGorynych · March 14th, 2006, 4:57 pm

Well generally convolution smoothes, therefore deconvolution unsmoothes and is always likely to be an unstable business. In my experience, convolution via FFT works fine and is way faster than doing it directly (n^2 vs. n log n I think).

alac · March 15th, 2006, 3:17 pm

If , then . By computing the FFT and evaluating the element-wise product you end up with samples of the FFT of the desired function h(x). Finally, by computing the inverse FFT you obtain the samples of h(x). Now, those samples are correct as opposed to any grid method in the time domain. Notice also that the result of your integral is a function, and the FFT method returns samples of this function.

boy · March 24th, 2006, 3:11 am

Hi guys, I finally got it working.. dt = 0.1;xmin = -5;xmax = 5;hmin = -1;hmax = 1;x = [xmin: dt:xmax];h = [hmin: dt:hmax];y = xmin+hmin: dt:xmax+hmax;fbar = f(x);gbar = g(h);I = conv(fbar, gbar) * dt;I2 = real(ifft(fft(fbar, length(y)) .* (fft(gbar, length(y))))) * dt;With above, I equals to I2, which is excellent.. but someone told me I should do conj instead:I2 = real(ifft(fft(fbar, length(y)) .* conj((fft(gbar, length(y)))))) * dt;and then my convolution graph is shifted. What was the purpose behind conj?? I won't get the same result as conv then.... Thanks!!