Multigrid for the Mortar Finite Element Method.
A multigrid technique for uniformly preconditioning linear systems arising from a mortar finite element discretization of second order elliptic boundary value problems is described and analyzed. These problems are posed on domains partitioned into subdomains, each of which is independently triangulated in a multilevel fashion. The multilevel mortar finite element spaces based on such triangulations (which need not align across subdomain interfaces) are in general not nested. Suitable grid transfer operators and smoothers are developed which lead to a variable V-cycle preconditioner resulting in a uniformly preconditioned algebraic system. Computational results illustrating the theory are also presented.
Introduction
The mortar finite element method is a non-conforming domain decomposition
technique tailored to handle problems posed on domains that are partitioned into
independently triangulated subdomains. The meshes on different subdomains need
not align across subdomain interfaces. The flexibility this technique offers by allowing
sub-structures of a complicated domain to be meshed independently of each
other is well recognized. In this paper we consider preconditioned iteration for the
solution of the resulting algebraic system. Our preconditioner is a non-variational
multigrid procedure.
The mortar finite element discretization is a discontinuous Galerkin approxima-
tion. The functions in the approximation subspaces have jumps across subdomain
interfaces and are standard finite element functions when restricted to the sub-
domains. The jumps across subdomain interfaces are constrained by conditions
associated with one of the two neighboring meshes. Bernardi, Maday and Patera
(see [2, 3]) proved the coercivity of the associated bilinear form on the mortar finite
element space, thus implying existence and uniqueness of solutions to the discrete
problem. They also showed that the mortar finite element method is as accurate
as the usual finite element method. Recently, stability and convergence estimates
for an hp version of the mortar finite element method were proved [16].
When each subdomain has a multilevel mesh, preconditioners for the linear system
arising from the mortar discretization can be developed by multilevel tech-
niques. A hierarchical preconditioner with conditioning which grows like the square
1991 Mathematics Subject Classification. 65F10, 65N55, 65N30.
Key words and phrases. mortar, finite element method, multigrid, V-cycle, preconditioning,
domain decomposition.
This work was supported by the National Science Foundation under grant DMS 9626567, the
Environmental Protection Agency under grant R 825207 and the State of Texas under ARP/ATP
grant 010366-168.
c
fl0000 American Mathematical Society
of the number of levels is described in [8]. In this paper, we show that a variable
V-cycle may be used to develop a preconditioned system whose condition number
remains bounded independently of the number of levels.
One of the difficulties in constructing a multigrid preconditioner for the mortar
finite element method arises due to the fact that the multilevel mortar finite
element spaces are, in general, not nested. Multigrid theory for nonnested spaces
[5] may be employed to construct a variable V-cycle preconditioner, provided a
suitable prolongation operator can be designed. We construct such a prolongation
operator and prove that it satisfies the "regularity and approximation" property
(Condition (C.2)) required for application of the multigrid theory.
The next difficulty is in the design of a smoother. Our smoother is based on the
point Jacobi method. Its analysis is nonstandard since the constraints at subdomain
interface gives rise to mortar basis functions with non-local support. We prove that
these basis functions decay exponentially away from their nodal vertex. This leads
to a strengthened Cauchy-Schwarz inequality which is used to verify the smoothing
hypothesis (Condition (C.1)).
The remainder of the paper is organized as follows. Section 2 introduces most of
the notation in the paper. Section 3 describes the multilevel mortar finite element
spaces. In Section 4 the variable V-cycle multigrid algorithm is given and the
main result (Theorem 4.1) is stated and proved. Section 5 provides proofs of some
technical lemmas. Implementation issues are considered in Section 6 while the
results of numerical experiments illustrating the theory are given in Section 7.
2. Preliminaries
In this section, we provide some preliminaries and notation which will be used in
the remainder of the paper. In addition, we describe the continuous problem and
impose an assumption on the regularity of its solution.
Let\Omega be an open subset of the plane. For non-negative integers s; the Sobolev
space H s
(see [7, 11]) is the set of functions in L
with distributional derivatives
up to order s also in L
If s is a positive real number between non-negative
integers
s(\Omega\Gamma is the space obtained by interpolation (by the real
method [13]) between H
The Sobolev norm on H
s(\Omega\Gamma is denoted
by k\Deltak
s;\Omega and the corresponding Sobolev seminorm is denoted by j\Deltaj
and a segment fl contained
in\Omega ; the trace of OE on fl is denoted by OEj
We will often write kOEk r;fl and jOEj r;fl for the H r (fl) norm and seminorm respectively,
of the trace OEj
Assume
that\Omega is connected and that its boundary, @ is polygonal. Let
@\Omega be
split into
@\Omega D and
@\Omega N such that
[@\Omega D and
@\Omega D is empty and
assume that
@\Omega D has nonzero measure. Denote by V the subspace of the Sobolev
space H 1
(\Omega\Gamma consisting of functions in H
whose trace on
@\Omega D is zero. Denote
by V 0 the dual of the normed linear space V : The dual norm k\Deltak
\Gamma1;\Omega is defined by
kuk
1;\Omega
denotes the duality pairing. Note that L
2(\Omega\Gamma is contained in V 0 if we
identify the functional ! v; OE ?= (v; OE), for all v 2 L
2(\Omega\Gamma6 Here (\Delta; \Delta) denotes the
inner product in L
s;\Omega is the norm on the space defined
by interpolation between V 0 and L
We seek an approximate solution to the problem
where A(\Delta; \Delta) is bilinear form on V \Theta V defined by
Z
\Omega
and F is a given continuous linear functional on H
This problem has a unique
solution. For the mortar finite element method, we restrict our attention to F of
the form
Z
\Omega
This is the variational form of the boundary value problem
@U
Although our results are stated for this model problem, extension to more general
second order elliptic partial differential equations with more general boundary
conditions are straightforward.
We will need to assume some regularity for solutions of Problem (2.1). We
formalize it here into Assumption (A.1).
There exists a fi in the interval (1=2; 1] for which
\Gamma1+fi;\Omega holds for solutions U to the problem (2.1).
This is known to hold for wide class of domains [11, 12]. Note that we do not
require full elliptic regularity
3. The Mortar Finite Element Method
In this section, we first provide notation for sub-domains and triangulations.
Next multilevel mortar finite element spaces are introduced and the mortar finite
element problem is defined.
Partition\Omega into non-overlapping polygonal
K: The
n@\Omega is broken into a set of disjoint open straight line segments
k each of which is contained in
@\Omega j for some i and j: The collection of these
edges will be denoted by Z; i.e.,
Each\Omega i is triangulated to produce a quasi-uniform mesh T i
1 of size h 1 . The
triangulations generally do not align at the subdomain interfaces. We assume that
the endpoints of each interface segment in Z are vertices of T p
and q are such that fl ae
Denote the global mesh [
To set
up the multigrid algorithm, we need a sequence of refinements of We refine the
triangulation T 1 to produce T 2 by splitting each triangle of T 1 into four triangles
by joining the mid-points of the edges of the triangle. The triangulation T 2 is
then quasi-uniform of size h Repeating this process, we get a sequence of
triangulations each quasi-uniform of size h
We next define the mortar finite element spaces following [1, 2, 3, 16] (our notation
is close to that in [16]). First, we define spaces e
M k by
e
@\Omega D g
and
f
is linear on each triangle of T k g:
Throughout this paper we will use piecewise linear finite element spaces for convenience
of notation. The results extend to higher order finite elements without
difficulty [10].
For every straight line segment fl 2 Z; there is an i and j such that fl '
Assign one of i and j to be the mortar index, M(fl); and the other then is the non-
mortar index, NM(fl):
Let\Omega M(fl) denote the mortar domain of fl
and\Omega NM(fl) be
the non-mortar domain of fl: For every u 2 e
and u NM
fl to be the trace
of
uj\Omega M(fl) on fl and the trace of
uj\Omega NM(fl) on fl respectively.
We now define two discrete spaces S k (fl) and W k (fl) on an interface segment
fl: Every fl 2 Z can be divided into sub-intervals in two ways: by the vertices of
the mesh in the mortar domain of fl and by those of the non-mortar domain of fl:
Consider fl as partitioned into sub-intervals by the vertices of the triangulation on
non-mortar side. Let these vertices be denoted by x i
Denote the sub-intervals
[x
are the sub-intervals
that are at the ends of fl: The discrete space S k (fl) is defined as follows.
v is linear on each ! k;i
v is constant on ! k;1 and on ! k;N ;
and v is continuous on fl:
We also define the space W k (fl) by
v is linear on each ! k;i
v vanishes at end-points of fl; namely x 0
k;fl and x N
and v is continuous on fl:
The multilevel mortar finite element spaces are now defined by:
ae
on each fl 2 Z;
R
for all - 2 S k (fl):
oe
The "mortaring" is done by constraining the jump across interfaces by the integral
equality above. We will call this constraint the weak continuity of functions in
Note that though the spaces f f
are nested,
f
the multilevel spaces fM k g are generally non-nested.
We next state the error estimates for the mortar finite element method. The
mortar finite element approximation of the solution U of Problem (2.1) (with F
given by (2.2)) is the function U
e
Z
\Omega
(3.
where e
A(u; v) is the bilinear form on e
V \Theta e
defined by
e
Z
It is shown in [2] that
A(u; u) for all
Here and in the remainder of this paper, we will use
C to denote a generic constant independent of h k which can be different at different
occurrences. It follows that (3.3) has a unique solution. It is also known (see [2])
that the mortar finite element approximation satisfies
We now define a projection, \Pi which will be very useful
in our analysis. For u 2 L 2 (fl), it can be shown [3] that there exists a unique
Z
Z
u- ds for all - 2 S k (fl):
We define \Pi k;fl u to be v. This projection is known to be stable in L 2 (fl) and H 1
i.e.,
under some weak assumptions on meshes (see [16]) which hold for the meshes
defined above.
The projector \Pi k;fl is clearly related to the weak continuity condition. Let fy j
denote the nodes of T k and the operator
M k be defined by (also see

Figures

It is easy to see that if e u is in f
is an element of M k .
We next define a basis for M k . Let f e
be the nodal basis for
f
. There are more than one basis element associated with a node which appears
in multiple subdomains. The basis for M k consists of functions of the form
For every vertex y l
k located in the open segment fl 2 Z and belonging to the non-
mortar side mesh, the corresponding OE l
k as defined above is zero. Every remaining
vertex y l
k leads to a nonzero OE l
k since OE l
k and e
OE l
k have the same nonzero value at
y l
Also, the values of OE l
k and e
OE l
k at all nodes which are not nodes from non-mortar
mesh lying in the interior of some fl 2 Z are the same. This implies that nonzero
functions in fOE i
k g are linearly independent. It is not difficult to check that these
also form a basis for at y l
k is one and all other OE i
are zero, these
functions, in fact, form a nodal basis. Denote by N k the total number of nonzero
6 JAYADEEP GOPALAKRISHNAN AND JOSEPH E. PASCIAK
Nonmortar
-0.4
-0.2
Figure

1. Two subdomains
with meshes that
do not align at interface.0.51.5-1
-0.4

Figure

2. A discontinuous
e u; which is 1 on a
mortar node and 0 on the
remaining nodes.
Mortar trace0.20.61

Figure

3. The thick
line shows e
the thin line shows
-0.4

Figure

4. Plot shows
e
by extending \Pi k;fl e u M
as
described by (3.8).
Illustrating the action of
We now re-index f e
in such a way that every nonzero OE i
k is in
fy i
k g in this new ordering.
Now that we have a nodal basis for M k ; we may speak of the corresponding
vertices of T k as degrees of freedom for Consider an interface segment
All vertices on fl are degrees of freedom except: (i) those on
@\Omega D ; and (ii) those on
fl and are from the nonmortar mesh. These are the vertices y i
4. Multigrid algorithm for the Mortar FEM
We will apply multigrid theory for non-nested spaces [5] to construct a variable V-cycle
preconditioner. Before giving the algorithm, we define a prolongation operator
and smoother. Later in this section, we will prove that our algorithm gives a
preconditioner which results in a preconditioned system with uniformly bounded
condition number.
First let us establish some notation: A k will denote the operator on M k ; generated
by the form e
A(\Delta; \Delta) i.e., A k is defined by
A(u; v) for all u;
The largest eigenvalue of A k is denoted by - k . For each basis element OE i
k , we define
to be the one dimensional subspace of M k spanned by OE i
k . Then
provides a direct sum decomposition of
4.1. Smoothing and Prolongation operators. We will use a smoother R k given
by a scaled Jacobi method i.e.,
A
where ff is a positive constant to be chosen later. Here, A
k and
are defined by
and
respectively. R k is symmetric in the (\Delta; \Delta) inner-product.
It will be proved in Section 5 that
There exists a positive number CR independent of k such that
(R k u; u); for all
In addition, I \Gamma R k A k is non-negative.
We now define "prolongation operators" I
Clearly, I k u needs to satisfy the weak continuity constraint (see Definition 3.2).
We define I k u by:
I k
In the next section we show that I k satisfies:
There exists a constant C fi independent of k such that
for all u in
Here P k is the e
A-adjoint of I k ; i.e.,
e
A(u; I k+1 OE) for all
Condition (C.2) is verified using the regularity of the underlying partial differential
equation.
4.2. The algorithm. Let m(k); positive integers depending on k
and
be defined by
The variable V-cycle preconditioner B k for defined as follows:
Algorithm 4.2:
1. For
2. For is defined recursively by:
(a) Set x
(b)
(c) Set y I k q; where q is given by
(d) Define y l for
We make the usual assumption on m(k) (cf. [5]):
(A.2): The number of smoothings m(k); increases as k decreases in such a way
that
holds
Typically fi 1 is chosen so that the total work required for a multigrid cycle is no
greater than the work required for application of the stiffness matrix on the finest
level. This condition is satisfied, if for instance,
The following theorem is the main result of this paper.
Theorem 4.1. Assume that (A.1) and (A.2) hold. There exists an ff and M ? 0
independent of J such that
A(u; u) for all
m(J) fi=2 .
The theorem shows that B J is a uniform preconditioner for the linear system
arising from mortar finite element discretization using M J even if Increasing
m(J) gives a somewhat better rate of convergence but increases the cost
of applying It suffices to choose ff above so that ff ! 1=C 1 where C 1 is as in
Lemma 4.4.
We use the following lemmas to prove Theorem 4.1. Their proofs will be given
in Section 5. First we state a lemma that is a consequence of regularity which will
be used in the proof of Condition (C.2).
Lemma 4.1. If (A.1) holds, then
0;\Omega
e
holds for all u in M
The next three lemmas are useful in analyzing the smoothing operator. We begin
with a lemma from the theory of additive preconditioners.
MULTIGRID FOR THE MORTAR FINITE ELEMENT METHOD 9
Lemma 4.2. Let the space V be a sum of subspaces
be a symmetric positive definite operator on V i and Q i be the L 2 projection
holds for all u in V:
Lemma 4.2 may be found stated in a different form in [14, Chapter 4] and we
do not prove it here. The following two lemmas are used in the proof of Condition
(C.1).
Lemma 4.3. For R k defined by (4.1), there exists a constant independent
of k such that (4.2) holds for all u in
Lemma 4.4. For all u in M k , there is a number C 1 not depending on J such that
e
where
k is the nodal basis decomposition.
We now prove the theorem.
Proof of Theorem 4.1: We apply the theorem for variable V-cycle in [4, Theorem
4.6]. This requires verification of Conditions (C.1) and (C.2).
Because of Lemma 4.3, (C.1) follows if we show that I \Gamma R k A k is non-negative,
i.e., for all
This is equivalent to showing that for all
(R
Fix
k be its nodal basis decomposition. Applying
Lemma 4.2 gives
(R
ff
ff
e
The non-negativity of I \Gamma R k A k follows provided that ff is taken to be less than or
equal to 1=C 1 where C 1 is as in Lemma 4.4.
Condition (C.2) is immediately seen to hold from Lemma 4.1. Indeed,
e
e
Here we have used the fact that - k - Ch \Gamma2
This proves (C.2) and thus completes
the proof of the theorem. 2
5. Proof of the lemmas
As a first step in proving Lemma 4.1, we prove that the operators fI k g are
bounded operators with bound independent of k. After proving Lemma 4.1, we
state and prove two lemmas used in the proof of Lemmas 4.3 and 4.4.
Lemma 5.1. There exists a constant C independent of k such that
for all
Proof: Fix . By definition, I k
on every interior vertex of the mesh
The above sum is taken over the vertices y i
k of
the\Omega NM(fl) mesh that lie on fl:
Here and elsewhere - denotes equivalence with constants independent of h k and
denotes the L 2 (fl) norm of the nonmortar trace of E k;fl u: By the L 2
stability of \Pi k;fl ,
Since u is in M denoting u M
by e; we have
where (\Delta; \Delta) fl denotes the L 2 (fl) inner-product. Applying the Cauchy-Schwarz inequality
to the right hand side, we have
where the last inequality follows from the approximation properties of S
Thus,
Applying the triangle inequality, an inverse inequality, and a trace theorem yields
That I k is bounded now follows by the triangle inequality, (5.1) and (5.5). 2
Proof of Lemma 4.1: The proof is broken into two parts. First, we prove that
holds for all u in M k\Gamma1 . Next, we show that
holds for all u in M k : Clearly the lemma follows using (5.7) to bound the first term
on the right hand side of (5.6) and the fact that - k - Ch \Gamma2
k .
Fix u in M k and set
e
be the solution of
Now u is the mortar finite element approximation to w from M k and hence by (3.4),
By the triangle inequality,
To estimate the second term of (5.10), we start by writing P
solves
e
The remainder v 2 satisfies
e
Here I denotes the identity operator. Then, by Lemma 5.1 and (3.4),
For the last term in (5.12), we proceed as in the proof of Lemma 5.1 (see (5.1))
to get
Setting
we have as in (5.3),
Let Q denote the L 2 projection into S Because of the approximation properties
of S Trivially, we also have that
Now since w is in H
1=2;@\Omega M(fl)
1=2;@\Omega NM(fl)
Since restriction to boundary is a continuous operator this becomes
Thus,
where we have used (3.4) in the last step. This gives (recall (5.13))
1+fi;\Omega which estimates the last term in (5.12).
For the middle term in (5.12), we find from (5.11) that
As in Lemma 5.1 (see (5.2) through (5.5)), we get that
This proves that jjjv 2 jjj - Ch k kA k uk
Combining the above estimates gives
Using this in (5.10) and applying Assumption (A.1) proves (5.6).
We next prove (5.7). Fix u in M k . Since k\Deltak
\Gamma1+fi;\Omega is the norm on the space in
the interpolation scale between V 0 and L
\Gamma1;\Omega
Thus it suffices to prove that
Given / in V , we will construct /
and
Assuming such a / k exists, we have
k/k
k/k
1;\Omega
k/k
1;\Omega
Inequality (5.15) then follows from
\Gamma1;\Omega - sup
0;\Omega k/k
1;\Omega
e
k/k
1;\Omega k/k
1;\Omega
e
To complete the proof, we need only construct / k satisfying (5.16) and (5.17).
For
M k be the L 2 projection of / into f
k . This projection is local
on\Omega i and satisfies (see [6]),
and
0;\Omega
To construct / k , we modify e
so that the result is in M k , i,e.,
We will now show that / k defined above satisfies (5.16). We start with
e
Using (5.18) on the first term on right hand side and using (5.1) on the remaining,
we get
e
Note that
e
by (5.2). Since / is in H
its trace on fl is in L 2 (fl): Moreover, / M
are equal. Hence,
e
where in the last step we have used a trace inequality. Using (5.18) and (5.19), we
then have,
e
k/k
Combining (5.21) and (5.20) gives (5.16).
14 JAYADEEP GOPALAKRISHNAN AND JOSEPH E. PASCIAK
It now remains only to prove (5.17). By the triangle inequality,
0;\Omega
0;\Omega
The first term on the right hand side is readily bounded as required by (5.19). For
the second term, as in (5.1),
0;\Omega
e
Inequality (5.17) now follows immediately from (5.21). This completes the proof of
Lemma 4.1. 2
We are left to prove the lemmas involving the smoother R k . A critical ingredient
in this analysis involves the decay properties of the projector \Pi k;fl away from the
support of the data. Specifically, we use the following lemma:
Lemma 5.2. Let v 2 L 2 (fl) be supported on oe ' fl: Then there is a constant c such
that for any set - ' fl disjoint from oe;
\Gammac dist(-; oe)
where dist(-; oe) is the distance between the sets - and oe:
Remark 5.1 Estimates similar to those in the above lemma for the L 2 -orthogonal
projection were given by Descloux [9]. Note that \Pi k;fl is not an L 2 -orthogonal
projection. For completeness, we include a proof for our case which is a modification
of one given in [18, Chapter 5].
Proof: Recall that a fl 2 Z is partitioned into sub-intervals ! k;i by the vertices
of the mesh
as the union of those
sub-intervals which intersect the support of v: Following the presentation in [18],
define r recursively, by letting r m be the union of those sub-intervals
of fl that are not in [l!m r l and which are neighbors of the sub-intervals of this set
(see

Figure

5). Further, let
We will now show that the L 2 norm of \Pi k;fl v on dm can be bounded by a constant
times its L 2 norm on r m : For all - 2 S k (fl) with support of - disjoint from r 0 ; we
have
Let -m 2 S k (fl), for m - 1, be defined by
ae
holds with -m in place of
-: Moreover, -m it vanishes on fl n
Z
dmn"
ds
Z
dm ""
ds
Z
rm
-m \Pi k;fl v ds:
Note that on each sub-interval of dm " "; -m is constant, and it takes the value
of \Pi k;fl v at the interior endpoint. Also, on the sub-intervals of r m ; -m is either
identically zero (if that sub-interval is part of r m " ") or takes the value of \Pi k;fl v on
ff fi
oe

Figure

5. An interface segment
one endpoint and zero on the other endpoint. From these observations, it is easy
to conclude that Z
dm ""
-m \Pi k;fl v ds - C k\Pi k;fl vk 2
and Z
rm
ds - C k\Pi k;fl vk 2
Thus,
Z
dmn"
ds
Z
dm ""
-m \Pi k;fl v ds
Z
rm
-m \Pi k;fl v ds - C k\Pi k;fl vk 2
Letting
0;dm ; the above inequality can be rewritten as q m -
It immediately follows that
'm
The lemma easily follows from (3.6) and the observation that the distance between
- and oe is O(mh). 2
Proof of Lemma 4.3: Fix
k be the nodal basis
decomposition. By Lemma 4.2,
(R
ff
l
ff
l
Note that the L 2 norm of every basis function OE i
k is O(h 2
Indeed, this is a standard
estimate for those basis functions that coincide with a usual finite element nodal
basis function on a subdomain. For the remaining basis functions, this follows from
the exponential decay given by Lemma 5.2. Thus,
(R
ff
On each
subdomain\Omega j we have that
k@
e
Combining the above inequalities gives
(R
The above inequality is equivalent to (4.2) and thus completes the proof of the
lemma.2
The proof of Lemma 4.4 requires a strengthened Cauchy-Schwarz inequality
which we provide in the next lemma. First, we introduce some notation. Define
the index sets e
k and N fl
k by
e
"\Omega NM(fl) g
Also denote the set [fN fl
Lemma 5.3. Let OE i
k and OE j
k be two basis functions of M k with
and y j
k be the corresponding vertices. Then, e
e
\Gammac jy i
e
where C and c are constants independent of k:
Proof: First, consider the case when y i
k and y j
k are on a same open interface
segment denote the set of triangles that have at least one vertex on
fl and are contained
denote the set of triangles that
have at least one vertex on fl and are contained
e
The first sum obviously satisfies the required inequality, because this sum is zero
whenever y i
k and y j
k are not vertices of the same triangle in
Now consider a triangle - 2 Recall that fl was subdivided by the non-
mortar mesh into sub-intervals ! k;i the union of two
or more of these sub-intervals which have the vertices of - as an end-point (see

Figure

R
k and OE j
are zero at
least on one vertex of -;
Now, recall that OE i
k and OE j
are obtained from e
k and e
k respectively, as described
by (3.9). Denote by s i and s j the supports of e
respectively. Then by
A
A
\Theta
\Theta
\Theta
A
A
A
A
\Delta?
\Omega M(fl)
\Omega NM(fl)
Shaded triangles form \Delta in
Unshaded triangles form \Delta out

Figure

6. Illustrating the notations in the proof of Lemma 5.3.
Lemma 5.2,
denotes the length of may easily be seen that
Further, by quasi-uniformity,
Split the sum over - 2 \Delta NM in (5.24) into a sum over triangles which have a vertex
lying in between y i
k and y j
k on fl; and a sum over the remaining triangles in \Delta NM .
We denote the former set of triangles as \Delta in
NM and latter as \Delta out
Note that the
number of triangles in \Delta in
NM is bounded by Cjy i
We first consider triangles in \Delta in
The observations of the previous paragraph
yield
in
in
A
exp
\Gammac jy i
\Gammac jy i
Now, for the sum over triangles in \Delta out
observe that one of the distances,
out
\Gammac jy i
\Theta
out NM
exp
\Gammac
The sum on the right hand side can be bounded by a summable geometric series.
out
\Gammac jy i
Thus, (5.25), (5.26) and (5.24) give
e
\Gammac jy i
This with the coercivity of e
A(\Delta; \Delta) on M k \Theta M k proves the lemma when y i
k and y j
lie on the same fl: Note that all the above arguments go through when either y i
k or
k is an endpoint of fl:
To conclude the proof, it now suffices to consider the case when y i
k ) is zero unless there is a triangle -
in T k which has one of its edges contained in fl 1 and another contained in In the
latter case, defining s i and s j to be the supports of e
respectively,
and using similar arguments as before, it is easy to arrive at an analogue of (5.25).
Specifically, if d ij is the distance from y i
k to y j
k when traversed along the broken
line
e
from which the required inequality follows as d ij - jy i
MULTIGRID FOR THE MORTAR FINITE ELEMENT METHOD 19
Proof of Lemma 4.4: Split u into a function u 0 that vanishes on the interface \Gamma
and a function u \Gamma that is a linear combination of OE i
By the triangle
inequality,
e
On each triangle - in T k ;
c i(- ;j) OE i(- ;j)
k on -;
are the vertices of -: Applying the arithmetic-geometric
mean inequality gives
e
e
All that remains is to estimate e
We clearly have
e
e
Applying Lemma 5.3 gives
e
\Gammac jy i
e
e
Here M is the matrix with entries
\Gammac jy i
and
denotes the cardinality of N \Gamma
k and '\Delta' indicates the standard dot product
in R jN \Gamma
To conclude the proof, it suffices to show that kMk ' 2 is bounded by a constant
independent of h k : Note that kMk ' 2 is equal to the spectral radius of M and
consequently, can be bounded by any induced norm. So,
For every fixed i; the sum on the right hand side can be enlarged to run over all
vertices of the mesh T k ; and then one obtains
exp
\Gammac jy j
ZZ
Thus
6. Implementation
This section will describe some details of implementing the mortar method and
the preconditioner B J . Since we shall be using a preconditioned iteration, all that
is necessary is the implementation of the action of the stiffness matrix and that of
the preconditioner.
Let A k denote the stiffness matrix for the mortar finite element method, i.e.,
be an element of M k . To apply A k to first expand v in the
basis f e
k g, apply the stiffness matrices for f
M k and finally accumulate A(v; OE i
. The application of the stiffness matrix corresponding to the space
f
k with nodal basis f e
k g is standard. As we shall see, the first and last steps are
closely related.
The first step above involves computing the nodal representation of a function v
with respect to the basis f e
given the coefficients fp i g appearing in (6.1). Thus,
we seek the vector e
e
e
e
Note that e
Thus, we only need to determine the values of
e
for the remaining indices. These indices appear in some set e
corresponding
to one of the interface segments. We define the transfer matrix T k;fl by
e
e
Then, for
The last step of accumulating e
is also implemented in
terms of T k;fl . Given the results of the stiffness matrix evaluation on f
i.e., the
vector of values e
k ), we need to compute e
k for nodes
which are not on any of the interface segments so we only need to compute e
for nodes such that i 2 N fl
k for some segment. This is given by
e
e
The sum on fl above is over the segments with i 2 N fl
k .
For convenient notation, let us denote by T k , the matrix of the linear process that
takes to fep
g. Then, the matrix corresponding
to f e
k )g is the transpose T t
We now discuss the implementation of the preconditioner Specifically, we
need a procedure that will compute the coefficients of B k v (in the basis fOE i
the values (v; OE i
. The corresponding matrix will be denoted by
The matrix that takes a vector f(w; OE i
k )g to coefficients
of R k w with respect to fOE i
will be denoted by R k : Finally, let C k be the matrix
associated with I k , i.e.,
I k OE i
Assuming B k\Gamma1 has been defined, we define B k g for an g 2 R Nk by:
1. Compute x l for
2. Set y
k q; where q is computed by
3. Compute y l for
4.
This algorithm is straightforward to implement as a recursive procedure provided
we have implementations of R
To compute q
k q k\Gamma1 , we first let e q We then apply the
coarse to fine interpolation corresponding to the imbedding f
k . This
gives a vector which we denote by e
q k . Then q k is given by the truncated vector
To compute the action of the transpose, q we start by defining e
to be the vector which extends q k by e q i
. Next we apply the adjoint
of the coarse to fine imbedding ( f
to define the vector e q k\Gamma1 . Then
Since our codes do not assemble matrices, we use the alternative smoother
where   k is the largest eigenvalue of A k . This avoids the computation of the diagonal
entry e
The corresponding matrix operator R k is just multiplication
by   \Gamma1
k .
We now show that this operator is a good smoother by showing that it satisfies
Condition (C.1). First, (4.2) holds for R k since by Lemma 4.3,
(R k v;
e
22 JAYADEEP GOPALAKRISHNAN AND JOSEPH E. PASCIAK
Now let v be in M k and p be as in (6.1). Then,
(R k A k v; A k
e
This shows that I \Gamma R k A k is non-negative and hence Condition (C.1) is satisfied.
7. Numerical Results
In this section we give the results of model computations which illustrate that
the condition numbers of the preconditioned system remain bounded as the number
of levels increase. The code takes as input general triangulations generated
independently on subdomains, recursively refines these triangulations by breaking
each triangle into four similar ones, solves a mortar finite element problem and
implements the mortar multigrid preconditioner.
We apply the mortar finite element approximation to the problem
where\Omega is the domain pictured in Figure 7 and f is chosen so that the solution
of (7.1) is y(y
domain\Omega is decomposed into sub-domains
and the subdomains are triangulated to get a coarse level mesh as shown
in

Figure

7. The triangulations were done using the mesh generator TRIANGLE
[17]. The smoother used was R k defined in the previous section and
Estimates of extreme eigenvalues of the operator B J A J were given by those of the
Level Minimum eigen- Maximum eigen- Condition Degrees of
J value of B J A J value of B J A J number freedom

Table

7.1. Conditioning of B J A J :
Lanczos matrix (see [15]). Note that the eigenvalues of B J A J coincide with those
of B J A J . As can be seen from Table 7.1, the condition numbers remain bounded
independently of the number of levels as predicted by the theory.



--R

The mortar finite element method with lagrange multipliers.
Domain decomposition by the mortar element method.
A new nonconforming approach to domain decom- position: the mortar element method
Multigrid Methods.
The analysis of multigrid algorithms with nonnested spaces or noninherited quadratic forms.
Some estimates for a weighted l 2 projection.
The Mathematical Theory of Finite Element Methods.
A hierarchical preconditioner for the mortar finite element method.
On finite element matrices.
PhD thesis
Elliptic Problems in Nonsmooth domains.
On the poisson equation with intersecting interfaces.

Multilevel Finite Element Approximation.
Iterative Methods for Sparse Linear Systems.
Uniform hp convergence results for the mortar finite element method.
Engineering a 2D Quality Mesh Generator and Delaunay Triangu- lator
Galerkin Finite Element Methods for Parabolic Problems.
--TR
mortar;multigrid;finite element method;v-cycle;domain decomposition;preconditioning