FFT Algorithms¶
TableCurve 2D offers four different FFT algorithms and a composite procedure that minimizes computation time.
FFT Radix 2¶
This is the conventional power of 2 FFT procedure. TableCurve 2D supports the following n: 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, and 65536. If the data size is not a power of 2, zeros are appended to the next larger n. To produce the fastest possible power of 2 FFTs, TableCurve 2D uses the Intel Signal Processing Library. This set of processor-specific DLLs includes architecture optimized FFTs. This is the fastest of the FFT algorithms.
Prime Factor¶
The prime factor FFT procedure used in TableCurve 2D processes primes through 13. TableCurve 2D uses an implementation of Temperton's Prime Factor FFT (C. Temperton, "Implementation of a Self-Sorting In-Place Prime Factor FFT Algorithm", Journal of Computational Physics, v. 58, p. 283, 1985). For real data, the following n are processed exactly: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 36, 40, 42, 44, 48, 52, 56, 60, 66, 70, 72, 78, 80, 84, 88, 90, 96, 104, 110, 112, 120, 126, 130, 132, 140, 144, 154, 156, 160, 168, 176, 180, 182, 198, 208, 210, 220, 224, 234, 240, 252, 260, 264, 280, 286, 288, 308, 312, 330, 336, 352, 360, 364, 390, 396, 416, 420, 440, 462, 468, 480, 504, 520, 528, 546, 560, 572, 616, 624, 630, 660, 672, 720, 728, 770, 780, 792, 840, 858, 880, 910, 924, 936, 990, 1008, 1040, 1056, 1092, 1120, 1144, 1170, 1232, 1248, 1260, 1320, 1386, 1430, 1440, 1456, 1540, 1560, 1584, 1638, 1680, 1716, 1760, 1820, 1848, 1872, 1980, 2002, 2016, 2080, 2184, 2288, 2310, 2340, 2464, 2520, 2574, 2640, 2730, 2772, 2860, 2912, 3080, 3120, 3168, 3276, 3360, 3432, 3640, 3696, 3744, 3960, 4004, 4290, 4368, 4576, 4620, 4680, 5040, 5148, 5280, 5460, 5544, 5720, 6006, 6160, 6240, 6552, 6864, 6930, 7280, 7392, 7920, 8008, 8190, 8580, 8736, 9240, 9360, 10010, 10080, 10296, 10920, 11088, 11440, 12012, 12320, 12870, 13104, 13728, 13860, 14560, 15840, 16016, 16380, 17160, 18018, 18480, 18720, 20020, 20592, 21840, 22176, 22880, 24024, 25740, 26208, 27720, 30030, 32032, 32760, 34320, 36036, 36960, 40040, 41184, 43680, 48048, 51480, 55440, 60060, 65520. For other sizes, zeros are appended to the next larger n. This is the second fastest of the FFT procedures.
Mixed Radix¶
The mixed radix FFT algorithm processes any size n exactly. TableCurve 2D uses a modification of Singleton's mixed radix algorithm (R. C. Singleton, "An Algorithm for Computing the Mixed Radix Fast Fourier Transform", IEEE Trans. Audio Electroacoust., v. AU-17, p. 93, June 1969) that removes the size limitation. This algorithm is slower than the radix 2 and prime factor procedures.
Chirp-Z¶
The Chirp-Z FFT algorithm (L. R. Rabiner, R. W. Schafer, C. M. Rader, "The Chirp z-Transform Algorithm and Its Application", BSTJ, 48, p.1249, May-June 1969) can also be used to exactly process any size n. The TableCurve 2D Chirp-Z implementation computes the z-transform at n equally spaced points on the unit circle, reproducing the FFT. The fast convolution requires two radix-2 FFT forward transforms and 1 FFT inverse. When very large primes are present, this algorithm is faster than the mixed radix procedure.
Best Exact N¶
This is the recommended algorithm for most procedures within TableCurve 2D that use the FFT. If the data size is a power of 2, the FFT Radix 2 algorithm is used. If not and the size is included in the prime-factor set, then the Prime Factor procedure is used.Otherwise, the Mixed Radix algorithm is used if the largest prime <= 509 and the Chirp-Z is used if the largest prime >= 521. This produces the fastest possible exact-n FFT.