Worst and average case roundoff error analysis for FFT

DOI10.1023/A:1021923430250MaRDI QIDQ5952348zbMATH OpenOpenAlexFDO

Authors Manfred Tasche, Hm. Zeuner

Publication date 9 January 2002

Published in BIT (Search for Journal in Brave)

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

zbMATH Keywords

Cooley-Tukey factorizationdiscrete Fourier transform matrixfast Fourier transformfloating point arithmeticnumerical examplesnumerical stabilityroundoff errorssubdivision scalingtwiddle factors

Mathematics Subject Classification ID

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

Review text

The paper deals with the stability of the fast Fourier transform (FFT) in floating point arithmetic. It is shown that FFTs are very sensitive with respect to the accuracy of the precomputation of the twiddle factors. The best results with respect to the numerical stability are obtained if the twiddle factors are precomputed by direct call or by repeated subdivision scaling. The analysis is based on the Cooley-Tukey factorization of the discrete Fourier transform matrix into a product of sparse unitary matrices. The paper presents both worst and average case analysis of roundoff errors. Numerical tests illustrate the theoretical results.

Recommendations

• Roundoff error analysis for fast trigonometric transforms
• scientific article; zbMATH DE number 1421270
• scientific article; zbMATH DE number 1971052
• scientific article; zbMATH DE number 2141510
• A Stochastic Roundoff Error Analysis for the Fast Fourier Transform

Cited in

(12)

• Accurate pairwise convolutions of non-negative vectors via FFT
• Roundoff error analysis of the recursive moving window discrete Fourier transform
• Quantum Fourier transform in computational basis
• Roundoff error analysis for fast trigonometric transforms
• A Stochastic Roundoff Error Analysis for the Fast Fourier Transform
• scientific article; zbMATH DE number 1971052 (Why is no real title available?)
• scientific article; zbMATH DE number 2141510 (Why is no real title available?)
• Accuracy of the Discrete Fourier Transform and the Fast Fourier Transform
• Numerical stability of biorthogonal wavelet transforms
• On numerical realizations of Shannon's sampling theorem
• Regularized Shannon sampling formulas related to the special affine Fourier transform
• Numerical stability of nonequispaced fast Fourier transforms

Describes a project that uses

Uses Software

• mctoolbox

This page was built for publication: Worst and average case roundoff error analysis for FFT

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