Multiplicative Schwarz Algorithms for the Galerkin Boundary Element Method.
We study the multiplicative Schwarz method for the h- and the p-version Galerkin boundary element method for a hypersingular and a weakly singular integral equation of the first kind. For both integral equations we prove that the contraction rate of the multiplicative Schwarz operator is strictly less than 1 for the h-version for the two level and the multilevel methods, whereas for the p-version we show that the contraction rate approaches one only logarithmically in p for the 2-level method. Computational results are presented for both the h-version and the p-version which support our theory.
Introduction
.
We study multiplicative Schwarz methods for the h and p versions of the Galerkin boundary
element method applied to hypersingular and weakly singular integral equations on open or
closed curves. These equations are integral reformulations for boundary value problems with
the Laplace equation and the Dirichlet or Neumann boundary conditions (see [4]). Application
of the Galerkin method to solve these integral equations yields linear systems with dense,
symmetric and positive-definite stiffness matrices. Since the condition numbers of these matrices
grow like h \Gamma1 in the h version and like p 2 in the p version (see [10]), the convergence rate of the
conjugate gradient algorithm approaches 1 (the non-convergent status of the iterative method)
like ch 1=2 as positive constant c. We shall
propose for both versions multiplicative Schwarz algorithms which significantly improve the
rate of convergence of the conjugate gradient method.
We shall analyze for the h-version a 2-level method which corresponds to a multigrid algorithm
using the Gau-Seidel algorithm for smoothing, and a multilevel method which corresponds
to a multigrid algorithm using the Jacobi smoother. We shall prove that both the
Institut f?r Angewandte Mathematik, University of Hannover, Germany
y Institut f?r Angewandte Mathematik, University of Hannover, Germany
z School of Mathematics, University of New South Wales, Sydney, 2052, Australia
2-level and multilevel methods yield an error reduction which is independent of the mesh sizes
and number of levels. This is an improved result compared with [8].
For the p-version we propose a 2-level method which has an error reduction factor approaching
one like
The analysis is based on the abstract framework of [3] (see also [13]) which requires two
main ingredients. The first ingredient is estimates for the extremum eigenvalues of the additive
Schwarz operator which is correspondingly defined from the multiplicative operator. For the
boundary integral operators considered in this paper, these estimates were recently obtained for
both versions [10, 11]. The second ingredient is a strengthened Cauchy-Schwarz inequality. We
will in this paper prove inequalities of this type for both versions for the hypersingular integral
equation, and for the p-version for the weakly singular equation. A strengthened Cauchy-Schwarz
inequality for the h-version of the Galerkin method applied to the weakly singular
integral equation is still an open question to us. It is noted that since the equations considered
in this paper yield dense stiffness matrices, the proofs of these inequalities are much more
complicated than those appear in the finite element method where differential operators are
considered which yield sparse matrices.
In Section 2 we introduce the gereral setting of multiplicative Schwarz methods and recall
the abstract analysis from [3, 13]. We prove in Section 3 strengthened Cauchy-Schwarz inequalities
for the hypersingular equation (Lemmas 3.2 and 3.12) and appropriately apply the result
of Section 2 to obtain estimates for the rates of convergence (Theorems 3.3, 3.9, and 3.13).
Similar treatment for the weakly singular equation is proceeeded in Section 4 (Lemma 4.2 and
Theorem 4.3). In Section 5 we present our numerical results which clearly underline the the-
ory. Some useful lemmas which are used in the proofs of the strengthened Cauchy-Schwarz
inequalities are proved in the Appendix.
For simplicity of notation, the integral equations considered in this paper are defined on the
interval (\Gamma1; 1). A generalization to a polygonal curve is straight forward.
General setting of multiplicative Schwarz methods.
Multiplicative (and additive) Schwarz methods are in general defined via a subspace decomposition
of the space of test and trial functions together with projections onto these subspaces.
More precisely, let
and let projections defined by
Here a(\Delta; \Delta) is a symmetric and positive-definite bilinear form on V . The multiplicative Schwarz
operator is then defined as
where I is the identity map and
is the error propagation operator. We note that
is the corresponding additive Schwarz operator.
By defining
we obtain
which in turn yields
We now present in this section some results which were mainly proved in [3] and [13]. We
include the proofs here for completeness. These results will be used in the analysis of the
following sections.
Lemma 2.1 For any v 2 V there holds
Proof. We have, for
or equivalently
Summing up we obtain the desired result. 2
The analyses in [3] and [13] suggest that we would have to prove a strengthend Cauchy-Schwarz
inequality corresponding to the decomposition (1). The following lemma shows that it
is possible to avoid the coarse grid subspace V 0 in this inequality and use instead a bound for
the maximum eigenvalue of the additive Schwarz operator.
Lemma 2.2 Let \Theta be an whose elements are
defined by
If there exist positive constants C 1 and C 2 such that
a(P AS v; v) - C 2 a(v; v) 8v 2 V; (3)
and that
then there holds for any v 2 V
a(P AS v; v) - C 1
Proof. Using (2) we obtain
implying
Cauchy-Schwarz's inequality implies
!1=2
On the other hand it follows from the definitions of ' ij and the k \Delta k 2 -norm of matrices that
!1=2
Inequalities (4), (5), and (6) yield
This inequality and (3) imply
The lemma is proved. 2
Theorem 2.3 If there exist positive constants C
and a constant C 1 satisfying
then there holds
a -
a is the norm given by the bilinear form a(\Delta; \Delta).
Proof. For any v 2 V we have using Lemma 2.2
Using Lemma 2.1 we deduce
which implies
a -
The theorem is proved. 2
Remark 2.4 If we use the multiplicative Schwarz method as a preconditioner for the CG-
scheme, we have to use the symmetrized version
The condition number is bounded by
a
a
Remark 2.5 C 0 is a lower bound for the minimum eigenvalue and C 2 is an upper bound for
the maximum eigenvalue of the additive Schwarz operator P AS .
Multiplicative Schwarz methods for the hypersingular integral
equation.
We consider the hypersingular integral equation
f:p:
Z
ds
where f.p. denotes a finite part integral in the sense of Hadamard. Let e
\Gamma be an arbitrary closed
curve containing \Gamma. We define, as in [7], the Sobolev spaces
e
loc
and H \Gamma1=2 (\Gamma) being the dual space of e
H 1=2 (\Gamma) with respect to the L 2 inner product on \Gamma. As
was shown in [4], D is continuous and invertible from e
H 1=2 (\Gamma) to H \Gamma1=2 (\Gamma). Moreover, D is
strongly elliptic, i.e., there exists a constant fl ? 0 such that
where h\Delta; \Deltai denotes the L 2 duality on \Gamma. Hence D defines a continuous, symmetric and positive-definite
bilinear form a(v;
3.1 The h-version.
We consider a uniform mesh of size h on \Gamma
and define on this mesh the space V h of continuous piecewise-linear functions on \Gamma which vanish
at the endpoints of \Gamma. We note that V h is a subset of e
(\Gamma). The h-version boundary element
method for Equation (7) reads as:
Find h such that
The stability and convergence of the scheme (9) was proved in [12]. It is known that the
condition number of the matrix system derived from (9) is N 2 . We show in this paper that
the multiplicative Schwarz method yields a preconditioned system which has convergence rate
strictly less than 1.
3.1.1 2-level method.
Let OE h;j , the hat functions forming a basis for V h . We then decompose
where VH is defined as V h with mesh size g. For notational
convenience we identify respectively. The projections
and the operators PMS and P AS are then well defined. Our task
is to verify the assumptions of Theorem 2.3.
The following result was proved in [11].
Lemma 3.1 There exist constants C independent of h such that for any v 2 V h
Let \Theta be an whose elements are defined by
It follows from the Cauchy-Schwarz inequality that 0 1. Therefore, in general there
holds
In view of Theorem 2.3 we will prove in the next lemma that the bound is indeed independent
of N . During the course of the proof, a strengthened Cauchy-Schwarz inequality is proved.
Lemma 3.2 There exists a positive constant C 3 such that
Proof. First we note that
u denotes the derivative of u with respect to the arc-length, and
Z
log
Let
z 2 log jzj for z 6= 0;
Then by using the formula
Z d
c
a
log
we can prove
where
This implies
log 2X
and hence it suffices to prove that
To do so, we define
to obtain
Since
f is a concave function on (1; 1), which results in G(m) ! 0 for m - 2. By the mean value
theorem there exist ' and ' 0 2 (0; 1) such that if


(For the mean value theorem argument used above, the reader is referred to [1, p. 101].) We
note that
Since
we deduce from (12) and (13)
for any m - 6;
which in turn yieldsX
x
x
dx +X
This completes the proof of the lemma. 2
As a consequence we obtain, due to the abstract Theorem 2.3,
Theorem 3.3 Let C 0 , C 2 , and C 3 be given by Lemmas 3.1 and 3.2, and let C g.
Then for any v 2 V h there holds
Remark 3.4 Due to the subspace decomposition (10) we see that this 2-level multiplicative
Schwarz algorithm corresponds to the unsymmetric 2-level multigrid algorithm using the Gau-
Seidel smoother.
3.1.2 Multilevel method.
We shall in this subsection design a multilevel method for the hypersingular equation. The
analysis for this method is slightly different from that of the general framework in Section 2.
The main reason for this difference is the non-availability of a strengthened Cauchy-Schwarz
inequality which can yield an estimate like Lemma 3.2.
Starting with a coarse mesh
we divide each subinterval into two equal intervals. Hence, if h l is the meshstep of N l ,
. For l be the spline space associated with N l
which contains continuous and piecewise-linear functions vanishing at the endpoints \Sigma1. Let
OE l
l
be the nodal basis for V l , where N is the dimension of V l . We then
decompose V l as
l
l
with V l
l . Eventually, V L is decomposed as
l
l
Let
l
for
i is defined for any v 2 V L by
and let
Y
The multilevel multiplicative Schwarz operator is now defined as
Analogously, we define
Letting
we deduce
which in turn yields
l
The following lemma follows easily in the same manner as Lemma 2.1.
Lemma 3.5 For any v 2 V L
The following two lemmas were proved in [11]:
Lemma 3.6 There exists a positive constant C 0 independent of h and L such that for any
there holds
Lemma 3.7 There exist constants such that for any v 2 V k where
there holds
The above lemma plays the role of Lemma 3.2 in the analysis of the multilevel method. We
also need the following technical lemma:
Lemma 3.8 For any there holds
where C 1 is the constant given by Lemma 3.7.
Proof. By using the Cauchy-Schwarz inequality for the symmetric and positive-definite
bilinear form a(T k \Delta; \Delta), and Lemma 3.7 we obtain
which implies
The lemma is proved. 2
Theorem 3.9 Let C 0 , C 1 , and fl be given by Lemmas 3.6 and 3.7. Then for any v 2 V L
where
Proof. The theorem is proved if we can prove that
By Lemma 3.5 it suffices to prove
We have from Lemma 3.6, the Cauchy-Schwarz inequality, the inequality 2ab - a noting
that
a(T l v; v)
It follows successively from (16), the Cauchy-Schwarz inequality,
Lemmas 3.7 and 3.8 that
Inequalities (18) and (19) yield (17) and theorem is proved. 2
Remark 3.10 Due to the subspace decomposition (14) this multilevel multiplicative Schwarz
algorithm corresponds to the unsymmetric multigrid algorithm using the Jacobi-smoother.
3.2 The p-version.
We shall in this subsection design a multiplicative method for the p-version of the Galerkin
boundary element method applied to the hypersingular integral equation.
We define on the mesh (8) the space V p of continuous functions on \Gamma whose restrictions
are polynomials of degree at most p, p - 1. In order to
guarantee that these functions belong to e
H 1=2 (\Gamma), we also require that the functions vanish at
the endpoints \Sigma1 of \Gamma. For the p-version of the Galerkin scheme, we approximate the solution
of (7) by functions in V p and increase the accuracy of the approximation not by reducing h
(which is fixed) but by increasing p. More explicitly, the p-version boundary element method
for Equation (7) reads as:
Find u
such that
The stability and convergence of the scheme (20) was proved in [9]. Note that the dimension of
Choosing a basis for V p , we derive from (20) a system of equations to
be solved for u
p . In practice, we use the following basis. Let OE k , defined
as hat functions satisfying
For we also define L q;j as the affine image onto \Gamma j of
where L q\Gamma1 is the Legendre polynomial of degree q \Gamma 1. We extend L q;j by 0 outside \Gamma j . It is
clear that
is a basis for V p . Solving the equation (20) amounts to solving
where the matrix AN has entries a(v; w) with v; w 2 B. The condition number of (21) grows
at least like p 2 and at most like p 3 . We will define a multiplicative Schwarz method to solve
instead of (21) a preconditioned system which has condition number growing significantly slower
than
We decompose V p as a direct sum
where
the space of continuous piecewise-linear functions on \Gamma vanishing at \Sigma1, and
The space V 0 serves the same purpose as the coarse grid space in the h-version. We note that
functions in V p
are supported in -
With the projections P j appropriately defined as in Section 2, we can define the multiplicative
and additive Schwarz operators as
where
Analogously to Lemma 3.1, we have
Lemma 3.11 [10] There exist constants C independent of p and N such that for any
there holds
Our next task is to show a strengthened Cauchy-Schwarz inequality for this version.
Lemma 3.12 Let V p
i be defined as in (23) and let
Then there exists a constant C independent of i; j; p such that
If 1-i;j-N , then there holds
where
Proof. Let
l=2 v l L l;j . Then we have
Due to Lemma A.6 (compare with [5, Lemma 1]) we have with
From (24) and (25) we obtain
\Theta
\Theta
oe
For
oe
oe
Due to Lemma A.1 we have (note the scaling)@ p
Using (26), (27) and (28) we obtain for
Due to the Cauchy-Schwarz inequality we have independent of p and N .
Therefore, for any there holds
Finally we have
This completes the proof of the lemma. 2
Using the abstract Theorem 2.3 we can prove
Theorem 3.13 Let C 0 , C 2 , and C 3 be given by Lemmas 3.11 and 3.12. If C 1
then for any v 2 V p there holds
Amultiplicative method for the weakly singular integral equation

We shall now in this section design a multiplicative algorithm for the p-version Galerkin method
applied to the weakly integral equation of the form
Z
log ds
As was shown in [4], V is continuous and invertible from e
H \Gamma1=2 (\Gamma) to H 1=2 (\Gamma). Here the Sobolev
space H 1=2 (\Gamma) is defined as the space of functions which are traces of functions in H 1
loc
e
H \Gamma1=2 (\Gamma) is its dual. It is known that there exists a constant fl ? 0 such that
e
where h\Delta; \Deltai denotes the L 2 duality on \Gamma. Hence V defines a continuous, symmetric and positive-definite
bilinear form a(v;
H \Gamma1=2 (\Gamma). We define on the mesh (8)
the space -
of piecewise continuous functions on \Gamma whose restrictions on \Gamma j :=
are polynomials of degree at most p, p - 1. For the p-version of the Galerkin
scheme, we approximate the solution of (29) by functions in -
increase the accuracy of
the approximation not by reducing h (which is fixed) but by increasing p. More explicitly, the
p-version boundary element method for Equation (29) reads as:
Find u
p such that
The stability and convergence of the scheme (30) was proved in [9]. Note that the dimension of
Choosing a basis for -
we derive from (30) a system of equations
to be solved for u
p . In practice, we use the following basis. Let OE k , be defined as
piecewise constant functions satisfying
For we also define L q;j as the affine image onto \Gamma j of the Legendre
polynomial L q of degree q. We extend L q;j by 0 outside \Gamma j . It is clear that
is a basis for -
. Solving the equation (30) amounts to solving
where the matrix AN has entries a(v; w) with v; w 2 B. The condition number of (31) grows at
least like p 2 and at most like p 3 . We will define a multiplicative Schwarz method to solve instead
of (31) a preconditioned system which has condition number growing significantly slower than
We decompose -
as a direct sum
where
the space of piecewise constant functions on \Gamma, and
The space -
serves the same purpose as the coarse grid space in the h-version. We note that
functions in -
are supported in -
With the projections P j defined appropriately as in Section 2 we can define the multiplicative
and additive Schwarz operators as
where
Similarly to Lemma 3.11, we have
Lemma 4.1 [10] There exist constants C 0 and C 2 independent of p and N such that for any
there holds
Again our next task is to prove a strengthened Cauchy-Schwarz inequality.
Lemma 4.2 Let -
i be defined as in (33), and let
there exists a constant C independent of i; j; p such that
Moreover, if
where C 3 := C- 2 =3.
Proof. Let
Due to Lemma A.6 (compare with [5, Lemma 1]) we have with
From (34) and (35) we obtain
l
l
\Theta
\Theta
oe
For
oe
oe
Due to Lemma A.3 we have for (note the scaling)
Using (36), (37) and (38) we obtain for
Due to the Cauchy-Schwarz inequality we have independent of p and N .
Therefore, for any there holds
Finally we have
This completes the proof of the lemma. 2
Using the abstract Theorem 2.3 we can prove
Theorem 4.3 Let C 0 , C 2 , and C 3 be given by Lemmas 4.1 and 4.2. If C 1
then for any v 2 -
there holds
5 Numerical results.
We consider the hypersingular integral equation (7) with the right hand side f(x) j 1. We
solve the Galerkin equations (20) for the p-version by the multiplicative Schwarz algorithm,
for different subspace decompositions and observe the expected behavior of the convergence
rate with respect to N and p (see Tab. 1). For the h-version we note the considerably lower
contraction rates of the 2-level method compared with the multilevel method in Tab. 3. But if
we take into account the high costs of solving a system of mesh width in each iteration
step we see that the multilevel method is the far superior method.
Analogously we consider the weakly singular integral equation (29) with the right hand side
We solve the Galerkin equations (30) for the p-version by the multiplicative Schwarz
algorithm. The numerical results in Tab. 2 show the expected behavior of the convergence rate.
In the case of the h-version we observe that the elements of the Galerkin matrix
x
f:p:
x
ds y ds x =: a i\Gammaj
depend only on the difference for an uniform mesh. Therefore we can reduce the memory
used to store the Galerkin matrix from O(N 2 ) to O(N ). In a more general case we have to use
a clustering or multipole technique to reduce the amount of memory needed. This also reduces
the amount of time for computing the Galerkin matrix. On a vectorcomputer SNI VPP 300/4
we have achieved a performance of 1000 MFlops/s.
In the case of the p-version we calculate the elements of the Galerkin matrix analytically.
Due to the smaller size of the Galerkin matrix we can store the full matrix in the main memory.
We have to note that our subspace decomposition in this case is actually a reordering of the
basis functions. Therefore the projections involved are simplyfied considerably.
Contraction rate
9 0.6245 0.6383 0.6524

Table

1: Hypersingular integral equation, p-version
Contraction rate
9 0.6401 0.6576 0.6745

Table

2: Weakly singular integral equation, p-version
A

Appendix


p. Then there exists a constant C
Contraction rate
2-level multilevel

Table

3: Contraction rates for the hypersingular integral equation, h-version
independent of u and p such that
~
Proof. From the definition of the interpolation norm k \Delta k ~
by the real K-method [2] we
have
~
Z 1'
u=v+w
We have
Therefore it is sufficient to take the infimum in H 1
~
Z 1t \Gamma2
dt: (40)
Due to v 2 H 1
0 (I) we can expand v also in antiderivatives of Legendre polynomials
For the norms in (40) there hold
and, due to Lemma A.2,
Let
l
and l 0
Using the the monotonicity of the square function and the inequality a when
we obtain from (40), (41), and (42)
~
Z 1t \Gamma2
dt
Z 1t \Gamma2 inf
dt
Z 1t \Gamma2 inf
dt
Z 1t \Gamma2 inf
(v k )2l  /
dt
Z 1t \Gamma2 inf
(v k )2l 0/
dt
Z 1t \Gamma2
dt: (43)
Note that if
a+b . Therefore we obtain
from equation (43)
~
Z 1t \Gamma2
dt
Z 1t \Gamma2
dt
Z 1Ck \Gamma5 2
dt
-s
This completes the proof. 2
. Then there holds
Proof. With the normalized antiderivatives of Legendre polynomials defined by L
there holds due to the proof of [6, Lemma 3.1]
Due to
there holds
This completes the proof. 2
Lemma A.3 Let
(x=h). Then there exists a constant C independent of u,
h and p such that
~
Proof. Due to ~
kuk ~
For
there holds
kuk ~
Due to Lemma A.4 we have
This completes the the proof. 2
(x=h). Then there exists a constant C independent of v, h
and p such that
Proof. Let 1). From the definition of the interpolation norm k \Delta k H 1=2 (\Gammah;h) by the
real K-method [2] we have
Z 1'
v=w+a
Z 1i
Z 1t \Gamma2 inf w
Z 1t \Gamma2 inf w
Z 1t \Gamma2 inf w
Z 1t \Gamma2 inf w
By the orthogonality property of the Legendre polynomials we have
On the other hand
It follows from the definition of matrix norms that
Lemma A.5 and a straightforward calculation give
2: (50)
Inequalities (48), (49), and (50) yield
This inequality and (47) imply
Z 1t \Gamma2 inf w k
dt
Z 1t \Gamma2 inf w k
dt
Z 1t \Gamma2
Lemma A.5 Let k; m - 1. Then we have
Proof. From the recurrence formula of the Legendre polynomials we have
which results in
and
be the Legendre polynomial of degree p i linearly transformed onto the
open straight line I ae IR 2 . L p i ;I is supposed to be continued by 0 outside I on the entire line
containing I where necessary. Let J ae IR 2 be another open straight line with -
there exists a constant C such that
Proof. Let x 0 be the midpoint of I and y 0 be the midpoint of J . Then there holds using the
Taylor expansion of log jx \Gamma yj
log
y log jx
and
y log
with 1). Due to the orthogonal properties of the Legendre polynomials the first sum
vanishes and we have
Z
I
Z
ds y ds x
Z
I
Z
ds y ds x : (52)
Applying the Cauchy-Schwarz inequality two times we obtain
'Z
I
ds x
ds y
I
Z
ds y ds x
'Z
I
Z
ds y ds x
sup
Since
y log
there holds
sup
(jI
(jI
Inequalities (53) and (54) imply
This completes the proof. 2



--R

Mathematical Analysis: A Modern Approach to Advanced Calculus

Convergence Estimates for Product Iterative Methods with Applications to Domain Decomposition
Boundary Integral Operators on Lipschitz Domains: Elementary Results
Efficient Algorithms for the p-Version of the Boundary Element Method
A Multilevel Additive Schwarz Method for the h-p Version of the Galerkin Boundary Element Method

Multigrid Solvers and Preconditioners for First Kind Integral Equations
On the Convergence of the p-Version of the Boundary Element Galerkin Method
Additive Schwarz Algorithms for the p-Version Boundary Element Method
Additive Schwarz Methods for the h-Version Boundary Element Method
A Hypersingular Boundary Integral Method for Two-Dimensional Screen and Crack Problems
Iterative Methods by Space Decomposition and Subspace Correction
--TR

--CTR
Matthias Maischak, Multiplicative Schwarz algorithms for the p-version Galerkin boundary element method in 3D, Applied Numerical Mathematics, v.56 n.10, p.1370-1382, October 2006
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
p-version Galerkin boundary element method;h-version Galerkin boundary element method;multiplicative Schwarz;multigrid algorithm