Non-nested multi-level solvers for finite element discretisations of mixed problems.
We consider a general framework for analysing the convergence of multi-grid solvers applied to finite element discretisations of mixed problems, both of conforming and nonconforming type. As a basic new feature, our approach allows to use different finite element discretisations on each level of the multi-grid hierarchy. Thus, in our multi-level approach, accurate higher order finite element discretisations can be combined with fast multi-level solvers based on lower order (nonconforming) finite element discretisations. This leads to the design of efficient multi-level solvers for higher order finite element discretisations.
Introduction
Multi-grid methods are among the most ecient and most popular solvers for nite element
discretisations of elliptic partial dierential equations. Their convergence theory in the case
of symmetric operators and nested conforming nite element methods is well-established;
see for example the books [7, 17, 30] and the bibliographies therein. Multi-grid methods
for nonconforming nite element approximations have been also studied in a number of
papers, e.g. see [3, 4, 6, 8, 9, 10, 11, 12, 13, 19, 31]. In this case, the nite element space
of a coarser level is in general not a subspace of the nite element space of a ner level;
Institut fur Analysis und Numerik, Otto-von-Guericke-Universitat Magdeburg, PF 4120, D-39016
Magdeburg, Germany
y Institute of Numerical Mathematics, Faculty of Mathematics and Physics, Charles University,
the resulting multi-grid method is called non-nested. The general framework of analysing
the two-level convergence of non-nested multi-grid methods, developed in [4] for elliptic
problems, will be the starting point for the methods studied herein. Multi-grid methods
for mixed problems, arising in the discretisation of the Stokes equations, are analysed in
[3, 5, 9, 19, 27, 31, 34]. The crucial point in the investigation of multi-grid methods for
mixed problems is the denition and analysis of the smoother. The currently best understood
type of smoothers, here called Braess-Sarazin type smoother, is a class of symmetric
incomplete Uzawa iteration proposed in [1] and analysed on its smoothing properties in
[5, 27, 34]. The Braess-Sarazin type smoother has a convergence rate of O(1=m) with
respect to the number of smoothing steps. By far the most analytical studies are applied
to standard multi-grid methods where on each multi-grid level the same discretisation of
the partial dierential equation is used.
In this paper, we investigate multi-level solvers for nite element discretisations of
mixed problems which allow dierent discretisations, in particular the use of dierent -
nite element spaces, on each level of the multi-grid hierarchy. The motivation for using this
type of multi-level solvers comes from general experiences that standard multi-level solvers
are very ecient for low order discretisations. But higher order discretisations might lead
to an overwhelming gain of accuracy of the computed solution so that their use should
be preferred for this reason. The multi-level solvers investigated in this paper allow an
accurate discretisation on the nest level and low order discretisations on all coarser levels.
In this way, an accurate solution can be obtained for whose computation the eciency of
multi-level solvers for low order discretisations is exploited. The crucial point in the construction
of such multi-level methods is the transfer operator between the nite element
spaces dened on dierent levels. We show that rather simple L 2 -stable prolongations
guarantee already the convergence of the two-level method for a suciently large number
of smoothing steps with a Braess-Sarazin type smoother. Our approach allows to handle
conforming and nonconforming nite element spaces in a general framework. As a concrete
application of the general theory developed in this paper, we have in mind in particular the
Stokes and Navier-Stokes equations. However, it is clear that the same ideas can be also
applied to selfadjoint elliptic equations. The eciency of multi-grid solvers for lowest order
non-conforming discretisations of these equations has been demonstrated, e.g., in [20, 32]
and the gain of accuracy of higher order discretisations in a benchmark problem in [18].
Dierent discretisations on the nest and on coarser grids have been already used in the
convergence theory of nonconforming nite element discretisations of the Possion equation
in [12, 13]. However, the motive of the approach in [12, 13] is completely dierent to ours.
The replacement of the P 1 -nonconforming coarse grid correction by a conforming P 1 coarse
grid correction enables the authors to apply the well-developed theory of multi-grid solvers
for conforming discretisations on the coarser levels.
The plan of the paper is as follows. In Section 2, we investigate the convergence properties
of a multi-level method for solving mixed nite element discretisations in an abstract
way. First, we introduce the variational and the discrete mixed problem and we describe the
matrix representation. Then, based on abstract mappings between nite element spaces,
the prolongation and restriction operators are dened. The smoothing property of the
basic iteration proposed in [5] is shown for symmetric positive denite spectral equivalent
pre-conditioners and without an additional projection step. Together with the approximation
property, the convergence of a two-level method and the W-cycle of a multi-level
method are established. Section 3 is devoted to the construction of a general mapping
between two nite element spaces. We show that this general transfer operator satises
all assumptions which are essential for our theory. As applications, we show in Section 4
how various discretisation concepts for solving the Stokes problem t in our general theory.
Finally, we present numerical results to verify the theoretical predictions on the multi-level
solvers.
Throughout this paper, we denote by C a \universal" constant which is independent
of the mesh size and the level but whose value can dier from place to place.
Multi-level Approach
2.1 Variational Problem
We consider a variational problem of the following form. Let V and Q be two Hilbert
spaces and let V  H  V 0 be the Gelfand triple. Given the symmetric bilinear form
R and a functional f 2 V 0 , we look for a
solution (u;
We assume:
(Solvability) For all f 2 V 0 , the problem (1), (2) admits a unique solution (u;
One example for this type of problems is the weak formulation of the Stokes problem
in d space dimensions
in
r
in
@
where
is a bounded domain with Lipschitz continuous boundary. Here we set
and a and b are given by
Z
Z
pr  v dx: (4)
Note that in this case (H1) is satised [16] since a is V -elliptic and b satises the Babuska-
Brezzi condition, i.e., there is a positive constant  such that
sup
2.2 Discretisation
be sequences of (possibly nonconforming) nite element
spaces approximating V and Q, respectively. Instead of the continuous bilinear forms
a and b we use the discrete versions a l :
again assume that the bilinear forms a l are symmetric. For f 2 H the discrete problem
corresponding to (1), (2) reads
Find such that
a l (u l ; v l
where (:; :) denotes the inner product in H.
(Solvability and convergence) We assume that the problem (6), (7) admits a unique
solution and that the error estimate
l kfkH (8)
holds, where h l characterises how ne is the nite element mesh on which V l and Q l
are dened.
Remark 2.1 Typically, the convergence estimate (8) is established using a regularity property
of the problem (1), (2). Such a regularity property usually states that if f 2 H, then
the solution (u; p) of (1), (2) belongs to a 'better' space W  R  V Q and satises
For example, for the Stokes problem mentioned above, one has
0(d ,
, and the regularity property holds if the boundary
of
is of class C 2
or
is a plane convex polygon. For (u; p) 2 W  R one can often prove that the solution
of (6), (7) satises
l
and taking into considerations the estimate in the regularity property, one obtains (8).
2.3 Matrix Representation
be bases of the spaces V l and Q l , respectively, where
I l , J l denote the corresponding index sets. The unique representations
i2I l
dene the nite element isomorphisms between the vector
spaces of coecient vectors u
and
the nite element spaces V l and Q l , respectively. We introduce the nite element matrices
A l and B l having the entries a Now the discrete
problem (6), (7) is equivalent to
l
u l
l
with f that A l is a symmetric matrix. In the vector spaces U l and P l ,
we will use the usual Euclidean norms scaled by suitable factors such that the following
norm equivalences
are satised with a mesh- and level-independent constant C.
2.4 Prolongation and Restriction
Essential ingredients of a multi-level algorithm for mixed problems are the prolongations
and the restrictions
R u
l 1;l
l 1;l
In case of a nested nite element hierarchy V 0      V l 1  V l , the canonical
prolongation P u
l 1;l is obtained by the nite element isomorphisms between U l 1 and V l 1 ,
U l and V l and the embedding V l 1  V l , thus
l 1;l :=  1
l   l
Similarly, we would have
l 1;l := 1
l  l 1
for assumed inclusion property Q 0      Q l 1  Q l is often
but not always satised in applications. For example, this inclusion property is violated
if the spaces Q l are constructed using the nonconforming piecewise linear element. The
corresponding velocity spaces V l , such that the pair (V l ; Q l ) satises the discrete version
of (5), may then be constructed using the bubble enriched nonconforming piecewise linear
element [33] or the modied nonconforming piecewise linear element [22]. As a dierent
example one could also think of using a continuous pressure space Q l on the level l and a
discontinuous space Q l 1 on the level l 1. We emphasise that Q l 1 can be dened on the
same mesh as Q l .
In the general case of non-nested velocity spaces, when V l 1 6 V l , we have to replace
the natural embedding by a suitable mapping  l , which results in the following
prolongation and restriction:
l
l   u   l 1 and R u
l 1
l
It turns out that the convergence analysis requires estimates for  u on the sum V l 1 +V l , thus
we will dene  l on the (possibly larger) space  l with V l 1 +V l   l  H. In the
case we introduce a mapping  giving the following prolongation
and restriction, respectively,
l
l   p  l 1 and R p
l 1
l
We assume that the following properties of the mapping  u hold:
Remark 2.2 In [4], the mapping  u has been assumed to be the product
l to allow more
exibility in constructing a suitable  u . In many
cases S can be chosen to coincide with V l or U l :
2.5 Smoothing Property
In this section, we will omit the index l indicating the current level and the underline
symbol for noting coecient vectors in U and P. For smoothing the error of an approximate
solution of (10), we take the basic iteration
0, which can be considered as a special case of the symmetric incomplete Uzawa
algorithm proposed by Bank, Welfert and Yserentant in [1]. The smoothing properties of
have been studied in [5] for the special case in [27] for the general case provided
that an additional projection step is performed, and in [34] for a more general setting. For
completeness, we give a proof of the smoothing property without an additional projection
step using partially results of [27].
The matrix D is a pre-conditioner of A such that the linear system (13) is more easily
solvable than (10). Note that we have
implying that after one smoothing step the iterate u j+1 , j  0, is discretely divergence-free,
i.e., Bu Here and in the following, we assume that
(H5) D is symmetric and positive denite and BB T is regular.
The matrix BB T is regular if the bilinear form b l , generating the matrix B satises a
discrete version of the Babuska-Brezzi condition (5). From the regularity of BB T it follows
that S := BD 1 B T is also regular.
The iteration is a so-called u-dominant method since the new iterate (u
on u j but not on p j . Indeed, let (u; p) be the solution of (10). Then, we have
u u j+1
(D A)(u
It is easy to verify that
and hence we particularly obtain for j  0
a projector, we can also write
where M is given by From (14) and (15) it follows for m  3
In the case of D = I, both P and M are symmetric. Choosing    max (A) the matrix
I  1 A is a contraction. Moreover, the spectrum of M is contained in [0; 1] and the usual
spectral decomposition argument (see [3]) results in the smoothing property
3: (19)
For proving (19) it is essential that the basis f' chosen in such a way that
holds. The proof of the smoothing property for D 6= I is more tricky.
In [27] an additional pressure update has been introduced to guarantee the smoothing
property. However, as already noticed in [3], a careful inspection shows that this additional
step can be omitted.
Lemma 2.1 Let be chosen such that
for some level- and mesh-independent constants  2 [1; 2) and
> 0. Moreover, let the
basis be chosen such that  Then, the basic iteration
satises the smoothing property
Proof. The projector P is similar to the matrix D 1=2 PD 1=2 . Since D 1=2 PD 1=2 is symmetric
it follows that D 1=2 MD 1=2 is also symmetric. In [27], it has been shown (see proof
of Lemma 3.9) that the spectrum of M satises
for some  2 [1; 2). This assumption holds since  >  max (A)= min (D)   2 . Then, from
the representation
we get by a spectral decomposition argument applied to the symmetric matrix D 1=2 MD 1=2
the existence of a (level independent) constant C
Since

I

1
1
with
the mapping
I
is a contraction for    2 =2. Thus, from (18) and (23), we get for m  3
C
The cases have to be considered separately. Starting with (14), we have
for
A(u
(D A)(u j+1
Taking into consideration that I  1 D 1=2 AD 1=2 is contractive for    2 =2, we obtain
for
kA(u
From (16), we get
and because
is the product of the projector D 1=2 PD 1=2 and the contraction (I  1 D 1=2 AD 1=2 ),
we conclude for all j  0
Using the triangular inequality, we nally obtain from (27) for all j  0
kA(u
which proves (20) for 2. |
2.6 Approximation Property
Let an approximation (~u l ; ~
of the solution of the problem (6),
(7) be given. We can think of (~u l ; ~
l ) as being the result after some smoothing steps, and
consequently assume that
b l (~u l ; q l
Then, the coarse-level correction is dened as the solution of the following problem:
Find
1 such that for all (v l 1
a l 1 (u
The coarse-level correction yields via the transfer operators  u ,  p from Section 2.4 the new
approximation
new
new
Now, the basic idea for proving the approximation property is to construct an auxiliary
(continuous) problem such that (u
l ) are nite element solutions
of the corresponding discrete problems on the spaces V l 1 Q l 1 and V l Q l , respectively.
This idea has been used for scalar elliptic equations already in [6] and has been applied
to more general situations in [4], [19]. We dene the Riesz representation F l 2  l of the
residue by
Then, the auxiliary problem will be
Find (z; w) 2 V Q such that
Indeed, for s 2 V l we have
which means that (u l ~
l ) is a nite element approximation of (z; w) in the space
l  Q l . On the other hand, becomes just the right-hand side of (28) if s
i.e.,
l 1 ) is the nite element approximation of (z; w) in the space V l 1 Q l 1 .
Lemma 2.2 Let h l 1  Ch l with a mesh- and level-independent constant C. Then, the
approximation property
l u new
l kH  Ch 2
l
l (p l
~p l
holds.
Proof. Applying (H3), (H4), the triangular inequality, and (8), we get
l u new
l
l
l
Cku l ~
l 1 kH
C(ku l ~
It remains to state a relation between the residue F l 2  l and the \algebraic" residue
d l 2 U l given by
d l := A l (u l ~
l (p l
~p l
For this, we rst consider the Riesz representation of the residue in V l , i.e., r l 2 V l dened
by
Since
A l (u l ~
l (p l
~p l
U l
for all v l 2 V l , we have
l r l ; v l ) U l
from which the representation
l r l (33)
follows. Now, using
l
l  u F l ) U l
we get from (11) and (H4)
H  kd l k U l
l  u F l k U l
Ckd l k U l
k u F l k H  Ckd l k U l
Dividing by kF l k H , we obtain
which together with (32) yields the statement of the lemma. |
2.7 Multi-level Convergence
We shortly describe the two-level algorithm using m smoothing steps on the level l, l
and the coarse-level correction (28), (29). Let (u 0
l ) be an initial guess for the solution
l ) of (6), (7). We apply m steps of the basic iteration
l ). Now,
the coarse-level correction (28), (29) is performed using
l
as an approximate solution of the discrete problem (6), (7). Finally, the new approximation
is dened as
new
l
new
l
Combining the smoothing and approximation property, we obtain
Theorem 2.1 Under the assumptions of Lemma 2.1 and Lemma 2.2, the two-level method
converges for suciently many smoothing steps with respect to the H- and U l -norm. In
particular, there are level- and mesh-independent constants C and ~
C such that
l u new
l k U l
l k U l
and
l u new
l k H
~
l
Proof. Applying Lemma 2.1 we have
l
l (p l
l
C
l
l k U l
Taking into consideration the norm equivalence (11) and Lemma 2.2, we conclude
l u new
l k U l
Cku l u new
l k H
l kA l (u l ~
l (p l
~p l
l k U l
which proves convergence in the U l -norm for suciently many smoothing steps m. The
convergence in the H-norm follows from the norm equivalence (11). |
Remark 2.3 Note that in our context the notation \two-level" does not necessarily mean
that we consider two levels of mesh renements. Thus, Theorem 2.1 is also applicable
in cases where we have two dierent nite element discretisations on the same mesh (see
Sections 4.2 and 4.3).
Once proven the convergence of the two-level method, the convergence of the W-cycle
multi-level method follows in a standard way (see e.g. [4], [17]). This is also true for a
combination of a nite number of dierent two-level algorithms provided that Theorem 2.1
holds true for each of these two-level methods.
3 A General Transfer Operator
In this section we will describe general nite element spaces V l and we will show how then
a space  l and a transfer operator
and the assumptions (H3) and (H4) can be constructed. In this way, the transfer operator
can be applied on a large class of nite elements, including in case of the Stokes problem,
for example, also velocity spaces generated by vector-valued basis functions [16].
We denote by fT l g l0 a family of triangulations of the
domain
Each triangulation
l consists of a nite number of mutually disjoint simply connected open cells K so that
we
have
K2T l
We assume that
(H6) For any l > 0, the triangulation T l is obtained from T l 1 by some \renement", i.e.,
each cell K 2 T l 1 is either a member of T l or it has been rened into child cells
In particular, we allow T l l , which gives us the additional possibility to dene
dierent nite element spaces V l 1 and V l on the same mesh.
We assume that there exists a nite number of reference domains b
Kc M such that,
for any level l  0 and for any cell K 2 T l , there exists
Mg and a one-to-one
mapping FK 2 W 1;1 ( b
We assume that
are independent of K and l. In addition, we suppose
that
and
BK is a ball
again with C independent of K, K 0 and l. The validity of (38)-(40) usually follows from
some shape-regularity assumption on the triangulations. Particularly, for simplicial trian-
gulations, the condition (40) already guarantees a shape-regularity of the cells and implies
(38). Moreover, if the triangulations satisfy usual compatibility assumptions (cf. e.g. [14]),
then (39) also follows. In case of hanging nodes, the dierence in the renement levels of
neighbouring elements is limited by (39).
On each reference cell b
M , we introduce a nite-dimensional space b
. Employing the mappings FK from (37), we introduce,
for any cell K 2 T l , a nite{dimensional space P l (K)  H 1 (K) d such that
We denote by 'K;j , functions in P l (K) satisfying
Usually, the coecients aK;jk are zeros or unit vectors in the direction of coordinate axes,
and one takes only one non-vanishing coecient for each j. However, in some cases, also
other choices of the coecients aK;jk may be of use. Particularly, this is the case if the
space P l (K) contains vector-valued basis functions which cannot be obtained by transforming
xed basis functions from the space [ b
K. As an example may serve the
Bernardi/Raugel element (cf. [2]) which contains vector-valued basis functions perpendicular
to element faces.
We introduce linear functionals fNK;i g dimP l (K)
dened on P
l (K), which we will call
local nodal functionals in the following. We assume that these functionals possess the
usual duality property with respect to the basis functions, i.e.,
denotes the Kronecker symbol. Examples of such nodal functionals can be found
in Section 4.
Now, for each level l, we introduce a nite element space V l satisfying
This space is smaller than the piecewise discontinuous space on the right-hand side of (41)
since we assume that there is some connection between functions on neighbouring cells.
This connection can be enforced by choosing pairs of nodal functionals from neighbouring
cells and by requiring that the two functionals from any pair are equal for any function
from the space V l . We denote by f' l;i g i2I l
a basis of the space V l obtained in this way,
where the set I l is an index set whose elements will be called nodes in the following. We
assume that the mentioned pairs of local nodal functionals were chosen in such a way that,
as usual, these basis functions have \small" supports. Precisely, we require that, for any
l , there exists K 2 T l such that
Further, we assume that, on any cell K 2 T l , the basis functions ' l;i coincide with the local
basis functions 'K;j . Thus, denoting by
I l
the set of all nodes which are associated with a cell K, we can introduce a one-to-one
mapping
such that
Using the mappings K we can renumber the local nodal functionals, i.e., we set
Then
Furthermore, we dene for any node j 2 I l
which is the set of all cells K 2 T l which are connected with the node j. Then we can give
a precise characterization of the space V l , namely,
This shows that a natural choice for a global nodal functional is the arithmetic mean of
the local nodal functionals
K2T l;i
NK;i (wj K
Note that we again have the duality relation
which implies that
i2I l
having described the spaces V l , we can turn to the question how the spaces  l
and the mappings  satisfying (36), (H3) and (H4) can be dened. Following
the ideas developed in [29], where the construction of general transfer operators for nite
element spaces has been investigated, we construct  l as a discontinuous nite element
space
l

with a nite dimension. To guarantee (36), we furthermore assume that
(H7) The local function space S l (K) is constructed such that
is the parent cell of a child cell K 2 T l for
We suppose that, for any K 2 T l , the local nodal functionals NK;i are well dened on
l (K), which usually means that the functions in S l (K) are of the same type as those in
l (K) (e.g., continuous). Then we can dene the transfer operator  simply by
i2I l
In view of (44) we immediately obtain the validity of (H3). To be able to prove (H4),
we assume that each of the spaces S l (K) can be obtained by transforming functions from
one of the reference cells onto K. Thus, we introduce nite element spaces b
M , with bases f b
and we assume that, for any K 2 T l , there exists
Mg such that
l
where FK is the mapping from (37) and C is independent of K and l. The last assumption
is automatically satised if the local nodal functionals NK;i are dened by means of a nite
number of functionals dened on the reference spaces b
which is often the case.
Lemma 3.1 The operator  u dened by (45) is uniformly L 2 stable, i.e., it satises (H4)
with a constant C independent of l and with k  k
Proof. Consider any w 2  l and any K 2 T l and let FK and b
S i be the mapping and the
space from (46), respectively. Then
for some real numbers w j and it follows from (47), from the equivalence of norms on
nite-dimensional spaces and from (38) that, for any m 2 I l (K),
jNK;m (wj K )j  C
Thus, we see that, for any i 2 I l , we have
jN l;i (w)j  C
K2T l;i
For any cell e
l , we derive using (38), (48), (42) and (39) that
k u wk 0; e

i2I l ( e

e
i2I l ( e
jN l;i (w)j  e
where we denoted by
i2I l ( e
K2T l;i
the vicinity of any cell e
l . In view of (39), (40) and (42), the number of cells in ( e
is bounded independently of e
K and l and hence we obtain
which expresses a local L 2 stability of the operator  u . Again, according to (39), (40) and
(42), the number of the sets ( e
K) which contain any xed cell K 2 T l is bounded independently
of l and hence the local L 2 stability of  u immediately implies the global L 2 stability
(H4). |
A signicant step in the above considerations was the assumption that there exist spaces
l (K) satisfying (H7) and (46). In the remaining part of this section, we will prove that
this is true for simplicial nite elements. Thus, from now on, we assume that there is only
one reference cell b
K, which is a d-simplex. It is essential for our further proceeding that,
for any simplicial cell K, there exists a regular ane mapping
K onto K. We denote the set of all these mappings by LR ( b
K;K).
above, we introduce a xed nite{dimensional space b
K) d and we assume
that, for any K 2 T l and any FK 2 LR ( b
K;K), we have
l (K)  fbv  F 1
We assume that, as usual, the cells of the triangulations are rened according to a nite
number of geometrical rules. Therefore, the renements of all cells K can be mapped by
the linear mappings F 1
K onto a nite number b L of renements of the reference cell b
K into
child cells b
L. That means that, for any cell K 2 T l obtained by
rening a parent cell F(K) 2 T l 1 and for any FF(K) 2 LR ( b
K;F(K)), there exist indices
such that
We denote
Then, for any v 2 P l 1
there exists b
ij such that
P and hence
Thus, for any K 2 T l and any FK 2 LR ( b
K;K), we have
l 1
for some indices i
g. Now, we dene
c
and, for any K 2 T l , we choose some FK 2 LR ( b
K;K) and set
l
It is easy to see that these spaces S l (K) satisfy the assumption (H7).
4 Applications to the Stokes Equations
In this section we give details how the general assumptions made in Section 3 can be
fullled for the Stokes problem. In particular, we will show that the usually used multi-grid
technique for the nonconforming nite elements of lowest order coincides with the use
of the general transfer operator described in the preceding section.
4.1 Lowest Order Nonconforming Elements
Our rst examples are the nonconforming nite elements of rst order on triangles and
quadrilaterals. The triangular element was introduced by Crouzeix and Raviart and analysed
in [15]. The element on quadrilaterals was established by Rannacher and Turek and
analysed in [24, 28].
We consider a hierarchy of uniformly rened grids. Let T 0 be a regular triangulation of
triangles or into convex quadrilaterals. The mesh T l is obtained from T l 1 by
subdividing each cell of T l 1 into four child cells. For triangles, we connect the midpoints
of the edges. In the quadrilateral case, we connect the midpoints of opposite edges.
Now we construct the nite element spaces V l . Let P 1 (K) be the space of linear polynomials
on the triangle K. The space of rotated bilinear functions on a quadrilateral K is
dened by
is the bilinear reference transformation from the reference cell ^
onto the cell K, see [24, 28]. Let E(K) denote the set of all edges of the element
K. We dene for any E 2 E(K) the nodal functional
Z
vj K ds:
K2T l
E(K) be the set of all edges of T l . The set E l
@
@
contains all boundary edges. The nite element space V l is given by
@
where P (K) is P 1 (K) on triangles and Q rot
1 (K) on quadrilaterals.
Since the triangulation T l is obtained from T l 1 by regular renement of all cells, we have
us show that the assumptions (H7) and (46) hold. In the case of triangles,
@
@
@
@
FK

Figure

1: Renement of original and reference cell
the inclusion P l 1 directly from the ane reference mapping
and we have P l 1 . Thus, we can choose S l
The situation is more complicated for the Q rot
element. Let us consider K
l be the child cells of K. We set ^
Fig. 1).
Let for example
which means that there is a function
K1
The mapping G
and FK
are bijective. Thus, we have FK 1
K1
Since the local space span(1; ^
2 ) is invariant with respect to the mapping G 1 we
conclude
P l (K 1 ). The same arguments can be applied to K i
which results in
l
l (K)  Q rot
This allows us to choose S l
in the denition of the space  l . Note that the
assumptions (46) and (47) are then fullled.
The nite element spaces V l 1 and V l are non{nested. In order to get a suitable prolongation
we will use the general transfer operator which was introduced in Section 3. The
denition of the global nodal functionals (43) simplies for the above spaces to
for all inner edges E with the neighbouring elements K and K 0 . For boundary edges we
get
E(K). The resulting mapping  u is the same as in [19].
The space Q l which approximates the pressure consists of piecewise constant functions,
i.e.,
For the proof of assumption (H2) we refer to [15, 24]. Since Q l 1  Q l the transfer operator
p is the identity.
For numerical experiments with the Crouzeix-Raviart element we refer to [19].
4.2 Modied Crouzeix-Raviart Element
It is sometimes necessary to use other types of boundary conditions than the Dirichlet
boundary condition considered in (3). For example, if a part N of
@
represents a free
surface of a
uid, then one can use the boundary conditions
where I is the identity tensor and n is the outer normal vector to N . The rst condition
in (50) states that zero surface forces act in the tangential direction to N . The boundary
conditions (50) generally do not allow to use the bilinear form a dened in (4) and instead
we have to consider
Z
If meas d 1
(@
then the ellipticity of this bilinear form for functions from H
d
vanishing on
@
n N is assured by the Korn inequality. However, the discrete Korn
inequality does not hold for most rst order nonconforming nite element spaces (cf. [21]),
particularly, it fails for the elements investigated in the preceding section. Consequently,
in these cases, the validity of (H2) cannot be shown.
One of the few rst order nonconforming elements which do not violate the discrete
Korn inequality is the modied Crouzeix-Raviart element P mod
which was developed in
[23] for solving convection dominated problems. Here we conne ourselves to a particular
example of this element for which the space of shape functions on the reference triangle b
is
are the barycentric coordinates on b
K. To each edge b
K, we assign
two nodal functionals, b
E;1 and b
E;2 , dened by
Z
Z
E2

Figure

2: Coarsest grids (level 0).
E is a barycentric coordinate on b
E. The space V l is now obtained by transforming
the space b
P and the six nodal functionals b
K, onto the cells of the
triangulation by means of regular ane mappings (cf. the preceding section). In this way,
we get the space
Z
denotes the jump of v across the edge E,
and  1 ,  2 ,  3 are the barycentric coordinates on the cell K. A nice property of the P modelement is that Z
It is easy to verify that the assumptions made in Section 3 are satised. The assumption
holds if the space Q l consists of discontinuous piecewise linear functions from L 2
and each cell has at least one vertex
in
since then an inf-sup condition holds (cf. [22]
and [15]). Consequently, (H2) is also satised if Q l is a subspace of L 2
consisting
e.g. of piecewise constant functions, continuous piecewise linear functions or nonconforming
piecewise linear functions.
Here we present numerical results for Q l consisting of piecewise constant functions so
that the transfer operator  p can be replaced by the identity. The discretisations are dened
on a sequence of uniformly rened triangular grids starting with the triangular grid from
Fig. 2 which we denote as T 0 (level 0). We shall consider two kinds of multi-level solvers for
solving the Stokes equations on a given geometrical mesh level. The rst one is a classical
multi-level method where each mesh corresponds to one level of the algorithm and on each
mesh we consider a discrete problem of the same type, i.e., the Stokes equations discretized
using the P mod
element. In the second multi-level solver, the discretisation using the
element is used on the nest mesh T L only and on all other mesh levels a 'cheaper'
discretisation is employed, namely the Crouzeix-Raviart element with piecewise constant
pressure denoted as P nc
In addition, the P nc
discretisation is also applied on the
nest mesh level T L so that two dierent discretisations corresponding to two levels of the
multi-level method are considered on the nest geometrical mesh. We refer to the next
section for more details on this technique. Note that both kinds of multi-level solvers t
into the framework of this paper and the prolongations and restrictions can be dened
using the general transfer operator  u described above. The numbers of degrees of freedom
to which the mentioned discretisations lead on dierent meshes are given in Table 3.
As a smoother, we use the basic iteration described in Section 2.5. Therefore, the system
(13) has to be solved in each smoothing step which implies that the ecient solution of
is essential for the eciency of the multi-level solver. In view of an application of
our procedure to the Navier-Stokes equations, where A and D are no longer symmetric,
we solve (13) iteratively by a preconditioned
exible GMRES method, see e.g. [25]. The
preconditioner is dened via the pressure Schur complement equation of (13)
is the right-hand side of (13). First, (51) is solved approximately by some steps of the
standard GMRES method by Saad and Schultz [26] providing the approximation ~
p of
Second, an approximation ~
u of u j+1 u j is computed by
~
The solution of (13) is the most time consuming part of the multi-grid iteration. It
was shown by Zulehner [34] that the smoothing property of the Braess{Sarazin smoother
is maintained if (13) is solved only approximately as long as the approximation is close
enough to the solution. Numerical experiments show that, in general, one obtains similar
rates of convergence of the multi-level algorithm like with an exact solution of (13).
Considering the ecency of the multi-level solver measured in computing time, the variant
with the approximate solution is in general considerably better and therefore it is used in
practice. Thus, in the computations presented below we stopped the solution of (13) after
the Euclidean norm of the residual has been reduced by the factor 10. The systems on
level 0 were solved exactly.
We shall present numerical results for the following
Example 4.1 W-cycle in a 2d test case. We consider the Stokes problem
in
with the prescribed solution
This example is taken from the paper [5] by Braess and Sarazin.
The computations were performed using the W (m; m)-cycle,
1:0.

Table

1 shows the geometric means of the error reduction rates
l u new
l k 0
l k 0
for the multi-level solver which uses the P mod
discretisations on all levels. Table 2
shows the averaged error reduction rates for the multi-level solver which combines the use
of the P mod
discretisations on the nest level with the use of P nc
discretisations on
all lower levels. We observe that, for each m, the error reduction rates can be bounded by
a level-independent constant as predicted by Theorem 2.1. In addition, it can be clearly
seen from the two tables that, for m > 1, the multi-level method which uses the Crouzeix-
Raviart element on lower levels converges faster than the standard multi-level method.

Table

1: Example 4.1, P mod
averaged error
reduction rates.
mesh level
5 2.20e-1 2.87e-1 3.13e-1 3.13e-1 3.08e-1
6 1.70e-1 2.36e-1 2.62e-1 2.62e-1 2.59e-1

Table

2: Example 4.1, P mod
nest level combined with P nc
lower levels,
averaged error reduction rates.
mesh level
6 6.17e-2 1.27e-1 1.06e-1 1.01e-1 1.02e-1
4.3 A Multi-grid Method for Higher Order Discretisations Based
on Lowest Order Nonconforming Discretisations
As the last and certainly most important application, we consider a multi-grid method for
higher order discretisations which is based on lowest order nonconforming discretisations
on the coarser multi-grid levels. Like in the previous section, the hierarchy of this multi-grid
has two dierent discretisations on the nest geometric mesh level L, i.e. the spaces
for the multi-grid levels L and L+1 are dened both on T L , see Figure 3. The higher order
discretisation is used on multi-grid level on all coarser levels l, 0  l  L, a
nonconforming discretisation of lowest order is applied.
level geometry multigrid discretization
higher order
low order nonconforming
low order nonconforming
low order nonconforming
low order nonconforming

Figure

3: The multi-level approach for higher order discretisations.
Remark 4.1 The construction of this multi-grid method was inspired by a numerical study
of a benchmark problem for the steady state Navier-Stokes equations in [18]. This study
shows on the one hand a dramatic improvement of benchmark reference values using higher
order discretisations in comparison to lowest order nonconforming discretisations. On the
other hand, the arising systems of equations for the lowest order nonconforming discretisations
could be solved very fast and eciently with the standard multi-grid approach. This
standard multi-grid approach showed a very unsatisfactory behaviour for all higher order
discretisations. Often, it did not converge at all. Sometimes, convergence could be achieved
by heavily damping, leading to a bad rate of convergence and a very inecient solver. These
diculties could be overcome by applying the multi-grid method described in this section.
Thus, this method has been proved already to be a powerful tool in the numerical solution
of Navier-Stokes equations combining the superior accuracy of higher order discretisations
and the eciency of multi-grid solvers for lowest order nonconforming discretisations.
In case of the Stokes problem, the proposed multi-grid method ts into the framework
of this paper. Between the lower levels l and l +1 of the multi-grid hierarchy, 0  l < L, we

Table

3: Degrees of freedom for the discretisations in the 2d tests cases, Example 4.1 and
4.2.
disc. mesh level
use the transfer operators which have been dened in Section 4.1. To dene the transfer
operator between the levels L and L have to be constructed
since in general V L 6 V L+1 and for some higher order discretisations also Q L 6 Q L+1 . The
construction can be done by applying the techniques from Section 3. We choose
where P L+1 (K) is the space of local shape functions of the corresponding nite element
spaces V L+1 and Q L+1 , respectively.
We will present numerical results obtained with this multi-grid technique for a number
of higher order nite element discretisations. Let P 0 and Q 0 denote the spaces of
piecewise constant functions on simplicial mesh cells and quadrilateral/hexahedral mesh
cells, respectively. By we denote the well-known nite element spaces of
continuous functions of piecewise k-th degree. The notation P disc
k is used for spaces of
discontinuous functions whose restriction to each mesh cell is a polynomial of degree k.
The Crouzeix-Raviart nite element space is again denoted by P nc
1 .
Three examples for the multi-level approach for higher order discretisations will be
considered. The rst example conrms the theoretical results of Theorem 2.1, i.e., we
consider a two-level method and solve the systems (13) arising in the smoothing process
exactly. The solution procedure was decribed in the preceding section. Then we consider
Example 4.1 from the previous section and Example 4.4 dened below to demonstrate the
behaviour of the multi-level W-cycle with approximated solutions of (13) for test problems
in 2d and 3d.
Example 4.2 Two-level method. This example has been designed to check the theoretically
predicted results with respect to the two-level method. We consider the Stokes
equations (3)
in
0, such that is the solution of (3). The
computations were carried out on a sequence of meshes starting with level 0 (see Fig. 2),
for which the corresponding numbers of the degrees of freedom are given in Table 3. The
discrete solution on each level is u we consider a two-level method,
there is only one mesh level in a specic computation. On this geometric mesh level, the
lowest order nonconforming discretisation of (3) denes the coarse level in the two-level
method and a higher order discretisation the ne level.
As initial guess of the two-level method for each computation, we have chosen u
for all interior degrees of freedom and p Thus, the initial error is smooth. The results
presented in Table 4 were obtained with 3 pre-smoothing steps, without post-smoothing,
and with Thus, we have exactly the situation investigated in Section 2.
The results of the numerical studies are given in Table 4 and Figure 4. Table 4 shows the
averaged error reduction rate for the two-level method applied to a number of higher order
discretisations. It can be clearly seen that the error reduction rate is for all discretisations
independent of the level as stated in Theorem 2.1. The second statement of Theorem
2.1, the decrease of the error reduction rate by O(1=m), where m is the number of pre-smoothing
steps, is illustrated for the P 3 =P 2 discretisation on mesh level 4 in Figure 4. The
situation is quite similar for the other higher order discretisations.

Table

4: Example 4.2, pre-smoothing steps, no post-smoothing,
averaged error reduction rates.
disc. mesh level
Example 4.3 Example 4.1 continued Now let us turn back to Example 4.1 formulated in
the preceding section. Table 5 shows the averaged error reduction rates obtained for higher
order discretisations with the W (1; 1)-cycle, solving
by the
exible GMRES method the reduction of the Euclidean norm of the residual by the
achieved with the rst
exible GMRES steps. We applied 10 iteration
steps each time in the GMRES method for solving the pressure Schur complement equation
(51).
Although system (13) is solved only approximately in each smoothing step, the results
in

Table

5 show averaged error reduction rates which are independent of the level.
number of pre smoothing steps
averaged
error
reduction
rate

Figure

4: Example 4.2, averaged error reduction rate for dierent numbers of pre-smoothing
steps, P 3 =P 2 discretisation, mesh level 4.

Table

5: Example 4.3, averaged error reduction
rates.
disc. mesh level
3 2.29e-1 2.27e-1 2.25e-1 2.21e-1 2.18e-1
Example 4.4 W-cycle in a 3d test case. This example demonstrates the behaviour of the
multi-level solver applied to a three-dimensional problem. We
consider
the prescribed solution given by
The constant c is chosen such that p 2 L 2
and the right hand side f is chosen such that
(u; p) full (3).
For discretisations based on hexahedra, the initial grid (level 0) was obtained by dividing
the unit cube into eight cubes of edge length 1=2 as indicated in Figure 5. The initial

Figure

5: Meshlevel 0 (left) and 1 (right)
grid for discretisations based on simplicial mesh cells consists of 48 tetrahedrons. The
corresponding numbers of degrees of freedom are given in Table 6. It is noteworthy that
sometimes a lower order nite element space possesses more degrees of freedom than a
higher order space on the same mesh level, e.g. compare P nc

Table

Degrees of freedom for the discretisations in the 3d test case, Example 4.4.
disc. mesh level

Table

7 presents results obtained with the W (3; 3)-cycle,
The saddle point problems in the smoothing process (13) were solved up to a reduction of
the Euclidean norm of the residual by a factor 10 4 or at most 20
exible GMRES iterations.
Computations with weaker stopping criteria did not lead to such clearly level-independent
rates of convergence as presented in Table 7. This behaviour corresponds to the theory by
Zulehner [34] which is valid if the approximation of the solution of (13) is close enough to
the solution.
4.4

Acknowledgement

The research of Petr Knobloch has been supported under the grants No. 201/99/P029 and
201/99/0267 of the Czech Grant Agency and by the grant MSM 113200007. The research

Table

7: Example 4.4, averaged error reduction rate
disc. mesh level
of Gunar Matthies has been partially supported under the grant FOR 301 of the DFG.



--R

A class of iterative methods for solving saddle point problems.
Analysis of some
A multigrid algorithm for the mortar
A multigrid method for nonconforming fe- discretisations with applications to non-matching grids


Multigrid Methods
An optimal-order multigrid method for P 1 nonconforming nite elements
A nonconforming multigrid method for the stationary Stokes equations.
On the convergence of Galerkin-multigrid methods for nonconforming nite ele- ments
On the convergence of nonnested multigrid methods with nested spaces on coarse grids.
Multigrid algorithms for the nonconforming and mixed methods for nonsymmetric and inde
Multigrid and multilevel methods for nonconforming Q 1 elements.

Conforming and nonconforming
Finite element methods for Navier-Stokes equations

Higher order
A coupled multigrid method for nonconforming
Numerical performance of smoothers in coupled multigrid methods for the parallel solution of the incompressible Navier-Stokes equations
On Korn's inequality for nonconforming
On the inf-sup condition for the P mod 1 element
The new nonconforming
Simple nonconforming quadrilateral Stokes element.
A exible inner-outer preconditioned GMRES algorithm
GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems.
Eine Klasse von e
Parallele L
A general transfer operator for arbitrary
Multigrid Methods for Finite Elements.
Multigrid techniques for a divergence-free nite element discretization

The derivation of minimal support basis functions for the discrete divergence operator.
A class of smoothers for saddle point problems.
--TR
GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems
Multigrid methods for nonconforming finite element methods
A flexible inner-outer preconditioned GMRES algorithm
The derivation of minimal support basis functions for the discrete divergence operator
An efficient smoother for the Stokes problem
Multigrid and multilevel methods for nonconforming <italic>Q</italic><subscrpt>1</subscrpt> elements
Multigrid Algorithms for Nonconforming and Mixed Methods for Nonsymmetric and Indefinite Problems
Convergence of nonconforming multigrid methods without full elliptic regularity
A multigrid method for nonconforming FE-discretisations with application to non-matching grids
A Multigrid Algorithm for the Mortar Finite Element Method
A coupled multigrid method for nonconforming finite element discretizations of the 2D-Stokes equation
A class of smoothers for saddle point problems
Finite Element Method for Elliptic Problems

--CTR
M. Jung , T. D. Todorov, Isoparametric multigrid method for reaction-diffusion equations on two-dimensional domains, Applied Numerical Mathematics, v.56 n.12, p.1570-1583, 12 December 2006
finite element discretisation;multi-level method;stokes problem;mixed problems