Fast Fourier transforms for nonequispaced data. II (Q1345056)

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)].