README
1ls_fft description:
2
3This package is intended to calculate one-dimensional real or complex FFTs
4with high accuracy and good efficiency even for lengths containing large
5prime factors.
6The code is written in C, but a Fortran wrapper exists as well.
7
8Before any FFT is executed, a plan must be generated for it. Plan creation
9is designed to be fast, so that there is no significant overhead if the
10plan is only used once or a few times.
11
12The main component of the code is based on Paul N. Swarztrauber's FFTPACK in the
13double precision incarnation by Hugh C. Pumphrey
14(http://www.netlib.org/fftpack/dp.tgz).
15
16I replaced the iterative sine and cosine calculations in radfg() and radbg()
17by an exact calculation, which slightly improves the transform accuracy for
18real FFTs with lengths containing large prime factors.
19
20Since FFTPACK becomes quite slow for FFT lengths with large prime factors
21(in the worst case of prime lengths it reaches O(n*n) complexity), I
22implemented Bluestein's algorithm, which computes a FFT of length n by
23several FFTs of length n2>=2*n-1 and a convolution. Since n2 can be chosen
24to be highly composite, this algorithm is more efficient if n has large
25prime factors. The longer FFTs themselves are then computed using the FFTPACK
26routines.
27Bluestein's algorithm was implemented according to the description at
28http://en.wikipedia.org/wiki/Bluestein's_FFT_algorithm.
29
30Thread-safety:
31All routines can be called concurrently; all information needed by ls_fft
32is stored in the plan variable. However, using the same plan variable on
33multiple threads simultaneously is not supported and will lead to data
34corruption.
35