Roundoff error analysis of the recursive moving window discrete Fourier transform

DOI10.1023/A:1021254709641MaRDI QIDQ1869353zbMATH OpenOpenAlexFDO

Authors Manfred Tasche, Hm. Zeuner

Publication date 10 April 2003

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

Full work available at URL https://doi.org/10.1023/a:1021254709641

zbMATH Keywords

average case studydiscrete windowed fast Fourier transformfast Fourier transformnumerical stabilityroundoff errorworst case study

Mathematics Subject Classification ID

Roundoff error (65G50) Numerical methods for discrete and fast Fourier transforms (65T50)

Review text

The authors give a detailed analysis of roundoff errors for the recursive moving window discrete Fourier transform with precomputed twiddle factors. As in the spirit of their papers [Handbook of analytic-computational methods in applied mathematics (2000; Zbl 0976.65123); BIT 41, 563--581 (2001; Zbl 0999.65152)] they study a worst case and an average case scenario. The latter assumes uncorrelated data, although the results can be extended to correlated data under additional conditions. The analysis shows that there is a similar behavior as it is known for the fast Fourier transform [cf. \textit{N. J. Higham}, Accuracy and stability of numerical algorithms (2002; Zbl 1011.65010)], i.e., there is a strong influence on the numerical stability of the accuracy of the initial fast Fourier transform and the error in the recursion step. Based on their error analysis, the authors present an improved version of the moving window discrete Fourier transform

Recommendations

• A Stochastic Roundoff Error Analysis for the Fast Fourier Transform
• Fixed-point round-off error analysis for the discrete cosine transform
• Worst and average case roundoff error analysis for FFT
• scientific article; zbMATH DE number 5038973
• Characterizing discrete Fourier transform errors in signal processing by inner product
• Roundoff error analysis of fast DCT algorithms in fixed point arithmetic
• Floating point error analysis of two-dimensional, fast Fourier transform algorithms
• On the Fixed-Point Accuracy Analysis of FFT Algorithms
• An accurate error analysis model for fast Fourier transform
• Roundoff error analysis for fast trigonometric transforms

Cited in

(5)

• Coarse quantization of highly redundant time-frequency representations of square-integrable functions
• scientific article; zbMATH DE number 3862403 (Why is no real title available?)
• scientific article; zbMATH DE number 1971052 (Why is no real title available?)
• Characterizing discrete Fourier transform errors in signal processing by inner product
• scientific article; zbMATH DE number 5038973 (Why is no real title available?)

This page was built for publication: Roundoff error analysis of the recursive moving window discrete Fourier transform

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