The Numeric Summary in the Fourier spectral options includes a prime factorization in the FFT
Size field.FFT Algorithms
AutoSignal 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. AutoSignal 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, AutoSignal 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 AutoSignal processes primes through 13. AutoSignal 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. AutoSignal 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 AutoSignal 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 AutoSignal 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.
Prime Factorization
The Numeric Summary in the Fourier spectral options includes a prime factorization in the FFT
Size field.
 |