Fast approximate Fourier transforms for nonequispaced data.

摘要

In recent years, several authors have addressed the problem of efficiently computing generalized discrete Fourier transforms ( GDFTs) and generalized inverse discrete Fourier transforms (GIDFTs), which are characterized by nonequispaced data. We call such rapid algorithms for GDFTs fast approximate Fourier transforms (FAFTs) and those for GIDFTs inverse fast approximate Fourier transforms (IFAFTs).; In this thesis, we develop a new one-dimensional (1D) fast algorithm using Hermite interpolation based on Hermite divided difference. We then extend 1D GIDFTs to higher dimensions in two different ways. We present multidimensional IFAFTs using ID IFAFTs in every dimension for GIDFTs defined on an irregular grid of points, and such IFAFTs are called dimension-by-dimension (DD) IFAFTs. We also present multidimensional fast algorithms that combine 1D IFAFTs with direct computation for GIDFTs defined on an arbitrary set of points, and such fast algorithms are called modified DD-IFAFTs. For further improvements, we develop direct multidimensional IFAFTs using Taylor series expansion, polynomial interpolation based on multidimensional divided difference and Hermite interpolation based on multidimensional Hermite divided difference for GIDFTs defined on an arbitrary set of points. Definitions, propositions, theorems and corollaries related to our IFAFTs are presented. Complexity, storage, and error analysis are provided for the new algorithms. Because ID Hermite interpolation needs only the first order derivative and 2D or 3D Hermite interpolation needs only 3 or 7 partial derivatives with orders up to 2 or 3 at every point, whereas Taylor series expansion needs all derivatives or partial derivatives up to a high order, it is expected that Hermite interpolation is applicable more widely than Taylor series expansion. We can use polynomial interpolation when the efficiency is more important and the accuracy is acceptable. Our algorithms can also be used for rapid computation of ID and multidimensional DFTs when the FFTs do not suit our needs. To speed up the calculation and to enlarge the sizes of solvable problems, we develop parallel algorithms corresponding to the three direct multidimensional IFAFTs using MPI based code. Numerical results are presented, and comparisons among algorithms are provided, Conclusions and further developments are also given.