Computational Physics

(Rick Simeone) #1

590 Appendix A


How efficient is the multigrid method? The Gauss–Seidel iterations on a grid
of sizeL×LrequireO(L^2 )steps, as do the restriction and prolongation oper-
ations for such a grid. These operations must be carried out on grids of size
L^2 ,L^2 /4,L^2 /16,..., so that the total number of operations required is


L^2


log∑ 2 L

n= 0

1


22 n

=L^2


1


1 − 1 / 4


(A.108)


which means that a full multigrid step takesO(L^2 )steps. For various types of
problems, theorems exist which state that the number of full multigrid steps required
to achieve convergence for Poisson’s equation is independent ofL, so that the
method has the best possible time scaling, that is time∝L^2.
Obviously, the definition of the coarse grid and the restriction and prolongation
operators are not unique; in setting up the multigrid method there are quite a few
options at each stage. We have only given one example in order to expose the
method.Formoredetails,thespecialisedliteratureshouldbeconsulted[ 16 – 19 ].


A8 Linear algebra problems


A8.1 Systems of linear equations

This section is devoted to an overview of matrix calculations, a topic that we have
touched on several times in previous sections. A first example is the solution of a
set ofNlinear equations ofNunknowns. In a matrix formulation, the equations
can be formulated as




a 11 a 12 ··· a 1 N
a 21 a 22 ··· a 2 N
..
.

..


.


..


.


aN 1 aN 2 ··· aNN













x 1
x 2
..
.
xN







=








b 1
b 2
..
.
bN







, (A.109)


which can be written in a more compact way as


Ax=b. (A.110)

Here,Ais a nonsingularN×Nmatrix with elementsaij,xis anN-dimensional
vector containing the unknowns andbis a knownN-dimensional vector.


Dense matrices

Adensematrix is one whose elements are mostly nonzero, so all its elements have
to be taken into account in a solution method involving such a matrix, such as the
solution of a system of linear equations.

Free download pdf