The equivalence of decimation in time and decimation in frequency in FFT computations
type: Item
instance of: scholarly article
title: The equivalence of decimation in time and decimation in frequency in FFT computations
zbMATH Open document ID: 0653.65034
DOI: 10.1016/0016-0032(87)90372-3
author: Nai-Kuan Tsao
published in: Journal of the Franklin Institute
publication date: 1987-01-01T00:00:00Z
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.
Mathematics Subject Classification ID: 65G50
Mathematics Subject Classification ID: 65T40
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4066230
zbMATH Keywords: data and error complexity
zbMATH Keywords: real division-free floating-point computations
zbMATH Keywords: complex floating-point computations
zbMATH Keywords: matrix-vector products
zbMATH Keywords: round-off error propagation
zbMATH Keywords: fast Fourier transform
zbMATH Keywords: statistical mean error behaviour
reviewed by: Vítězslav Veselý
MaRDI profile type: Publication
full work available at URL: 0016-0032(87)90372-3
OpenAlex ID: W2015425419
cites work: An Algorithm for the Machine Calculation of Complex Fourier Series
cites work: A Generalized Asymptotic Upper Bound on Fast Polynomial Evaluation and Interpolation
cites work: Fast Algorithms for Partial Fraction Decomposition
cites work: Accumulation of Round-Off Error in Fast Fourier Transforms
cites work: Roundoff Error Analysis of the Fast Fourier Transform
cites work: Error Complexity Analysis of Algorithms for Matrix Multiplication and Matrix Chain Product
cites work: Q4342463
cites work: A Round-Off Error Model with Applications to Arithmetic Expressions
description: scientific article; zbMATH DE number 4066230