ABSTRACT
In this chapter, we describe fast computationally efficient algorithms for computing two- and higher-dimensional cyclic convolution of sequences. These computational tasks may arise naturally in multidimensional digital signal processing or may be used as a tool to compute one-dimensional cyclic convolution via the Agarwal-Cooley algorithm as described in Section 9.6. The basic idea remains the same as in previous chapters. We are focused on exposing and exploiting the mathematical properties of the computational task in order to reduce its computational burden. Number-theoretic results and polynomial algebra form the core of these properties. Once again, results pertaining to finite fields and finite integer rings are presented in separate sections.
