The regular Fourier matrices and nonuniform fast Fourier transforms

For any triple of positive integers (rn, N, q), the matrix F(m, N, q), call ed the (m, N, q)-regular Fourier matrix, is defined. The regular Fourier ma trices F(m, N, q) are then applied to set up new algorithms for nonuniform fast Fourier transforms. Numerical results show that the accuracies obtaine d by our algorithms are much better than previously reported results with t he same computation complexity. The algorithms require O(N . log(2) N) arit hmetic operations, where N is the number of data points.