Fast discrete transforms by means of eigenpolynomials

Let A = (aij) be an n x n matrix. Consider the discrete transform u + Au, and associate with the jth column of A the eigenpolynomial aj(z) = cyzol aij xj. The properties of eigenpolynomials play an important role in the case where A is a matrix of eigenvectors of a Toeplitz matrix [1,2]. Here we consider the cases where A is the matrix defining the Discrete Fourier Transform (DFT), the Discrete Hartley ‘Transform (DHT), the Discrete Sine Transform (DST) and the Discrete Cosine ‘Dansform (DCT) in its two versions of (31 and (41. For each eigenpolynomial of each transform, we explicitly determine all its zeros. We use eigenpolynomials as a unifying tool for describing the Decimation In Frequency (DIF) versions of the main known algorithms for DFT. Moreover, by using the information about the zeros of the eigenpolynomials we devise new algorithms for DFT, DHT, DST and DCT, which reach or improve (in the case of DST and DCT) the record complexity bounds without requiring the use of the algorithm for complex multiplication with three multiplications and three additions [5] and of the implicit preconditioning.