Fast pseudospectral algorithms for boundary value problems for the Laplace equation on a rectangle

We present a fast pseudospectral algorithm for the solution of the Laplace equation with Dirichlet boundary data on a rectangle. We construct the solution by the method of separation of variables. The boundary data on each side is approximated by trigonometric polynomials with half-integer frequencies, resulting in a pseudospectral convergence. With N nodes per side, this approximation is performed in O(N2 log N) floating point operations using the Fast Fourier Transform. The final solution is a combination of seperable solutions obtained from the trigonometric polynomials on the boundary. The pseudospectral accuracy of the method is justified theoretically.