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.
Fast discrete transforms by means of eigenpolynomials
BOZZO, Enrico
1993-01-01
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 [5] and of the implicit preconditioning.File | Dimensione | Formato | |
---|---|---|---|
eigenpoly.pdf
non disponibili
Tipologia:
Altro materiale allegato
Licenza:
Non pubblico
Dimensione
1.21 MB
Formato
Adobe PDF
|
1.21 MB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.