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.