
FFT interface
Detailed Description
This package is intended to calculate onedimensional real or complex FFTs with high accuracy and good efficiency even for lengths containing large prime factors. The code is written in C, but a Fortran wrapper exists as well.
Before any FFT is executed, a plan must be generated for it. Plan creation is designed to be fast, so that there is no significant overhead if the plan is only used once or a few times.
The main component of the code is a C port of Swarztrauber's FFTPACK (http://www.netlib.org/fftpack/), which was originally done by Pekka Janhunen and reformatted by Joerg Arndt.
I added a few digits to the floatingpoint constants to achieve higher precision, split the complex transforms into separate routines for forward and backward transforms (to increase performance a bit), and replaced the iterative twiddling factor calculation in radfg() and radbg() by an exact calculation of the factors.
Since FFTPACK becomes quite slow for FFT lengths with large prime factors (in the worst case of prime lengths it reaches O(n*n) complexity), I implemented Bluestein's algorithm, which computes a FFT of length n by several FFTs of length n2>=2*n and a convolution. Since n2 can be chosen to be highly composite, this algorithm is more efficient if n has large prime factors. The longer FFTs themselves are then computed using the FFTPACK routines. Bluestein's algorithm was implemented according to the description at Wikipedia.
Threadsafety: All routines can be called concurrently; all information needed by ls_fft is stored in the plan variable. However, using the same plan variable on multiple threads simultaneously is not supported and will lead to data corruption.
Typedef Documentation
The opaque handle type for complexFFT plans.
Definition at line 85 of file ls_fft.h.
The opaque handle type for realFFT plans.
Definition at line 106 of file ls_fft.h.
Function Documentation
Returns a plan for a complex FFT with length elements.
Definition at line 37 of file ls_fft.c.
Destroys a plan for a complex FFT.
Definition at line 55 of file ls_fft.c.
void complex_plan_forward 
( 
complex_plan 
plan, 


double * 
data  

) 
  
Computes a complex forward FFT on data, using plan. Data has the form r0, i0, r1, i1, ..., r[length1], i[length1].
Definition at line 61 of file ls_fft.c.
void complex_plan_backward 
( 
complex_plan 
plan, 


double * 
data  

) 
  
Computes a complex backward FFT on data, using plan. Data has the form r0, i0, r1, i1, ..., r[length1], i[length1].
Definition at line 69 of file ls_fft.c.
Returns a plan for a real FFT with length elements.
Definition at line 78 of file ls_fft.c.
Destroys a plan for a real FFT.
Definition at line 96 of file ls_fft.c.
void real_plan_forward_fftpack 
( 
real_plan 
plan, 


double * 
data  

) 
  
Computes a real forward FFT on data, using plan and assuming the FFTPACK storage scheme:
 on entry, data has the form r0, r1, ..., r[length1];
 on exit, it has the form r0, r1, i1, r2, i2, ... (a total of length values).
Definition at line 102 of file ls_fft.c.
void real_plan_backward_fftpack 
( 
real_plan 
plan, 


double * 
data  

) 
  
Computes a real forward FFT on data, using plan and assuming the FFTPACK storage scheme:
 on entry, data has the form r0, r1, i1, r2, i2, ... (a total of length values);
 on exit, it has the form r0, r1, ..., r[length1].
Definition at line 161 of file ls_fft.c.
void real_plan_forward_fftw 
( 
real_plan 
plan, 


double * 
data  

) 
  
Computes a real forward FFT on data, using plan and assuming the FFTW halfcomplex storage scheme:
 on entry, data has the form r0, r1, ..., r[length1];
 on exit, it has the form r0, r1, r2, ..., i2, i1.
Definition at line 155 of file ls_fft.c.
void real_plan_backward_fftw 
( 
real_plan 
plan, 


double * 
data  

) 
  
Computes a real backward FFT on data, using plan and assuming the FFTW halfcomplex storage scheme:
 on entry, data has the form r0, r1, r2, ..., i2, i1.
 on exit, it has the form r0, r1, ..., r[length1].
Definition at line 186 of file ls_fft.c.
void real_plan_forward_c 
( 
real_plan 
plan, 


double * 
data  

) 
  
Computes a real forward FFT on data, using plan and assuming a fullcomplex storage scheme:
 on entry, data has the form r0, [ignored], r1, [ignored], ..., r[length1], [ignored];
 on exit, it has the form r0, i0, r1, i1, ..., r[length1], i[length1].
Definition at line 192 of file ls_fft.c.
void real_plan_backward_c 
( 
real_plan 
plan, 


double * 
data  

) 
  
Computes a real backward FFT on data, using plan and assuming a fullcomplex storage scheme:
 on entry, data has the form r0, i0, r1, i1, ..., r[length1], i[length1];
 on exit, it has the form r0, 0, r1, 0, ..., r[length1], 0.
Definition at line 229 of file ls_fft.c.
Generated on Fri Jun 18 16:12:29 2010 for LevelS FFT library

