Published in

Association for Computing Machinery (ACM), ACM Transactions on Mathematical Software, 2(46), p. 1-27, 2020

DOI: 10.1145/3368619

Links

Tools

Export citation

Search in Google Scholar

Error Analysis of Some Operations Involved in the Cooley-Tukey Fast Fourier Transform

This paper is available in a repository.
This paper is available in a repository.

Full text: Download

Green circle
Preprint: archiving allowed
Green circle
Postprint: archiving allowed
Red circle
Published version: archiving forbidden
Data provided by SHERPA/RoMEO

Abstract

We are interested in obtaining error bounds for the classical Cooley-Tukey fast Fourier transform algorithm in floating-point arithmetic, for the 2-norm as well as for the infinity norm. For that purpose, we also give some results on the relative error of the complex multiplication by a root of unity, and on the largest value that can take the real or imaginary part of one term of the fast Fourier transform of a vector x , assuming that all terms of x have real and imaginary parts less than some value b .