Direct computation of the discrete Fourier transform (DFT) and its FFT computational algorithms requires multiplication (and addition) of complex numbers. Complex number multiplication requires four real-valued multiplications and two real-valued additions, or three real-valued multiplications and five real-valued additions, as well as the requisite added memory for temporary storage. In this paper, we present a method for computing a DFT via a natively real-valued algorithm that is computationally equivalent to a -length DFT (where k is a positive integer), and is substantially more efficient for any other length, N. Our method uses the eigenstructure of the DFT, and the fact that sparse, real-valued, eigenvectors can be found and used to advantage. Computation using our method uses only vector dot products and vector-scalar products.
Following the earlier work, the discrete Hirschman transform (DHT) structure is extended to other transforms: the cosine, sine, Walsh-Hadamard and the wavelet transforms. The eigenstructure of the discrete Hirschman transforms are derived, and in fact we show that they are inherited directly from the DFT eigenstructure. Two properties of the discrete Hirschman transforms, invertibility and unitarity, are proven.