Modified Winograd FFT algorithm and its variants for transform size N=p^ k and their implementations

DOI10.1016/0196-8858(89)90012-2MaRDI QIDQ1823640zbMATH OpenOpenAlexFDO

Authors Chao Lu, Robert W. Johnson, R. Tolimieri

Publication date 1989

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0196-8858(89)90012-2

zbMATH Keywords

fast Fourier transformFFT-algorithmsparallel computingWinograd's algorithm

Mathematics Subject Classification ID

Trigonometric interpolation (42A15) Numerical methods for trigonometric approximation and interpolation (65T40) Parallel numerical computation (65Y05)

Review text

The present paper is the continuation of a program, initiated by the authors [IEEE Trans. Acoust. Speech Signal Process (to appear)]. They propose two FFT-algorithms with highly structured data flow and transformation size \(N=p^ 2\), where p is an odd prime. One algorithm is suited for parallel computing while the other one with a better operational count is suited for conventional serial machines. The operational counts of these algorithms are close to those of Winograd's algorithm, but the better structure simplifies their implementations.

Recommendations

• FFT algorithms for prime transform sizes and their implementations on VAX, IBM3090VF, and IBM RS/6000
• scientific article; zbMATH DE number 991433
• On the structure of efficient DFT algorithms
• scientific article; zbMATH DE number 3938512
• Modified FFTs for Fused Multiply-Add Architectures

Cites work

• scientific article; zbMATH DE number 3140885 (Why is no real title available?)
• scientific article; zbMATH DE number 3839315 (Why is no real title available?)
• On computing the Discrete Fourier Transform
• On Computing the Discrete Fourier Transform

Cited in

(3)

• scientific article; zbMATH DE number 3938512 (Why is no real title available?)
• FFT algorithms for prime transform sizes and their implementations on VAX, IBM3090VF, and IBM RS/6000
• Automatic parallel library generation for general-size modular FFT algorithms

This page was built for publication: Modified Winograd FFT algorithm and its variants for transform size \(N=p^ k\) and their implementations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1823640)