Accession Number : AD0646628
Title : AN ALGOL CONVOLUTION PROCEDURE BASED ON THE FAST FOURIER TRANSFORM.
Descriptive Note : Research memorandum,
Corporate Author : STANFORD RESEARCH INST MENLO PARK CALIF MATHEMATICAL SCIENCES DEPT
Personal Author(s) : Singleton,Richard C.
Report Date : JAN 1967
Pagination or Media Count : 15
Abstract : The body of the report was written as a contribution to the Algorithm section of the Communications of the ACM, and consists of three ALGOL procedures with comments. Two fast Fourier transform procedures, FASTFOURIERS and REVERSEFOURIERC, are included because of their use by procedure CONVOLUTION, but can be used independently. Procedure CONVOLUTION computes the convolution of two real vectors A and B of period n. If a noncircular convolution is wanted, the data vectors are extended by adding zeros before computing. The convolution is computed by first transforming A and B to Fourier coefficient vectors alpha and beta forming the complex conjugate product alpha beta, then computing the Fourier transform of alpha beta. The result of the final step is the desired convolution. Computing time for this method increases as n log 2 n, as compared to n2 for the direct method of computing lagged products. Tests show a 10 to 1 time advantage for the transform method at n = 256.
Descriptors : (*INTEGRAL TRANSFORMS, ALGORITHMS), (*VECTOR ANALYSIS, *ALGORITHMS), COMPUTER PROGRAMS, PROGRAMMING LANGUAGES, FOURIER ANALYSIS, SERIES(MATHEMATICS)
Subject Categories : Theoretical Mathematics
Computer Programming and Software
Distribution Statement : APPROVED FOR PUBLIC RELEASE