Computational Physics

A7 Differential equations 587

This equation is easily solved because it is diagonal: we have simplyL^2 independent
trivial equations. The solution in direct space is found by Fourier transformingψˆ
back to real space.
The computational cost is that of performing the necessary Fourier transforms,
and this requiresO(L^2 logL)floating point operations in two dimensions. The
method is therefore very efficient with respect to relaxation methods, which require
L^2 floating point operations per scan over the lattice. Remember this is to be multi-
plied by the number of iterations, which is at leastO(L)for satisfactory accuracy (in
the SOR method), so that the total time needed for these methods scales asO(L^3 ).

Multigrid methods

Multigrid methods are based on iterative ideas (see ‘Boundary value problems’
above) and aim – crudely speaking – at increasing the relaxation rate by updating the
solution on blocks of grid points alongside the short-range update on the grid points
themselves. The method is based on residual minimisation; see ‘The conjugate
gradient method’ above. For some trial solutionψijwith residualrij, we consider
the difference betweenψand the exact solutionχ

A(ψ−χ)=r, (A.102)

hence, if we would have a solutionδof the equation

Aδ=r, (A.103)

the exact solutionχwould be given by

χ=ψ−δ. (A.104)
If we have performed a few iterations, e.g. Gauss–Seidel iterations, the residual
will contain on average an important contribution from the long-wavelength com-
ponents and only weak short-wavelength modes, since iteration methods tend to
eliminate the short-wavelength errors in the solution faster than the long-wavelength
ones, because a Gauss–Seidel update involves only nearest neighbours. In the mul-
tigrid method, the remaining smooth components are dealt with in a coarser grid.
We shall roughly describe the idea of the multigrid method; details will be given
below. The coarse grid is a grid with half as many grid points along each cartesian
direction, so in our two-dimensional case the number of points on the coarse grid
is one-fourth of the number of fine grid points. A function defined on the fine grid
isrestrictedto the coarser grid by a suitable coarsening procedure. We apply this
coarsening procedure to the residual and perform a few Gauss–Seidel iterations on
the result. The idea is that the wavelength of the long-wavelength modes is effect-
ively twice as small on the coarse grid, so hence the long-wavelength modes can
be dealt with more efficiently. The solution on the coarse grid must somehow be