Two-level algorithms for Rannacher-Turek FEM
In this paper a multiplicative two-level preconditioning algorithm for second order elliptic boundary value problems is
 considered, where the discretization is done using Rannacher-Turek non-conforming rotated bilinear finite elements on
 quadrilaterals. An important point to make i...
Saved in:
| Date: | 2006 |
|---|---|
| Main Authors: | , , |
| Format: | Article |
| Language: | English |
| Published: |
Інститут програмних систем НАН України
2006
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/1583 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Two-level algorithms for Rannacher-Turek FEM / I. Georgiev, J. Kraus, S.Margenov // Проблеми програмування. — 2006. — N 2-3. — С. 694-700. — Бібліогр.: 6 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860119179750801408 |
|---|---|
| author | Georgiev, I. Kraus, J. Margenov, S. |
| author_facet | Georgiev, I. Kraus, J. Margenov, S. |
| citation_txt | Two-level algorithms for Rannacher-Turek FEM / I. Georgiev, J. Kraus, S.Margenov // Проблеми програмування. — 2006. — N 2-3. — С. 694-700. — Бібліогр.: 6 назв. — англ. |
| collection | DSpace DC |
| description | In this paper a multiplicative two-level preconditioning algorithm for second order elliptic boundary value problems is
considered, where the discretization is done using Rannacher-Turek non-conforming rotated bilinear finite elements on
quadrilaterals. An important point to make is that in this case the finite element spaces corresponding to two successive levels of
mesh refinement are not nested in general. To handle this, a proper two-level basis is required to enable us to fit the general
framework for the construction of two-level preconditioners originally introduced for conforming finite elements. The proposed
variant of hierarchical two-level splitting is first defined in a rather general setting. Then, the involved parameters are studied and
optimized. The major contribution of the paper is the derived uniform estimates of the constant in the strengthened CBS
inequality which allow the efficient multilevel extension of the related two-level preconditioners.
|
| first_indexed | 2025-12-07T17:38:04Z |
| format | Article |
| fulltext |
Прикладне програмне забезпечення
© K. Georgiev, E. Donev, 2006
ISSN 1727-4907. Проблеми програмування. 2006. №2-3. Спеціальний випуск 694
UDC 004.75
TWO-LEVEL ALGORITHMS FOR RANNACHER-TUREK FEM
Ivan Georgiev
Institute for Parallel Processing Bulgarian Academy of Sciences
Acad. G. Bonchev Bl. 25A 1113 Sofia, Bulgaria,
john@parallel.bas.bg
Johannes Kraus
Johann Radon Institute for Computational and Applied Mathematics Austrian Academy of Sciences
Altenbergerstrasse 69 A-4040 Linz, Austria,
johannes.kraus@oeaw.ac.at
Svetozar Margenov
Institute for Parallel Processing Bulgarian Academy of Sciences
Acad. G. Bonchev Bl. 25A 1113 Sofia, Bulgaria,
john@parallel.bas.bg
In this paper a multiplicative two-level preconditioning algorithm for second order elliptic boundary value problems is
considered, where the discretization is done using Rannacher-Turek non-conforming rotated bilinear finite elements on
quadrilaterals. An important point to make is that in this case the finite element spaces corresponding to two successive levels of
mesh refinement are not nested in general. To handle this, a proper two-level basis is required to enable us to fit the general
framework for the construction of two-level preconditioners originally introduced for conforming finite elements. The proposed
variant of hierarchical two-level splitting is first defined in a rather general setting. Then, the involved parameters are studied and
optimized. The major contribution of the paper is the derived uniform estimates of the constant in the strengthened CBS
inequality which allow the efficient multilevel extension of the related two-level preconditioners.
Introduction
In this paper we consider the elliptic boundary value problem
( )
,o0=))()((
,o0=
,i)(=)()(
N
D
nnu
nu
nfuLu
Γ⋅∇
Γ
Ω∇⋅−∇≡
xxa
xxxa
(1)
where Ω is a convex polygonal domain in, 2R )(xf is a given function in )(2 ΩL , the coefficient matrix )(xa is
symmetric positive definite and uniformly bounded in Ω , n is the outward unit vector normal to the boundary
Ω∂Γ = , and ND ΓΓ=Γ ∪ . We assume that the elements of the diffusion coefficient matrix )(xa are a piece-wise
smooth functions on Ω . The weak formulation of the above problem reads as follows: given )(2 Ω∈ Lf find
}on 0=:)({=)( D
11 ΓΩ∈Ω≡∈ vHvHVu D , satisfying
.)()()(=),( (ΩH),(=),( where1
D xxxxa dvuvuAvvfvuA ∇⋅∇∈∀ ∫Ω (2)
We assume that the domain Ω is discretized by the partition hΤ which is obtained by a proper refinement of a given
coarser partition HΤ . We assume also that HT is aligned with the discontinuities of the coefficient )(xa so that over
each element HTE ∈ the coefficients )(xa of are smooth functions. The variational problem (2) is then discretized
using the finite element method, i.e., the continuous space V is replaced by a finite dimensional subspace hV . Then
the finite element formulation is: find hh Vu ∈ , satisfying
.)(=),( ),(=),( hhhhhhhhhhh
h
where xa dvuevuAVvvfvuA
e
Te
∇⋅∇∈∀ ∫∑
∈
(3)
Here )(ea is a piece-wise constant symmetric positive definite matrix, defined by the integral averaged values
Прикладне програмне забезпечення
695
of )(xa over each element from the coarser triangulation hT . We note that in this way strong coefficient jumps across
the boundaries between adjacent finite elements from hT are allowed. The resulting discrete problem to be solved is
then a linear system of equations hhh =A fu , with A and hf being the corresponding global stiffness matrix and
global right hand side, and h being the discretization (meshsize) parameter for the underlying partition hT of Ω .
The two-level setting. We are concerned with the construction of a two-level preconditioner M for hA ,
such that the spectral condition number )AM( h
1−
κ of the preconditioned matrix h
1AM − is uniformly bounded with
respect to the meshsize parameter h , and the possible coefficient jumps. The classical theory for constructing optimal
order two-level preconditioners was first developed in [2, 3], see also [1]. The general framework requires to define two
nested finite element spaces hH VV ⊂ , that correspond to two consecutive (regular) mesh refinements. The well
studied case of conforming linear finite elements is the starting point in the theory of two-level and multi-level methods.
Let hT and HT be two successive mesh refinements of the domain Ω , which correspond to HV and hV . Let
},1,2,=k,φ{ (k)
H HNL and },1,2,=k,φ{ h
(k)
h NL be the standard finite element nodal basis functions. We split
the meshpoints hN from hT into two groups: the first group contains the nodes HN from HT and the second one
consists of the rest, where the latter are the newly added node-points H\hN from Hh \ TT . Next we define the so-called
hierarchical basis functions
}.\ φ~{} φ~{=},1,2,=,φ~{ Hh
(m)
hH
(l)
Hh
(k)
h onon TTTNk ∪L (4)
Let then hA
~
be the corresponding hierarchical stiffness matrix. Under the splitting (4) both matrices hA and hA
~
admit in a natural way a two-by-two block structure
}
} ,
AA
AA
=A
H
H\h
2221
1211
h N
N
}
} .
AA
~
A
~
A
=A
~
H
H\h
H21
1211
h N
N
(5)
As is well-known, there exists a transformation matrix
221
1
IJ
0I
=J , which relates the nodal point vectors for the
standard and the hierarchical basis functions as follows,
,J~
~
~
2
1
2
1
=
=
v
v
v
v
v
2121
1
2
1
J~
~
vv
v
v
v
+=
=
Remark 1.1 Clearly, the hierarchical stiffness matrix hA
~
is more dense than hA and therefore its action on a vector
is computationally more expensive. The transformation matrix J , however, enables us in practical implementations to
work with hA , since T
hh JJA=A
~
.
Two-level preconditioners and the strengthened Cauchy-Bunyakowski-Schwarz (CBS) inequality.
Consider a general matrix A , which is assumed to be symmetric positive definite and partitioned as in (5). The quality
of this partitioning is characterized by the corresponding CBS inequality constant:
( ) ( ) ,
AA
A
sup
,
=
1/2
2222
1/2
1111
2121
n
2
nn
1
221 vvvv
vv
RvRv TT
T
∈∈ −
γ (6)
where hNn =1 and HNn =2 . Let us assume also that
.A)(1CAA)(1CA 22222221111111 and δδ +≤≤+≤≤ (7)
The inequalities (7) are in a positive semidefinite sense where 11C and 22C are symmetric and positive definite
matrices for some positive constants iδ , 1,2=i . The multiplicative preconditioner is then of the form
Прикладне програмне забезпечення
696
.
I0
ACI
CA
0C
=M
2
12
1
111
2221
11
F
−
(8)
Then
[ ]{ }.4)(5.01
1
1
)AM( 2
21
2
21212
1
F γδδδδδδ
γ
κ +−+++
−
≤− (9)
When 1111 A=C and 2222 A=C , then estimate (9) reduces to )1/(1)AM( 21
F γκ −≤− . Detailed proof of (9) is
found, for instance, in [1]. In the hierarchical bases context 1V and 2V are subspaces of the finite element space hV
spanned, respectively, by the basis functions at the new nodes H\hN and by the basis functions at the old nodes HN .
For the strengthened CBS inequality constant, there holds that
),(),(
),(
sup
,
),cos(=
hh
h
21
21
vvAuuA
vuA
VvVu
VV
∈∈
=γ (10)
where ),(h ⋅⋅A is the bilinear form which appears in the variational formulation of the original problem. When
{0}=21 VV ∩ , the constant γ is strictly less than one. As shown in [2], it can be estimated locally over each finite
element (macro-element) HTE ∈ , which means that ,max= E
E
γγ where
.,
),(),(
),(
sup
)(),E(
=
EE
E
21
constv
vvAuuA
vuA
EVvVu
E ≠
∈∈
γ
The spaces )(EVk above contain the functions from kV restricted to E and ),( vuAE corresponds to ),(h vuA
restricted over the element E of HT (see also [5]). Using the local estimates, it is possible to obtain uniform estimates
for γ . In the case of linear conforming finite elements, it is known that γ does not depend on h and on any
discontinuities of the coefficients of the bilinear form ),(h ⋅⋅A , as long as they do not occur within any element of the
coarse triangulation used. The h -independence means that if we have a hierarchy of refinements of the domain which
preserve the properties of the initial triangulation (refinement by congruent triangles, for example), then γ is
independent of the level of the refinement as well. For certain implementations, it is shown that γ is independent of
anisotropy. Hence, as long as the rate of convergence is bounded by some function of γ , it is independent of various
problem and discretization parameters, such as the ones mentioned above.
We stress here, that the above technique is originally developed and straightforwardly applicable for
conforming finite elements and nested finite element spaces, i.e., when hH VV ⊂ .
1 Rannacher-Turek finite elements
Nonconforming finite elements based on rotated multilinear shape functions were introduced by Rannacher
and Turek [6] as a class of simple elements for the Stokes problem. More generally, the recent activities in the
development of efficient solution methods for non-conforming finite element systems are inspired by their attractive
properties as a stable discretization tool for illconditioned problems.
The unit square 21,1][− is used as a reference element ê to define the isoparametric rotated bilinear element
hTe ∈ . Let eee →ˆ:ψ be the corresponding bilinear one-to-one transformation, and let the nodal basis functions be
determined by the relation
Fig. 1. Rotated bilinear finite element.
Прикладне програмне забезпечення
697
}.,,{1,}φ̂{,}ψφ̂{=}φ{ 224
1=
14
1= yxyxspaniiiii −∈−
o
For the variant MP (mid point), 4
1=}φ̂{ ii are found by the point-wise interpolation condition
,=)(φ̂ ij
j
i b δΓ
where 1,4=, jb j
Γ are the midpoints of the edges of the quadrilateral ê . Then,
)).(2(1
4
1
=),(φ̂)),(2(1
4
1
=),(φ̂
)),(2(1
4
1
=),(φ̂)),(2(1
4
1
=),(φ̂
22
4
22
3
22
2
22
1
yxyyxyxyyx
yxxyxyxxyx
−−+−−−
−++−+−
The variant MV (mid value) corresponds to integral midvalue interpolation conditions. Let j
eje ˆ
4
1=ˆ = ΓΓ U . Then
4
1=}φ̂{ ii are determined by the equality
,=φ̂|| ˆ
ˆ
1
ˆ ij
j
eij
e
j
e d δΓΓ ∫Γ
−
which leads to
)).3(4(2
8
1
=),(φ̂)),3(4(2
8
1
=),(φ̂
)),3(4(2
8
1
=),(φ̂)),3(4(2
8
1
=),(φ̂
22
4
22
3
22
2
22
1
yxyyxyxyyx
yxxyxyxxyx
−−+−−−
−++−+−
2 Hierarchical two-level splitting by differences and aggregates (DA)
Let us consider two consecutive discretizations HT and hT . Figure 2 illustrates a macro-element obtained
after one regular mesh-refinement step. We see that in this case HV and hV are not nested.
The DA splitting is easily described for one macro-element. If 121 φ,,φ K are the standard nodal basis functions for
the macro-element, then we define
.}φφφ,φφφ
,φ φ,φφφ{=)(
}φφ,φφ,φφ,φφ,φ,φ,φ,φ{=)(
,)()(=}φ,,φ{=)(
4
1,4=
12113
1,4=
87
2
1,4=
1091
1,4=
652
1211871096543211
21121
jj
j
jj
j
jj
j
jj
j
spanEV
spanEV
EVEVspanEV
αα
αφα
∑∑
∑∑
++++
++++
−−−−
⊕K
Using the related transformation matrix ,EJ
(a) One macro-element (b) One element
Figure 2: Uniform refinement on a general mesh.
Прикладне програмне забезпечення
698
,=
1144434241
1134333231
1124232221
1114131211
11
11
11
11
2
2
2
2
2
1
−
−
−
−
αααα
αααα
αααα
αααα
EJ (11)
the vector of the macro-element basis functions 12
1=E }φ{=φ ii is transformed to a new hierarchical basis
.J=}φ~{=~
E
12
1=E Eii ϕϕ Accordingly, EJ transforms the macro-element stiffness matrix into a hierarchical form
.
)E(φ~
)E(φ~
A
~
A
~
A
~
A
~
=JAJ=A
~
2
1
E,22E,21
E,12E,11T
EEEE V
V
i
i
∈
∈
(12)
Following the local definitions, for the whole finite element space hV with the standard nodal finite element
basis hN
i
i
h 1=
)( }φ{=φ we can similarly construct the new hierarchical basis hN
i
i
h 1=
)( }~{=~ ϕϕ and the corresponding splitting
.= 21 VVVh ⊕ (13)
The transformation J such that ,J=~ ϕϕ can be used for transformation of the stiffness matrix hA to
hierarchical form ,JJA=A
~ T
hh which allows preconditioning by the two-level preconditioners based on the splitting
(13). Now, we are in a position to analyze the constant ),(cos= 21 VVγ for the splitting (13). Again, as in the previous
section, we would like to perform this analysis locally, by considering the corresponding problems on macro-elements.
For this purpose we need to have satisfied the condition
(I) )(ker=)
~
(ker ,22 eE AA , which is equivalent to 1=
4
1= iji
α∑ , {1,2,3,4}∈j .
There are obviously various DA splittings satisfying the condition )(i . When the two-level algorithm is recursively
generalized to the multilevel case, it is useful if
(II) ,22
~
EA is proportional to eA .
Such a property holds in a very general setting for the DA splitting of the Crouzeix-Raviart finite element space, see [4].
Unfortunately, it seems to be rather complicated to find a parameter matrix ][ ijα , which satisfies the condition )(ii in
the general case of Rannacher-Turek finite elements.
3. Uniform estimates of the CBS constant
We study in this section the isotropic model problem where all elements HTe ∈ are squares, and the uniform
refinement is as shown in Figure 3. Both variants MP and MV of rotated bilinear finite elements, are considered.
Due to the symmetry of the problem, the down-left block of the transformation matrix EJ can be simplified to
the form
bcaa
cbaa
aabc
aacb
(14)
Прикладне програмне забезпечення
699
The condition )(i is equivalent to 1=2 cba ++ . Let us write the condition )(ii in the form eE pAA =
~
,22 . Then,
)(ii is reduced to a system of two nonlinear equations for, say, ),( cb , with a parameter p . It appears, that the system
for ),( cb has a solution if ),[ 0 ∞∈ pp . In such a case, we can optimize the parameter p , so that the related CBS
constant is minimal.
Variant MP:
Lemma 4.1 There exists a two-level splitting satisfying the condition )(ii , if and only if,
7
3
≥p . Then, the solutions for
),( cb are invariant with respect to the local CBS constant
p
E
4
1
1=2 −γ , and for the related optimal splitting
.
12
52
MP ≤γ (15)
Although the statements of Lemma 4.1. look very simply, the midterm derivations are rather technical, which is
just illustrated by the following expressions of one of the similarly looking solutions for ),( cb :
( ))(6
70
1
=
)(3)(7280)(26587616024786
)224072970(
1
=
pc
ppppp
p
b
φ
φφφ
−
+−+−
+−
−
where 2420326314036401329=)( pppp +−−+−φ .
Variant MV: The same approach is applied to get the estimates below.
Lemma 4.2 There exists a two-level splitting satisfying the condition )(ii , if and only if,
5
2
≥p . Then, the solutions for
),( cb are invariant with respect to the local CBS constant
p
E
4
1
1=2 −γ , and for the related optimal splitting
.
8
32
MV ≤γ (16)
Acknowledgments
This work has been performed during the Special Radon Semester on Computational Mechanics, held at
RICAM, Linz, Oct. 3rd - Dec. 16th 2005. The authors gratefully acknowledge the support by the Austrian Academy of
Sciences. The research of the third author was also partially supported by the NATO Scientific Program Grant CRG
960505.
(a) One macro-element (b) One element
Figure 3: Uniform refinement on a square mesh.
Прикладне програмне забезпечення
700
1. O. Axelsson, Iterative solution methods. Cambridge University Press, 1994.
2. O. Axelsson and I. Gustafsson, Preconditioning and two-level multigrid methods of arbitrary degree of approximations, Math. Comp., 40(1983),
Р. 219-242.
3. R. Bank and T. Dupont, An Optimal Order Process for Solving Finite Element Equations, Math. Comp., 36 (1981), Р. 427-458.
4. R. Blaheta, S. Margenov, M. Neytcheva, Uniform estimate of the constant in the strengthened CBS inequality for anisotropic non-conforming
FEM systems, Numerical Linear Algebra with Applications, Vol. 11 (4) (2004), Р. 309-326.
5. V. Eijkhout and P.S. Vassilevski, The Role of the Strengthened Cauchy-Bunyakowski-Schwarz Inequality in Multilevel Methods, SIAM Review,
33 (1991), Р. 405-419.
6. R. Rannacher, S. Turek, Simple non-conforming quadrilateral Stokes Element, Numerical Methods for Partial Differential Equations, 8(2)
(1992), Р. 97-112.
|
| id | nasplib_isofts_kiev_ua-123456789-1583 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1727-4907 |
| language | English |
| last_indexed | 2025-12-07T17:38:04Z |
| publishDate | 2006 |
| publisher | Інститут програмних систем НАН України |
| record_format | dspace |
| spelling | Georgiev, I. Kraus, J. Margenov, S. 2008-08-27T09:36:44Z 2008-08-27T09:36:44Z 2006 Two-level algorithms for Rannacher-Turek FEM / I. Georgiev, J. Kraus, S.Margenov // Проблеми програмування. — 2006. — N 2-3. — С. 694-700. — Бібліогр.: 6 назв. — англ. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/1583 004.75 In this paper a multiplicative two-level preconditioning algorithm for second order elliptic boundary value problems is
 considered, where the discretization is done using Rannacher-Turek non-conforming rotated bilinear finite elements on
 quadrilaterals. An important point to make is that in this case the finite element spaces corresponding to two successive levels of
 mesh refinement are not nested in general. To handle this, a proper two-level basis is required to enable us to fit the general
 framework for the construction of two-level preconditioners originally introduced for conforming finite elements. The proposed
 variant of hierarchical two-level splitting is first defined in a rather general setting. Then, the involved parameters are studied and
 optimized. The major contribution of the paper is the derived uniform estimates of the constant in the strengthened CBS
 inequality which allow the efficient multilevel extension of the related two-level preconditioners. en Інститут програмних систем НАН України Прикладне програмне забезпечення Two-level algorithms for Rannacher-Turek FEM Article published earlier |
| spellingShingle | Two-level algorithms for Rannacher-Turek FEM Georgiev, I. Kraus, J. Margenov, S. Прикладне програмне забезпечення |
| title | Two-level algorithms for Rannacher-Turek FEM |
| title_full | Two-level algorithms for Rannacher-Turek FEM |
| title_fullStr | Two-level algorithms for Rannacher-Turek FEM |
| title_full_unstemmed | Two-level algorithms for Rannacher-Turek FEM |
| title_short | Two-level algorithms for Rannacher-Turek FEM |
| title_sort | two-level algorithms for rannacher-turek fem |
| topic | Прикладне програмне забезпечення |
| topic_facet | Прикладне програмне забезпечення |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/1583 |
| work_keys_str_mv | AT georgievi twolevelalgorithmsforrannacherturekfem AT krausj twolevelalgorithmsforrannacherturekfem AT margenovs twolevelalgorithmsforrannacherturekfem |