The hallmark of the Cooley-Tukey algorithm for Fast Fourier Transform is the butterfly network, which helps reduce O(N^2) computations to O(NlogN). Butterflies are very special graphs entangled in routing [Arora], switching [Chung], shuffling [Yang], and mixing [Czumaj].

Three butterflies – FFT flow graph, shuffling network, and a nonblocking interconnect