Clausen M., Baum U. Fast Fourier Transforms

Wissenschaftsverlag, 1993. — 181.Since its discovery by Cooley and Тukey in 1965, the classical fast Fourier transform has been successfully applied to а wide range of problems in mathematics, computer science and engineering. Сооley and Тukey proved that the discrete Fourier transform (DFT) of length n can be computed with О(n log n) arithmetic operations if n is а power of two. From an algebraic point of view, performing а DFT amounts to evaluating the irreducible representations of а cyclic group. This interpretation allows to define а DFT on any finite group. As every such DFT on а group of order n is а linear transform described by an n-square matrix, it can be performed in time О(n²). However, this is too slow for many real-time applications. Soon after the Cooley-Tukey FFT became known, people started investigating FFTs for abelian groups. By 1970, it was clear through work of Bluestein that any abelian group has an О(n log n) FFT.
А first step towards FFTs for non-abelian groups was taken by Atkinson and Karpovsky in 1977, who discussed direct products of finite groups. Major progress was made by Beth in 1984. In his pioneering work, he used the theory of group representations to propose an О(n^3/2) FFT algorithm for solvable groups. This marked the beginning of an algebraic theory of non-abelian FFTs that has developed rapidly ever since. Soon it was realized that Beth's ideas only work with а special choice of bases that adapts the corresponding matrix representations to а composition series. In the following years, this method of symmetry adapted representations was developed in а general setting and used as а unifying tool in the design of FFT algorithms. In 1991, supersolvable groups (which include all groups of prime power order) were shown to have an О(n log n) FFT. These FFTs (i.e. а suitable set of irreducible representations) can also be constructed in time О(n log n). This was the first time а large class of non-abelian FFTs became available in а practical sense.
The aim of this book is to provide an up-to-date account of the theory of fast Fourier transforms on finite groups. We have concentrated on recent results, not always following the history of the subject. The material is intended for а one-semester graduate course in mathematics or computer science. We have tried to keep it mostly self-contained, only assuming that the reader is familiar with basic algebra as covered in а standard one-semester course. Exercises ranging from very simple ones to larger projects are included at the end of each chapter.Motivating Examples
Group Algebras, Representations and DFT
Linear Complexity
FFT for Abelian Groups
Lower Complexity Bounds
Tools from Representation' Theory
Symmetry Adapted DFTs
FFT for Supersolvable Groups
FFT for Symmetric Groups
Group Circulants and Applications
Spectral Analysis