Optimality of the Fast Fourier transform
Christos H. Papadimitriou · Journal of the ACM · 1979
A graph-theoretic model for a class of linear algorithms computing the discrete Fourier transform of sequences of length a power of 2, the mformat~on flow network, is presented The information flow network correspondmg to the fast Fourier transform IS shown to be umquely optimal in tim class with respect to a naturally defined cost