Fast discrete transforms by means of eigenpolynomials (Q1311982)

The linear transform \(\mathbb{C}^ N \to \mathbb{C}^ N\), \(u\mapsto Au\) is equivalent with the computation of the coefficients of the polynomial \(\sum^{n-1}_{j=0} u_ ja_ j(z)\), where \(a_ j\) denotes the eigenpolynomial \(a_ j(z):=\sum^{n-1}_{i=0} a_{ij} z^ i\) associated with the \(j\)-th column of \(A\). For the matrices \(A\) defining the discrete Fourier transform, discrete Hartley transform, discrete sine transform, and discrete cosine transform the authors determine the zeros of the eigenpolynomials and use this information for the construction of known and new fast algorithms for the above transforms.