ON THE FAST FOURIER-TRANSFORM OF FUNCTIONS WITH SINGULARITIES

We consider a simple approach for the fast evaluation of the Fourier t ransform of functions with singularities based on projecting such func tions on a subspace of Multiresolution Analysis. We obtain an explicit approximation of the Fourier Transform of generalized functions and d evelop a fast algorithm based on its evaluation. In particular, we con struct an algorithm for the Unequally Spaced Fast Fourier Transform an d test its performance in one and two dimensions. The number of operat ions 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 i s the number of computed frequencies and N, is the number of nodes. We also address the problem of using approximations of generalized funct ions for solving partial differential equation with singular coefficie nts or source terms. (C) 1995 Academic Press, Inc.