The Conditioning of Boundary Element Equations on Locally Refined Meshes and Preconditioning by Diagonal Scaling.
Consider a boundary integral operator on a bounded,d-dimensional surface in $\mbox{\smallBbb R}^{d+1}$. Suppose that the operator is a pseudodifferential operator of order $2m,$ $m\in\mbox{\smallBbb R},$ and that the associated bilinear form is symmetric and positive-definite. (The surface may be open or closed, and m may be positive or negative.) Let B denote the stiffness matrix arising from a Galerkin boundary element method with standard nodal basis functions. If local mesh refinement is used, then the partition may contain elements of very widely differing sizes, and consequently B may be very badly conditioned. In fact, if the elements are nondegenerate and 2|m|< d, then the $\ell_2$ condition number of B satisfies  {\rm cond}({\mbox {\bf {\em B}}})\leq C N^{2|m|/d} \left(\frac{h_{\rm max}}{h_{\rm min}}\right)^{d-2m},    where hmax and h min are the sizes of the largest and smallest elements in the partition, and N is the number of degrees of freedom. However, if B  is  preconditioned using a simple diagonal scaling, then the condition number is reduced to ${\cal O}(N^{2|m|/d})$. That is, diagonal scaling restores the condition number of the linear system to the same order of growth as that for a uniform partition. The growth in the critical case 2|m|=d is worse by only a logarithmic factor.
Introduction
\Gamma be a bounded, d-dimensional, open or closed surface in R d+1 , where d - 1.
H s (\Gamma) denote the usual Sobolev spaces. Precise definitions and
assumptions are deferred until a later section. However, observe if \Gamma is a closed
surface then the spaces e
H s (\Gamma) and H s (\Gamma) coincide since \Gamma has no boundary. Let m
The authors were supported by the Australian Research Council.
y Mathematics Department, Leicester University, Leicester LE1 7RH, United Kingdom.
M.Ainsworth@mcs.le.ac.uk
z School of Mathematics, The University of New South Wales, Sydney 2052, Australia.
x Centre for Mathematics and its Applications, School of Mathematical Sciences, Australian
National University, Canberra, A.C.T. 0200, Australia. Thanh.Tran@maths.anu.edu.au
be a real number and suppose that B(\Delta; \Delta) : e
R is a symmetric,
bilinear form satisfying
e
(Throughout, the notation a - b will be used to indicate that a - Cb for some
positive constant C that is independent of the main quantities of interest, while
a ' b is equivalent to a - b and b - a.) Consider the problem of finding
R is a bounded, linear functional. The existence of a unique
solution u for each f follows immediately from the Riesz Representation Theo-
rem. Typically, (2) arises from the variational formulation of a boundary integral
equation associated with an elliptic boundary value problem. If the surface \Gamma is
smooth then the integral operator associated with the bilinear form B is a classical
pseudodifferential operator of order 2m on the manifold \Gamma.
The problem (2) will be approximated by first constructing a finite dimensional
subspace
m (\Gamma) on a partition P of the surface \Gamma, and then finding
This problem can be written as a system of linear equations by introducing a nodal
basis Ng. The precise details will be given later. The approximation uX
is then written in the form
with the coefficients fff determined by the equations
or, in matrix form,
where [B]
The assumptions on the bilinear form B(\Delta; \Delta) mean that the matrix B will be
symmetric and positive definite. The solution of the system (4) is typically accomplished
by the use of a direct solver such as Gaussian elimination (Cholesky
or sometimes by an iterative solver such as the conjugate gradient
method. The size of the condition number cond(B) of the matrix B is important
for the quality of the answers obtained by a direct method or the rate of convergence
of the iterative method. Either way, a large condition number points to possible
difficulties and it is important to understand and control the condition number.
The classical version of the boundary element method seeks to improve the
accuracy by uniformly subdividing all elements in the partition. While this process
does improve the approximation properties of the subspace X , the condition number
is also increased. Specifically, the growth of the condition number depends on the
the order 2m of the operator and the number of spatial dimensions d, as follows
where N is the number of degrees of freedom in the approximation space; cf. Hsiao
and Wendland [7, Remark 4], [8, Corollary 2.1].
If the solution u has singularities or other local features then it is more efficient to
refine the partition adaptively so that the space X is tailored towards approximating
the particular solution u of the specific problem in hand. Often, the final adaptively
refined partition contains elements of very widely differing sizes. This also has an
adverse effect on the growth of the condition number. For instance, we shall see
that if 2jmj ! d then
where hmax and h min are the sizes of the largest and smallest elements in the partition

The severe growth of the condition number due to the local refinements might
easily mean that the advantages accrued by adaptively refining the mesh are dissipated
by the cost of dealing with the solution of a highly ill-conditioned linear
system. The purpose of the current work is to address this issue. It will be shown
that if the matrix B is preconditioned or scaled using the matrix diag B, obtained
by taking the elements on the leading diagonal, then the extra growth factor
in (5) depending on the global mesh ratio is, provided essentially removed:
That is to say, diagonal scaling restores the condition number of the linear system
to the same order of growth as would be obtained if a uniform refinement scheme
were employed. The growth in the critical case marginally worse.
The current work finds much of its inspiration in the paper of Bank and Scott [2]
for the finite element approximation of problems associated with second order elliptic
partial differential equations in two and three dimensions. The current investigation
focuses on boundary element equations and as such allows for operators of
non-integer and possibly negative orders. This means that the associated Sobolev
spaces are also of non-integer and possibly negative orders, resulting in a number
of technical difficulties. Nevertheless, the conclusions are simple and applicable to
the practical solution of boundary element equations on highly refined meshes such
as those commonly arising from adaptive refinement procedures.
The remainder of the paper is organized as follows. The next section elaborates
on the construction of the boundary element approximation and on the conditioning
of the linear system, and concludes with a statement of the main result of
the paper: Theorem 1. Section 3 illustrates with numerical experiments how the
theory applies in practice to boundary element approximations of weakly singular
and hypersingular boundary integral equations posed on surfaces in R 2 and R 3 .
The Sobolev spaces are defined in Section 4, and we prove several technical results.
Theorem 9 in this section contains sharp estimates for the norms of standard nodal
basis functions in fractional order Sobolev spaces, and may be of independent interest
for the analysis of boundary element methods in general. Section 5 consists
of five lemmas, that together constitute the proof of our bounds on the growth of
the extreme eigenvalues of the stiffness matrix, with and without diagonal scaling,
and hence establish Theorem 1.
Partitions and Preconditioning
2.1 Galerkin Subspace
It will be assumed that the surface \Gamma is bounded and, for some fixed integer r - jmj,
is locally the graph of a C r\Gamma1;1 function over a C r\Gamma1;1 domain in R d . In particular,
this assumption is needed so that the Sobolev spaces H m (\Gamma) and e
later) are well-defined.
Let P be a partitioning of the boundary \Gamma into boundary elements K, as described
in [9, 11]. In particular, the non-empty intersection of a pair of distinct
elements K and K 0 is a single common vertex or edge. If \Gamma is a two dimensional
surface then K is typically a curvilinear triangle or quadrilateral. Each element
K is assumed to be the image of a common reference element b
K under a smooth
bijective mapping FK . Let
\Delta be a finite element in the sense of Ciarlet [5],
with the set b
consisting of polynomials defined on b
K, unisolvent with respect to
the finite set b
\Sigma of degrees of freedom. The degrees of freedom are identified with
point evaluations at distinct nodes fb x
Ig on b
K. The placement of the nodes
depends on the interelement continuity requirements of functions in the space X ,
and standard placements are well-established [5]. The local nodes in turn give rise
to a set of global nodes fx denotes a suitable indexing set
of size N . A set of global, nodal basis functions f' defined by the
normalization condition
and the requirement for the restriction of each function ' k (x) to an element K to
be of the form b
w(b x), where (b x) for some b
. The Galerkin subspace
is defined by and has dimension N . If
order to apply Lemma 6 during the proof of Theorem 9, we impose the condition
Z
where doe is the element of arc length surface area (d = 2) on \Gamma. Condition
rules out certain placements of the nodes: for instance, if
is affine, then the nodes f\Gamma1=
3g on the reference element b
would lead to a discontinous quadratic basis function with mean value zero.
Each partition P belongs to a family of partitions of \Gamma. The family is assumed to
be non-degenerate, so that the ratio of the diameter of an element to the diameter
of its largest inscribed ball is uniformly bounded over the whole family. It is also
assumed that the number of elements intersecting \Gamma k , the support of ' k , is also
uniformly bounded. Associated with each nodal basis function ' k is a parameter
defined to be the average of the diameters of the elements forming the support \Gamma k .
The non-degeneracy assumption implies, if d - 2, that the ratio of the diameters of
any pair of adjacent elements is uniformly bounded (that is, the partition is locally
quasi-uniform). In the one dimensional case, assumption is stipulated
separately. It is important to realize that locally quasi-uniform partitions may still
contain elements of greatly differing size. Indeed, if hmax and h min respectively
denote the diameters of the largest and smallest elements in the mesh, then the
global mesh ratio hmax=h min may be arbitrarily large. In particular, the assumptions
do not rule out families of partitions of the type generated by adaptive refinement
algorithms starting from an initial coarse mesh and creating a sequence of nested
partitions by selectively refining elements on the basis of some suitable criterion.
2.2 Conditioning of Stiffness Matrix
The Galerkin approximation entails the solution of a linear system of the form
One of our goals is to obtain bounds on the growth of the condition number of the
stiffness matrix B in terms of the number of degrees of freedom N and the mesh
quantities hmax and h min . The basic strategy is to determine positive quantities -
and  , depending on the partition, such that
min Nh 2d
min N \Gamma2m=d h d\Gamma2m

Table

1: One-sided bounds on the extreme eigenvalues of the stiffness matrix B
constructed from the standard nodal basis functions.
This equivalence yields bounds on the actual minimum eigenvalue -   (B) and maximum
eigenvalue     (B), since
and
Consequently the ' 2 -condition number of the matrix may be bounded as

For the purposes of analysis, it is convenient to reformulate (7) in terms of functions
from the Galerkin subspace X , by defining an isomorphism R N 3 ff using
the rule
The assumptions on the bilinear form and properties of the basis functions imply
that
e
and
Therefore, the task of establishing (7) is equivalent to determining positive quantities
- and   such that:
e
In particular, such an estimate also gives bounds on the behaviour of the largest and
smallest eigenvalues. A summary of the results obtained in Section 5, concerning
the behaviour of the eigenvalues, is given in Table 1. The results indicate that the
smallest eigenvalue decreases according to the size h min of the smallest element,
while the largest eigenvalue decreases according to the size hmax of the largest
element. Overall, this means that the ' 2 -condition number of the stiffness matrix
is dangerously sensitive to the global mesh ratio hmax=h min .
2.3 Preconditioning by Diagonal Scaling
One can attempt to control the growth of the condition number by means of a
preconditioner. Let D be the diagonal matrix formed from the entries on the leading
min )j

Table

2: One-sided bounds on the extreme eigenvalues of the diagonally scaled
stiffness matrix B 0 .
diagonal of B (i.e [D] It is simple to use D as a preconditioner
for B in an iterative solver since this only entails scaling the residual by D \Gamma1 at
each iteration. The effectiveness of the preconditioner depends on the condition
number of the diagonally scaled, or preconditioned, matrix
Of course, this matrix is never actually constructed in practice. The goal now, is
to obtain bounds on the growth of the condition number of the diagonally scaled
in terms of the number of degrees of freedom N and properties of the
partition. As before, the basic strategy is to determine positive quantities - 0 and
0 such that
or equivalently
These estimates may be reformulated by using the isomorphism given in (8), with
e
reducing the task to determining positive quantities - 0 and   0 such
e
e
e

Table

summarizes our results, proved in Section 5, concerning the growth or
decay of the extreme eigenvalues of the diagonally scaled stiffness matrix. It will
be observed that the effect of the preconditioner is to remove essentially the factors
involving the extreme mesh sizes hmax and h min from the bounds on the eigenvalues
of the condition number of the original stiffness matrix. In other words, a simple
diagonal scaling restores the growth of the condition number to the same order as
would be observed on a uniform mesh. The numerical results reported in Section 3
indicate that our one-sided bounds are usually, but not always (see Tables 7, 8 and
12), achieved in practice for realistic problems and meshes. It appears that the
bounds cannot be improved (except perhaps for some of the logarithmic factors)
unless one imposes additional restrictions on the mesh.
Theorem 1 Let cond(B) and cond(B 0 ) denote the ' 2 -condition numbers of the
stiffness matrix and the diagonally scaled stiffness matrix (10) respectively.
1. If j2mj ! d, then
and
2. If
min )j
and
min )j
3. If 2m = \Gammad, then for hmax sufficiently small,
and
min )j
Here hmax and h min are respectively the diameters of the largest and smallest elements
in the partition, and N is the number of degrees of freedom in the Galerkin
subspace X.
Proof. The results follow immediately from the above discussion, the norm equivalences
and (11), the inequality (25), and Lemmas 11, 12, 13 and 14; cf. Tables
1 and 2.
3 Numerical Examples
We illustrate the our general theory by considering some weakly singular
\Gamma1=2) and hypersingular integral equations on various boundaries
2.
These boundary integral equations were discretized on uniform and non-uniform
meshes using varying numbers of degrees of freedom N . The functions in the
Galerkin subspace X were piecewise-constant in the case of the weakly singular
equations, and piecewise-linear in the case of the hypersingular equations. We computed
the extreme eigenvalues -   and     , and also the condition number     =-   , of
the stiffness matrix B and of the diagonally scaled stiffness matrix B 0 . The numerical
values of these quantities, along with their apparent growth or decay exponents,
are given in the tables that follow, and compared with our theoretical bounds from

Tables

1 and 2, and from Theorem 1.
Three different boundaries \Gamma were considered:
Boundary 1: the L-shaped polygon in R 2 having vertices (0; 0), (0; 1),
Boundary 2: the open curve (\Gamma1; 1) \Theta f0g in R 2
Boundary 3: the screen (\Gamma1; 1) \Theta (\Gamma1; 1) \Theta f0g in R 3
3.1 Weakly Singular Equations
The weakly singular equations arise when boundary integral methods are used to
solve the Dirichlet problem for the Laplacian in domains in R 2 or R 3 with boundaries
defined as above. The integral equations take the forms shown below.
Boundary 1:2-
Z
doe
Boundary 2:2-
Z
doe
Boundary 3:4-
Z
u(y)
doe
If B(\Delta; \Delta) is the bilinear form associated with the operator on the left-hand side of
each of (12), (13), or (14), then it is shown in [6, 12] that
e
Hence, our assumption (1) is satisfied with \Gamma1=2. The factor 5 appearing in
(12) ensures that the bilinear form is positive definite; see [10].
3.2 Hypersingular Equations
First kind integral equations with hypersingular kernels arise when boundary integral
methods are used to solve the Neumann problem for the Laplacian in domains
in R 2 or R 3 . These equations take the forms shown below.
Boundary 1:
\Gamma2-
@
Z
u(y)
@
@- y
doe y +4
Z
u(y) doe
Boundary 2:
\Gamma2-
@
Z
u(y)
@
@- y
doe
Boundary 3:
\Gamma4-
@
Z
u(y) @
doe
If B(\Delta; \Delta) is the bilinear form associated with the operator on the left-hand side of
each of (15), (16), or (17), then it is shown in [6, 15] that
e
Once again, our assumption (1) is satisfied, now with +1=2. The second term
on the left-hand side of equation (15) ensures that the bilinear form is positive-definite
and not just positive-semidefinite; see [10].
3.3 Results with Boundary 1
For the weakly singular equation (12) on the L-shaped boundary, we have
so for the unscaled stiffness matrix,
min and
but after diagonal scaling,

Table

3 gives results for a quasi-uniform mesh (Figure 1), and Table 4 for a non-uniform
mesh (Figure 2) that is refined towards the re-entrant corner at (0; 0). In
the latter case, diagonal scaling leads to a very dramatic reduction in the condition
Turning to the hypersingular equation (15), we have
Indeed, the numerical results in Tables 5 and 6 show that, both for the quasi-uniform
and non-uniform meshes, diagonal scaling has little effect.
3.4 Results with Boundary 2
For the weakly singular equation (13) on the open curve, we again have
giving the bounds (18) and (19). For a uniform mesh, and for a graded
mesh with h observed the same growth
and decay rates as for the closed (L-shaped) curve, and do not tabulate the results
here. We also investigated a geometric mesh grading for which h
log h min ' \GammaN , we see from (18) and (19) that
In fact, the numerical results shown in Table 7 suggest that
our theoretical upper bounds are not attained for this mesh.
In the case of the hypersingular equation (16) on the open curve, our results
using a uniform mesh, or a graded mesh with h
gave the same growth and decay rates as on the closed curve, and again are not
reported here. Table 8 shows our results using the geometric mesh, for which (20)
gives
This time, the lower bounds are not attained, as we observe that -   (B) and -   (B 0 )
are decaying only very slowly, leading to very slow growth of cond(B) and cond(B 0 ).
3.5 Results with Boundary 3
For the weakly singular equation on the screen our theory
gives

Table

9 shows our numerical results for a uniform mesh (Figure 3), and Table 10
for a non-uniform mesh (Figure 4) that has been refined in a neighbourhood of the
corner (\Gamma1; 1).
Finally, in the case of the hypersingular equation (17) on the screen
Our results for a uniform mesh (Figure 3), given in Table 11, are as expected, but
those for a non-uniform mesh (Figure 4), given in Table 12, contain one surprise.
The minimum eigenvalue -   (B) of the unscaled matrix appears to behave like N \Gamma1 ,
whereas our lower bound is - . As a consequence, cond(B) grows at the
same rate as cond(B 0 ). However, all of the results shown in Table 13, for a different
non-uniform mesh (Figure 5), achieve the one-sided bounds from our theory.
theory
theory

Table

3: Weakly singular integral equation on L-shaped boundary with uniform
Theoretical bounds (18) and (19).
theory
theory

Table

4: Weakly singular integral equation on L-shaped boundary with non-uniform
Theoretical bounds (18) and (19).
128
theory
128
theory

Table

5: Hypersingular integral equation on L-shaped boundary with quasi-uniform
Theoretical bounds (20).
128
theory
128
theory

Table

Hypersingular integral equation on L-shaped boundary with non-uniform
Theoretical bounds (20).
48 \Gamma0.3279e+2 1.02 0.2523e+0 0.00 0.4398e+14 32.60
theory
48
theory

Table

7: Weakly singular integral equation on open curve with geometric
Theoretical bounds (21).
theory
theory

Table

8: Hypersingular integral equation on open curve with geometric
Theoretical bounds (22).
theory
theory

Table

9: Weakly singular integral equation on a screen with uniform
Theoretical bounds (23).
528 0.17e\Gamma7 \Gamma3.13 0.38e\Gamma2 \Gamma1.04 0.23e+6 2.09
theory
528 0.33e+0 \Gamma0.01 0.24e+2 0.52 0.73e+2 0.53
theory

Table

10: Weakly singular integral equation on a screen with non-uniform
theory
9 0.68e+0 0.12e+1 0.18e+1
961
theory - N \Gamma1=2 - 1 - N 1=2

Table

11: Hypersingular integral equation on a screen with uniform
Theoretical bounds (24).
52
theory - N \Gamma3=2 - N \Gamma1=2 - N
966
142
548 0.4436e\Gamma2 \Gamma0:99 0.1803e+0 \Gamma0:20 0.4064e+2 0.78
theory

Figure

1: L-shaped boundary

Figure

2: L-shaped boundary with non-uniform
O(N refinement around re-entrant corner.

Figure

3: Uniform mesh on the screen.

Figure

4: Successive meshes in a sequence of non-uniform meshes on the screen,
with local refinement at one corner: h

Figure

5: Successive meshes in a different sequence of non-uniformly refined meshes
on the screen: h
4 Technical Preliminaries
4.1 Sobolev Spaces and Norms
For s 2 R, we define the Sobolev space H s (R d ) in the usual way, via the Fourier
transform (see the proof of Lemma 5). Given a Lipschitz
domain\Omega ' R d , we put
j\Omega for some U 2 H s (R d ) g
and
e
'\Omega
and equip these spaces with the norms
u=Uj\Omega kUk H s (R d ) and kuk e
These spaces satisfy the duality relations
\Gammas(\Omega\Gamma and e
with respect to the usual extension of the bilinear pairing
Z\Omega
Also, it is clear that
H s for
For s ? 0, an equivalent norm for H
s(\Omega\Gamma is
where the seminorm j
(\Omega\Gamma is defined, if
jffj=s
and if
The Sobolev spaces also have the interpolation properties
and e
for real s 0 Explicitly, we use
as the interpolation norm
Z 1jt \Gamma' K(t; u)j 2 dt
where the K-functional is defined, for
When the
domain\Omega is rescaled, different equivalent norms for H
s(\Omega\Gamma or e
might scale differently. We therefore fix a particular family of norms, denoted by
s(\Omega\Gamma , that will be used whenever we need estimates in which the
constants are independent of the domain(s) involved. These norms will be defined
only for jsj - r, and
when\Omega is bounded. Firstly, we set
and
r(\Omega\Gamma and jjjujjj 2
e
The latter is a norm by virtue of Poincar'e's inequality, because the functions
in e
on the boundary of \Omega\Gamma For we define the
norms by interpolation, i.e., if
and jjjujjj e
with the K-functionals using the jjj \Delta jjj-norms. Finally the negative-order norms are
defined by duality:
and jjjujjj e
The following inequalities are taken from the thesis of von Petersdorff [14]. A
modified proof is included here for the sake of completeness.
Theorem 2
;\Omega N be a partitioning of a bounded Lipschitz
domain\Omega into
non-overlapping Lipschitz domains. For \Gammar - s - r,
e
e
Proof. Introduce the product spaces
Y
s(\Omega
Y
e
s(\Omega
with norms given by
e
e
where product spaces X
the K-functional satisfies
so
and in particular
\Pi s for
Moreover,
with the duality pairing
Now consider the restriction and sum operators R and S, defined by
s(\Omega\Gamma and jjjSujjj e
\Pi s . Hence, by
interpolation,
s(\Omega\Gamma and jjjSujjj e
for In fact, these estimates hold also for \Gammar - s ! 0 by duality, because
Svi\Omega .
If jsj - r, then the Sobolev spaces of order s are invariant under C r\Gamma1;1 changes
of coordinates, allowing us to define H s (\Gamma) and e
H s (\Gamma) via a partition of unity
subordinate to an atlas of local coordinate patches. Thus, the Sobolev norms on \Gamma
are defined ultimately in terms of Sobolev norms on R d and, when \Gamma is an open
surface, on R d
.
In certain circumstances, Sobolev spaces may be continuously embedded in
type spaces and vice versa.
Theorem 3
1. If 0 - 2s ! d and
2. If
where the constant is independent of p.
3. If 0 - 2s ! d and
4. If
H \Gammas (\Gamma) -
r q
where the constant is independent of q.
Proof.
1. This follows immediately from the result (see [1]) H s (\Gamma) ,! L p (\Gamma) where
2. The following estimate (see, for example, [13, p.12])
Lp (R d
H d=2 (R d )
holds for any p - 2 with constant independent of p. The analogous result
holds for the domain \Gamma thanks to its construction in terms of local coordinate
patches in R d .
3. Applying H-older's inequality and the result in Part 1,
kwk Lp (\Gamma) kvk Lq (\Gamma)
and the result is proved.
4. The result follows from the estimate in Part 2, in a similar manner to the
proof of Part 3.
4.2 Scaling Properties of Norms
It will be useful to consider the behaviour of the Sobolev norms under a rescaling
of the bounded
domain\Omega\Gamma
2\Omega g: (28)
Then, for s 2 [0; r],
1. if u 2 e
e
e
2. if u
3. if u 2 H \Gammas
\Gammas(\Omega - d+2s jjjujjj 2
4. if u 2 e
H \Gammas
e
e
e
Proof. Since
L2 and @ ff u - \Gammajffj (@ ff u) - , Parts 1 and 2
hold for and hence by interpolation also for
3 and 4 then follow by duality, thanks to hu
vi\Omega .
Analogous results hold for Sobolev spaces defined on the whole of R d . For instance,
if (R d ) then
H s (R d )
or, if u 2 H \Gammas (R d ) then
H \Gammas (R d
H \Gammas (R d
H \Gammas (R d
Sharper estimates than these are possible with additional assumptions on u. The
next lemma gives an improved upper bound on the norm in H \Gammas .
(R d )
then
H \Gammas (R d
H \Gammas (R d
L1 (R d
where
- d+2s for
- 2d for d ! 2s ! 1.
Likewise, if u 2 L 1 (R d
H \Gammas (R d
e
H \Gammas (R d
e
H \Gammas (R d
(R d
Proof. Denote the Fourier transform of u by
Z
R d
e \Gammai2- \Deltax u(x) dx for - 2 R d ,
so that
H \Gammas (R d
Z
R d
u(-), the substitution
H \Gammas (R d
Z
R d
and
Z
Z
H \Gammas (R d
We have j-u(y)j - kuk L1 (R d ) for all y 2 R d , and thus
Z
L1 (R d )
Z
leading to the desired upper bound for ku - k 2
H \Gammas (R d )
, with
A - d+2s
Z
dy
Z 1=-t
Finally, if u 2 L 1 (R d
H \Gammas (R d
(R d ) denotes the
extension of u by zero, then
e
H \Gammas (R d
H \Gammas (R d
H \Gammas (R d
L1 (R d )
e
H \Gammas (R d
L1 (R d
We now consider lower bounds on the norm in H \Gammas .
such that if u 2 L 1 (R d (R d ) satisfies
Z
R d
Z
R d
then
H \Gammas (R d
Z
R d
where A - is given in (29). The same is true when R d is replaced by the half-space
R d
Proof. Let (R d ), and assume that (31) holds. By the mean
value theorem,
dt
Z
R d
so if we put -
Hence, from (30), if
H \Gammas (R d
Z
Z
jyj \Gamma2s dy;
and if
Z
Z 2-0
ae
- d\Gamma2s for 2s ? d,
implying the desired lower bound.
To obtain the estimate for the half-space R d
, we use the Seeley extension oper-
ator, setting
R, and where
so that 1
see [4, p. 64-66]. Since
Z
R d
Z
Z
R d
and
Z
R d
Z
Z
we see that if u satisfies
Z
Z
then Z
R d
Z
R d
fi fi . Simple manipulations show
so the series is alternating, with 2 \Gamma(k+1) j-
implying that f
(R d
(R d ) is bounded, and (Eu)
E(u - ), there is a -
H \Gammas (R d
H \Gammas (R d
H \Gammas (R d )
Z
R d
Z
R d
To improve the lower bound in the H s -norm, we observe that the seminorm
defined in (26) and (27) satisfies
for any open
set\Omega ' R d (bounded or unbounded).
the following is true.
(R d ) for (R d ),
and
(R d
(R d
(R d
4.3 Norms of Nodal Basis Functions
It is possible to obtain estimates for Sobolev norms of the nodal basis function ' k
in terms of the average size h k of the elements in the support \Gamma k of ' k .
Lemma 8 If ' k , k 2 N , is a nodal basis function, then
e
and
with constants independent of \Gamma k and p.
Proof. Follows immediately from Parts 1. and 3. of Lemma 4. The final result is
a simple computation.
Examining the proof of this result suggests one might also obtain useful estimates
by making use of Parts 2. and 4. of Lemma 4. However, the resulting estimates
would be sub-optimal as shown by:
Theorem 9 Let ' k , k 2 N , be a nodal basis function.
1. If 2s ? \Gammad, then
e
2. If sufficiently small,
e
3. If 2s ! \Gammad, then for h k sufficiently small,
e
In parts 2 and 3, we assume that the condition (6) holds.
Proof. If d, then we may apply part 1 of Theorem 3, followed by
Lemma 8, to obtain the lower bound
In the critical case d, we can use part 2 of Theorem 3, with
to obtain
Lp (\Gamma) 'p
but this estimate is not sharp. In fact, Lemma 7 shows that k' k k 2
k for
all s - 0. Theorem 2 and Lemma 8 give the sharp upper bound
e
e
e
and part 1, for s - 0, follows from (25).
then we can apply part 3 of Theorem 3, followed by Lemma 8,
to obtain the upper bound
e
In the critical case \Gammad, we instead use part 4 of Theorem 3, choosing q 2 (1; 2]
such that 1
to obtain
e
ph 2d
Lemma 5 provides an alternative proof of these two estimates, as well as showing
that
e
k for 2s ! \Gammad.
Theorem 2 and Lemma 8 yield the lower bound
but this estimate is not sharp when 2s - \Gammad. Indeed, we see from Lemma 6 that
for h k sufficiently small,
ae h 2d
The results for negative s follow at once from these bounds along with (25).
5 Proof of the Main Results
The earlier remarks indicate the key role played by decompositions of the form (8):
where v belongs to the Galerkin subspace X and v k is of the form ff k ' k (with
The assumptions on the partition P and the construction of the nodal basis
functions mean that the following properties are valid:
ffl Let K 2 P be any element, define
and let
Then M is uniformly bounded over the family of partitions.
ffl The indexing set N may be partitioned into disjoint subsets N
preserving the property
where L is uniformly bounded over the family of partitions.
For instance, if \Gamma is an open arc and the Galerkin subspace consists of continuous
piecewise polynomials of degree
be decomposed as in (32). Then, for
Proof. The left hand bound is proved by making use of the property (34) as follows
k2N l
and then by H-older's inequality and the fact that M in (33) is uniformly bounded,
Integrating over x 2 K and then summing over all K 2 P completes the proof.
Lemma 11 Let v 2 X be decomposed as in (32).
1. If 0 - 2m ! d then
and X
e
2. If
min )j
and X
e
min )j
Proof. Let k 2 N . By Lemma 8,
where the constants are independent of p, and by Theorem 9,
e
Hence, summing over the degrees of freedom leads to
and X
e
1. Suppose 2m ! d. Choosing
min
and X
e
using H-older's Inequality and Lemma 10,
Hence, with the aid of Theorem 3 part 1,
and X
e
2. Suppose d. Then (39) and (40) read
and X
e
For
Applying Theorem 3 part 2 and Lemma 10 gives
so that
Choosing
min )j) allows the first factor to be bounded as follows
min )j
and the proof is complete.
Lemma 12 Let v 2 X be decomposed as in (32). If 0 - 2m - d then
e
and
e
Proof. By the Cauchy-Schwarz inequality and Theorem 2,
e
k2N l
k2N l
k2N l
e
Theorem 9 imply that, if 0 - 2m - d, then
e
and
e
The results are obtained by summing over k 2 N .
be decomposed as in (32). If \Gammad - 2m - 0 then
Moreover,
e
Proof. Let k 2 N and choose K 2 P such that x k 2 K. By Lemma 4 part 3,
K is the reference element and - Summing over all k 2 N yields
min
K2P
for \Gammad - 2m - 0. The first estimate now follows, since, applying Theorem 2,
K2P
with the aid of Theorem 9 and (45),
e
e
again using Theorem 9 and (45),
e
e
Summing each of these estimates over k 2 N , and applying Theorem 2 as above,
completes the proof.
Lemma 14 Let v 2 X be decomposed as in (32).
1. If \Gammad ! 2m - 0 then
e
and
e
2. If
e
and
e
min )j
Proof.
1. Suppose \Gammad ! 2m - 0. Applying Theorem 3 part 3 and Lemma 10 gives
e
inequality,
and hence,
e
Applying Lemma 8 reveals that
and so, on the one hand,
and, on the other hand, by Theorem 9,
2. Suppose \Gammad. Then applying Theorem 3 part 4 and Lemma 10 gives, for
any q 2 (1; 2],
e
where the constants are independent of q. To obtain the first result, apply H-older's
inequality to obtain
and therefore,
e
choose
e
The second result is obtained using a variation of the same argument. By H-older's
inequality,
then the first factor is bounded as
and, using Theorem 9, the second factor may be bounded by
Therefore,
e
min )j) and choose
(Nh d
min )j
and the result follows immediately.



--R

On the conditioning of finite element equations with highly refined meshes.

Introduction to the Theory of Linear Partial Differential Equations
The Finite Element Method for Elliptic Problems.
Boundary integral equations for mixed boundary value problems in polygonal domains and Galerkin approximation.
A finite element method for some integral equations of the first kind.
The Aubin-Nitsche lemma for integral equations
The approximation of closed manifolds by triangulated manifolds and the triangulation of closed manifolds.
A preconditioning strategy for boundary element Galerkin methods.
Curved finite element methods for the solution of singular integral equations on surfaces in R 3
An augmented Galerkin procedure for the boundary integral method applied to two-dimensional screen and crack problems
Partial Differential Equations III
Randwertprobleme der Elastizit-atstheorie f?r Polyeder Sin- gularit-aten und Approximation mit Randelementmethoden
A hypersingular boundary integral method for two-dimensional screen and crack problems
--TR

--CTR
N. Heurer , M. E. Mellado , E. P. Stephan, hp-adaptive two-level methods for boundary integral equations on curves, Computing, v.67 n.4, p.305-334, December 2001
T. Tran , E. P. Stephan, Two-level additive Schwarz preconditioners for the h-p version of the Galerkin boundary element method for 2-d problems, Computing, v.67 n.1, p.57-82, July 2001
diagonal scaling;condition numbers;boundary element method;preconditioning