ABSTRACT
The fast Fourier transform (FFT) and related fast trigonometric transforms are nowadays essential tools for practical computations. It is very important that fast algorithms work stable in a floating point arithmetic. This survey paper presents both worst case and average case analysis of roundoff errors occuring in floating point computation of FFTs with precomputed twiddle factors and show the strong influence of precomputation errors on the numerical stability of FFT. The results are mainly based on a factorization of the Fourier matrix into a product of almost unitary and sparse matrices. Finally we consider roundoff errors of fast convolutions and fast algorithms for discrete cosine/sine transforms.
