Problem using the Fourier transform and convolution to compute an integral

536 Views Asked by At

I'm trying to write a subroutine (in Fortran) to compute integrals of the form $$I=\int_{-L}^{L} f(x)g(y-x) \:\mathrm{d}x, $$ using the convolution theorem and fast Fourier transforms. In my routine, I have discretized $f$ and $g$ uniformly on a domain $(-L,L]$. I then try to compute the integral via $$ I = \mathrm{ifft}(\:\mathrm{fft}(f(x))\cdot\mathrm{fft}(g(x))). $$ However, I cannot get my routine to give me the correct results. As a test, I try to compute $$\int_{-\pi}^{\pi}\mathrm{sin}(x)\mathrm{cos}(y-x)\:\mathrm{d}x, $$ which I believe should give me $\pi\; \mathrm{sin}(y)$. I discretize $x$ into $n$ points. Following the advice of some textbooks, I extend the arrays which contain my discretized functions, and pad them with zeros, so that the sin$(x)$ "signal" looks like: sin$(x)$

and the cos$(x)$ "signal" looks like: enter image description here

where the function has also been "wrapped around" as well as zero padded. These two signals are then multiplied together, then multiplied by the grid spacing, $2\pi/n$, and then inverse transformed. The result, (which should be the convolution) looks like this: enter image description here

My textbook tells me that part of the result is garbage, which should be discarded, leaving me with the convolution. Looking at the plot above, it looks like I should discard the last half of the signal. The first half of the signal resembles the $\pi$sin$(x)$ that I'm looking for, but it is not scaled correctly. How can I get the correct convolution? I've been stuck on this for some days now and would really appreciate any comments or tips. Thanks.

Edit : Update

I am now trying without the zeropadding. However I am still using "wrap-around" format for the second function. That is, the first half of the array contains the function at positive $x$, and the second half of the array contains the function at negative $x$. The result I get is a sin wave, but still not scaled correctly. In fact here is a plot of the error of my routine for different $n$: enter image description here

Clearly its crap.

Edit 2

By extending the arrays to include multiple periods of the signals - as suggested by @copper.hat - instead of zero padding, I am getting good results. My routine now accurately approximates the integral, giving me accuracy to within machine precision as desired : enter image description here