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  and of the implicit preconditioning.

### Fast discrete transforms by means of eigenpolynomials

#### Abstract

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  and of the implicit preconditioning.
##### Scheda breve Scheda completa Scheda completa (DC)
1993
File in questo prodotto:
File
eigenpoly.pdf

non disponibili

Tipologia: Altro materiale allegato
Licenza: Non pubblico
Dimensione 1.21 MB
Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11390/676167`
• ND
• 3
• 2