On the fast Fourier transform of functions with singularities (Q1907304)

This paper gives a fast algorithm for the Fourier transform of functions with singularities. In particular, this paper contracts an algorithm for the fast Fourier transform on unequally spaced samples and tests its performance. The number of operations required in this algorithm is \(O(N \log N + N_p (- \log \xi))\) in one dimension, and \(O(N^2 \log N + N_p (- \log \xi)^2)\) in two dimension, where \(N\) is the number of computed frequencies, \(N_p\) is the number of nodes, and \(\xi\) is the precision of computation.