FFT-based 2D Poisson solvers
In this lecture, we discuss Fourier spectral methods for accurately solving multidimensional Poisson equations
on rectangular domains subject to periodic, homogeneous Dirichlet or Neumann BCs. We also note how the
DFT can be used to efficiently solve finite-difference approximations to such equations. The methods can
be generalized to other elliptic equations with only even derivatives.
WIth N = 2
p
gridpoints along each of d dimensions, the methods require O(N
d
log N) flops, or O(log N )
flops per gridpoint, which is close to the best possible efficiency of O(1) flops per gridpoint. For large N and
d ≥ 2 this is better efficiency than a direct sparse LU solver applied to the FDA matrix problem.
The two-dimensional Poisson problem
Consider a two-dimensional Poisson equation:
u
xx
+ u
y y
= f(x, y), (1)
on a periodic domain [0, L] × [0, L]. The Fourier gridpoints are (x
j
, y
l
), where x
j
= (j − 1)h, y
l
= (l − 1)h,
and h = L/N. The spectral approximation to the solution is
u(x, y) = N
−2
N
X
m=1
N
X
n=1
U
mn
exp[i(k
n
x + l
p
y)]
with k
n
= 2πM
n
/L defined in terms of the harmonics M
n
as in the 1D case, and l
p
defined similarly. We
define u
jl
= u(x
j
, y
l
). We now search for the approximate solution that exactly solves (1) at the Fourier
gridpoints. This is
ˆ
f = DF T
x
(DF T
y
(f)),
ˆu
np
= −
ˆ
f
np
/(k
2
n
+ l
2
p
),
ˆu
11
= 0,
ˆ
u = IDF T
x
(IDF T
y
(
ˆ
u))
We have assumed the solvability condition
ˆ
f
11
= 0 (the RHS has zero grid-mean over the 2D domain), and
for uniqueness we have imposed the condition that the solution have zero mean (ˆu
11
= 0).
1