Worst and average case roundoff error analysis for FFT (Q5952348)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1688764
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Worst and average case roundoff error analysis for FFT |
scientific article; zbMATH DE number 1688764 |
Statements
Worst and average case roundoff error analysis for FFT (English)
0 references
9 January 2002
0 references
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.
0 references
numerical examples
0 references
fast Fourier transform
0 references
floating point arithmetic
0 references
twiddle factors
0 references
numerical stability
0 references
subdivision scaling
0 references
Cooley-Tukey factorization
0 references
discrete Fourier transform matrix
0 references
roundoff errors
0 references
0.9064309000968932
0 references
0.8324620127677917
0 references
