Worst and average case roundoff error analysis for FFT (Q5952348)

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.