Hands-On GPU Programming with Python and CUDA

Using an FFT for convolution

We will now look at how we can use an FFT to perform convolution. Let's review what exactly convolution is, first: given two one-dimensional vectors, x and y, their convolution is defined as follows:

This is of interest to us because if x is some long, continuous signal, and y only has a small amount of localized non-zero values, then y will act as a filter on x; this has many applications in itself. First, we can use a filter to smooth the signal x (as is common in digital signal processing and image processing). We can also use it to collect samples of the signal x so as to represent the signal or compress it ...