Videos

The Tangent FFT

Presenter
April 17, 2007
Abstract
My goal in this talk is to advertise an algorithm found by James Van Buskirk, the first improvement in more than thirty years in the exact complexity of the discrete Fourier transform over the reals. The previous speed record was held by the split-radix FFT, announced by Yavne in 1968 and widely understood since the early 1980s. The split-radix FFT uses 4nlg n-6n+8 operations over the reals for a size-n complex DFT when n is a large power of 2, and therefore (12+o(1))nlg n operations for a complex cyclic convolution of length n. Bruun's real-factor FFT also uses (12+o(1))nlg n operations. An analysis by Johnson and Frigo shows that Van Buskirk's new algorithm uses only (34/3+o(1))nlg n operations.