Iterative Substructuring Preconditioners for Mortar Element Methods in Two Dimensions.
The mortar methods are based on domain decomposition and they allow for the coupling of different variational approximations in different subdomains. The resulting methods are nonconforming but still yield optimal approximations. In this paper, we will discuss iterative substructuring algorithms for the algebraic systems arising from the discretization of symmetric, second-order, elliptic equations in two dimensions. Both spectral and finite element methods, for geometrically conforming as well as nonconforming domain decompositions, are studied. In each case, we obtain a polylogarithmic bound on the condition number of the preconditioned matrix.
Introduction
. Since the late nineteen eighties, interest has developed in non-overlapping
domain decomposition methods coupling different variational approximations
in different subdomains. The mortar element methods, see [10], have been designed
for this purpose and they allow us to combine different discretizations in an optimal
way. Optimality means that the error is bounded by the sum of the subregion-by-
subregion approximation errors without any constraints on the choice of the different
discretizations. One can, for example, couple spectral methods of different polynomial
degrees, or spectral methods with finite elements, or different finite element methods
with different meshes. Also, the domain partitioning need not be geometrically con-
forming, i.e. the intersection of the closures of two neighboring subdomains may only
be parts of certain edges of these subdomains.
The basic ideas of the mortar method can be outlined as follows: the skeleton of
the decomposition (i.e. the union of the subdomains interfaces) is itself partitioned
into mortars. Each mortar is an entire edge of one of the subdomains; the mortars
are disjoint open sets. The chosen local discretizations may force the method to be
nonconforming and we only impose a type of weak continuity. For each
and for each nonmortar side \Gamma j
k of
@\Omega k , we introduce a carefully chosen discrete space
~
kh of functions supported on \Gamma j
k . Weak continuity, in this context, then means that
the
k )\Gammaprojection of the jump across \Gamma j
k into the space ~
kh vanishes. In the first
version of the mortar method, strong continuity constraints were also imposed at the
vertices of the subdomains but this turned out not to be necessary. A second version
of the mortar method, developed and analyzed by Ben Belgacem and Maday [6],[7],
does not require such constraints. In particular for problems in three dimensions, the
second version offers important advantages over the first and in what follows, we shall
exclusively work with this more recently developed method. We note that, in a finite
element context, similar nonconforming methods have been studied by Le Tallec et al
INSA Rennes, 20 Av des Buttes de Coesmes, 35043 Rennes, France and CMAP, Ecole Polytechnique
91128 Palaiseau, cedex France. Electronic mail address: achdou@cmapx.polytechnique.fr
y Laboratoire ASCI, B"atiment 506, Universit'e Paris Sud, 91405 Orsay and Universit'e Paris 6,
Paris, France. Electronic mail address: maday@ann.jussieu.fr
z Courant Institute of Mathematical Sciences, 251 Mercer St, New York, NY 10012. Electronic
mail address: widlund@cs.nyu.edu. URL: http://cs.nyu.edu/cs/faculty/widlund/index.html. This
work was supported in part by the CNRS, while this author was visiting Universit'e Paris 6, in part by
the National Science Foundationunder Grant NSF-CCR-9503408, and in part by the U. S. Department
of Energy under contract DE-FG02-92ER25127.
.
Mortar element methods offer many advantages:
ffl They increase the portability of spectral methods.
ffl In the context of finite elements, they provide flexibility in the construction of
the mesh. For example, they may be used in some cases to avoid updating the finite
element mesh (sliding meshes [5]) or, on the contrary, to simplify the adaption of the
meshes ([9]).
ffl They are well suited for parallel computing.
There has already been several implementations of the mortar methods, among
them [5] with sliding meshes, [23] for spectral element methods, [18] for a nonconforming
finite element method for elasticity problems, and [4] for the Navier Stokes
equation.
In the present paper, we propose algorithms for solving the algebraic linear systems
arising from the mortar methods. After the elimination, in parallel, of the degrees
of freedom internal to the subdomains, there remains to find the traces of the solution
on the subdomain boundaries, i.e. to solve the Schur complement system. In our
methods, we work only with the true unknowns of the Schur complement systems, i.e.
the unknowns associated with the mortars and the vertices of the subdomains. The
method presented here can be viewed as a generalization of an iterative substructuring
algorithm first introduced by Bramble, Pasciak, and Schatz [12], for two-dimensional
conforming discretizations and which was reinterpreted in terms of block-Jacobi methods
in [14]. The algorithm consists essentially of decomposing suitably the discrete
space into a direct sum of subspaces in such a way that the related block-Jacobi preconditioned
conjugate gradient method has a satisfactory rate of convergence. Each
mortar can be associated in a natural way with a subspace but, in addition, a global
coarse space must be included to deal with the low frequency error. We obtain a
polylogarithmic bound, in terms of the local number of unknowns, on the number of
iterations required for a given accuracy. Therefore, the proposed algorithm can be
considered as almost perfectly scalable.
Other algorithms have also been proposed. A Neumann-Neumann preconditioner
is studied and tested in [18]. In [2], a saddle point formulation of the system, as in
[6], is considered, and iterative methods based on a certain class of preconditioners is
suggested. A saddle point algorithm for which the internal degrees of freedom need
not be eliminated is proposed in [16]. In [13], a method based on a hierarchical basis
representation, cf. [24], is developed and tested for low order mortar finite elements
and geometrically conforming decompositions of the regions.
In three dimensions, the preconditioner of this paper is not satisfactory, and another
iterative substructuring method has been proposed; see [22]. In addition, an extension
of the theory for two-level Schwarz algorithms, using overlapping subregions,
has been completed for the mortar finite element case; see [26].
The paper is organized as follows. In Section 2, a brief review is given of the
mortar finite element method in the geometrically conforming case. An iterative substructuring
preconditioner for that case is proposed and studied in Section 3. The
geometrically nonconforming mortar finite element method is discussed in Section 4.
Finally, a generalization to the spectral element method in the geometrically conforming
and geometrically nonconforming cases is carried out in Section 5.
2. Mortar Element Methods in the Geometrically Conforming Case.
Let\Omega be a bounded polygonal domain of IR 2 , and let
k=1 be a partition
of\Omega
into K non-overlapping open quadrilaterals:
We make this restriction to polygonal domains and subdomains only to simplify the
presentation. The domain decomposition is called geometrically conforming if the
intersection of the closure of two subdomains is either empty, a vertex, or an entire
common edge of the two subdomains. For any 1  k 6= '  K, let \Gamma k' be the closed
straight segment, possibly degenerate, given by \Gamma k'
us also introduce
V as the set of crosspoints of the domain decomposition which are not on @
\Omega\Gamma and the
skeleton, defined by
We assume that the subdomains have uniformly bounded aspect ratios but there
is no need to assume that the subdomains form a quasiuniform coarse triangulation.
All what follows concerns the Dirichlet problem for Poisson's equation
(1)
but our results hold for any self-adjoint, elliptic, second order operator.
Families of finite element triangulations T k;h are associated with
K, which we assume satisfy the classical shape regularity assumption on the elements.
We denote by h k the maximum diameter of the elements of T k;h . To simplify our
analysis, we also assume that the meshes are quasiuniform for each
recall that quasiuniformity for a triangular mesh means that there exist two positive
constants  and oe such that for all triangles T of T k;h , h k  hT  oeae T . Here hT is
the diameter of T , and ae T the diameter of the circle inscribed in T . Let X kh be the
related space of piecewise linear continuous finite element functions which vanish on
@
Denoting by T r k the trace operator
The product spaces X h and X h are defined by:
Y
Y
If j\Gamma k' j 6= 0, we also introduce X k;';h by
Clearly, X k;';h is a subspace of the space
X k;';h of the piecewise linear continuous
functions on the corresponding mesh of \Gamma k' (X
;). The
dimension of
denoted by N k' the number of nodes of T k;h on \Gamma k' .
We note that the meshes need not match at the interface between two subdomains.
Thus, in order to discretize the space H 1
0(\Omega\Gamma8 we have to introduce, for each 1  k !
space ~
W k;';h of Lagrange multipliers used to impose a weak
continuity constraint across \Gamma k' . A choice has to be made since this space of Lagrange
multipliers can be associated with either
X k;';h or
One strategy is always to
choose the one of largest dimension, but we emphasize that any other choice can also
be supported by existing theory, and that the same asymptotical error bound results
in all cases.
In the case where the Lagrange multiplier space ~
W k;';h is based on
be the shape functions of X k;';h associated with the nodes of
T k;h on \Gamma k' , with OE 0 and OE Nk'+1 associated with the endpoints of \Gamma k' . Then, ~
W k;';h is
Fig. 1. Shape functions of the spaces
chosen as the space spanned by (OE it is a
subspace of
X k;';h of codimension two. Figure 1 illustrates the construction of ~
from
It is now possible to define the subspace Y h of
R
oe
and the subspace Y h of
ae
Z
(v
oe
Consider an edge Assuming that the Lagrange multiplier space ~
is built from the mesh T kh , then the nodes of T are called
slave and master nodes, respectively, because the value of v h 2 Y h at any slave node is
completely determined by the values at the master nodes and crosspoints. Assuming
that j\Gamma k' j ? 0, then the edge
is said to be a slave, or nonmortar, and
master, or mortar, edge
respectively, if the space ~
W k;';h is based on the mesh
T kh and T 'h , respectively. We denote by NV the number of degrees of freedom at the
crosspoints of the domain decomposition, and by Nm and N s the number of master
and slave nodes, respectively. Then, the dimension of X h and Y h are NV
and NV +Nm , respectively.
IR; be the bilinear form:
Z\Omega
The discretized problem corresponding to (1) is: Find u h 2 Y h such that
Z\Omega
It is natural to introduce two subspaces which are orthogonal in the sense of this
energy inner product. The first, X ffi
consists of functions which vanish on the
interfaces, i.e. X ffi
0g. The other is the
subspace of the discrete harmonic extensions ~
i.e. the unique
solution ~ u h of
a(~
~
(2)
In order to reduce the size of the problem, it is possible to solve, in parallel, a discrete
Dirichlet problem for each subdomain, i.e. to find u
h such that
Z\Omega
Defining the bilinear form s corresponding to a discrete Poincar'e-
Steklov operator
there remains to find u h 2 Y h such that
The solution of (2) is then given by u
The goal of the next section is to find a basis of Y h for which a block diagonal
preconditioner for S h yields a condition number almost independent of the mesh
parameters.
3. Preconditioners for the Geometrically Conforming Mortar Element
Method. In the following c and C will denote positive constants uniformly bounded
away from 0 and 1, respectively. They are, in particular, independent of the H k and
the diameters of the
subdomain\Omega k and its elements, and in the spectral case, of
the degree of the polynomials.
3.1. Decomposition of the space Y h . The purpose of this section is to decompose
the vector space Y h into the direct sum of a coarse space YH of dimension
NV (the number of degrees of freedom associated with the crosspoints) and of a fine
space Y H
h of dimension Nm (the number of master nodes):
Here
A few notations will be needed in order to specify the coarse space YH . Let A be a
crosspoint and let KA denote the set
It is clear that
cardinal (KA ). For each crosspoint A, and for each k 2 KA ,
we define a basis vector e A;k 2 Y h , such that,
1. e A;k
2. for all vertices B 6= A
3. for all ' 6= k, and for all vertices B
4. e A;k is linear on master edges.
For a given crosspoint A 2
clearly vanishes on all edges except those
which have A as an endpoint. Let A and B be the endpoints of In
the case where \Gamma k' is a master side of
@\Omega k , the restriction of e A;k
k to \Gamma k' is the linear
function ~ e k;';A with the value 1 at A and 0 at B. The restriction of e A;k
l to \Gamma k' is the
unique function ~
';k;h such that
R
If conversely, \Gamma k' is a slave side of
@\Omega k , the restriction of e A;k
l to \Gamma k' is 0, while
the restriction of e A;k
k to \Gamma k' is the unique function ~ e k;';A in X k;';h such that,
~
Z
~
e k;';A
The coarse space YH is defined by
It is clear that the dimension of YH is NV .
In what follows, it will be necessary to have accurate estimates of certain Sobolev
norms of the basis vectors of the coarse space YH .
Lemma 1. Let A be a crosspoint and k; ' 2 KA , with j\Gamma k' j ? 0. Assume that
is a slave side
of\Omega k and let ~ e k;';A be the unique function in X k;';h defined
by (6). Then,
Proof. Let ~
E be the vector of coordinates of ~
e k;';A in the previously described basis
of shape functions of X k;';h associated to the nodes of T k;h which lie on
. Using the boundary values for ~
e k;';A , we find that the vector ~
satisfies:
~
~
l 13
l
l N kl \Gamma23
(l N kl \Gamma2
l N kl \Gamma13
l
Here l i is the length of the i-th mesh interval of \Gamma k' . Since the mesh T kh is quasiuniform,
~
B is spectrally equivalent to the diagonal matrix D j h k I and therefore the Euclidean
norm of the vector ~
E is of order 1, since the Euclidean norm of F is of order h k .
Therefore, (8) is proved. The next inequality, (9), now follows by using a well known
inverse inequality for quasiuniform meshes. Finally, (10) is obtained from (8) and
and the Gagliardo-Nirenberg interpolation inequality.
Remark 1. In the same way, we can also prove the same estimates for the
function ~ e ';k;A \Gamma ~
e k;';A when the side
is a master side
of\Omega k .
Remark 2. From (10) and Remark 1, it follows immediately that 8A 2 V; 8k 2
KA ,
Denoting by j:j 1=2;  the product semi-norm on
useful to have bounds of je A;k j 1=2;  for any A 2 V and k 2 KA . Three cases can be
1. Both sides
adjacent to A are slave sides.
2. Both sides
adjacent to A are master sides.
3. One side
adjacent to A is a slave side, the other a master side.
In the third case, we have the following result.
Lemma 2. Let A be a crosspoint and let k;
Assume that
is a slave side
of\Omega k and that
master side
of\Omega k . Then,
je A;k
Proof. From the quasiuniformity of the mesh T kh , there exists a constant C such
that for all ffl 2 (0; 1=2),
je A;k
Ch \Gamma2ffl
Let f k;m;A and f k;';A be the functions on
@\Omega k , which coincide with e A;k
respectively, and with 0 on
@\Omega k n\Gamma km and and
respectively. It is then
clear that at all mesh points which are not vertices,
e A;k
The semi-norm jf k;m;A j 2
can be computed explicitly, because f k;m;A is
piecewise linear, and the following bound is obtained:
It now follows from (8) and an inverse inequality that
Ch 2ffl
Choosing
combining (13) and (14), we obtain the desired
result by using (12).
The next lemma is proved in the same way as Lemma 2.
Lemma 3. Let A be a crosspoint and let k; ' 2 KA , with j\Gamma k' j ? 0. Assume that
is a master side
of\Omega k . Then,
je A;k
It is also possible to prove the following result for the first and second cases:
Lemma 4. Let A be a crosspoint and let k;
Assume that the sides
are either both master or
both slave sides
of\Omega k . Then,
je A;k
C:
Proof. The result is very easy when both sides are master sides, because e A;k
is then continuous and piecewise linear on
@\Omega k . When both sides are slave sides, it
follows from Lemma 1 that
and the proof is completed by using an inverse inequality.
Lemmas 2-4 can be summarized in the following corollary:
Corollary 1. Let A be a crosspoint and let k 2 KA . Then,
3.2. A block-Jacobi preconditioner.
Let ~
S be the matrix of S h in the new basis described above. The matrix ~
S can be
written as
~
ShH
~
~
In order to design a preconditioner for ~
S, we replace the block ~
ShH by 0, and the
block ~
S hh by its block diagonal part with one block for each mortar. The resulting
preconditioner is "
S with
In this section, we will develop bounds for the condition number of the preconditioned
S. For that purpose, the following well known result will prove useful:
There exist two constants c and C such that
see, e.g., [11], in particular the discussion of an extension theorem for finite element
spaces. Let " s h be the bilinear form corresponding to the matrix "
S. The following
lemma gives an upper bound for the eigenvalues of "
Lemma 5. There exists a positive constant C such that
Proof. Consider an element v h 2 Y h . There then exists a unique pair (v H
h \Theta YH such that
Obviously,
Observing that for any x 2 \Gamma, there is a uniform bound on the number of subspaces
with elements which do not all vanish at x, we deduce that there exists a constant C
such that
In addition,
To find a lower bound for the eigenvalues of "
S, the following lemma is needed:
Lemma 6. There exists a constant C such that
is the coarse space component of v h .
Proof. Consider a vector v h 2 Y h , and let (v H
h \Theta YH be given as in
(17). Then,
Consider specifically the
subdomain\Omega ' and denote by fV i g 1iNV;' the vertices of
and by
1iNV;' the subdomains adjacent
to\Omega ' . We choose a numbering such
that
joins the crosspoints V i and V i+1 .
It is clear that
vH
Denote by w'H the continuous piecewise linear function on
@\Omega ' which interpolates
v 'h at the V i . We can then write v'H as
\Gamma k' is a slave side of
(v kh
Here ~ e ';k;V i is defined by (5). Proceeding exactly as in [12], we can prove that
In addition, since v h
denotes the mean value of v kh over the edge \Gamma k' . Therefore,
k' is a slave side of
But, see, e.g., [15],
and
In addition, from Lemma 3,
which gives the desired result
since\Omega ' has a uniformly bounded number of neighbors.
We can now prove a lower bound for the eigenvalues of "
Theorem 1. There exists a constant C such that
Proof. Consider a vector v h 2 Y h , and let (v H
h \Theta YH be given by (17).
It is clear that
C
We now focus on the term jv
. Using exactly the same arguments as
in [12],[15], it is possible to bound this expression by
which completes the proof of the theorem. To make our paper more self contained, we
will outline a proof of this result.
Assume that \Gamma k' is the segment (0; H). By the definition of the H 1=2
x
dx:
Clearly,
and it is possible to use Lemma 6.
Since the last two terms of (21) are very similar, we concentrate on the first. As
in [15], this integral is split into two, over (0; h k ), respectively. It is easily
seen that
x
and that
Z hkjv kh
x
From (11), it follows that
Thus, from (22),(23), and (24),
We now use the following very important property of the projection into the coarse
space: the component v kH
depends only on v kh
and v lh
, and, for any c 2 IR,
c is associated through this mapping to v kh
Recalling
that
, and choosing c =! v kh
, we find,
ck 2
ck 2
as in (20).
We can now obtain a bound on the condition number of "
Theorem 2. There exists a constant C such that
Remark 3. In order to design a convenient and inexpensive preconditioner,
we should replace the blocks of "
S hh in a suitable way. The preconditioners defined
above can be simplified in two ways: first the fine space blocks can be replaced by
more convenient matrices by using for instance hierarchical bases as described in [24]
and [13]. Another possible simplification is crucial for parallelism: it makes sense to
replace the block "
S hh of the preconditioner, related to the fine space, by a matrix
corresponding to a bilinear form  s
h \Theta Y H
constructed as follows: Each
h is mapped to  v h 2 X h given by
on the mortar sides,
on the nonmortar sides,
For the resulting preconditioner, it is easy to prove, by using the stability result of Ben
Belgacem [6], Lemma 1, that the condition number estimate (25) remains valid in the
geometrically conforming case. A full discussion will be given, in Subsection 4.3, of
the geometrically nonconforming case.
4. Preconditioners for the Geometrically Nonconforming Mortar Element
Methods.
4.1. The geometrically nonconforming mortar element method. In this
section, we turn to the mortar element method in the case when the decomposition
is no longer geometrically conforming. We will still assume that the aspect ratios
of the subdomains are bounded by a positive constant, and we recall that H k is the
diameter of the
subdomain\Omega k . We also assume that there exists a constant c such
that if
Before formulating the discrete problem, we will adapt some of our previous notations
and introduce some new ones. For
denote the edges
of
@\Omega k . Among the set of all edges
we select a family
of mortars ffl m g 1mM , satisfying the following three conditions:
1. [
2. 8(m; n)
3. 8m 2 there exists k(m); j(m) such that
k(m) .
Denoting by X j
kh the vector space of the traces on \Gamma j
k of the functions of X kh , we
introduce the vector space W h
Y
As in the geometrically conforming case, let us introduce the space
kh of the piecewise
linear continuous functions on the corresponding mesh of \Gamma j
k . Then ~
kh denotes the
subspace of
kh of the functions which are constant in the two end segments of T kh "\Gamma j
k .
The nonconforming approximation of H 1
0(\Omega\Gamma is given by the space
if 9m such that (k;
else
R
We can also introduce the trace space Y h
As in Section 2, the edge
k is called a mortar or master side
of\Omega k if there exists
Mg such that (k; and a nonmortar or slave side
otherwise.
Again, the unknowns interior to each subdomain can be eliminated by solving, in
parallel, one Dirichlet problem for each subdomain, and we are led to the problem of
solving (4). As in the previous section, the goal is to find a basis of Y h for which a
block-Jacobi preconditioner leads to condition numbers which are almost independent
of the size of the subdomains and elements. As in Section 3, the preconditioner will
consist of a coarse space block and a block for each mortar.
4.2. Decomposition of the vector space Y h . As in Subsection 3.1, we decompose
the vector space Y h into the direct sum of a coarse space YH of dimension NV
(the number of degrees of freedom associated with the crosspoints) and a fine space
h of dimension Nm (the number of master nodes). Thus,
where
A basis of YH is defined as follows. For each vertex A, and for each k 2 KA , the basis
vector e A;k 2 YH is fully determined by the following four conditions:
1. e A;k
2. for all vertices B 6= A
3. for all ' 6= k, for all vertices B
4. e A;k is linear on the master edges.
As in Subsection 3.1, the coarse space YH is defined by
Consider first a vertex A
k is a slave side
of\Omega k and let B be the other
end point of
k . Then,
e A;k
e A;k
R
e A;k
Exactly as in Lemma 1, we can prove that
C
Cp
C:
Assume now that \Gamma j
k is a master side
Let ~
e A;k
be the trivial extension of e A;k
k . Just as in Lemma 1, and
Remark 1, we can prove that
To give a flavor of the proof, let us consider the case depicted in Figure 2:
Let C 0 and C 1 be the endpoints of \Gamma i
' and let D 0 and D 1 be the endpoints of
the mesh segment containing the crosspoint A. We introduce the continuous function
~
e A;k;' defined on \Gamma i
' , which is piecewise linear on the mesh of \Gamma i
' , and satisfies
~
k on (D
linear on (D
l
Fig. 2.
In turn, ~ e A;k;' is split into the sum of two piecewise linear functions ~ e A;k;'
1 and ~ e A;k;'such that
~
e A;k;'
e A;k;'
where
~
e A;k;'
1 linear on (D
Let  h be the L 2 -projection onto X i
'h . It is clear that
e A;k
Therefore,
It is clear that k~e A;k
' and from the L 2 stability of  h , the first
term of the right hand side of the inequality above is bounded by C
h ' . Then, an argument
as in Remark 1 yields the same bound for the second term k(I \Gamma  h )~e A;k;'
From the observation (30), it is possible to prove the following lemma in the same
way as Lemma 3.
Lemma 7. Let A be a crosspoint and let \Gamma j
k be a master side
of\Omega k with an end
point A. Let ' 6= k, and let
je A;k
As in Subsection 3.2, let ~
S be the matrix of S h in the new basis described above.
Again, the matrix ~
S can be described by formula (15) and it is possible to define a
block diagonal preconditioner "
S by (16). The bilinear form related to "
S is called
An upper bound for the eigenvalues of "
S is given by a counterpart of Lemma 5,
which is proved exactly as for the geometrically conforming case. To find a lower
bound, we have to prove an analogue of Lemma
Lemma 8. There exists a positive constant C such that
where v H is the projection of v h on YH along Y H
h .
Proof. Consider a vector v h 2 Y h , and let (v H
h \Theta YH be given by (17).
One can check that
We focus on one subdomain denoted
wH be the
continuous piecewise linear function on
@\Omega 0 taking the same values as v 0h at the
vertices of
@\Omega 0 . v 0H can be rewritten as
0 is a slave side of
~
where the functions ~
H will be specified below.
Let us focus on a single slave side \Gamma j
0 of
which we call
convenience. The related space of Lagrange multipliers ~
0h is denoted ~
W flh . Let
be the subdomains such that jfl "
in such a way that
and\Omega k+1 are adjacent. In the rest of the proof, we assume that k(fl) ? 1, but the
results also hold for slight modification, which will not be discussed
here. Also denote by the side of
adjacent to fl, as shown in Figure
3:
Fig. 3. The side fl of
@\Omega 0 and adjacent subdomains
The length of fl and fl k are called d fl and d fl k , respectively.
A calculation shows that
~
where
and
where the function wH has been extended linearly outside fl. Let us further focus
on the term fi k e Ck ;k
0 can be estimated in the same way. For
can be rewritten as
(v kh (C k
For simplicity only, we assume that for 0  k  k(fl), the intersection of fl and fl k
contains the support of at least one basis function of the Lagrange multiplier space
related to fl; this hypothesis can be eliminated by decomposing the quantities v kh (C k )\Gamma
it is possible to choose
a nonnegative  h 2 ~
W flh supported in fl k , such that
R
R
R
R
R
R
Therefore, as in the proof of Lemma 6,
Additionally, because of (28), we can prove the following estimate:
je Ck ;k
which is slightly stronger than (31).
For k(fl), the ratio d(A;Ck )
is smaller than one and the estimate
follows from (32) and (33). For the situation is somewhat more difficult
because d(A;Ck )
may be large; however, in this case je C k(fl) ;k(fl)
is bounded
by C
h0 )). Therefore, we find that
Exactly as for the geometrically conforming case, it is now possible to prove the
following result:
Theorem 3. There exists a constant C such that
4.3. The fine space block "
S hh . To simplify the implementation, it makes sense
to replace the block "
S hh of the preconditioner, related to the fine space, by a matrix
corresponding to a bilinear form  s
h \Theta Y H
constructed as follows: Each
h is mapped to  v h 2 X h given by
on the mortar sides,
on the nonmortar sides,
and
The related preconditioner is called
S, and it is easy to prove that
To obtain a condition number estimate, we first state the following lemma.
Lemma 9.
Let\Omega 0 be a subdomain and let fl be a nonmortar side of
@\Omega 0 . Let
1kk(fl) be the mortars adjacent to fl; here fl k is a whole side of
@\Omega k . Then,
there exists a constant C such that 8v h 2 Y H
Proof. Let the function ~ v h be defined on [ 1kk(fl)  fl k by the restrictions of v kh to
Let  be the mortar projection which maps ~ v h to v 0h j fl . As in the proof of Lemma
8, we set w be the piecewise linear continuous
function which interpolates ~ v h at (C k ) 0kk(fl) , A and B. Of course, w vanishes at all
the C k and thus depends linearly only on the two parameters v 1h (A) and v k(fl)h (B).
When necessary, we shall use the notation w(\Delta; \Delta).
It is clear that
Let us first bound w. Using the same arguments as in Lemma 7, we find that the
square of the H 1=2(fl)-norm of w(0; 1) and w(1; are bounded by C(1
Additionally,
Therefore,
There remains to estimate (~v h \Gamma w). From the stability of the operator , given in
Lemma 1 of [6], we have
C
The right hand side of (36) can be bounded using the same argument as in the proof
of Theorem 1, and we obtain
The proof of the lemma follows by using (35), (36), and (37).
The following corollary is an analogue of Lemma 5:
Corollary 4.1. There exists a positive constant C such that
The next result follows from Corollary 4.1, the analogue of Theorem 1 for the
geometrically nonconforming case, and (34):
Theorem 4. There exists a constant C such that
5. Preconditioners for the Mortar Spectral Method.
5.1. The geometrically conforming case. For simplicity only, we shall now
assume that the
subdomains\Omega k are rectangles with sides parallel to the coordinate
axes. We first give a brief review of the mortar spectral method; see [7] for more
details. For a review on the analysis of the Legendre spectral methods, see, e.g., [8].
Consider a family of integers fN k g k2f1:::Kg , all greater than two. Let X kN be the
space of polynomials
on\Omega k of degree N k in each space variables, which vanish on
\Omega\Gamma and let X kN be the space of traces of functions of X kN on
@\Omega k . A product
space is defined by
Y
For each
subdomain\Omega k , a quadrature formula is given, by the Gauss-Lobatto-
Legendre formula on (\Gamma1; 1), an affine transformation, and tensorization. We denote
the corresponding nodes and weights by  i;j;k and ! i;j;k , and by
GL;k the quadrature
GL;k
The nodes  i;j;k define a grid T kN
on\Omega k . A discrete bilinear form is given by
GL;k
Consider two adjacent
and\Omega ' and let L k' be equal to N k or N ' . Let
and denote by ~
W k;';N the space of polynomials of degree N k' . The
subspace YN of XN is now introduced by
R
oe
and the subspace YN of XN by
R
(v
oe
Slave and mortar sides are introduced exactly as in Section 2, and the Poincar'e-Steklov
bilinear form s can be introduced in terms of the problem of finding
YN such that
GL;k
f ~
Here
N is obtained by solving the analogue of (3) and ~ vN is the discrete harmonic
extension of vN .
As before, we look for a decomposition of the space YN into the direct sum of
a coarse space YH , of dimension NV , and a fine space Y H
N . For each crosspoint A
and for each k 2 KA , the basis vector e A;k of YH is fully determined by the following
conditions:
1. e A;k
2. for all vertices B 6= A
3. for all ' 6= k, for all vertices B
4. e A;k is linear on the master edges.
Suppose first that \Gamma k' is a slave edge of
@\Omega k . We can then check, using coordinates
such that \Gamma with the value H corresponding to A, that
e A;k
e A;'
Here Ln is the Legendre polynomial of degree n. From (39) and (40), it is straight-forward
to show that C: The next lemma provides estimates of the
and H 1=2
\Gammanorms of e A;k .
Lemma 10.
log(N k' )
Proof. Without loss of generality, we can assume that \Gamma k' and to simplify
the notations, we also set . Recalling that
it is easy to show that
In order to evaluate the H 1=2 -norm of ~
e k;';A , we compute the H 1=2 -norm of Ln . By
the definition of the norm, we have to estimate
dxdy:
Integration by parts, in the case where n is even, leads to
x\Gammay
x\Gammay
x\Gammay
1\Gammay
\Gamma1\Gammay
x\Gammay
and similarly, in the case where n is odd,
Hence,
dxdy
1\Gammay 2 dy n even;
1\Gammay 2 dy n odd:
In order to estimate the last terms in this formula, we use Gaussian quadrature based
on the roots (i i ) 1in of Ln . It is well known that there exists positive quadrature
weights (! i ) 1in such that
We therefore obtain
We now recall, see [25],(thm 6.21.3 & (15.3.14)) that
and that there exist two positive constants c and C such that
c
We find that
dy
We recognize this last expression as a Riemann sum of ( 1
dy  Clog(n):
The same argument leads to
dy  Clog(n);
which in turn leads to
x\Gammay
x\Gammay dxdyj  Clog(n):
Finally, we remark that
Here (Ln (x)\GammaL n (y)\Gamma(x\Gammay)L 0
(x\Gammay) 2 is a polynomial of degree ! n in both x and y. The
orthogonality of the Legendre polynomials then leads to
By using (41), we find that
dxdy  Clog(n):
Thus, the square of the H 1=2 -norm of Ln is bounded by Clog(n) and so is the square
of the H 1=2 -norm of ~
The next result is the analogue of Lemma 2:
Lemma 11. Let A be a crosspoint and let k;
Assume that
is a slave side
of\Omega k and that
master side
of\Omega k . Then,
je A;k
Proof. Since we are interested in the H 1=2
is possible to
rescale the problem and assume that the edge \Gamma k' is (\Gamma1; 1). We again set
We first use the following inverse inequality,
je A;k
Cn 4ffl je A;k
see [8].
Let us denote by f k;m;A and f k;';A the functions on
@\Omega k which are equal to e A;k
respectively, and vanish on
@\Omega k n\Gamma k' , respectively. It
is clear that, almost everywhere,
e A;k
The semi-norm jf k;m;A j 2
can be computed explicitly, because f k;m;A is
piecewise linear, and the following estimate is obtained:
To evaluate the contribution of f k;';A , it is enough to estimate the following quantity
Here  is the characteristic function of (\Gamma1; 1). It can be proved, as in Lemma 5.1,
that the contribution of
jx\Gammayj 2\Gamma2ffl is bounded by C(1+log(n)). There
remains to estimate
This is done as follows:
Hence,
je A;k
Choosing
log(n)
yields
je A;k
Let ~
S be the matrix of s N in the new basis described above. The matrix ~
S can
be written as
~
~
~
In order to design a preconditioner for ~
S, we replace the block ~
SNH by 0, and the block
~
SNN by its block diagonal with one block for each edge. The resulting preconditioner
is
s N be the bilinear form corresponding to the matrix "
S. The bound,
is obtained exactly as in Lemma 5.
The following lemma will also be needed:
Lemma 12. There exists a constant C such that 8v kN 2 X kN ,
Similarly, if x 0 is a point of
Proof. To prove (43), we first rescale so that the diameter
then prove that
This formula is true for any function and can be derived by using a Fourier transform
argument. From an inverse inequality for polynomials, we also have
Choosing
yields the desired result. Finally, (44) is obtained by a standard
quotient space argument.
Given Lemma 12, analogues of Lemma 6 and Theorem 1 can be obtained as in
the finite element case. The only notable difference is when estimating the integral
\GammaH
cf. (21)-(24) in the proof of Theorem 1. The integral is again split into two, over
respectively. Here the ( i ) i2f0;Nkg are the Gauss-Lobatto
points in [\Gamma1; 1]. We note that  1
) and that an inverse inequality for
polynomials of degree n is given by
Finally, since all necessary technical tools are at hand, the proof of the following
main result can be obtained
Theorem 5. There exists a constant C such that
5.2. The geometrically nonconforming case. The previous mortar spectral
element method can be generalized straightforwardly to the case where the assumption
of geometrical conformity is relaxed. The analysis of our preconditioner requires, in
Lemma 5.5 below, a bound on the relative size of the intersection of two edges; in
order to provide estimates which only depend polylogarithmically on the parameter
N , we make the assumption that
c;
a condition less standard and more stringent than (28). The mortar method is based
on the definition of the master and slave sides as described in Section 4 in the finite
element context. The projection that gives slave values in terms of those on the master
edges is defined as in Subsection 5.1. The iterative substructuring algorithm now
considered is the same as that of Section 4. We now have the new tools of Subsection
5.1 at our disposal, and in order to prove a result equivalent to Theorem 3 for the
spectral approximation, we additionally only have to derive an analogue of Lemma 7.
We do so after some preliminary work.
The definition of the mortar condition naturally leads to the introduction of a
projection operator
N (\Gamma1; 1); given by
This projection operator has already been analyzed in [7] and certain stability and
approximation properties are given in that paper. While we do not now know how to
prove a uniform bound for the H 1=2
00 -norm of this operator, the following results will
allow us to derive a strong result on our preconditioner.
Lemma 13. Let a be any real number in a denote the piecewise
linear, discontinuous function on that vanishes on linearly
from 1 and 0 over the interval [a; 1]. There then exists a constant C such that
log(N
Proof. Let 'N be a polynomial of degree N in one variable that vanishes at \Sigma1.
It is easy to see that it can be written as
an
Recalling that the Legendre polynomials Ln are L 2 (\Gamma1; 1)-orthogonal, with norm
and that they satisfy the differential equation
d
dx
we can first show that
a 2
Using now the integral relation
and the differential equation once more, we find that
an
Here we have used the L 2 \Gammaorthogonality of the Ln and the formula
an
(a
Let us denote by [IP N (\Gamma1; 1)"L 2 (\Gamma1; 1); IP N (\Gamma1; 1)"H 1
the interpolation
space, with index ', between the space of polynomials IP N (\Gamma1; 1) of degree N provided
with the L 2 -norm and the H 1
respectively. By a main result of interpolation
theory [20], it follows from our two estimates of the norms of 'N that there exists a
constant C such that, for all 'N 2 IP N (\Gamma1; 1),
C
We recall now that, according to [21], [IP N (\Gamma1; 1)"L 2 (\Gamma1; 1); IP N (\Gamma1; 1)"H 1
coincides topologically with IP N (\Gamma1; 1) provided with the H '
-norm. In particular, we
can conclude that
C
In order to complete the proof, we now evaluate the coefficients an of the decomposition
of given by (46). By using the definition of  a , we find that
a (x)L 0
a
a Ln (x)
Combining the integral and the differential formulae for the Legendre polynomials,
we deduce
(a)
(a)
From [1], (22.14.9), we know that
jLn (a)j  C
As another consequence of the integral formula, we find that
which yields
(a)
Finally from (48),(49), and (50), we deduce that
By using (46), we obtain
Thus,
an
and hence
By introducing this bound into formula (47), we can conclude that
log(N
It is now an easy matter to state an analogue of the Lemma 7.
Lemma 14. Assume that (45) holds, let A be a crosspoint, and let \Gamma j
k be a master
side
of\Omega k with A as an end point. Let ' 6= k,
je A;k
Proof. Let us denote by  ' the function obtained from  by a scaling which maps
' with the further property that  '
B are the end points of \Gamma i
k . By construction, e A;k
continuous and it even
belongs to H 3
2 \Gamma" for any positive ". We decompose e A;k
' into the following sum
e A;k
supplies the desired bound for the first term j '
(@\Omega l ) . The bound
on the second, j '
(@\Omega l ) , is obtained as in the geometrically conforming
case.
Lemma 14, we are ready to prove the following result using the same arguments
as in Section 4.
Theorem 6. Under the assumption (45), there exists a constant C such that



--R

Handbook of mathematical functions
Substructuring preconditioners for the Q 1 mortar element method
M'ethodes it'eratives de sous-structuration pour les 'el'ements avec joints
A fast solver for Navier-Stokes equations in the laminar regime using mortar finite element and boundary element method
On the mortar element method: generalization and implementation
The mortar finite element method with Lagrange multipliers
A spectral methodology tuned to parallel implementations
Approximations Spectrales de Probl'emes aux Limites Ellip
Raffinement de maillage en 'el'ements finis par la m'ethode des joints
A new nonconforming approach to domain de- composition: the mortar element method
Iterative methods for the solution of elliptic problems on regions partitioned into substructures
The construction of preconditioners for elliptic problems by substructuring
A hierarchical preconditioner for the mortar finite element method
Some domain decomposition algorithms for elliptic problems
Domain decomposition algorithms with small overlap
Efficient iterative solvers for elliptic finite element problems on nonmatching grids
Domain decomposition methods in computational mechanics
Domain decomposition with non matching grids: Augmented Lagrangian approach

Probl'emes aux Limites non Homog'enes et Applications
Rel'evement de traces polynomiales et interpolations hilbertiennes entre espaces de polyn
In preparation.
Nonconforming discretizations and a posteriori error estimators for adaptive spectral element techniques
A domain decomposition algorithm using a hierarchical basis


--TR

--CTR
C. Cinquini , P. Venini, A mortar approach for the analysis and optimization of composite laminated plates, Computational structures technology, Civil-Comp press, Edinburgh, UK, 02
Ilaria Perugia , Dominik Schtzau, On the Coupling of Local Discontinuous Galerkin and Conforming Finite Element Methods, Journal of Scientific Computing, v.16 n.4, p.411-433, December 2001
Dan Stefanica, FETI and FETI-DP Methods for Spectral and Mortar Spectral Elements: A Performance Comparison, Journal of Scientific Computing, v.17 n.1-4, p.629-638, December 2002
Micol Pennacchio, The Mortar Finite Element Method for the Cardiac Bidomain Model of Extracellular Potential, Journal of Scientific Computing, v.20 n.2, p.191-210, April 2004
Feng , Catherine Mavriplis , Rob Feng , Rupak Biswas, Parallel 3D Mortar Element Method for Adaptive Nonconforming Meshes, Journal of Scientific Computing, v.27 n.1-3, p.231-243, June      2006
T. P. Mathew , G. Russo, Maximum norm stability of difference schemes for parabolic equations on overset nonmatching space-time grids, Mathematics of Computation, v.72 n.242, p.619-656, 1 April
domain decomposition;mortar finite element method;iterative substructuring