The Influence of Interface Conditions on Convergence of Krylov-Schwarz Domain Decomposition for the Advection-Diffusion Equation.
Several variants of Schwarz domain decomposition, which differ in the choice of interface conditions, are studied in a finite volume context. Krylov subspace acceleration, GMRES in this paper, is used to accelerate convergence. Using a detailed investigation of the systems involved, we can minimize the memory requirements of GMRES acceleration. It is shown how Krylov subspace acceleration can be easily built on top of an already implemented Schwarz domain decomposition iteration, which makes Krylov-Schwarz algorithms easy to use in practice. The convergence rate is investigated both theoretically and experimentally. It is observed that the Krylov subspace accelerated algorithm is quite insensitive to the type of interface conditions employed.
Introduction
We consider domain decomposition for the two-dimensional advection-diffusion equation with
application to a boundary conforming finite volume incompressible Navier-Stokes solver in mind,
see [27, 6, 20]. Therefore, our interests are more practical than theoretical. An advantage of the
boundary conforming approach is that the structures of the systems of equations that arise are
known beforehand. This enables us to develop efficient iterative solvers that can be vectorized
with relative ease. A disadvantage is that the boundary conforming approach is not suitable for
domains not topologically rectangular. Domain decomposition is used to overcome this problem.
The name Krylov-Schwarz refers to methods in which a Schwarz type domain decomposition
iteration is accelerated by a Krylov subspace method (such as CG or GMRES), see the preface
of [17]. Equivalently, Krylov-Schwarz means that Schwarz domain decomposition is used as preconditioner
for a Krylov subspace method. In this paper we use the GMRES method because of
non-symmetry of the discretized advection-diffusion equation.
Applied Analysis Group, Delft University of Technology, Mekelweg 4, 2628 CD Delft, The Netherlands,
(e.brakkee@math.tudelft.nl)
y Applied Analysis Group, Delft University of Technology, Mekelweg 4, 2628 CD Delft, The Netherlands,
(p.wilders@math.tudelft.nl)
Schwarz domain decomposition considered here uses a minimal overlap and no coarse grid
correction. Algebraically, this algorithm is formulated as a block iteration applied to a (possibly
augmented) matrix, see [14, page 372] and [25]. Theory [28] and experiments [9] show that both
a constant overlap in physical space and a coarse grid correction are needed to obtain constant
iteration count when the mesh is refined and the number of subdomains increases. Examples
of constant overlap in physical space can be found in [15, 22, 30]. However, despite that large
overlap gives better convergence rates, minimal overlap typically leads to lower computing times,
see [13, 11, 9], even for large and ill-conditioned problems. The reason is that with minimal
overlap, there is less duplication of work in overlap regions. Methods with small overlap are also
much easier to implement for practical complicated problems.
A coarse grid correction [18, 8, 1, 2] can be quite effective for improving convergence of domain
decomposition. However, as noted in [23, pp. 188], for small numbers of subdomains the
additional cost in forming and solving the coarse grid problem outweighs the reduction of the
number of iterations it gives. Moreover, in large codes used for engineering computations coarse
grid correction is very difficult to implement.
Similar to [12] and [25, 24], we study the influence of interface conditions on convergence rate.
A unified treatment of nonoverlapping Neumann-Dirichlet and Schwarz methods with minimal
overlap is not straightforward. An example at the analytic level can be found in [23, page 207].
Examples at the algebraic level are in [25, 24], where complicated augmentations of the discretization
matrix are needed. This paper unifies Neumann-Dirichlet and Schwarz methods in a simpler
way: by premultiplying the discretization matrix with a so-called influence matrix, which has a
very simple structure.
Our acceleration method differs from [12] in that we do not use relaxation but GMRES ac-
celeration. In [25, 24] good convergence was obtained with the unaccelerated Schwarz algorithm
by using optimized interface conditions. Instead, we do not use optimization, but investigate the
effect of some simple strategies for choosing interface conditions on the convergence rate of the
Krylov-Schwarz domain decomposition algorithm. We find that the accelerated method is quite
insensitive to the types of interface conditions used.
It is well-known that GMRES requires much storage if the vector length is large. In standard
Krylov-Schwarz algorithms, the full vector length is used. We will show, that, if subdomain
problems are solved accurately, one can reduce the vector length in GMRES. In fact, GMRES
then solves a reduced system, which consists of equations with only unknowns on or near the
interfaces.
Discretization
We consider the 2-D advection-diffusion equation written in general coordinates:X
@
a i @u
Equation (1) is obtained after a boundary-fitted coordinate
transformation to a rectangular
are interested in (1) because
it is a realistic model for the momentum equations occurring in computational fluid dynamics for
incompressible flows.
We discretize (1) using either cell-centered or vertex-centered finite volumes with a central
approximation of the advection terms on a uniform grid with mesh sizes h 1 and h 2 , which leads
to a 9-point discretization molecule. The resulting system of discretized equations is denoted by
3 Domain decomposition
In practice, complicated flow domains are used and one needs complete freedom in decomposing
the domain into subdomains. However, for the present model study we investigate only a rectan-
gular
it into a rectangular array of (nonoverlapping)
subdomains, see Figure 1. The difference between cell-centered and vertex-centered finite-volumes
is that in the latter case there are nodal points on the interfaces between subdomains. Following
[25], the unknowns at these nodal points are copied into each subdomain, see Figure 2.b. This
means that most nodal points on the interface are doubled into a left and right unknown. At cross
points, four copies are present. The respective equation is repeated for each copied unknown,
adding zeroes in the discretization matrix at positions associated with copies from other domains.
This is in contrast to [25] where the coefficients of the discretization are also adapted. The latter
mechanism leads to subdomain problems with the desired types of boundary conditions on the
interfaces. As opposed to [25], we use premultiplication with the influence matrix, see further on.
For the analysis and description of the algorithm we restrict ourselves to two non-overlapping
Some details on the multi-domain case
will be given.
\Omega 9
\Omega 6

Figure

1: Decomposition of a
domain\Omega into 3 \Theta 3 domains of each 6 \Theta 6 cells. The global grid is
uniform
We find the following way to describe domain decomposition convenient. Replace (2) by
The matrix M in (3) is called the influence matrix and is used to obtain various types of coupling
conditions on the interfaces. Section 3.1 describes M in detail. The use of the matrix M leads to
a 12 point molecule for the first layer of points near the interface, see Figure 2.
Define the disjoint index sets I j such that i 2 I j if u i
This definition of I j is also valid
for the vertex-centered case because the unknowns at the interface are doubled in that case. Both
A and -
f are partitioned into blocks according to these index sets I 1 and I 2 . Eq. (3) then becomes
A 11
A 12
A 21
A 22
Schwarz domain decomposition is a block Gauss-Seidel or Jacobi iteration applied to (4),
with
A 22
A 21 gives block Gauss-Seidel and Jacobi. The algorithm (5) is a
Schwarz domain decomposition algorithm with a minimal (O(h)) overlap. Following [14, p. 370],
we classify the algorithm as non-overlapping. The Gauss-Seidel variant corresponds to multiplicative
Schwarz and the Jacobi variant, which is suitable for parallelization, corresponds to additive
Schwarz. Section 3.3 describes Krylov subspace acceleration of this Schwarz algorithm.
3.1 The influence matrix
The purpose of the influence matrix M , introduced in (3), is to give a unified framework to
treat both classical Schwarz and Neumann-Dirichlet algorithms. The different types of interface
conditions are obtained by varying parameters in M . This study only uses a one-parameter
coupling, but extensions to more parameters are also possible.
(a) (b)

Figure

2: Interface variables: cell-centered (a) and vertex-centered (b)
Let I denote the index set of all variables and let J be the subset of I containing the indices of
two rows of variables near the interface, see Figure 2. These variables are called interface variables
and play an important role in the next sections. Let K denote the subset of J containing the
indices of variables in the first layer on either side of the interface \Gamma. The influence matrix M
takes linear combinations of discretization molecules associated with unknowns in K, and thus
influences the discretization at points in K. The influence matrix is defined as follows:
1.
2. do not correspond to the same subdomain.
Furthermore, we restrict M by allowing nonzero M ij only at points i and j directly opposite each
other with respect to the interface. This means that we omit any tangential dependencies in M
and consider only a single normal dependencies. This leads to a 1-parameter coupling.
For the situation of two subdomains in Figure 2, the matrix M has at most two non-zero
entries at each row i 2 K: one at M ii = 1 and the other at . The subscript i shows
that - may vary along the interface. The parameter - ij depends on the coupling strategy used.
Of course, we also have M so that
Invertibility of the influence matrix M is ensured by the condition
In the general multi-domain case, cross-points can occur. At cross-points (corner points), the
influence matrix M has at most three non-zero entries: M
at one interface and M ij 2
at the other.
Some interesting choices for - are:
Neumann
Dirichlet
is the normal mesh P'eclet number defined by
with the coordinate direction corresponding to the normal direction. For the present
model study, we have, for vertical interfaces,
with depending on which subdomain i corresponds to. This means that the normal
mesh P'eclet numbers as seen from the different blocks always have opposite signs.
In [7], the choices listed in (9) are worked out in detail for the constant coefficients case with
In that case, the discretized subdomain problems are identical to the ones obtained
by imposing Neumann (- N
ij ) or Dirichlet (- D
conditions at the interface and by discretizing using
the finite volume method.
At 0, the use of a Dirichlet condition is required to obtain well-posed subdomain
problems. However, the corresponding - D
ij is singular for \Gamma2. Therefore, we have omitted
a further study of this choice and use - S
ij instead. In the vertex-centered case, we can avoid this
problem by taking
This leads to a relation between the first layer of left and right unknowns only, which is equivalent
to a direct Dirichlet update. In this way, we get a vertex-centered finite volume version of the
Neumann-Dirichlet algorithm studied in [19], by taking
In general one wants to vary the type of interface condition depending on the local flow parameters
We choose
parameter that can vary along the interface. The basic Schwarz iteration is obtained
with
The choice (14) is referred to as the Schwarz-Schwarz (S-S) algorithm. Neumann-Schwarz (N-S)
is obtained with ae
In this case the transition is discontinuous. The Robin-Schwarz (R-S) method uses a smooth
transition, with
This paper takes p 2. Note that the three strategies for domain decomposition (14), (15)
and (16) all reduce to Schwarz iteration when applied to the Poisson equation.
3.2 The interface equations
The Krylov-Schwarz algorithm corresponds to a Krylov subspace method for solving the following
preconditioned system
where N is the block lower triangular or block diagonal matrix from (6). We will show that we
can reduce the system (17) to a smaller system concerning only interface unknowns u i with
see

Figure

2. Let denote the vector of interface variables and let
the remaining variables.
the following injection operators:
I the trivial injection operator from w into u defined by
else (18)
I the trivial injection operator from v into u defined by
ae
The following theorem provides useful information about the structure of a matrix.
Theorem 1 If the matrix
A satisfies the following property
I \Theta J; (20)
then after ordering u such that
, the system (17) becomes
I P
f
Proof:
or -
f .
By premultipling with N \Gamma1 , we get
and by premultiplying the result with
\Theta P Q
, we get
f
f
by ordering the components of u as pre-
scribed. 2
Since the influence matrix has nonzero entries only for the first layer of unknowns near the
interface, and the discretization is a 9-point molecule, it can be shown that the matrix N \Gamma A can
only have nonzero elements at positions (i; I \Theta J ; the proof of this is omitted. Therefore, the
matrices N and -
A of this paper satisfy the conditions of Theorem 1.
The block form of (21) shows that v can, in principle, be solved for independently of w, by
solving the system of interface equations
A numerical example of (24) can be found in [16] for a small one-dimensional Poisson problem.
Note that we assume accurate subdomain solution: that is
corresponding
to the same domain. With inaccurate subdomain solution, we can get
I 2 J which violates the assumption of Theorem 1.
From (21) we see that the matrix N
A in (17) has an eigenvalue
equal to the number of non-interface variables and that all the other eigenvalues are shared with
the interface equations (24). This property means that the interface equations (24) have the same
spectrum as the preconditioned system (17), apart from - = 1. Hence, (24) does not need to be
preconditioned further.
The approach is strongly related to the Schur complement method, typical of finite element
methods, in which subdomain problems are solved exactly and domain decomposition also amounts
to solving an interface problem. In [4, 10], it is shown that the multiplicative overlapping Schwarz
method is equivalent to a Schur complement method with appropriate block preconditioner.
In [29], a different proof of this is given for the nonoverlapping method of the present paper.
The interface problem is somewhat different from that arising in Schur complement methods because
in our terminology, the interface unknowns do not (all) reside on the interface. Furthermore,
our method is more general because it can be applied to finite volume/difference methods as well.
3.3 Krylov acceleration of the Schwarz method
Since domain decomposition methods in general tend to converge slowly if at all, an acceleration
technique is needed. We use the GMRES [21] Krylov subspace method to solve the
interface equations (24). To solve (24), all that is required is a method to compute the interface
matrix-vector product Q
v. Similar to methods based on Schur's complement, see for
instance [3], it is not necessary to form the matrix of the interface equations explicitly.
It turns out that a single iteration of the unaccelerated algorithm (5) can be used to obtain
the interface matrix-vector product for Q
AQ. This enables a step-wise implementation of
accelerated domain decomposition, which is of major importance for complicated CFD codes.
Also, the required vector length in GMRES is quite small because only a small system of interface
equations must be solved. This makes the approach practical for large problems.
Given the implementation of unaccelerated domain decomposition (5), we can compute -
f if u is given. Because of the property that
I \Theta J ,
we have if
f . Furthermore, if we introduce -
u,
we get
f
The injection Q and restriction Q T are easily implemented as subroutines, so that computation of
given v is easy. If we define
f . The problem
to be solved is rewritten as
Given the initial guess v 0 , GMRES acceleration proceeds as follows:
1. Compute the right-hand side
2. Solve the problem Q
using GMRES with initial guess
product is computed from Q
3.
The final inner subdomain solutions collected in the vector u are computed by doing a last domain
decomposition iteration with the computed interface solution v:
f .
Theoretical background
Some theoretical analysis is possible under simplified conditions. In equation (1) we assume
field with a 1 ; a 2 - 0. The boundary conditions are
periodic in the y-direction. On the left boundary (inflow) we prescribe a Dirichlet condition and
on the right boundary (outflow) a homogeneous Neumann condition. We take h and we
split the domain in two parts with a vertical interface in the middle.
To obtain convergence estimates for GMRES accelerated domain decomposition, we use theorem
5 of [21], from which it follows that for GMRES without restart
for some K ? is the number of eigenvalues of B with non-positive real parts and the
other eigenvalues are enclosed in a circle centered at C ? 0 with radius R ! C. In practice,
formula (26) may give only a crude upper bound on convergence, especially if the spectrum is not
evenly distributed but consists of a few clusters of eigenvalues, see [26]. However, it turns out that
for our problems, (26) is a good estimate.
Using Fourier analysis in the y-direction we can obtain the eigenvalues of the iteration matrix
A of the multiplicative (block Gauss-Seidel) algorithm. Some straightforward but
tedious calculations give the eigenvalues of E in closed, but difficult to analyze form, see [7,


Appendix

A]. For brevity we omit the details. The eigenvalues of the matrix
coincide with those of N
(apart from the multiple eigenvalue
leading
to an estimate of ae in formula (26).
To compare the S-S, N-S, R-S and N-D (only vertex-centered) algorithms, we compute the
theoretical convergence rates for different ranges of flow magnitudes and flow angles. The flow
magnitude is given by the dimensionless mesh-P'eclet number with jaj the magnitude
of velocity, the diffusion coefficient. The flow angle is given by ff,
so ae a
h pmax sin ff; (27)
with flow normal to the interface and flow tangential to the interface.
The average theoretical convergence rates 1 over (p
are listed in Tables 1 and 2. The cell-centered results from Table 1 show that
P'eclet range S-S N-S R-S

Table

1: Average theoretical convergence rates and corresponding number of iterations (in brack-
ets) for the multiplicative algorithm to solve with relative accuracy of 10 \Gamma4 , for different mesh
P'eclet ranges averaged over all flow angles. Cell-centered discretization.
for small flow magnitudes, the Neumann-Schwarz algorithm is approximately twice as fast as
the Schwarz-Schwarz and Robin-Schwarz algorithms. The advantages of the Neumann-Schwarz
algorithms are much smaller for larger flow magnitudes. The results indicate that Neumann-
Schwarz is the best choice for the Poisson equation. However, because of symmetry of that
equation, it is not certain at what sides of the interfaces, Neumann conditions must be imposed.
This problem becomes important for small flow magnitudes when p ij changes sign along the
interface.
P'eclet range S-S N-S R-S N-D

Table

2: Average theoretical convergence rates and corresponding number of iterations (in brack-
ets) for the multiplicative algorithm to solve with relative accuracy of 10 \Gamma4 , for different mesh
P'eclet ranges averaged over all flow angles. Vertex-centered discretization.
The vertex-centered results from Table 2 show much smaller differences between the different
methods as the cell-centered results from Table 1. With vertex-centered discretization, the differences
are also small for small flow magnitudes. The Neumann-Dirichlet method from [19] has
similar convergence as the Neumann-Schwarz method at low flow magnitudes. However, at larger
flow magnitudes, the Neumann-Dirichlet has a worse convergence rate.
The next section compares the above theoretical results with experiments.
5 Numerical experiments
This section presents some numerical experiments and compares the influence of interface conditions
(Schwarz-Schwarz, Neumann-Schwarz, Robin-Schwarz, Neumann-Dirichlet) on convergence
of Krylov subspace accelerated Schwarz domain decomposition.
1 The N-S algorithm was modified so that also for flow tangential to the interface, Neumann and Schwarz
conditions were used instead of the S-S algorithm
We use a relative stopping criterion
with r m the residual after m iterations defined by
The experimental convergence rate ae(m) is computed from
Some care must be taken interpreting convergence rates. Large differences in convergence
rates do not necessarily indicate large differences in the number of iterations. For instance, to reach
a relative accuracy of 10 \Gamma4 with ae = 0:1 we need 4 iterations while with ae = 0:2 we need only
iterations more. On the other hand, with ae close to 1, small differences are very important:
the difference between ae = 0:98 and ae = 0:99 is a factor of two in iteration count.
All experiments take the initial guess v We use the Sparse 2 solver for solving the sub-domain
problems. All results in this section are for the multiplicative method, which, in our
experience, converges about twice as fast as the additive method. Restarted GMRES(20) was
used for Krylov subspace acceleration of Schwarz domain decomposition.
5.1 Convergence as a function of flow magnitude and angle
Results are given for a
divided into two blocks by a vertical interface at
. A uniform mesh of 40 \Theta 40 cells
on\Omega is used. In the numerical results, a Dirichlet condition
is enforced on the left and lower boundaries
of\Omega and a Neumann condition
is enforced on the right and upper boundaries. The right-hand side is f = 1. All coefficients
in (1) are assumed to be constant with k As in Section 4, we compute
the (experimental) convergence rate as a function of flow magnitude pmax and angle ff. Similar
to Section 4, we have modified the Neumann-Schwarz method so that Neumann and Schwarz
conditions are always used for block 1 and 2 respectively, even for flow tangential to the interface.
This is different from the description of Neumann-Schwarz (15) but enables a comparison of the
effect of different coupling conditions on convergence.
To demonstrate the quality of the theoretical prediction of convergence rates, Figure 3 shows, as
an example, a comparison of experimental and theoretical convergence rates for the multiplicative
Neumann-Schwarz algorithm. The theoretical convergence rates agree well with the experimental
ones. Note that the convergence rate is zero along the curve pmax cos 2. This is not a property
of the domain decomposition algorithm but of the discretization. Since a central discretization is
used for the advective terms, the discretization reduces to a first order upwind discretization for
mesh P'eclet numbers equal to 2.
To compare the S-S, N-S, R-S and N-D methods again, we use the same averaging procedure
as described in Section 4. The average convergence rate is computed over some ranges of flow
magnitude and over all flow angles. Tables 3 and 4 show the results. The results are similar to
the theoretical results of Section 4. Also, the Neumann-Schwarz method performs best for low
flow magnitudes in comparison to the Schwarz-Schwarz and Neumann-Schwarz methods for both
cell-centered and vertex-centered. For larger flow magnitudes, the differences are almost negligible.
Note that the differences between the methods are even smaller than in the theoretical analysis.
This is because the weak periodic boundary conditions in the theoretical analysis were replaced by
angle
angle
R/C
experimental theoretical

Figure

3: Experimental and theoretical convergence factors for the GMRES accelerated Neumann-
Schwarz algorithm
P'eclet range S-S N-S R-S

Table

3: Average experimental convergence rates and corresponding number of iterations (in
brackets) to solve with relative accuracy of 10 \Gamma4 , for different mesh P'eclet ranges averaged over
all flow angles. Cell-centered discretization.
stronger boundary conditions in the experiments. Similar to the theoretical results of Section 4,
the Neumann-Dirichlet method of [19] (vertex-centered) shows almost identical convergence rate
as the Neumann-Schwarz method for low flow magnitudes and shows a slightly worse convergence
behavior for larger flow magnitudes.
5.2 Recirculating flow
As an example, we investigate a uniform flow problem, for which domain decomposition in general
converges slower than for simple uniform flow problems. The problem is defined by k
a 2 (x;
2 Sparse is a public domain direct solver available from netlib@ornl.gov
P'eclet range S-S N-S R-S N-D

Table

4: Average theoretical convergence rates and corresponding number of iterations (in brack-
ets) to solve with relative accuracy of 10 \Gamma4 , for different mesh P'eclet ranges averaged over all flow
angles. Vertex-centered discretization.
on (x; y)
controls the angle of flow across the interfaces. Two
decompositions of the domain are considered: the first in only two blocks with a vertical interface
at and the second into 2 \Theta 2 blocks with interfaces at uniform grid of
on\Omega is used combined with a cell-centered discretization.

Table

5 lists the results for the accelerated algorithm. Good convergence factors are obtained
and, the algorithm is quite insensitive to the direction of the flow on the interface and to the
type of coupling condition. The Robin-Schwarz method provides only a small improvement with
respect to Neumann-Schwarz, but this difference is so small that it does not always show up in
the iteration count.
blocks
blocks

Table

5: Experimental convergence rate ae(m) (iteration counts in brackets) for the recirculation
problem for increasing obliqueness, cell-centered discretization.
The differences in number of iterations (work) are very small for the three coupling strate-
gies. The relative differences in the number of iterations are even smaller when the number of
subdomains is increased from 2 to 4.
5.3 Further remarks on robustness
Further numerical experiments in [7] have shown that the GMRES accelerated algorithm is quite
insensitive to the coupling strategy used. The experiments in [7] also investigate the influence on
convergence rate of the types of external boundary conditions and of adding cross diffusion terms
k 12 . Furthermore, some experiments investigate the effect of variations in the ordering of blocks
and refinement within the subdomains. All these experiments show that the accelerated algorithm
is rather insensitive to these factors. In particular with respect to refinement this is promising for
applications to complicated flow problems.
6 Conclusions
We have investigated three domain decomposition methods, namely: the Schwarz-Schwarz, Neumann-
Schwarz and Robin-Schwarz algorithms. The algorithms were accelerated by a GMRES Krylov
subspace method. Assuming accurate solution of subdomain problems, the dimension of the vector
length in GMRES was reduced significantly by introducing the interface equations. This makes
the overhead of Krylov subspace acceleration negligible and enables the solution of large complex
CFD problems.
The GMRES Krylov subspace acceleration procedure can be implemented easily on top of
an already implemented unaccelerated domain decomposition algorithm, by repeatedly calling the
subroutine that performs a single Schwarz domain decomposition iteration with given initial guess.
This is of major importance for the implementation in complex CFD codes.
The theoretical and experimental convergence rates agree reasonably well. The experiments
show that for low flow magnitudes, the Neumann-Schwarz methods can provide a reduction in the
number of iterations of at most a factor 2. For large flow magnitudes, the differences between the
methods are less significant. The Robin-Schwarz and Schwarz-Schwarz methods are comparable in
convergence rates for both low and high flow magnitudes. The Neumann-Dirichlet method of [19],
has convergence rate similar to the Neumann-Schwarz method except for large flow magnitudes
for which it requires more iterations.
The differences in convergence rates found experimentally are typically less than the predicted
convergence rates. This effect is even stronger when non-uniform flow fields are used. For the
recirculating flow problem, the Robin-Schwarz (R-S) method has a slightly better convergence rate
than than the Neumann-Schwarz (N-S) and Schwarz-Schwarz (S-S) algorithms. The differences
in number of iterations (amount of work) between the S-S, N-S and R-S methods are very small:
in the number of iterations the difference is not significant at all. The differences between the
S-S, N-S, R-S methods are even less when the number of subdomains is increased from 2 to 4.
Further numerical experiments in [7] show these conclusions to be true for a larger number of test
problems: the method is reasonably robust with respect to coupling conditions, grid refinement,
velocity field and external boundary conditions.
Our experiments show that varying the type of interface conditions, depending of flow magnitude
and angle, in general gives only a moderate reduction in iteration count. In the experiments,
at most a reduction factor 2 was observed. Such limited reduction factors in general have a small
effect on total computing time. This is because, especially with complex CFD applications, solving
the system of equations may take only a small portion of the total computing time.
Possibly, a more detailed study of interface conditions will lead to more significant reductions
in iteration counts. In particular, this is interesting for limiting cases, such as low-speed (Stokes)
or high-speed (Euler) flows. For example, in [25, 24] good convergence for the unaccelerated
algorithm is obtained for such problems by optimizing interface conditions. Further research is
necessary to determine whether such a conclusion also holds for the accelerated algorithm.
A disadvantage of the methods described in [25, 24] is that convergence seems to depend
sensitively on the coupling parameters. Another problem is that these methods are in general
difficult to implement, especially in complex CFD codes. Besides that, one can imagine that
the complexity of such methods increases with the complexity of the CFD code: for instance,
extensions from two to three dimensions, adding new models and turbulence modeling. This
property makes the CFD software more difficult to maintain.
These are the reasons that we have omitted optimization of interface conditions and have chosen
to start with a simple Schwarz-Schwarz domain decomposition method for the incompressible
Navier-Stokes equations. We intend to study the parallel aspects of the present method and to
generalize the method to the full incompressible Navier-Stokes equations in general coordinates
on staggered grids, see [6, 5].

Acknowledgements

The authors would like to thank P. Wesseling for many valuable discussions on this work.



--R

Domain decomposition algorithms of Schwarz type

Iterative methods for the solution of elliptic problems on regions partitioned into substructures
To overlap or not to overlap: a note on a domain decomposition method for elliptic problems
A parallel domain decomposition algorithm for the incompressible Navier-Stokes equations
Schwarz domain decomposition for the incompress- sible Navier-Stokes equations in general coordinates
A domain decomposition method for the advection-diffusion equation
The construction of preconditioners for elliptic problems by substructuring I
A comparison of some domain decomposition and ILU preconditioned iterative methods for nonsymmetric elliptic problems
On the relationship between overlapping and nonoverlapping domain decomposition methods
Some recent results on Schwarz type domain decomposition algorithms
An iterative procedure with interface relaxation for domain decomposition methods
Experiences with domain decomposition in three di- mensions: Overlapping Schwarz methods
Iterative solution of large sparse systems of equations
Multigrid on composite meshes
Aerodynamics applications of Newton-Krylov-Schwarz solvers

Iterative solution of elliptic equations with refinement: The two-level case
A relaxation procedure for domain decomposition methods using finite elements
Benchmark solutions for the incompressible Navier-Stokes equations in general coordinates on staggered grids
GMRES: a generalized minimal residual algorithm for solving non-symmetric linear systems
A domain decomposition method for incompressible flow
Domain decomposition methods in computational mechanics
Local coupling in domain decomposition

The superlinear convergence behaviour of GMRES

Some Schwarz methods for symmetric and nonsymmetric elliptic problems
Schwarz and Schur: a note on finite-volume domain decomposition for advection-diffusion
A pressure-based composite grid method for the Navier-Stokes equations
--TR
GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems
The construction of preconditioners for elliptic problems by substructuring. I
Iterative methods for the solution of elliptic problems on regions partitioned into substructures
Multigrid on composite meshes
To overlap or not to overlap: a note on a domain decomposition method for elliptic problems
A relaxation procedure for domain decomposition methods using finite elements
Generalized Schwarz splittings
On the relationship between overlapping and nonoverlapping domain decomposition methods
A domain decomposition method for incompressible viscous flow
A pressure-based composite grid method for the Navier-Stokes equations
The superlinear convergence behaviour of GMRES
krylov subspace method;advection-diffusion equation;neumann-dirichlet method;schwarz alternating method;domain decomposition;krylov-schwarz algorithm