FFT for convolution

I am the actuary for a reinsurance company in Bermuda. I have come across a
problem that would be solved faster using the FFT. all i need to use it for
is convolution. For instance does anyone have a code that would convolute
(.26274,.21074,.15547,.11472)*(.26274,.21074,.15547,.11472) using the FFT?
I would actually be convoluting 2^13 or 8192 numbers in each vector instead
of 4. I just want to get the jist of it for now though. Any help would be
greatly appreciated.  

"roachekilla" <david.roache@arielre.com> wrote in 
news:18qdnfKXHJ9NiDPYnZ2dnUVZ_uiknZ2d@giganews.com:

> I just want to get the jist of it for now though. Any help would be
> greatly appreciated.  

The jist of it is to take the ffts of both vectors, do an element-by-
element multiplication of the two result vectors (which might very well be 
complex), and take the ifft to get your result.

-- 
Scott
Reverse name to reply

Scott Seidman wrote:
> "roachekilla" <david.roache@arielre.com> wrote in
> news:18qdnfKXHJ9NiDPYnZ2dnUVZ_uiknZ2d@giganews.com:
>
> > I just want to get the jist of it for now though. Any help would be
> > greatly appreciated.
>
> The jist of it is to take the ffts of both vectors, do an element-by-
> element multiplication of the two result vectors (which might very well be
> complex), and take the ifft to get your result.
>
> --
> Scott
> Reverse name to reply

One more step: the FFT-multiplication method actually performs circular
convolution. If you want "regular" convolution, you need to zero-pad
the two input vectors x[n] and h[n] so that their new lengths are equal
to length(x[n]) + length(h[n]) - 1. With the zero-padding in place, the
circular convolution is equivalent to "regular" convolution.

http://cnx.org/content/m10963/latest/

Jason

cincydsp@gmail.com wrote in
news:1169043061.596898.125620@11g2000cwr.googlegroups.com: 

> 
> Scott Seidman wrote:
>> "roachekilla" <david.roache@arielre.com> wrote in
>> news:18qdnfKXHJ9NiDPYnZ2dnUVZ_uiknZ2d@giganews.com:
>>
>> > I just want to get the jist of it for now though. Any help would be
>> > greatly appreciated.
>>
>> The jist of it is to take the ffts of both vectors, do an element-by-
>> element multiplication of the two result vectors (which might very
>> well be complex), and take the ifft to get your result.
>>
>> --
>> Scott
>> Reverse name to reply
> 
> One more step: the FFT-multiplication method actually performs
> circular convolution. If you want "regular" convolution, you need to
> zero-pad the two input vectors x[n] and h[n] so that their new lengths
> are equal to length(x[n]) + length(h[n]) - 1. With the zero-padding in
> place, the circular convolution is equivalent to "regular"
> convolution. 
> 
> http://cnx.org/content/m10963/latest/
> 
> Jason
> 
> 

Absolutely true.  I just get used to ignoring the first and last n/2 
points when I'm convolving.

-- 
Scott
Reverse name to reply

Scott Seidman wrote:
> "roachekilla" <david.roache@arielre.com> wrote in
> news:18qdnfKXHJ9NiDPYnZ2dnUVZ_uiknZ2d@giganews.com:
>
> > I just want to get the jist of it for now though. Any help would be
> > greatly appreciated.
>
> The jist of it is to take the ffts of both vectors,

I think you have to flip one vector first

"steve" <bungalow_steve@yahoo.com> wrote in news:1169066600.516870.176540
@v45g2000cwv.googlegroups.com:

> 
> Scott Seidman wrote:
>> "roachekilla" <david.roache@arielre.com> wrote in
>> news:18qdnfKXHJ9NiDPYnZ2dnUVZ_uiknZ2d@giganews.com:
>>
>> > I just want to get the jist of it for now though. Any help would be
>> > greatly appreciated.
>>
>> The jist of it is to take the ffts of both vectors,
> 
> I think you have to flip one vector first
> 
> 

Nope

-- 
Scott
Reverse name to reply

Scott Seidman wrote:
> "steve" <bungalow_steve@yahoo.com> wrote in news:1169066600.516870.176540
> @v45g2000cwv.googlegroups.com:
>
> >
> > Scott Seidman wrote:
> >> "roachekilla" <david.roache@arielre.com> wrote in
> >> news:18qdnfKXHJ9NiDPYnZ2dnUVZ_uiknZ2d@giganews.com:
> >>
> >> > I just want to get the jist of it for now though. Any help would be
> >> > greatly appreciated.
> >>
> >> The jist of it is to take the ffts of both vectors,
> >
> > I think you have to flip one vector first
> >
> > 
> 
> Nope
> 
sorry, my mistake, had cross correlation on my mind