The equivalence of decimation in time and decimation in frequency in FFT computations

DOI10.1016/0016-0032(87)90372-3MaRDI QIDQ1107953zbMATH OpenOpenAlexFDO

Authors Nai-Kuan Tsao

Publication date 1987

Published in Journal of the Franklin Institute (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0016-0032(87)90372-3

zbMATH Keywords

complex floating-point computationsdata and error complexityfast Fourier transformmatrix-vector productsreal division-free floating-point computationsround-off error propagationstatistical mean error behaviour

Mathematics Subject Classification ID

Roundoff error (65G50) Numerical methods for trigonometric approximation and interpolation (65T40) Analysis of algorithms and problem complexity (68Q25)

Review text

The author extends his data and error complexity concepts in real division-free floating-point computations [IEEE Trans. Comput. C-30, 758- 771 (1981; Zbl 0464.68047)] to complex floating-point computations inclusively matrix-vector products and applies them to the analysis of round-off error propagation in two different power-of-2 fast Fourier transform (FFT) algorithms - the decimation in time FFT and the decimation in frequency FFT. Both algorithms are shown to be ``equivalent (they produce the same error characteristics on output) under the assumption that all components of the input vector are ``equivalent as well. This theoretical result is very well evidenced with several numerical experiments and reaffirms previous conclusions based on statistical mean error behaviour.

Recommendations

• A Stochastic Roundoff Error Analysis for the Fast Fourier Transform
• Floating point error analysis of two-dimensional, fast Fourier transform algorithms
• An improved fast Fourier transform algorithm using mixed frequency and time decimations
• Some results in fixed point error analysis of the Bruun-FTT algorithm
• Fast and precise Fourier transforms

Cites work

• A Generalized Asymptotic Upper Bound on Fast Polynomial Evaluation and Interpolation
• A Round-Off Error Model with Applications to Arithmetic Expressions
• Accumulation of Round-Off Error in Fast Fourier Transforms
• An Algorithm for the Machine Calculation of Complex Fourier Series
• Error Complexity Analysis of Algorithms for Matrix Multiplication and Matrix Chain Product
• Fast Algorithms for Partial Fraction Decomposition
• scientific article; zbMATH DE number 1024452 (Why is no real title available?)
• Roundoff Error Analysis of the Fast Fourier Transform

This page was built for publication: The equivalence of decimation in time and decimation in frequency in FFT computations

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