Thursday, December 5, 2013

Getting started with FFTW for computing the Discrete Fourier Transform

The FFTW (Fastest Fourier Transform in the West) is a library for, among other things, computing the Discrete Fourier Transform (DFT) of real data.

I have been using Scipy for computing the DFT of real data, but I have a love/hate relationship with Python so I wanted to have it working with C/C++. Additionally, my understanding is that the FFTW is supposed to have exceptional performance when computing the DFT of many arrays of the same size because it invests in an initialization step that tailors the computation to the hardware (the "plan").

The installation on Ubuntu 12.10 went smoothly after downloading the package from their website. The usual round of
./configure
make
sudo make install
took care of everything.

The FFTW documentation was very helpful and got me up and running. My code and Makefile are posted on Github. The code generates an array of real numbers and computes the DFT, returning an array of complex numbers in the first function, and it returns the "halfcomplex" format in the second function (check the FFTW documentation for more on the "halfcomplex" format):
$./fftw_test 
Hello from main

Hello from real2complex()

This takes in a real number array and returns a complex number array:
Input array: 
 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
Output array: 
 (8,0) (0,0) (0,0) (0,0) (-4,4) (0,0) (0,0) (0,0) (0,0) (0,0) (0,0) (0,0) (0,0) (0,0) (0,0) (0,0)

Hello from real2real()

This takes in a real number array and returns a real number array:
Input array
 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
"Halfcomplex" output array: 
 8 0 0 0 -4 0 0 0 0 0 0 0 4 0 0 0
Power spectrum
 0 0 0 5.65685 0 0 0
Frequencies of spectrum 
 0.0625 0.125 0.1875 0.25 0.3125 0.375 0.4375
Please let me know if you find any errors, and use the code at your own risk; my theoretical understanding of the DFT certainly isn't reliable!

No comments:

Post a Comment