FFT interface


Data Structures
struct	complex_plan_i
Typedefs
typedef complex_plan_i *	complex_plan
typedef real_plan_i *	real_plan
Functions
complex_plan	make_complex_plan (int length)
void	kill_complex_plan (complex_plan plan)
void	complex_plan_forward (complex_plan plan, double *data)
void	complex_plan_backward (complex_plan plan, double *data)
real_plan	make_real_plan (int length)
void	kill_real_plan (real_plan plan)
void	real_plan_forward_fftpack (real_plan plan, double *data)
void	real_plan_backward_fftpack (real_plan plan, double *data)
void	real_plan_forward_fftw (real_plan plan, double *data)
void	real_plan_backward_fftw (real_plan plan, double *data)
void	real_plan_forward_c (real_plan plan, double *data)
void	real_plan_backward_c (real_plan plan, double *data)

Detailed Description

This package is intended to calculate one-dimensional 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 floating-point 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.

Thread-safety: 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

typedef complex_plan_i* complex_plan

The opaque handle type for complex-FFT plans.

Definition at line 85 of file ls_fft.h.

typedef real_plan_i* real_plan

The opaque handle type for real-FFT plans.

Definition at line 106 of file ls_fft.h.

Function Documentation

complex_plan make_complex_plan ( int length )

Returns a plan for a complex FFT with length elements.

Definition at line 37 of file ls_fft.c.

void kill_complex_plan ( complex_plan plan )

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[length-1], i[length-1].

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[length-1], i[length-1].

Definition at line 69 of file ls_fft.c.

real_plan make_real_plan ( int length )

Returns a plan for a real FFT with length elements.

Definition at line 78 of file ls_fft.c.

void kill_real_plan ( real_plan plan )

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[length-1];
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[length-1].

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[length-1];
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[length-1].

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 full-complex storage scheme:

on entry, data has the form r0, [ignored], r1, [ignored], ..., r[length-1], [ignored];
on exit, it has the form r0, i0, r1, i1, ..., r[length-1], i[length-1].

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 full-complex storage scheme:

on entry, data has the form r0, i0, r1, i1, ..., r[length-1], i[length-1];
on exit, it has the form r0, 0, r1, 0, ..., r[length-1], 0.

Definition at line 229 of file ls_fft.c.

FFT interface

Data Structures

Typedefs

Functions

Detailed Description

Typedef Documentation

Function Documentation