ABSTRACT
In this chapter, we develop fast algorithms for computing one- and higher-dimensional acyclic convolution of discrete sequences. Techniques will also be described for converting one-dimensional acyclic convolution into multidimensional acyclic convolution. A worthwhile objective is to design algorithms with as low a multiplicative complexity as possible. We analyze the computational complexity of various algorithms and use it as a benchmark to compare them. Let us first consider one-dimensional convolution of two sequences expressed as the polynomial product,
