Quasi-Optimal Schwarz Methods for the Conforming Spectral Element Discretization.
The spectral element method is used to discretize self-adjoint elliptic equations in three-dimensional domains. The domain is decomposed into hexahedral elements, and in each of the elements the discretization space is the set of polynomials of degree N in each variable. A conforming Galerkin formulation is used, the corresponding integrals are computed approximately with Gauss--Lobatto--Legendre (GLL) quadrature rules of order N, and a Lagrange interpolation basis associated with the GLL nodes is used. Fast methods are developed for solving the resulting linear system by the preconditioned conjugate gradient method. The conforming finite element space on the GLL mesh, consisting of piecewise Q1 or P1 functions, produces a stiffness matrix Kh that is known to be spectrally equivalent to the spectral element stiffness matrix KN. Kh is replaced by a preconditioner $\tilde{K}_h$ which is well adapted to parallel computer architectures. The preconditioned operator is then $\tilde{K}_h^{-1} K_N$.Techniques for nonregular meshes are developed, which make it possible to estimate the condition number of $\tilde{K}_h^{-1} K_N$, where $\tilde{K}_h$ is a standard finite element preconditioner of Kh , based on the GLL mesh. Two finite element--based preconditioners: the wirebasket method of Smith and the overlapping Schwarz algorithm for the spectral element method are given as examples of the use of these tools. Numerical experiments performed by Pahl are briefly discussed to illustrate the efficiency of these methods in two dimensions.
Introduction
. In the past decade, many preconditioners have been developed
for the large systems of linear equations arising from the finite element discretization
of elliptic self-adjoint partial differential equations; see e.g. [6], [14], [27]. A specially
challenging problem is the design of preconditioners for three dimensional problems.
More recently, spectral element discretizations of such equations have been proposed,
and their efficiency has been demonstrated; see [15], [16], and references therein. In
large scale problems, long range interactions of the basis elements produce quite dense
and expensive factorizations of the stiffness matrix, and the use of direct methods is
not economical due to the large memory requirements [12].
Early work on preconditioners for these equations was done by Pavarino [20], [21],
[19]. His algorithms are numerically scalable (i.e., the number of iterations is independent
of the number of substructures) and quasi-optimal (the number of iterations
grows slowly with the degree of the polynomials.) However, each application of the
preconditioner can be very expensive.
Several iterative substructuring methods which preserve scalability and quasi-
optimality was introduced by Pavarino and Widlund [22], [24]. These preconditioners
can be viewed as block-Jacobi methods after transforming the matrix to a particular
basis. The subspaces used are the analogues of those proposed by Smith [28] for
piecewise linear finite element discretizations. The bounds for the condition number
of the preconditioned operator grows only slowly with the polynomial degree, and are
independent of the number of substructures.
Courant Institute of Mathematical Sciences, New York University, 251 Mercer Street, New York,
N.Y. 10012. Electronic mail address: casarin@cims.nyu.edu. This work has been supported in part by
a Brazilian graduate student fellowship from CNPq, and in part by the U. S. Department of Energy
under contract DE-FG02-92ER25127.
The tensorial character of the spectral element matrix can be exploited when evaluating
its action in a vector [16], but does not help when evaluating the action of the
inverse of blocks of this matrix, as in the case of the above preconditioners. Following
Pahl [17], based on the work of Deville and Mund [7] and of Canuto [5], the above
constructions give rise to different and spectrally equivalent preconditioners using the
same block partitioning of the finite element matrix generated by Q 1 elements on
the hexahedrals of the Gauss-Lobatto-Legendre (GLL) mesh. This observation and
experiments for a model problem in two dimensions were made by Pahl [17], who
demonstrated experimentally that this preconditioner is very efficient. Thus, high order
accuracy can be combined with efficient and inexpensive low-order preconditioning.
We remark that similar ideas also appear in [18] and [26].
The analysis of Schwarz preconditioners for piecewise linear finite elements for
the h-method, has relied upon shape regularity of the mesh [10], [9], [3], which clearly
does not hold for the GLL meshes. We extend the analysis to such meshes, deriving
estimates for these finite element preconditioners of spectral element methods.
We give polylogarithmic bounds on the condition number of the preconditioned
operators for iterative substructuring methods, and a result analogous to the standard
bound for overlapping Schwarz algorithms. Then, by applying Canuto's result, [5],
we propose and analyze a new overlapping preconditioner that depends only on the
spectral element matrix. We also give a new proof of one of the estimates in [23] by
using the same equivalence.
The remainder of this paper is organized as follows. The next section contains
some notation and a precise definition of the discrete problem. Our motivation and
strategy are presented in detail in Section 3. In Section 4 we give the statement and
proofs of our technical results. In the two remaining sections we formulate and analyze
our algorithms.
2. Differential and Discrete Model Problems.
Let\Omega be a bounded polyhedral
region in R 3 with diameter of order 1. We consider the following elliptic self-adjoint
Find
(1)
where
Z\Omega
Z\Omega
fv dx for f 2 L
This problem is discretized by the spectral element method (SEM) as follows;
see [16]. We
triangulate\Omega into non-overlapping substructures
of diameter
on the order of H .
Each\Omega i is the image of the reference cube
a mapping F is an isotropic dilation and G i a C 1 mapping
such that its derivative and inverse of the derivative are uniformly bounded by a
constant close to one. Moreover, we suppose that the intersection between the closure
of two substructures is either empty, a vertex, a whole edge or a whole face. Each
substructure\Omega i is called a distorted cube. We notice that some additional properties of
the mappings F i are required to guarantee an optimal convergence rate. We refer to [2],
problem 2 and the references therein for further detail on this issue, but remark that
affine mappings are covered by the available convergence theory for these methods.
We assume for simplicity that k(x) has the constant value k i in each
with possibly large jumps occurring only across substructure boundaries. This point
is important only in the analysis of iterative substructuring algorithms in Section 5,
where our estimates are independent of the jumps of k(x).
We define the space P N (
-\Omega ) as the space of QN functions, i.e. polynomials of
degree at most N in each of the variables separately. The space P
is the space
of functions v N such that v N ffi F i belongs to P N (
-\Omega ). The conforming space P N
H 1(\Omega\Gamma is the space of continuous functions the restrictions of which
belong to
The discrete L 2 inner product is defined by
(2)
are, respectively, the Gauss-Lobatto-Legendre (GLL) quadrature
points and weights in the interval [\Gamma1; +1]; see [2].
The discrete problem is: find uN 2 P N
0(\Omega\Gamma9 such that
aQ
The functions OE N
of P N(\Omega\Gamma that are one at the GLL node j and zero at the other
nodes form the nodal basis of this space which gives rise in the standard way to the
linear system KN b. Note that the mass matrix of this nodal basis generated
by the discrete L 2 inner product 2 is diagonal. The analysis of the SEM method
just described and experimental evidence show that it achieves very good accuracy
for reasonably small N for a wide range of problems; see [2], [16], [15] and references
therein. The practical application of this approach for large scale problems, however,
depends on fast and reliable solution methods for the system KN b. The condition
number of KN is very large even for moderate values of N [2]. Our approach is to
solve this system by a preconditioned conjugate gradient algorithm. The following
low-order discretization is used to define several preconditioners in the next sections.
The GLL points define a triangulation T - h of
-\Omega into parallelepipeds, and on this
triangulation we define the space P - h ( -
\Omega\Gamma of continuous piecewise trilinear
tions. The spaces P
are defined analogously to P
The finite element discrete problem associated with (1) is: Find u
0(\Omega\Gamma5 such
that
The standard nodal basis f -
in P - h ( -
\Omega\Gamma is mapped by the F j , 1
basis for P h(\Omega\Gamma4 This basis also gives rise to a system K h in the standard way.
We use the following notations: x - y , z - u, and v i w to express that there
are positive constants C and c such that
Here and elsewhere c and C are moderate constants independent of H or N .
Let - h be the distance between the first two GLL points in the interval [\Gamma1; +1];
- h is proportional to 1=N 2 [2], and the sides h of an element K belonging
to T - h satisfy
depending on the location of K inside
-\Omega . The triangulation is therefore non-regular.
In the case of a region of diameter H; such as a
we use a norm
with weights generated by dilation starting from a region of unit diameter,
3. General Setup and Simplifications. In this section, we give our plan of
study.
uN be a function belonging to P N ( -
\Omega\Gamma3 and let -
I h
uN be the function of
-\Omega ) for which
uN
for every GLL point xG in -
and
where a -
Q is given by (2) and (3) with see [5] and [2]. We remark that the key
point of these results is the stability of the interpolation operator at the GLL nodes
for functions of
proved by Bernardi and Maday [1], [2].
Consider now a function v defined in a substructure
-\Omega with diameter of order H .
Changing variables to the reference substructure by - using simple
estimates on the Jacobian of F i , we obtain
2(\Omega
where the dimension d is equal to 1, 2, or 3.
These estimates can be interpreted as spectral equivalences of the stiffness and
mass matrices generated by the norms introduced above. Indeed, the nodal basis f -
is mapped by interpolation at the GLL nodes to a nodal basis of P N (
can be written as
u is the vector of nodal values of both -
uN or - u h , and -
K h and -
KN are the stiffness
matrices corresponding to j
and a -
Therefore, if K (i)
h and K (i)
N are the stiffness matrices generated by the basis fOE h
and fOE N
respectively, for all nodes j in the closure
and
a
(\Delta; \Delta), then
where u is the vector of nodal values, by (9), (8), and (5). The stiffness matrices KN
and K h are formed by subassembly [9],
h
for any nodal vector u, where u (i) are the sub-vectors of nodal values
an analogous
expression is true for KN . These last two relations imply
for any vector u. All these matrix equivalences and their analogues in terms of norms
are hereafter called FEM-SEM equivalence.
The equivalence (11) shows that K h is an optimal preconditioner for KN in terms
of number of iterations. However, the solution of systems K h expensive to
be used as an efficient preconditioner for large scale problems, which typically involve
many substructures.
We next show that the same reasoning applies to the Schur complements S h
and SN , i.e., the matrices obtained by eliminating the interior nodes of
in a
classical way; see [9]. Let uN be Q-discrete (piecewise) harmonic if aQ
for all i and all v N belonging to P N
The definition of h-discrete (piecewise)
harmonic functions is analogous. It is easy to see that u T SN
and uN are respectively Q and h-discrete harmonic and
u is the vector of the nodal values on the interfaces of the substructures.
The matrices S h and SN are spectrally equivalent. Indeed, by the subassembly
equation (10), it is enough to verify the spectral equivalence for each substructure
separately. For the
where I h
N is the interpolation at the nodes of T h , H h is the h-discrete harmonic extension
of the interface values, and the
subscript\Omega i indicates the restriction of the
bilinear form to this substructure. Here, we have used FEM-SEM equivalence and
the well known minimizing property of the discrete harmonic extension. The reverse
inequality is obtained in an analogous way.
This equivalence means that S h is also an optimal preconditioner for SN . As
before, the action of the inverse of S h is too expensive to produce an efficient preconditioner
for large problems.
In his Master's thesis [17], Pahl proposed the use of easily invertible finite element
preconditioners B h and S h;WB for K h and S h , respectively. If the condition number
with a moderately increasing function C(N ), then a simple Rayleigh quotient argument
shows that -(B \Gamma1
analogously for S h;WB and SN . Since the
evaluation of the action of B h
h;WB is much cheaper, these are very efficient
preconditioners.
Our goal is to establish (13) and its analogue for S h and S \Gamma1
h;WB . We note that the
triangulation T h is non-regular, and that all the bounds of this form established in the
literature require some kind of inverse condition, or regularity of the triangulation,
which does not hold for the GLL mesh.
4. Technical Results. This section presents the technical lemmas needed to
prove our results. As it is clear from the start, we draw heavily upon the results,
techniques, and organization of Dryja, Smith, and Widlund [9].
4.1. Some estimates for non-regular triangulations. We state here all the
estimates necessary to extend the technical tools developed in [9] to the case of non-regular
hexahedral triangulations. We let -
3 be the reference element, and
K be its image under an affine mapping F . K ae
-\Omega is an element of the triangulation
sides proportional to h 1 , h 2 and h 3 . The function u is a piecewise trilinear
defined in K. Notice that in this subsection we use hats to represent
functions and points of -
K.
The first result concerns the expressions of the L 2 and H 1 norms in terms of the
nodal values. Let - e i be one of the coordinate directions of -
K, and let - a, - b, - c and -
d
be the nodes in one of the faces that is perpendicular to -
a
etc. be the
corresponding points on the parallel face. The notation x i denotes a generic node of
K, and a; b; are the images of -a and - b, etc.
Lemma 1.
x=a;b;c;d
Proof. These expressions follow by changing variables, and by using the equivalence
of norms in the finite dimensional space Q
K).
In the next lemma we give a bound on the gradient of a trilinear function in terms
of bounds on the difference of the values at the nodes (vertices).
Lemma 2. Let u be trilinear in the element K such that ju(a)\Gammau(b)j - Cdist(a; b)=r
for some constants C and r, and for any two vertices a and b of the element K. Then
r
Proof. The functions u and u x can be written as
fy
The values of u x at the vertices belonging to the face are clearly bounded
by C=r. This implies estimates for the coefficients of u x and then the desired estimate.
The other derivatives of u are treated analogously.
Lemma 3. Let u be a trilinear function defined in K, and let # be a C 1 function
such that jr#j - C=r, and j#j - C for some constants C and r. Then
Here C is independent of all the parameters, and I - h is the interpolation to a Q 1
function of the values in the vertices of K.
Proof. By equation (15), and letting h 1 , h 2 , and h 3 be the sides of the element K:
x=a;b;c;d
Each term in the sum above can be bounded by
The bound on r# implies that
I - h (#u)jj 2
x=a;b;c;d
x=a;b;c;d
since # is bounded.
4.2. Technical tools. We introduce notations related to certain geometrical ob-
jects, since the iterative substructuring algorithms are based on subspaces directly
related to the interiors of the substructures, the faces, edges and vertices.
be the union of two
which share a common face,
wirebasket of the
which is the union of all the edges
and vertices of this subdomain. We note that a face in the interior of the
region\Omega is
common to exactly two substructures, an interior edge is shared by more than two,
and an interior vertex is common to still more substructures. All the substructures,
faces, and edges are regarded as open sets.
The following simple standard reductions greatly simplify our analysis in the next
sections.
The preconditioner S h;WB that we use is defined by subassembly of the matrices
h;WB , see Section 5. Therefore we can restrict our analysis to one substructure. The
results for the whole region follow by a standard Rayleigh quotient argument. It is
also enough to estimate the preconditioning of -
S h by -
these results can
be translated into results for each substructure by the equivalences (7), (8), and (5).
The assumption that the fF i g M
are arbitrary smooth mappings improves the
flexibility of the triangulation, but does not make the situation essentially different
from the case of affine mappings. This is seen from the estimates in Section 3, where
we only used properties of the derivative of F i . Therefore, without loss of generality,
we assume, from now on, that the F i are affine mappings.
In some of the following results, we state the result for substructures of diameter
proportional to H , but prove the theorem only for a reference substructure. The
introduction of the scaling factors into the final formulas by the methods and results
of Section 3 are routine.
For a proof of Lemma 4 and a general discussion, see Bramble and Xu [4].
Lemma 4. Let Q H u h be the L 2 projection of the finite element function u h onto
the coarse space
and
We remark that these bounds are not necessarily independent of the values K i of
the coefficient. To guarantee that, one has to work with weighted norms, and insist
that the coefficients k i satisfy the quasi-monotone condition [8], [25].
Lemma 5. Let - u h
be the average value of u h on W j ; the wirebasket of the
and
Similar bounds also hold for an individual substructure edge.
Proof. In the reference substructure, we know that P - h ae V - h , where V - h is a
standard space defined on a shape regular triangulation that includes
. This can be done by refining appropriately all the elements of T - h with sides bigger
than, say, 3 - h=2.
Now we apply the well-known result for shape regular triangulations, lemma 4.3
in [9], to get both estimates, recalling that in the reference substructure - h i 1=N 2 .
In the abstract Schwarz convergence theory, the crucial point in the estimate of the
rate of convergence of the algorithm is to demonstrate that all functions in the finite
element space can be decomposed into components belonging to the subspaces such
that the sum of the resulting energies are uniformly, or almost uniformly, bounded
with respect to the parameters H and N . The main technique for deriving such a
decomposition is the use of a suitable partition of unity. In the next two lemmas, we
explicitly construct such a partition.
Lemma 6. Let F k be the common face
k be the function
in P h
(\Omega\Gamma that is equal to one at the interior nodes of F k , zero on the remainder
of
1(\Omega
The same bound also holds for the other
Proof. We define the functions -
and -
in the reference cube; ' F k
and #F k
are
obtained, as usual, by mapping, see subsection 3. We construct a function -
having
Fig. 1. One of the segments CCk
the same boundary values as - ' F k
, and then prove the bound for the former. The
standard energy minimizing property of discrete harmonic extensions then implies the
bound for -
. The six functions which correspond to the six faces of the cube also
form a partition of unity at all nodes at the closure of the substructure except those
on the wirebasket; this property is used in the next lemma.
We divide the substructure into twenty four tetrahedra by connecting its center
C to all the vertices and to all the six centers C k of the faces, and by drawing the
diagonals of the faces of
Fig 1.
The function -
associated to the face F k is defined as being 1=6 at the point C.
The values at the centers of the faces are defined by -
is the
Kronecker symbol. -
is defined to be linear at the segments CC j for 6. The
values inside each subtetrahedron formed by a segment CC j and one edge of the cube
are defined to be constant on the intersection of any plane through that edge, and is
given by the value, already known, at the segment CC j . The values at the edge of the
cube belonging to this subtetrahedron are then modified to be equal to zero. Next,
the whole function -
is modified to be a piecewise Q 1 function by interpolating at
the vertices of all the GLL nodes of the reference cube.
We claim that jr -
x is a point belonging to any element K
that does not touch any edge of the cube, and r is the distance between the center of
K and the closest edge of the cube. Let ab be a side of K. We analyze in detail the
situation depicted in Fig 2, where ab is parallel to CC k . Let e be the intersection of
the plane containing these two segments with the edge of the cube that is closest to
ab.
(a)j - D, by construction of -
, where D is the size of the
radial projection of ab on CC k . By similarity of triangles, we may write:
where r 0 is the distance between e and the midpoint of ab. Here we have used that the
distance between e and CC k is of order 1. If the segment ab is not parallel to CC k ,
the difference j -
(a)j is even smaller, and (18) is still valid. Notice that r 0
is within a multiple of 2 of r. Therefore Lemma 2 implies that jr -
In order to estimate the energy of -
, we start with the elements K that touch
one of the edges of the face F k . Let h 3 be the largest side of one of these elements.
Since the nodal values of -
at K are 0, 1, and 1=6,
Fig. 2. Geometry underlying equation (18)
a
r
by a simple use of equation (15). By summing over K, we conclude that the energy
of -
is bounded independently of N for the union of all elements that touch one of
the edges of the face F k .
To estimate the contribution to the energy from the rest of the substructure, we
consider one subtetrahedron at a time and introduce cylindrical coordinates using the
substructure edge, that belongs to the subtetrahedron, as the z-axis. The bound now
follows from the bound on the gradient given above and elementary considerations.
We refer to [9] for more details.
The following lemma corresponds to Lemma 4.5 in [9]. This lemma and the
previous one are the keys to avoiding H 1=2estimates and extension theorems.
Lemma 7. Let #F k
(x) be the function introduced in the proof of Lemma 6, let F k
be a face of the
I h denote the interpolation operator associated
with the finite element space P h and the image of the GLL points under the mapping
I h (# F k
and
Proof. The first part is trivial from the construction of -
made in the previous
lemma. For the second part, we first estimate the sum of the energy of all the elements
K that touch the wirebasket. The nodal values of the interpolator I - h ( -
in such
an element are 0,0,0,0, -
(c)-u(c) and -
lies between 0 and
1. Moreover, we denote by h 3 the side of K that is larger than the other two sides
Note that this larger side is parallel to the closest wirebasket edge.
using equation (15), we obtain:
Then, by using the expression of the L 2 norm in the two segments that are parallel to
the edge, and lemma 5, we have:
where the sum is taken over all elements K that touch the boundary of the face F k .
We next bound the energy of the interpolant for the other elements. Since r -
C=r where r is the distance between the element K and the nearest edge of -
(see
the proof of the previous lemma), Lemma 3 implies that
Kae
Kae
where the sum is taken over all elements K that do not touch the edges of
-\Omega .
The bound of the first term in the sum is trivial, and to bound the second term
we partition the elements of
-\Omega into groups, in accordance to the closest edge of
the exact rule for the assignment of the elements that are halfway between is of no
importance. For each edge of the wirebasket, we use a local cylindrical coordinate
system with the z axis coinciding with the edge, and the radial direction, normal to
the edge. In cylindrical coordinates, we estimate the sum by an integral
Kae
-\Omega r \Gamma2 jj-ujj 2
Z C
Z
Z
z
drd'dz:
The integral with respect to z can be bounded by using Lemma 5. We obtain
Kae
-\Omega r \Gamma2 jj-ujj 2
Z C
and thus
Kae
This proof is an adaptation of an argument given in [9] for shape regular meshes.
Note that equation (16) replaces the use of the inverse inequality, which cannot be
used here because of the bad aspect ratios of the elements. Equation (16) is analogous
to the L 2 bound of the derivative of a product in terms of L 2 norms of the functions
and L 1 norms of the gradients, which cannot be applied directly to our case because
we have the interpolation operator I h .
Lemma 8. Let -
W k be the averages of u h on @F k ; and W k , respectively.
Then,
The proofs are direct consequences of the Cauchy-Schwarz inequality.
Lemma 9. Let u h be zero on the mesh points of the faces
of\Omega j and discrete
harmonic
This result follows by estimating the energy norm of the zero extension of the
boundary values by means of equation (15) and by noting that the harmonic extension
has a smaller energy.
5. Iterative Substructuring Algorithms. The first algorithm we analyze is
a wirebasket based method, based on Algorithm 6.4 in [9]. This is a block-diagonal
preconditioner after transforming the original matrix to a convenient basis.
According to the abstract framework of Schwarz methods [9], we only need to
prescribe spaces whose union is the whole space, and the corresponding bilinear forms.
Each internal face F k generates a local space VF k
of all the h-discrete harmonic
functions that are zero at all the interface nodes that do not belong to this face. Notice
that the functions belonging to VF k
have support in the union of the two substructures
and\Omega j that share the face F k . The bilinear form used for this space is just a(\Delta; \Delta).
We also define a wirebasket subspace that is the range of the following interpolation
operator:
I h
Here, ' k is the discrete harmonic extension of the standard nodal basis functions OE k ,
W h is the set of nodes in the union of all the wirebaskets, and - u h
@F k is the average of
u h on @F k . The bilinear form for this coarse subspace is given by
These subspaces and bilinear forms define, via the Schwarz framework, a preconditioner
of S h that we call S h;WB .
Theorem 1. For the preconditioner S h;WB , we have
where the constant C is independent of the N , H, and the values k i of the coefficient.
Proof. We apply word by word the proof of theorem 6.4 in [9] to the matrix S h ,
using now the tools developed in Section 4. This gives
The harmonic FEM-SEM equivalence (12) and a Rayleigh quotient argument complete
the proof, as explained in Section 3.
We do not give the complete proof here because it would be a mere restatement
of the proof in [9].
The next algorithm is obtained from the previous one by the discrete harmonic
FEM-SEM equivalence, by which we find a preconditioner SN;WB from the preconditioner
studied above. Each face subspace related to a face F k is composed
of the set of all Q-discrete harmonic functions that are zero at all the interface nodes
that do not belong to the interior of the face F k .
The wirebasket subspaces are defined as before, by prescribing the values at the
GLL nodes on a face to be equal to the average of the function on the boundary of the
face. The bilinear forms used for the face and wirebasket subspaces are aQ and b 0 (\Delta; \Delta),
respectively. Notice that this is the wirebasket method based on GLL quadrature
given in [24].
The following lemma shows the equivalence of the two functions uN and u h with
respect to the bilinear form b 0 (\Delta; \Delta).
Lemma 10. Let u h be a Q 1 finite element function on the GLL mesh of the
interval I = [\Gamma1; +1], and let uN be its polynomial interpolant. Then
Proof. We prove only the - part. The inequality without the infimum is valid
for the constant c r that realizes the inf in the right hand side by the FEM-SEM
equivalence. By taking the inf in the left hand side we preserve the inequality.
Theorem 2. For the preconditioner SN;WB , we have
where the constant is independent of the parameters H, N and the the values k i of the
coefficient.
Proof. In this proof, the functions with indices h and N are all discrete harmonic
functions with respect to the appropriate norms, related in the same way as uN and u h ,
i.e.
According to Section 3, it is enough to analyze one substructure
\Omega i at a time, and prove the following equivalence:
1(\Omega
We prove only the - part, and the other inequality is analogous. Lemma 10 gives
an upper bound of the first term in the left hand side by the corresponding term in
the right hand side.
Each term in the sum on the left hand side can be bounded by
The first term of this expression can be bounded by the corresponding term on the
right hand side by interpolation and the harmonic FEM-SEM equivalence. The second
term is bounded by
where c h;W i
is the average of u h over W i . Here we used the estimate on the energy
norm of ' h;F k
which implies a similar estimate of ' N;F k
. Applying the Cauchy-Schwarz
inequality, as in lemma 8, and the FEM-SEM equivalence, we can bound this last
expression in terms of the first term in the right hand side of equation (19).
The polynomial analogues of the lemmas in Section 4 can be proved using the
harmonic FEM-SEM equivalence. This provides a theory for polynomials, which is
completely parallel to the one we have presented, that can be used to prove this
theorem directly. A variation of this approach is taken in [22] and [24], but without
the use of the FEM-SEM equivalence.
6. Overlapping Schwarz Algorithms. We now consider the additive overlapping
Schwarz methods, which are presented for instance in [10]. We recall that an
abstract framework, theorem 3.1 in [10], is available for the analysis of this type of
algorithm. Here we only discuss the additive version, but the analysis also applies in a
standard way to the multiplicative variant, which is more effective in many practical
problems.
In the abstract framework for the additive Schwarz methods, a preconditioner B h
for K h can be defined by specifying a set of local spaces together with a coarse space.
We can also provide approximate solvers for the elliptic problem restricted to each of
the proposed subspaces. Here we only work with exact solvers, since the extension to
inexact solvers is straightforward by using the abstract framework.
The
domain\Omega is covered by
substructures\Omega i , which are the original spectral
elements. We enlarge each of them to produce overlapping
i , in such a
way that the boundary
i does not cut through any element of the triangulation
generated by the GLL nodes. The overlap ffi is defined as the minimum distance
between the boundaries
i . When ffi is proportional to H the overlap is called
generous, and when ffi is comparable to the size of the Q 1 elements it is called a small
overlap. For the sake of simplicity, we again restrict our analysis to the case when all
the mappings F j are affine mappings. The general situation is treated similarly.
The local spaces are given by P h
i ), the set of functions in P h
that vanish at
all the nodes on or outside
. The coarse space is a Q 1 finite element space given
by the mesh generated by the vertices and edges of the
subregions\Omega i . Each subregion
\Omega i is then one element of this coarse finite element space. We note that this coarse
mesh is regular by assumption. This construction is completely parallel to that of
Section 2.1 of [11] for this particular choice of subregions. This setting incorporates
the small and the generous overlap preconditioners. We use the bilinear form a(\Delta; \Delta)
for the coarse and local spaces.
Theorem 3. For this additive Schwarz algorithm, the condition number of the
preconditioned operator satisfies:
The constant C is independent of the parameters H, N , and ffi .
Proof. As before, we follow the proof of the analogous theorem, theorem 3 in [11].
The proof follows word by word, except for the estimate of aK
where I h is the interpolation operator, f' i g is a partition of unity, w h is a finite
element function, and aK is just the restriction of a(\Delta; \Delta) to one element.
In this case it is known that j' i
and the rest of the proof follows without any change.
Remark 1. Even though the theory does not rule out the possibility of growth of
the constant when the coefficient k has large jumps, such a growth is very moderate in
numerical experiments; see e.g [13]. We note also that when the overlap is generous,
the method is optimal in the sense that the condition number is uniformly bounded
with respect to the parameters of the problem; see [19] for early work on this type of
preconditioner. Our results and techniques allow a very flexible choice of subregions.
We now apply FEM-SEM equivalence to the subspaces used to define B h;AS ; this
is the same technique used to derive the preconditioner SN;WB from S h;WB . The
coarse space is the same, and the local spaces are defined by
N (v N
where I h
N (v N ) interpolates v N at the GLL points and belongs to P h .
These subspaces and the use of the bilinear forms aQ (\Delta; \Delta) and a(\Delta; \Delta) for the local
and coarse spaces, respectively, define our preconditioner BN;AS . Theorem 3 and
a simple application of the FEM-SEM equivalence for each one of the local spaces
immediately give:
Theorem 4. The condition number of the preconditioned operator satisfies:



--R

Polynomial interpolation results in sobolev spaces.
Approximations Spectrales de Probl'emes aux Limites Elliptiques
The construction of preconditioners for elliptic problems by substructuring
Some estimates for a weighted L 2 projection.
Stabilization of spectral methods by finite element bubble functions.
Voigt, editors. Fifth International Symposium on Domain Decomposition Methods for Partial Differential Equations

Multilevel Schwarz methods for elliptic problems with discontinuous coefficients in three dimensions.
Widlund Schwarz analysis of iterative substructuring algorithms for elliptic problems in three dimensions.
Additive Schwarz methods for elliptic finite element problems in three dimensions.
Widlund Domain decomposition algorithms with small overlap.
Parallel Domain Decomposition for Incompressible Fluid Dynamics.
Experiences with domain decomposition in three di- mensions: Overlapping Schwarz methods
Domain Decomposition Methods in Science and Engi- neering
Analysis of iterative methods for the steady and unsteady Stokes problem: Application of spectral element dis- cretization
Spectral element methods for the Navier-Stokes equations
Schwarz type domain decomposition methods for spectral element discretiza- tions
Preconditioning legendre spectral collocation approximation to elliptic problems.
Domain Decomposition Algorithms for the p-version Finite Element Method for Elliptic Problems
Additive Schwarz methods for the p-version finite element method
Some Schwarz algorithms for the p-version finite element method
Iterative substructuring methods for spectral elements in three dimensions.
Iterative substructuring methods for spectral elements: Problems in three dimensions based on numerical quadrature.
Widlund A polylogarithmic bound for an iterative substructuring method for spectral elements in three dimensions.
Preconditioned conjugate gradient methods for spectral elements in three dimensions.
Finite element preconditioning for legendre spectral collocation approximations to elliptic equations and systems.
editors. Domain Decomposition Methods in Science and Engineering: The Sixth International Conference on Domain Decomposition
A domain decomposition algorithm for elliptic problems in three dimensions.
--TR

--CTR
James W. Lottes , Paul F. Fischer, Hybrid Multigrid/Schwarz Algorithms for the Spectral Element Method, Journal of Scientific Computing, v.24 n.1, p.613-646, July      2005
Luca F. Pavarino , Elena Zampieri, Overlapping Schwarz and Spectral Element Methods for Linear Elasticity and Elastic Waves, Journal of Scientific Computing, v.27 n.1-3, p.51-73, June      2006
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
V. Korneev , J. E. Flaherty , J. T. Oden , J. Fish, Additive Schwarz algorithms for solving hp-version finite element systems on triangular meshes, Applied Numerical Mathematics, v.43 n.4, p.399-421, December 2002
Marcello Manna , Andrea Vacca , Michel O. Deville, Preconditioned spectral multi-domain discretization of the incompressible Navier-Stokes equations, Journal of Computational Physics, v.201 n.1, p.204-223, 20 November 2004
schwarz methods;preconditioned conjugate gradients;iterative substructuring;domain decomposition;spectral element method