Newsgroups: comp.parallel
From: Martin Watts <m.watts@ic.ac.uk>
Subject: Convolution using FFT
Organization: Imperial College, London, UK
Date: 2 Apr 1998 02:31:28 GMT
Message-ID: <6futa0$9dm$1@encore.ece.cmu.edu>

Hi Folks,

Sorry that this is not a question specifically about parallel computing.
Being a rather infrequent user of Usenet, I couldn't find a group that
looked any more likely to deal with such queries -- if anyone knows of
one, please let me know!

I am looking for a fast algorithm to perform convolution of a function
with itself, sampled at equally spaced intervals. As everyone knows, 
the Fast Fourier Transform offers an efficient way of performing
convolutions, provided that the functions concerned can be assumed to
repeat themselves after a given number of samples. If this 'wrapround'
assumption is not valid, it is customary to pad the functions with as
many zeros as are necessary to eliminate any wrapround pollution prior
to performing the initial transform. However, in the case of a function
to be convolved with itself, this amounts to a doubling in the length
of  the initial array. In my particular case, I wish to perform this
'auto-convolution' in 3 dimensions -- this means generating an array
eight times bigger than the original data array in order to eliminate
wrapround problems. I'm already stuck for space, so can anybody suggest
a way of reducing the seriousness of this problem, or suggest a fast
algorithm for convolution which doesn't have the wrapround problem?

Many thanks in advance.

Cheers,

Martin Watts
Geophysics Group,
Imperial College, UK.

--
Articles to parallel@ctc.com (Administrative: bigrigg@cs.cmu.edu)
Archive: http://www.hensa.ac.uk/parallel/internet/usenet/comp.parallel