Civil Engineering Reference
In-Depth Information
1
/
6 is realistic. Then
Algorithm 4.1 produces an approximation with error
(
5
/
2
)c h
2
, and one additional
cycle suffices to reduce the error to less than
4.3 Remark.
In many cases a convergence rate of
ρ
≤
1
2
ch
2
.
Complexity
To estimate the computational complexity, we can assume that the amount of
computation for
smoothing in
S
,
prolongation of
S
−
1
to
S
, and
restriction of the residue
d
(
4
.
4
)
all involve
cN
operations, where
N
=
dim
S
. The number of arithmetic opera-
tions for one smoothing step is proportional to the number of nonzero elements in
the system matrix. For affine families of finite elements on uniform grids, this num-
ber is proportional to the number of unknowns. The prolongation and restriction
matrices are even sparser. Thus, the operation count at level
is
≤
+
(ν
1
)cN
,
(
4
.
5
)
where
ν
is the number of smoothings.
For grids in
2
, we collect the operations (4.4) from all levels. Each time we
move to a coarser grid the number of unknowns decreases by approximately the
factor 4. Summing the terms (4.5) for the multigrid iteration
MGM
gives
R
4
3
(ν
+
1
)cN
(ν
+
1
)c(N
+
N
−
1
+
N
−
2
+···
)
≤
for the V-cycle,
1
)cN
for the W-cycle.
(
4
.
6
)
In addition, we must include the work needed to solve the system of equations on
the coarsest grid. We ignore this additional computational effort for the moment.
This is justified if the number of levels is large. The special case of a small number
of levels will be treated separately later.
The computation of starting values can be analyzed in the same way. Because
of the increase in dimension, each cycle of Algorithm 4.1 requires four times as
(ν
+
1
)c(N
+
2
N
−
1
+
4
N
−
2
+···
)
≤
2
(ν
+
much work as its predecessor. Since
k
4
−
k
4
/
3, we have that
The operation count for computing the starting value is
=
4
3
times
the operation count for one multigrid cycle on the finest grid.
In view of Remark 4.3, the operation count for the complete calculation is
7
3
times
the count for one multigrid cycle on the finest grid, provided the convergence rate
is 1/6 or better. Thus, in particular, the complexity increases only linearly with the
number of unknowns.
Search WWH ::
Custom Search