Fast algorithms for computing one- and two-dimensional convolution in integer polynomial rings
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.
- A fast computation of complex convolution using a hybrid transform
- Convolution using a conjugate symmetry property for number theoretic transforms over rings of regular integers
- Convolution using a conjugate symmetry property for the generalized discrete Fourier transform
- Convolutions of long integer sequences by means of number theoretic transforms over residue class polynomial rings
- Digital filtering using pseudo fermat number transforms
- Discrete Convolutions via Mersenne Transforms
- Discrete transforms over polynomial rings with applications in computing multidimensional convolutions
- Number theoretic transforms for the calculation of convolutions
- On the factorization of polynomials and direct sum properties in integer polynomial rings
- Rings, fields, the Chinese remainder theorem and an extension-Part I: theory
- Rings, fields, the Chinese remainder theorem and an extension-Part II: applications to digital signal processing
- The AICE-CRT and digital signal processing algorithms: The complex case
- The Discrete Fourier Transform Over Finite Rings with Application to Fast Convolution
- The generalized discrete Fourier transform in rings of algebraic integers
- Two-dimensional convolutions by means of number theoretic transforms over residue class polynomial rings
- A fast algorithm for exact convolution of rational sequences by using integer arithmetics only
- A novel modularized fast polynomial transform algorithm for two- dimensional convolutions
- The AICE-CRT and digital signal processing algorithms: The complex case
- On the factorization of polynomials and direct sum properties in integer polynomial rings
- An efficient method for performing discrete convolution using Kronecker products
- Two-dimensional convolutions by means of number theoretic transforms over residue class polynomial rings
- scientific article; zbMATH DE number 3980375 (Why is no real title available?)
- scientific article; zbMATH DE number 179269 (Why is no real title available?)
- scientific article; zbMATH DE number 2058027 (Why is no real title available?)
- Application of modular computing technique for high speed implementation of cyclic convolution
- Two optimum algorithms for short convolutions
- Convolution algorithms, based on the CRT (Chinese remainder theorem).
- On fast algorithms for one-dimensional digital signal processing in finite integer and complex integer rings
- Automatic derivation and implementation of fast convolution algorithms
This page was built for publication: Fast algorithms for computing one- and two-dimensional convolution in integer polynomial rings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q677546)
