Discrete transforms over polynomial rings with applications in computing multidimensional convolutions

Discrete transforms over polynomial rings are developed and rings that possess simple transform kernels are investigated. A polynomial transform is used to transform a linear multidimensional convolution into a set of one-dimensional noncircular convolutions. A mapping which can be used to convert a noncircular convolution into a circular one and vice versa is presented. This is used to map the one-dimensional noncircular convolutions resulting from the polynomial transforms into circular ones, for which efficient discrete transform methods do exist. A convolution circular in all dimensions is computed by mapping one of its dimensions into a noncircular form and using the same polynomial transforms. Several other methods of evaluating multidimensional circular convolutions using polynomial transforms are also described. It is shown that these polynomial transforms can be evaluated using FFT-type computational algorithms. This class of polynomial transforms is free of multiplications and hence represents a suitable technique for the fast, accurate computation of multidimensional convolutions.