Reply to topic  [ 3 posts ] 
Trouble doing an inverse fourier transform 
Author Message
Yorick Padawan

Joined: Tue Jun 07, 2011 1:46 pm
Posts: 32
Location: UNH
Post Trouble doing an inverse fourier transform

I was looking for ways to do an inverse fourier transform or reverse discrete fourier transform like the ifft function in Matlab. I thought that fft(x, -1) would do a "backwards" or an inverse fft, but when I run this code in Matlab:
>x = [1,2,3,4,5,6,7,8,9,10];
ans =

  Columns 1 through 3

   5.5000            -0.5000 - 1.5388i  -0.5000 - 0.6882i

  Columns 4 through 6

  -0.5000 - 0.3633i  -0.5000 - 0.1625i  -0.5000         

  Columns 7 through 9

  -0.5000 + 0.1625i  -0.5000 + 0.3633i  -0.5000 + 0.6882i

  Column 10

  -0.5000 + 1.5388i

I get values different from this code in Yorick:
>x = indgen(10);
>fft(x, -1);

The only way I have come across to do an inverse fft in yorick is to install yeti_fftw (or just the entirety of yeti) with the linop.i include.

So I followed this topic and post and downloaded linop.i to my /yorick/i0/ folder.

This is my code:
>x = indgen(10);
>obj = linop_new_fftw();
>linop_apply(obj, x, 2); // 2 is supposed to be an inverse

and then yorick dies and gives me this error message:
/opt/eaarl/yorick/bin/yorick: symbol lookup error: /opt/eaarl/yorick/lib/ undefined symbol: fftw_create_plan

I googled fftw_create_plan and it seems that it was located in the fftw package. I had downloaded precompiled fftw2.1.5 files into my include directory in my yorick installation.

I checked the /opt/eaarl/yorick/lib/ file with the one in my yeti install folder and the number of bytes matched. I followed the instructions, I think, properly from the README in the yeti folder. I used:
$ ./configure --yorick=/opt/eaarl/bin/yorick
$ yorick -batch ./config.i --with-regex \
    --with-fftw --with-fftw-defs="-I/usr/local/include" \
    --with-fftw-libs="-L/usr/local/lib -lrfftw -lfftw" \
    --with-gsl --with-gsl-defs="-I/usr/local/include" \
    --with-gsl-libs="-L/usr/local/lib -lgsl -lgslcblas" \
    --with-tiff --with-tiff-libs="-ltiff"
$ sudo make
$ sudo make all
$ sudo make install

Everything was OKed but it doesn't work. What am I doing wrong?

Edit: I also tried the repository after compiling fftw 2.1.5 successfully:
$ sudo yum install yeti --skip-broken
Loaded plugins: fastestmirror
Loading mirror speeds from cached hostfile
* base:
* extras:
* updates:
Setting up Install Process
Resolving Dependencies
--> Running transaction check
---> Package yeti.i586 0:6.2.1-gemini2007dec31 set to be updated
--> Processing Dependency: yorick >= 2.1 for package: yeti
--> Processing Dependency: fftw2 for package: yeti
--> Running transaction check
---> Package yeti.i586 0:6.2.1-gemini2007dec31 set to be updated
--> Processing Dependency: fftw2 for package: yeti
---> Package yorick.i586 0:2.1.05-gemini2007dec31 set to be updated
--> Finished Dependency Resolution
yeti-6.2.1-gemini2007dec31.i586 from maumae has depsolving problems
  --> Missing Dependency: fftw2 is needed by package yeti-6.2.1-gemini2007dec31.i586 (maumae)

Packages skipped because of dependency problems:
    yeti-6.2.1-gemini2007dec31.i586 from maumae
    yorick-2.1.05-gemini2007dec31.i586 from maumae

Installing yorick-yeti yielded the same dependency issue. I googled fftw2 and found an RPM for CentOS 5, but I couldn't install it due to a missing GPG key. I'll keep looking but any help would be much appreciated.


Wed Jun 15, 2011 12:19 pm
Yorick Master

Joined: Mon Nov 22, 2004 9:43 am
Posts: 354
Location: Livermore, CA, USA
Post Re: Trouble doing an inverse fourier transform
Yorick's fft is working exactly as advertised. Type

and read the description very carefully; the function does exactly what it says in the help document. Most low level (C or Fortran) fft functions, including the netlib Swarztrauber routines that are the basis of yorick's fft, and, I believe fftw, use this normalization convention -- which is that you get the coefficients of the exponentials in the DFT unnormalized. This is actually the correct choice for encapsulating the FFT algorithm; the raw algorithm produces these unnormalized coefficients. Different packages disagree on the sign of i which is "forward" versus "backward" -- the help comment specifies which convention yorick (Swarztrauber) follows. Under this standard (lack of) normalization, fft(fft(x),-1) will return numberof(x)*x. That's why the directions are called "forward" and "backward"; the word "inverse" is not quite correct. The other amusing property of the DFT (and Fourier transforms in general) is fft(fft(fft(fft(x)))) equals N*N*x where N=numberof(x), so if you don't like fft(x,-1), you can always just apply fft() three times...

> fft(fft(indgen(5)),-1)/5
> fft(fft(fft(fft(indgen(5)))))/25

I do not use the fftw package, so I won't comment on what went wrong for you there. For most users, the built-in yorick fft performance is more than adequate; there is no reason to use the specialized fftw package.

I suspect that the ifft function in Matlab is equally well-documented (they've done the division by N=10 in your example); I'm not responsible for their non-standard choice of normalization, although to their credit, they did call it "inverse" instead of "backward". The normalization and sign of i are variable across the literature and software of Fourier transforms in general and DFTs in particular.

Sat Jun 18, 2011 8:20 am
Yorick Padawan

Joined: Tue Jun 07, 2011 1:46 pm
Posts: 32
Location: UNH
Post Re: Trouble doing an inverse fourier transform
Ahh that makes so much sense. I had a feeling it was off by a factor of 10 but wasn't sure due to the varying imaginary values. I figured since the imaginary numbers were off by a factor other than 10 while the real number was off by 10, that I was either using the functions wrong or the functions were doing different things. Unfortunately, matlab's ifft didn't mention that different n value for normalization but I'm glad you explained it to me.

I had the below function work fine in cases where I had to apply the inverse FFT to convert the matlab code to yorick code.
func ml_ifft( x )
   return fft( x, -1 ) / numberof(x);

I won't bother with the fftw plugin then. Thank you munro.

Ronak :)

Mon Jun 20, 2011 10:24 am
Display posts from previous:  Sort by  
Reply to topic   [ 3 posts ] 

Who is online

Users browsing this forum: No registered users and 1 guest

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group.
Designed by STSoftware for PTF.