PuSH - Publication Server of Helmholtz Zentrum München

Kunis, S. ; Melzer, I.*

A stable and accurate butterfly sparse fourier transform.

SIAM J. Numer. Anal. 50, 1777-1800 (2012)
Publ. Version/Full Text Volltext DOI
Free by publisher
Open Access Green as soon as Postprint is submitted to ZB.
Recently, the butterfly approximation scheme was proposed for computing Fourier transforms with sparse and smooth sampling in the frequency and spatial domains. We present a rigorous error analysis which shows how the local expansion degree depends on the target accuracy and the nonharmonic bandwidth. Moreover, we show that the original scheme becomes numerically unstable if a large local expansion degree is used. This problem is removed by representing all approximations in a Lagrange-type basis instead of the previously used monomial basis. All theoretical results are illustrated by numerical experiments.
Altmetric
Additional Metrics?
[➜Log in]
Edit extra informations Login
Publication type Article: Journal article
Document type Scientific Article
Corresponding Author
Keywords Trigonometric Approximation ; Nonharmonic Fourier Series ; Fast Fourier Transform; Algorithm
ISSN (print) / ISBN 0036-1429
e-ISSN 1095-7170
Journal SIAM Journal on Numerical Analysis
Quellenangaben Volume: 50, Issue: 3, Pages: 1777-1800 Article Number: , Supplement: ,
Publisher Society for Industrial and Applied Mathematics (SIAM)
Non-patent literature Publications
Reviewing status Peer reviewed
Institute(s) Institute of Biomathematics and Biometry (IBB)