The FFT requires O(N log N) work to compute N Fourier modes from N data points rather than O(N2) work.
When the data is irregular in either the "physical" or "frequency" domain, unfortunately, the FFT does not apply. Over the last twenty years, a number of algorithms have been developed to overcome this limitation - generally referred to as non-uniform FFTs (NUFFT), non-equispaced FFTs (NFFT) or unequally-spaced FFTs (USFFT). They achieve the same O(N log N) computational complexity, but with a larger, precision-dependent, and dimension-dependent constant.
We have developed some NUFFT libraries in Fortran 77 and Fortran 90 that are freely available under the GPL license.
A new, high performance version of the NUFFT which is significantly faster than the NUFFT codes on this page (especially for dimensions greater than 1) can be found at FINUFFT .
Please acknowledge the NUFFT package in programs or publications in
which you use the code. We suggest as references:
 Accelerating the Nonuniform Fast Fourier Transform:
(L. Greengard and J.-Y. Lee)
SIAM Review 46, 443 (2004).
 The type 3 nonuniform FFT and its applications: (J.-Y. Lee and L. Greengard) J. Comput. Phys. 206, 1 (2005).
For the original NUFFT paper, see
Fast Fourier Transforms for Nonequispaced data: (A. Dutt and V. Rokhlin) SIAM J. Sci. Comput. 14, 1368 (1993).
LATEST RELEASE: includes MATLAB interfaces (fixed MATLAB
incompatibility for Mac OS X: 8/04/2014)