A Note on Fast Cyclic Convolution,
Abstract
The note presents a new algorithm for computing the cyclic convolution of two vectors over a commutative ring. The algorithm requires n((n sub 1)+1)...((n sub k)+1)/(2 to the kth power) multiplications for the convolution of two n-vectors, where n=(n sub 1)...(n sub k) is a factorization of n into factors which are pairwise relatively prime. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 08, 1970
- Accession Number
- AD0717209
Entities
People
- Y. Zalcstein
Organizations
- Carnegie Mellon University