Fast Algorithms of Fourier and Hartley transform and their implementation in MATLAB
Vítězslav Veselý · 1998
. This paper is mainly intended as survey article on construction of fast algorithms for the computation of the discrete Fourier transform (DFT) and discrete Hartley transform (DHT), all in relation to discrete linear and cyclic convolution which are fundamental operations in many data processing tasks. The exposition prefers purely algebraic approach to explain the basic ideas in concise but clear manner. The benefits of author's new algebraic setting of generalized Kronecker product are demonstrated in deriving fast algorithms of Cooley-Tukey type for the computation of multidimensional fast Fourier and Hartley transform. These algorithms have been implemented as FORTRAN MEX-files in MATLAB which makes it easy to use them and evaluate their performance. Compared with other commonly used procedures the results of performance tests exhibit equal or better numerical stability and for most larger transform lengths time efficiency superior to that of the comparative procedures. The result...