  The so-called non-uniform FFT (NFFT) is a family of algorithms for
efficiently computing the Fourier transform of finite-length signals, whenever
the time or frequency grid is nonuniformly spaced. Following the usual
classification, there exist five NFFT types. Types 1 and 2 make it possible to
pass from the time to the frequency domain with nonuniform input and output
grids respectively. Type 3 allows for both input and output nonuniform grids.
Finally, types 4 and 5 are the inverses of types 1 and 2 and are expensive
computationally, given that they involve iterative methods. In this paper, we
solve this last drawback in the one-dimensional case by presenting
non-iterative type 4 and 5 NFFT methods that just involve three NFFTs of types
1 or 2 plus some additional FFTs. The methods are based on exploiting the
structure of the Lagrange interpolation formula. The paper includes several
numerical examples in which the proposed methods are compared with the Gaussian
elimination (GE) and conjugate gradient (CG) methods, both in terms of
round-off error and computational burden.
