Discontinuous Fast Fourier Transform with Triangle Mesh for Two-dimensional Discontinuous Functions

Abstract

In computational electromagnetics and other areas of computational science, Fourier transforms of discontinuous functions are frequently encountered. This paper extends the discontinuous fast Fourier transform (DFFT) algorithm which was presented previously by Fan and Liu to deal with the two dimensional (2-D) function with a discontinuous boundary of arbitrary shape. First, the proposed algorithm discretizes the support domain of the function by triangle mesh, which reduces the stair-casing error of an orthogonal grid required by FFT. Second, the algorithm adopts the basic idea of double interpolation used by the original 1-D DFFT algorithm in the literature, but with a significant modification that the nonuniform fast Fourier transform (NUFFT) with the least square error (LSE) interpolation other than a Lagrange interpolation is used to process nonuniformly spaced samples of the exponentials. The proposed 2-D DFFT algorithms obtain much higher accuracy than the conventional 2-D FFT for the discontinuous functions while maintaining similar computational complexity as that of the 2-D FFT.