Fast Fourier transforms for nonequispaced data. II
type: Item
instance of: scholarly article
title: Fast Fourier transforms for nonequispaced data. II
zbMATH Open document ID: 0822.65130
published in: Applied and Computational Harmonic Analysis
publication date: 1995-03-01T00:00:00Z
review text: The paper proposes an \(O(N\log N+ N\log(1/\varepsilon))\) algorithm for the computation of the discrete Fourier transform on nonequispaced data, where \(\varepsilon\) denotes the desired accuracy. The algorithm is based on the fast (adaptive) multipole method with respect to the kernel \(1/\tan(x- y)\). It works for the transposed and for the inverse transforms in the same manner. Therefore, especially the inverse transforms are more efficient than a previous method of the authors in part I [SIAM J. Sci. Comput. 14, No. 6, 1368-1393 (1993; Zbl 0791.65108)]. The algorithm should be compared with the direct \(O(N\log^ 2 N)\) algorithm of \textit{S. S. B. Moore}, \textit{D. M. Healy} and \textit{D. N. Rockmore} [Linear Algebra Appl. 192, 249-299 (1993; Zbl 0786.65130)].
Mathematics Subject Classification ID: 65T50
zbMATH DE Number: 727208
zbMATH Keywords: algorithm
zbMATH Keywords: discrete Fourier transform
zbMATH Keywords: fast (adaptive) multipole method
zbMATH Keywords: inverse transforms
author: Alok Dutt
author: Vladimir Rokhlin
reviewed by: Gabriele Steidl
MaRDI profile type: Publication
full work available at URL: acha.1995.1007
OpenAlex ID: W1998152471
DOI: 10.1006/ACHA.1995.1007
description: scientific article; zbMATH DE number 727208