Multigrid Methods - Finite Elements: Theory, Fast Solvers, and Applications in Elasticity Theory - page 234

1 ;

The matrix r is simplest and easiest to find for variational problems in R

see Fig. 51. For piecewise linear functions,

* -

1
2

1
2
1
2

1

, / 1

2
1
2

1

r =

1
2

1 . ( 1 . 14 )

. . . . . . . . .

1
2

1
2

1

For affine families of finite elements, we only need to compute the coefficients for
one (reference) element. In particular, for piecewise linear triangular elements,

1 f z − 1 = z i ,

j

1
2

if z i

is not a grid point of T − 1 ,

r ji =

T of z − 1 but is a neighbor in ,

j

0 otherwise.

If the variables are numbered as in the model Example II.4.3 on a rectangular
grid, then the operators can be expressed as stencils. For the example we have

< ?

1
2

1
2

> A

1
2

1
2

p = . ( 1 . 15 )

1

1
2

1
2

∗

Note that r is always a sparse matrix, and thus there is never a need to store a
full matrix. Frequently, it is given only in operator form, i.e., we have a procedure
for computing the vector rx

N − 1

for any given x

N . The way in which

∈ R ∈ R

the nodes of the grid T − 1 are related to those of T , and the way they are numbered,

are critical to the efficiency of an algorithm.
For completeness, we describe the multigrid algorithm once again, paying
more attention to the computational details. This formulation can also be used for
difference methods. Suppose we are given the smoothing S = S , the restriction
r = r , and the prolongation p = p .

1.7 Multigrid Iteration MGM (k-th cycle at level ≥ 1 in matrix-vector form):

Let x ,k be a given approximation in S .
1. Pre-Smoothing. Carry out ν 1 smoothing steps:

x ,k, 1

ν 1 x ,k .

= S ( 1 . 16 )

2. Coarse-Grid Correction. Compute the residue d = b − A x ,k, 1

and the

restriction b − 1 = rd . Let

A − 1 y − 1

= b − 1 .