Existence of a 2 n FFT algorithm with a number of multiplications lower than 2 n +1
Pierre Duhamel, Henk D. L. Hollmann · Electronics Letters · 1984
First we give a decomposition of an FFT of length 2n into a number of one-dimensional polynomial products. If these products are computed with minimum multiplication algorithms, we show that the 2n FFT can be computed with less than 2n+1 nontrivial complex multiplications. A variation of this algorithm is also shown to give the same multiplication count as the ‘split-radix’ FFT.