Implementation of a new class of FFT algorithms on transputer computational structures

This work presents the theoretical formulation of a new class of fast Fourier transform algorithms and the experimental results obtained from the implementation of these algorithms on transputers computational structures. The theoretical formulation is based on a new methodology for the tensor or Kronecker product decomposition of the discrete Fourier transform matrix into a product of sparse matrices, with not all matrices having the same order. Special attention is given to what is termed a general twiddle or phase factor operator. Conforming this generalized operator, and the other factors present in a Kronecker product formulation of an algorithm, to the specific topology of a given transputer computational structure results in more efficient software implementations