Existence of a 2n FFT algorithm with a number of multiplications lower than 2n+1

Abstract

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.