Abstract of Linear Bijections and the Fast Fourier Transform

Mathematics Research Report CMA-MRR64-94

Abstract of Linear Bijections and the Fast Fourier Transform

Markus Hegland and Wayne W. Wheeler

Abstract: Fast Fourier transform algorithms are based on linear bijective mappings of the indices of the data arrays. Two basic mappings have been used in the literature, one for Cooley-Tukey like algorithms and the other for prime factor algorithms. Many other mappings are possible and lead to FFT algorithms. A complete classification of these mappings is provided. One particular mapping leads to a new FFT algorithm which generalizes the prime factor algorithm for non-relatively prime factors. It reduces the floating point operation count by reducing the number of trigonometric function evaluations. Linear bijective mappings are used to define the carry function of addition. It is shown that equivalence classes of mappings can be identified with equivalence classes of group extensions of the cyclic group. In the relatively prime case only one corresponding class of FFTs exists and in other cases each class contains both Cooley-Tukey like algorithms and algorithms of the new type.

This service is maintained by the Mathematical Sciences Institute (MSI)
Comments to webmaster@maths.anu.edu.au URL: http://wwwmaths.anu.edu.au/