Computation of Convolutions and Discrete Fourier Transforms by Polynomial Transforms

Key Points

• The aim is to develop polynomial transforms that efficiently compute convolutions and discrete Fourier transforms without multiplications.
• Introduction of discrete transforms defined in a ring of polynomials.
• Use of polynomial transforms to demonstrate convolution properties.
• Derivation of efficient algorithms for computing one-dimensional convolutions and discrete Fourier transforms.
• Polynomial transforms enable computation of two-dimensional convolutions with fewer operations.
• One-dimensional convolutions can be computed more efficiently than traditional methods.
• Discrete Fourier transforms are also derived effectively using the polynomial approach.