Error analysis of some operations involved in the Fast Fourier Transform

Nicolas Brisebarre (1) , Mioara Joldes (2) , Jean-Michel Muller (1) , Ana-Maria Naneş (3) , Joris Picot (1)

1 ARIC - Arithmetic and Computing
2 LAAS-MAC - Équipe Méthodes et Algorithmes en Commande
3 Technical University of Cluj-Napoca

We are interested in obtaining error bounds for the classical FFT 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 FFT of a vector x, assuming that all terms of x have real and imaginary parts less than some value b.

Mots clés: Fast Fourier Transform; Floating-point arithmetic; Rounding error analysis

Domaines: Autre [cs.OH]; Arithmétique des ordinateurs

Nicolas Brisebarre, Mioara Joldes, Jean-Michel Muller, Ana-Maria Naneş, Joris Picot. Error analysis of some operations involved in the Fast Fourier Transform. 2018. ⟨hal-01949458v1⟩