On the computational complexity of the general discrete Fourier transform (Q1094136)

The complexity of computing the General Discrete Fourier Transform over group algebras of finite groups is studied. Starting with a short introduction to known results, the complexity gains of a new algorithm derived from Clifford's theorem are discussed. Applying these results to the class of finite solvable groups, new upper bounds, also for the complexity of the underlying group algebras, are derived. The main result on the asymptotic complexities is stated as follows: Theorem: Let M be a finite set of primes. Let G be a solvable group, the order n of which contains only primes in M. Let \({\mathbb{F}}\) be a splitting field for G fulfilling Maschke's condition. Then the complexity of computing the Generalized Discrete Fourier Transform of \({\mathbb{F}}G\) and its inverse is in \(O(n^{u/2})\) where u is an exponent for matrix multiplication. The same order statement therefore holds for the complexity of computations in the group algebra \({\mathbb{F}}G.\) Based on the present knowledge about u the result of the main theorem implies that, asymptotically, the linear complexity L(\({\mathbb{F}}G)\) of the group algebra of solvable groups of order n can be reduced from \(O(n^ 2)\) to \(O(n^{1.19})\). For specific computations in group rings of `moderate' size it can easily be shown that by using the straightforward matrix-multiplication the proposed algorithm requires at most \(3.5\times n^{1.5}\) steps. It should also be mentioned that the proposed algorithm also covers the much simpler case of abelian groups, thus producting the known FFT- algorithms of reduced \({\mathbb{F}}\)-linear complexity. In these cases, multidimensional representations do not occur. Thus the known bound O(n log n), where the \(p_ i\) have to be bounded, are reproduced.