D D h
Domain decomposition methods are all implicitly or explicitly based on different ways
of handling the unknown at the interfaces. From the PDE point of view, if the value of the
solution is known at the interfaces between the different regions, these values could be used
in Dirichlettype boundary conditions and we will obtain uncoupled Poisson equations.
We can then solve these equations to obtain the value of the solution at the interior points.
If the whole domain is discretized by either ¬nite elements or ¬nite difference techniques,
then this is easily translated into the resulting linear system.
Now some terminology and notation will be introduced for use throughout this chapter.
Assume that the problem associated with domain shown in Figure 13.1 is discretized with
centered differences. We can label the nodes by subdomain as shown in Figure 13.3. Note
that the interface nodes are labeled last. As a result, the matrix associated with this problem
will have the structure shown in Figure 13.4. For a general partitioning into subdomains,
the linear system associated with the problem has the following structure:
£¤ £¤ ¨¦
§ ¨¦
§ £¤ ¨¦
§
¥
¤ ¤§ c5 § ¤ §
’
c
c
c
¤ ¤§
§ ¤ §
¥
¤ § ¨ ¤ § 5 ¤ §¨
¨ ¨
Pn ¦ j
. . .
.. ˜ ˜
. . .
. . . .
D
¥ © ¥ © ¥ ©
¥
a5 
W W W W
£ ¨£ £
c §TVT
T
W
where each represents the subvector of unknowns that are interior to subdomain and
C C
represents the vector of all interface unknowns. It is useful to express the above system
in the simpler form,
¥ ¥ ¥
An ¦ j
¥ a5
˜

˜ ˜
with
D D h
£
¦ ¦ ¦
Thus, represents the subdomain to interface coupling seen from the subdomains, while
5
represents the interface to subdomain coupling seen from the interface nodes.
£
¡
¤ ¤ ¤ 5
©
! @ $"
#%
# ¥B
7 ) I 9 7 ¡C C
F
9F ( 4(
F $
I
When partitioning a problem, it is common to use graph representations. Since the sub
problems obtained from a given partitioning will eventually be mapped into distinct pro
cessors, there are some restrictions regarding the type of partitioning needed. For example,
in ElementByElement ¬nite element techniques, it may be desirable to map elements into
processors instead of vertices. In this case, the restriction means no element should be split
between two subdomains, i.e., all information related to a given element is mapped to the
same processor. These partitionings are termed elementbased. A somewhat less restric
tive class of partitionings are the edgebased partitionings, which do not allow edges to be
split between two subdomains. These may be useful for ¬nite volume techniques where
computations are expressed in terms of ¬‚uxes across edges in two dimensions. Finally,
vertexbased partitionings work by dividing the origin vertex set into subsets of vertices
and have no restrictions on the edges, i.e., they allow edges or elements to straddle be
tween subdomains. See Figure 13.2, (a), (b), and (c).
t§™
p wy z ‘wf {
{7 } p7
s£¤§
§ !
(a) (b)
9 10 11 12 9 10 11 12
c
5 6 7 8 5 6 7 8
¨
1 2 3 4 1 2 3 4
(c)
9 10 11 12
c
7
5 6 8
¨
1 2 3 4
Y% ™ #
3¡
!
(a) Vertexbased, (b) edgebased, and (c)
elementbased partitioning of a mesh into two subregions. ¢
¡
¤ ©§¡¤
¨) ¨
% @ $"
#%
# ¥B
7 ) I 9 4(0
F
1 ) I