Algebraic signal processing theory: Cooley-Tukey type algorithms for polynomial transforms based on induction

Abstract. A polynomial transform is the multiplication of an input vector x ∈ Cn by a matrix Pb;α ∈ Cn×n; whose ðk;lÞth element is defined as plðαkÞ for polynomials plðxÞ ∈ Cx from a list b fp0ðxÞ; : : : ; pn−1ðxÞg and sample points αk ∈ C from a list α fα0; : : :;αn−1g. Such transforms find applica-tions in the areas of signal processing, data compression, and function interpolation. An important example includes the discrete Fourier transform. In this paper we introduce a novel technique to derive fast algorithms for polynomial transforms. The technique uses the relationship between polynomial transforms and the repre-sentation theory of polynomial algebras. Specifically, we derive algorithms by decomposing the regular mod-ules of these algebras as a stepwise induction. As an application, we derive novel Oðn log nÞ general-radix algorithms for the discrete Fourier transform and the discrete cosine transform of type 4