Efficient type-4 and type-5 non-uniform FFT methods in the one-dimensional case
Por favor, use este identificador para citar o enlazar este ítem:
http://hdl.handle.net/10045/84077
Título: | Efficient type-4 and type-5 non-uniform FFT methods in the one-dimensional case |
---|---|
Autor/es: | Selva, Jesus |
Grupo/s de investigación o GITE: | Señales, Sistemas y Telecomunicación |
Centro, Departamento o Servicio: | Universidad de Alicante. Departamento de Física, Ingeniería de Sistemas y Teoría de la Señal |
Palabras clave: | Non-uniform fast Fourier transform (NFFT) | Efficient methods | One-dimensional case |
Área/s de conocimiento: | Teoría de la Señal y Comunicaciones |
Fecha de publicación: | 8-feb-2018 |
Editor: | IET |
Cita bibliográfica: | IET Signal Processing. 2018, 12(1): 74-81. doi:10.1049/iet-spr.2016.0509 |
Resumen: | 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 |
Idioma: | eng |
Tipo: | info:eu-repo/semantics/article |
Derechos: | © The Institution of Engineering and Technology 2017 |
Revisión científica: | si |
Versión del editor: | https://doi.org/10.1049/iet-spr.2016.0509 |
Aparece en las colecciones: | INV - SST - Artículos de Revistas |
Archivos en este ítem:
Archivo | Descripción | Tamaño | Formato | |
---|---|---|---|---|
2018_Selva_IETSignalProcess_final.pdf | Versión final (acceso restringido) | 1,51 MB | Adobe PDF | Abrir Solicitar una copia |
2018_Selva_IETSignalProcess_accepted.pdf | Accepted Manuscript (acceso abierto) | 1,25 MB | Adobe PDF | Abrir Vista previa |
Todos los documentos en RUA están protegidos por derechos de autor. Algunos derechos reservados.