Sum-accelerated pseudospectral methods: the Euler-accelerated sinc algorithm

Pseudospectral discretizations of differential equations are much more accurate than finite differences for the same number of grid points N. The reason is that derivatives are approximated by a weighted sum of all N values of u(x,), rather than just three as in a second-order finite difference. The price is that the N X N pseudospectral matrix is dense with N nonzero elements (rather than three) in each row. Truncating the pseudospectral sums to create a sparse discretization fails because the derivative series are alternating and very slowly convergent. However, these series are perfect candidates for sum-acceleration methods. We show that the Euler summation can be applied to a standard pseudospectral scheme to produce an algorithm which is both exponentially accurate (like any other spectral method) and yet generates sparse matrices (like a finite difference method). For illustration, we use the sine basis with an evenly spaced grid on x E [- co, 001. However, the same techniques apply equally well to Chebyshev and Fourier polynomials. 1