Linear bijections and the fast Fourier transform (Q677564)

Fast Fourier transform (FFT) algorithms are among the most important applications of scientific computing, and since the 1960's they have revolutionized signal processing and computational science. These algorithms can be based on the algebraic idea of group representation of cyclic groups, and in this framework FFT algorithms have been generalized to certain types of nonabelian groups. Another approach to studying FFT algorithms involves the idea of representing indices of the data array in a manner analogous to the decimal representation of an integer in terms of digits. This significant paper builds on the observation that FFT algorithms rely upon the choice of certain bijective mappings between the indices of the data arrays. The two basic mappings used in the literature lead to Cooley-Tukey algorithms or to prime factor algorithms. The authors provide a complete classification of bijections that leads to FFT algorithms. One particular choice leads to a new FFT algorithm that generalizes the prime factor algorithm. It has the advantage of reducing the floating point operation count by reducing the trigonometric function evaluations. The authors define a certain equivalence relation on the set of bijections that lead to FFT algorithms, and study its connection with isomorphism classes of group extensions. Remarkably, under this equivalence relation every equivalence class contains bijections leading to an FFT algorithm of the new type. The paper exhibits an affinity between fast Fourier transforms and the algebraic theory of group extensions.