A. Averbuch et al., A FAST POISSON SOLVER OF ARBITRARY ORDER ACCURACY IN RECTANGULAR REGIONS, SIAM journal on scientific computing, 19(3), 1998, pp. 933-952
In this paper we propose a direct method for the solution of the Poiss
on equation in rectangular regions. It has an arbitrary order accuracy
and low CPU requirements which makes it practical for treating large-
scale problems. The method is based on a pseudospectral Fourier approx
imation and a polynomial subtraction technique. Fast convergence of th
e Fourier series is achieved by removing the discontinuities at the co
rner points using polynomial subtraction functions. These functions ha
ve the same discontinuities at the corner points as the sought solutio
n. In addition to this, they satisfy the Laplace equation so that the
subtraction procedure does not generate nonperiodic, nonhomogeneous te
rms. The solution of a boundary value problem is obtained in a series
form in O(N log N) floating point operations, where N-2 is the number
of grid nodes. Evaluating the solution at all N-2 interior points requ
ires O(N-2 log N) operations.