Why not use 'higher power of 2' radix FFT?

Question

I have been reading quite a bit about FFTs and I understand quite well the following:

• radix 2 FFT, and its 'divide and conquer' advantage vs DFT,
• radix 4 FFT, and why it is better than radix 2 FFT (1 radix 4 needs an overall lower number of operations than 2 radix 2 FFTs),
• split radix 4/2 FFT: 'naively' it looks like there are more operations than radix 4, but actually quite a few more trivial operations (in particular multiplications by 1, -1, i, -i that actually need no complex multiplications), so less 'expensive' operations overall.

My question is: I cannot find as much / I read much less about 'higher radix' FFTs: I can find a bit here and there about radix 8, very little about radix 16, nothing so far about radix 32, 64, and 2**n in general. Naively, I would have guessed that going for higher and higher 2**n radix for array length that are compatible with it should give additional gains compared with combining several lower radix stages. Is this wrong / any reason why higher radix FFTs are not discussed as much?

Answer 1

Let's take a closer look how the FFT butterflies actually work (we stick with decimation in time for simplicity)

For Radix N, you take N samples, multiply these with N twiddle factors and than multiply the resulting vector with a N by N "recombination" matrix to get N output samples. This covers $\log_2(N)$ stages. The first twiddle factor is always 1 so we need N-1 actual twiddle factors

We can write this roughly as $$Y_k = X_k\cdot \hat{W}_{N,k} \cdot M_N$$

For N=2 the recombination matrix is simply

$$ M_2 = \begin{bmatrix} 1 & 1\\ -1 & 1 \end{bmatrix} $$

For N = 4, we get

$$M_4 = \begin{bmatrix} 1 & 1 & 1 & 1\\ 1 & -j & -1 & j\\ 1 & -1 & 1 & -1\\ 1 & j & -1 & -j \end{bmatrix} $$

Note that the first column is always 1.

For the execution of the radix 2 butterfly we need 1 complex multiply and 2 complex adds (or subtracts). That's a total of 4 real multiplies and 6 real adds.

For the execution of the radix 4 butterfly we need 3 complex multiplies for the twiddle factors. The recombination matrix consists ONLY of powers of $j$ so we don't have to actually execute any complex multiplies but can achieve this by simply swapping real/imaginary parts and/or signs. Due to the specific structure of this matrix we can implement this with 8 complex adds (not 12 if we were to do this directly). That's a total of 12 real multiplies and 22 real adds.

A radix 4 butterfly does 4 times the work of a radix-2 butterfly, so to compare apples, we need to divide by 4. A radix 4 butterfly requires 3 real multiplies 5.5 real adds per radix-2 butterfly. So it's only relatively mild improvement.

For higher radix butterflies the recombination matrix becomes truly complex. For a radix 8 butterfly half of the elements in the matrix will require a an actual complex multiply. You can still take advantage of the structure of the matrix but you will pick up at least 16 additional real multiples (with $\sqrt(0.5)$). At the same time the code becomes pretty complicated and unwieldy, so it's a questionable value proposition.

Answer 2

I believe that there are diminishing returns beyond radix 4. While arithmetic complexity probably continues to decrease (?) that decrease is too slow to compensate for «other factors».

Finding new factorizations that have lower arithmetic complexity is an interesting venture, but in practical applications, stuff like cache organization, simd instructions, the presence of bit reverse instructions can be more important than going for he currently lowest arithmetic complexity. I guess that could change if someone find a radically simpler factorization (I dont know that there is a theoretical bound on how simple factorizations might be found, but it seems that it is s fairly well studied topic).

-k

Answer 3

The package FFTW will work on vectors of any length. According to this presentation it uses both Rader's and Bluestein's algorithms. See also "prime factor FFT".

I found this out by doing a brief web search on the terms "fast fourier transform with vectors of prime length". Algorithms for doing this sort of thing appear to have been known since at least the 1960's (and Karl Gauss was doing interesting stuff with the FFT in the late 18th or early 19th century, but his results were not published until after his death, so the credit goes to Fourier).