Worst and average case roundoff error analysis for FFT

被引：18

作者：

Tasche, M

Zeuner, H

机构：

[1] Univ Rostock, Dept Math, D-18051 Rostock, Germany

[2] Med Univ Lubeck, Inst Math, D-23560 Lubeck, Germany

来源：

BIT NUMERICAL MATHEMATICS | 2001年 / 41卷 / 03期

关键词：

roundoff error analysis; worst case study; average case study; precomputed twiddle factors; fast Fourier transform;

D O I：

10.1023/A:1021923430250

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

This paper presents both worst case and average case analysis of roundoff errors occuring in the floating point computation of fast Fourier transform (FFT) with precomputed twiddle factors and shows the strong influence of precomputation errors on the numerical stability of FFT. Numerical tests confirm the theoretical results.

引用

页码：563 / 581

页数：19

共 13 条

[1]

[Anonymous], 1997, ALGORITHMS DISCRETE

[2]

[Anonymous], HDB ANAL COMPUTATION

[3] Componentwise error analysis for FFTs with applications to fast Helmholtz solvers [J].