New algorithms for convolution and DFT based on polynomial transforms

Discrete transforms, defined in rings of polynomials, have been introduced recently. These polynomial transforms have the convolution property and can be computed in ordinary arithmetic, without multiplications. We show that, by combining the polynomial transform approach with a split nesting technique, multidimensional convolutions can be computed very efficiently in general purpose computers. This computation method can also be used for the evaluation of one-dimensional convolutions and discrete Fourier transforms (DFT's).