Combining triangle Gaussian integration and modified NUFFT for evaluating two-dimensional Fourier transform integrals

The regular fast Fourier transform (FFT) requires a uniform Cartesian orthogonal grid which has considerable stair-casing errors when dealing with the function having an arbitrary shape boundary. The recently proposed two-dimensional discontinuous fast Fourier transform (2D-DFFT) can overcome this problem by using triangle mesh discretization and Gaussian numerical integration. However, the interpolation is used for the function data in the original 2D-DFFT, which reduces the accuracy performance especially for the case of oscillating functions. This work presents a useful modification of the original 2D-DFFT by removing the requirement of function interpolation to obtain significant accuracy improvement. In addition, the modified 2D nonuniform fast Fourier transform (NUFFT) with real-valued least-square interpolation coefficients are developed to speed up the computation of numerical Fourier transform over the triangle mesh. Numerical experiments are conducted to demonstrate the effectiveness and advantages of the proposed algorithms.