Nonuniform fast cosine transform and Chebyshev PSTD algorithms

We propose highly accurate forward and inverse nonuniform fast cosine transform (NUFCT) algorithms for data sampled nonuniformly. Using the fast interpolation with regular Fourier matrices, the NUFCT algorithms requires only O(N log2 N) arithmetic operations. These algorithms are then utilized in the Chebyshev pseudospectral time- domain (PSTD) method to solve Maxwell's equations on a nonuniform grid. Representing the fields and their derivatives in terms of Chebyshev polynomials, the derivatives on a nonuniform grid can be calculated with the NUFCT algorithms. The Chebyshev PSTD methods only requires π cells per wavelength on the average. Numerical results show the efficiency of the fast NUFCT and Chebyshev PSTD algorithms.