Efficient type-4 and type-5 non-uniform FFT methods in the one-dimensional case

Please use this identifier to cite or link to this item: http://hdl.handle.net/10045/84077
Información del item - Informació de l'item - Item information
Title: Efficient type-4 and type-5 non-uniform FFT methods in the one-dimensional case
Authors: Selva, Jesus
Research Group/s: Señales, Sistemas y Telecomunicación
Center, Department or Service: Universidad de Alicante. Departamento de Física, Ingeniería de Sistemas y Teoría de la Señal
Keywords: Non-uniform fast Fourier transform (NFFT) | Efficient methods | One-dimensional case
Knowledge Area: Teoría de la Señal y Comunicaciones
Issue Date: 8-Feb-2018
Publisher: IET
Citation: IET Signal Processing. 2018, 12(1): 74-81. doi:10.1049/iet-spr.2016.0509
Abstract: The so-called non-uniform fast Fourier transform (NFFT) is a family of algorithms for efficiently computing the Fourier transform of finite-length signals, whenever the time or frequency grid is non-uniformly spaced. Among the five usual NFFT types, types 4 and 5 involve an inversion problem, and this makes them the most intensive computationally. The usual efficient methods for these last types are either based on a fast multipole (FM) or on an iterative conjugate gradient (CG) method. The purpose of this study is to present efficient methods for these type-4 and type-5 NFFTs in the one-dimensional case that just require three NFFTs of types 1 or 2 plus some additional fast Fourier transforms (FFTs). Fundamentally, they are based on exploiting the Lagrange formula structure. The proposed methods roughly provide a factor-ten improvement on the FM and CG alternatives in computational burden. The study includes several numerical examples in double precision, in which the proposed and the Gaussian elimination, CG and FM methods are compared, both in terms of round-off error and computational burden.
URI: http://hdl.handle.net/10045/84077
ISSN: 1751-9675 (Print) | 1751-9683 (Online)
DOI: 10.1049/iet-spr.2016.0509
Language: eng
Type: info:eu-repo/semantics/article
Rights: © The Institution of Engineering and Technology 2017
Peer Review: si
Publisher version: https://doi.org/10.1049/iet-spr.2016.0509
Appears in Collections:INV - SST - Artículos de Revistas

Files in This Item:
Files in This Item:
File Description SizeFormat 
Thumbnail2018_Selva_IETSignalProcess_final.pdfVersión final (acceso restringido)1,51 MBAdobe PDFOpen    Request a copy
Thumbnail2018_Selva_IETSignalProcess_accepted.pdfAccepted Manuscript (acceso abierto)1,25 MBAdobe PDFOpen Preview


Items in RUA are protected by copyright, with all rights reserved, unless otherwise indicated.