|
| 1 | +PocketFFT |
| 2 | +--------- |
| 3 | + |
| 4 | +This is a heavily modified implementation of FFTPack [1,2], with the following |
| 5 | +advantages: |
| 6 | + |
| 7 | +- strictly C99 compliant |
| 8 | +- more accurate twiddle factor computation |
| 9 | +- very fast plan generation |
| 10 | +- worst case complexity for transform sizes with large prime factors is |
| 11 | + `N*log(N)`, because Bluestein's algorithm [3] is used for these cases. |
| 12 | + |
| 13 | +License |
| 14 | +------- |
| 15 | + |
| 16 | +3-clause BSD (see LICENSE.md) |
| 17 | + |
| 18 | + |
| 19 | +Some code details |
| 20 | +----------------- |
| 21 | + |
| 22 | +Twiddle factor computation: |
| 23 | + |
| 24 | +- making use of symmetries to reduce number of sin/cos evaluations |
| 25 | +- all angles are reduced to the range `[0; pi/4]` for higher accuracy |
| 26 | +- an adapted implementation of `sincospi()` is used, which actually computes |
| 27 | + `sin(x)` and `(cos(x)-1)`. |
| 28 | +- if `n` sin/cos pairs are required, the adjusted `sincospi()` is only called |
| 29 | + `2*sqrt(n)` times; the remaining values are obtained by evaluating the |
| 30 | + angle addition theorems in a numerically accurate way. |
| 31 | + |
| 32 | +Parallel invocation: |
| 33 | + |
| 34 | +- Plans only contain read-only data; all temporary arrays are allocated and |
| 35 | + deallocated during an individual FFT execution. This means that a single plan |
| 36 | + can be used in several threads at the same time. |
| 37 | + |
| 38 | +Efficient codelets are available for the factors: |
| 39 | + |
| 40 | +- 2, 3, 4, 5, 7, 11 for complex-valued FFTs |
| 41 | +- 2, 3, 4, 5 for real-valued FFTs |
| 42 | + |
| 43 | +Larger prime factors are handled by somewhat less efficient, generic routines. |
| 44 | + |
| 45 | +For lengths with very large prime factors, Bluestein's algorithm is used, and |
| 46 | +instead of an FFT of length `n`, a convolution of length `n2 >= 2*n-1` |
| 47 | +is performed, where `n2` is chosen to be highly composite. |
| 48 | + |
| 49 | + |
| 50 | +[1] Swarztrauber, P. 1982, Vectorizing the Fast Fourier Transforms |
| 51 | + (New York: Academic Press), 51 |
| 52 | +[2] https://www.netlib.org/fftpack/ |
| 53 | +[3] https://en.wikipedia.org/wiki/Chirp_Z-transform |
0 commit comments