Fast polynomial transform algorithms for digital convolution

We have recently introduced new transforms, called polynomial transforms, which are defined in rings of polynomials and give efficient algorithms for the computation of multidimensional DFT's and convolutions. In this paper we present a method for computing one-dimensional convolutions by polynomial transforms. We show that this method is computationally efficient, even for large convolutions, and can be implemented with FFT-type algorithms, while avoiding the use of trigonometric functions and complex arithmetic. We then extend this technique to complex convolutions and to multidimensional convolutions.