The equivalence of decimation in time and decimation in frequency in FFT computations (Q1107953)

The author extends his data and error complexity concepts in real division-free floating-point computations [IEEE Trans. Comput. C-30, 758- 771 (1981; Zbl 0464.68047)] to complex floating-point computations inclusively matrix-vector products and applies them to the analysis of round-off error propagation in two different power-of-2 fast Fourier transform (FFT) algorithms - the decimation in time FFT and the decimation in frequency FFT. Both algorithms are shown to be ``equivalent'' (they produce the same error characteristics on output) under the assumption that all components of the input vector are ``equivalent'' as well. This theoretical result is very well evidenced with several numerical experiments and reaffirms previous conclusions based on statistical mean error behaviour.