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

descriptionPublicationkeyboard_double_arrow_right Article 19 May 2020 France English Publisher:Association for Computing Machinery (ACM)Journal:ACM Transactions on Mathematical Software, volume 46, pages 1-27 (issn: 0098-3500, eissn: 1557-7295,

Copyright policy )

Authors: Brisebarre, Nicolas; Joldes, Mioara; Muller, Jean-Michel; Naneş, Ana-Maria; Picot, Joris;

doi: 10.1145/3368619

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

- Summary
- Subjects
- Metrics

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 .

Country

France

Related Organizations

View all View all

Keywords

[INFO.INFO-AO]Computer Science [cs]/Computer Arithmetic, Numeric approximation algorithms, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], Fast Fourier Transform, Floating-point arithmetic, 510, 004, [INFO.INFO-OH] Computer Science [cs]/Other [cs.OH], Rounding error analysis, • Theory of computation → Design and analysis of algorithms, Additional Key Words and Phrases: Floating-point arithmetic, Rounding error analysis ACM Reference format:, CCS Concepts: • Mathematics of computing → Mathematical software, [INFO.INFO-AO] Computer Science [cs]/Computer Arithmetic

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	13
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Top 10%
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 10%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Top 10%