Premium
Matrix recursive expressions of the DFT of even and odd complex sequences
Author(s) -
Notarnicola Filippo
Publication year - 2005
Publication title -
numerical linear algebra with applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.02
H-Index - 53
eISSN - 1099-1506
pISSN - 1070-5325
DOI - 10.1002/nla.452
Subject(s) - mathematics , discrete sine transform , recursion (computer science) , sine , discrete fourier transform (general) , matrix (chemical analysis) , dft matrix , fast fourier transform , discrete cosine transform , sequence (biology) , sine and cosine transforms , trigonometric functions , matrix multiplication , algorithm , discrete mathematics , fourier transform , pure mathematics , mathematical analysis , fourier analysis , square matrix , symmetric matrix , fractional fourier transform , computer science , geometry , eigenvalues and eigenvectors , materials science , artificial intelligence , image (mathematics) , composite material , biology , genetics , quantum mechanics , physics , quantum
The discrete Fourier transform of even complex sequences involves, in matrix formulation, a cosine matrix and, in the same way, the discrete Fourier transform of odd complex sequences is related with a sine matrix. Using structural characteristics of the two matrices, whose order is half the length of the symmetric input data, some recursive expressions of them will be constructed. Unlike the previous classical forms of the discrete Fourier transform of an even or odd real vector, the recursive terms in the matrix expressions derived here only involve the same cosine and sine matrices, with halved order. That is, it is shown that, as for the FFT of a general complex sequence, a divide and conquer approach can also be used to compute the DFT of even or odd sequences. The recursion is closed in the family of the sine and cosine matrices used to describe the DFT of even and odd sequences and no other kind of sine or cosine based matrices are required in recursive terms. Although the obtained results give a new theoretical view on the problem of computing the DFT of even and odd complex sequences, these are not of immediate practical use since the computational cost is higher than other currently employed algorithms. Copyright © 2005 John Wiley & Sons, Ltd.