Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

A stochastic roundoff error analysis for the fast Fourier transform


Author: Daniela Calvetti
Journal: Math. Comp. 56 (1991), 755-774
MSC: Primary 65T20; Secondary 65G05
MathSciNet review: 1068824
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We study the accuracy of the output of the Fast Fourier Transform by estimating the expected value and the variance of the accompanying linear forms in terms of the expected value and variance of the relative roundoff errors for the elementary operations of addition and multiplication. We compare the results with the corresponding ones for the direct algorithm for the Discrete Fourier Transform, and we give indications of the relative performances when different rounding schemes are used. We also present the results of numerical experiments run to test the theoretical bounds and discuss their significance.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65T20, 65G05

Retrieve articles in all journals with MSC: 65T20, 65G05


Additional Information

DOI: http://dx.doi.org/10.1090/S0025-5718-1991-1068824-0
PII: S 0025-5718(1991)1068824-0
Keywords: Accompanying linear forms, floating-point arithmetic, Radix-2 Fast Fourier Transform, rounding errors, random variables
Article copyright: © Copyright 1991 American Mathematical Society