Abstract:
We propose two new discrete sine and cosine differential Fourier transforms of a complex vector which are based on the finite-difference solution of inhomogeneous harmonic differential equations of the first order with complex coefficients and of the second order with real coefficients respectively. In basic form, the differential Fourier methods need less arithmetic operations as compared to the classical discrete Fourier transform method. The matrix of the sine differential Fourier transform is a complex matrix with alternating real and imaginary entries, and the matrix of the cosine transform is real. As in the classical case, both matrices transform into cyclic convolution matrices, and to them we can apply all fast convolution algorithms including the Winograd and Rader algorithms.
The differential Fourier methods are compatible with the Good–Thomas fast Fourier transform algorithm and, if combined with fast convolution algorithms, it can potentially be faster than all known methods of acceleration of the fast Fourier transform.