A Class of Finite Computation Structures Supporting the Fast Fourier Transform
Richard J. Bonneau · 1973
this paper analyzes the question oi' when these two techniques can be utilized concurrently. The desirabilit3' of the convolution property of the FFT suggests a practical definition for the support of an FFT, while a generalization of the modular rings of integers motivates a reasonable definition of a finite computation structure. A Finite Com.utation Structure is defined to be a commutative ring with unity, and of finite, non-zero characteristic. This report first completely characterizes the modular rings of integers which support the FFT by considering. the prime factorization of the modulus. This characterization is then extended to provide the following result: Theorem: Let R be a finite computation structure of characteristic m. Then R will support a K-point T if K divides p-1 for each prime p dividing m. The paper then concludes with examples of the application of this result to the protlems of computing products and powers of symbolic ultivariate polynomials