Componentwise error analysis for FFTs with applications to fast Helmholtz solvers (Q1921320)

The authors present a componentwise error analysis for the fast Fourier transform of order \(n = 2^k\) and for its inverse, based on the Cooley-Tuckey algorithm. In this connection they assume that the computations are done using a rounded arithmetic. They describe the structure of the error matrix and they improve known bounds for the total error in the maximum norm and in the \(L_2\) norm. In addition, they derive statistical properties of the algorithmic error under some hypotheses on the distribution of the rounding errors. Numerical experiments are reported which confirm the statistical error bounds. The results are applied to turbulence theory using spectral methods, and to the roundoff error analysis of fast solvers for the Helmholtz equation when these solvers are based on the fast Fourier transform.