Fast algorithms for computing one- and two-dimensional convolution in integer polynomial rings (Q677546)

The aim of the paper is to give new computationally efficient algorithms for compute discrete convolution of data sequences in rings of the form: \(\mathbb{Z}/(m),\mathbb{Z}[i]/(m), \mathbb{Z}[\theta]/(m), \mathbb{Z}[i,\theta]/(m)\) (where \(m \in \mathbb{Z}\) and \(\theta\) is algebraic over \(\mathbb{Z}\)), and polynomial extensions of these rings. The algorithms are based on the possibility of decomposing the above rings into direct sums of components (obtained from the factorization of \(m\)), hence a large size problem is expressed as a sum of a number of smaller size problems that are then computed in parallel. In order to obtain the desired solution, suitable formulations of the Chinese remainder theorem are used. The algorithms described regard the computation of one and two dimensional convolution of data sequences. Both cyclic and acyclic convolution algorithms are derived for the one dimensional case, whereas only cyclic convolution algorithms are developed for the two dimensional case.