Accession Number : AD0717209

Title :   A Note on Fast Cyclic Convolution,

Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Zalcstein,Y.

Report Date : 08 DEC 1970

Pagination or Media Count : 13

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)

Descriptors :   (*INTEGRAL TRANSFORMS, THEOREMS), FOURIER ANALYSIS, MATRICES(MATHEMATICS), PERMUTATIONS

Subject Categories : Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE