ON THE FAST FOURIER-TRANSFORM OF FUNCTIONS WITH SINGULARITIES

We consider a simple approach for the fast evaluation of the Fourier transform of functions with singularities based on projecting such functions on a subspace of Multiresolution Analysis. We obtain an explicit approximation of the Fourier Transform of generalized functions and develop a fast algorithm based on its evaluation. In particular, we construct an algorithm for the Unequally Spaced Fast Fourier Transform and test its performance in one and two dimensions. The number of operations required by algorithms of this paper is O(N . log N + N-p .(-log epsilon)) in one dimension and O(N-2 . log N + N-p .(-log epsilon)(2)) in two dimensions, where epsilon is the precision of computation, N is the number of computed frequencies and N, is the number of nodes. We also address the problem of using approximations of generalized functions for solving partial differential equation with singular coefficients or source terms. (C) 1995 Academic Press, Inc.