ABSTRACT
In this chapter, we analyze the algebraic structure of fast algorithms for computing one- and two-dimensional convolution of sequences defined over https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315141312/eb9507de-5963-43d1-b207-f60a521e202b/content/z.tif" xmlns:xlink="https://www.w3.org/1999/xlink"/> and https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315141312/eb9507de-5963-43d1-b207-f60a521e202b/content/cz.tif" xmlns:xlink="https://www.w3.org/1999/xlink"/>. These algorithms are based on factorization properties of polynomials and the direct sum property of modulo computation over such fields. Algorithms are described for cyclic as well as acyclic convolution. It is shown that under certain non-restrictive conditions, all the previously defined algorithms over https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315141312/eb9507de-5963-43d1-b207-f60a521e202b/content/z.tif" xmlns:xlink="https://www.w3.org/1999/xlink"/> and https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315141312/eb9507de-5963-43d1-b207-f60a521e202b/content/cz.tif" xmlns:xlink="https://www.w3.org/1999/xlink"/> are also valid over the rings of finite integers.
