Fast algorithms for the discrete Fourier transform and for other transforms

A new matrix factorization is proposed for DCT-IV, which is the basis of fast algorithms for many sinusoidal transforms. A new fast algorithm for complex-data DFT based on the new factorization requires the same number of multiplications and far fewer additions than the Preuss algorithm. A new fast algorithm for real-data DFT based on a new algorithm for the discrete Hartley transform is also proposed.