Schwarz methods can be used broadly in wireless sensor network especially the
vehicle navigation (Heinzelman et al., 2000; Intanagonwiwat
et al., 2000). Among the recent research progresses, the information
sensor field was constructed following diffusion law (Gao
et al., 2007: Lin et al., 2008). The
approximate solution is not a smooth surface (Verma et
al., 2005). In order to get it as much as possible, a new time dependent
model is introduced which can be solved by Schwarz methods. Compared with other
efficient numerical algorithms such as the full-discretization method, the Schwarz
method has its own characters. Firstly, it is very flexible for many special
model problems. For example, if the model is defined on a domain with corners
such as the one demonstrated in Fig. 1, common numerical algorithms
could not solve it very efficiently. For the finite difference method, the gradient
in the corners can not be approximated easily. The Schwarz methods could solve
this problem by decomposing the domain to different parts. Each part is very
easy to solve.
Second, even the domain is very smooth and common methods could be used to
construct a common mesh, if the coefficients have some jumps, Schwarz method
can be used to simulate better. For example, in the multiphase flow field, the
oil and water have significantly different viscosity number, which means the
coefficients of the mathematical model have a great jump on boundaries between
oil and water, like the Fig. 2. In this case, if the ordinary
numerical methods such as finite difference or finite element methods are used,
this jump could cause great difficulties because of the ill-condition coefficient
matrix after the discretization.
||The definition domain with corners (Appended in page)
||The sketched demonstration of different levels in multiphase
flow (Appended in page)
To overcome the phenomena, this problem can be solved by Schwarz method. For
example, we can decompose the domain according to the natural boundary and solve
CONSTRUCTING OF INFORMATION FIELD
In practical scenario, the information potential field is desired to not only
describe the local level but also approaches the original distribution (Ye
et al., 2005). To improve the smoothness of the information surface
and the distance to the initial surface, we introduce the following energy functional:
where, α , β and γ are weighted coefficients. The first integral requires that v approach the target function u as close as possible, the second and the third ones indicate the kinetic and potential energy, respectively. To get the best surface v which means this surface is smooth enough and the distance to u small enough, the following optimal problem can be constructed:
is the Sobolev space on Ω. Computing the corresponding Euler-Lagrange equation
relative with the energy functional for the minimal surface, we can find the
time-dependent evolution equation as following:
Consequently, we need for the information potential field evolution equation, to use a fast algorithm, which is the Schwarz method we will introduce in the next section.
THE EVOLUTION PROCESS OF SCHWARZ METHOD
Alternating direction method: The motivation of Schwarz method which is adopted as a iteration scheme to solve partial differential equation problems. The name of the original version is alternative direction method because there are frequently alternated computational subdomains between successive iterations in the whole process. The method is a sequential one. Only after the former subproblem is solved, the next one could be solved since the information needed is enough. In order to describe the method more specifically, we show the following domain in Fig. 3.
Here Γj stand for the artificial boundaries and some restrictions
are proposed on them. They are called the transmission condition.
||The two subdomain decomposition with artificial boundaries
(Appended in Page)
There are several kinds of transmission condition which are Dirichlet, Neumann,
Robin and the recent optimized condition, which we will give a short introduction
later. Here we just focus on the simplest model, which is the Laplace equation.
The whole process for other model problems including time dependent problem
is similar to this one. Its specific formula is as follows:
In this case, we just consider the situation of two subdomains. Actually, it
can be easily extended to more subdomians. In the left part of this paper, without
special speaking, the two subdomain situation is considered. H.A. Schwarz proved
the convergence of this method using the maximum principle. However, it strongly
depended on the model equation to be solved. For general proof for time dependent
partial differential equations, (Lions, 1988).
PARALLEL SCHWARZ METHOD
From the above formula (1), we can conclude that the iteration process is serial.
When the parallel computer becomes more and more popular, many mathematicians
found out the potential of alternating direction method to be extended to parallel
versions. The first person to research on it is Lions (1988)
who proposed the parallel Schwarz method by giving a small but essential improvement
of the iteration scheme. He changed the iteration index of the second transmission
condition. The specific formula is the following:
Instead of waiting for the information from neighborhood subdomains, the boundary values of each subproblem needed are enough because they are known from the old iteration. This change promises the iteration can be executed independently in different cpus. Of course the alternation direction method could also be parallel. That needs the coloring technique, which means we can use the same color to stand for the subdomains nonoverlapped with each other. Because different subdomains with same colors dont communicate, they can be parallel computed in different cpus. Even though, its potential can not be compared with the parallel Schwarz methods. The proof of the paralleled Schwarz can also be obtained by the maximum principle and here we dont supply it because of the limit of pages.
OPTIMIZED SCHWARZ METHOD
We present the recent research progress of Schwarz method. It is based on the considerations about the transmission conditions. For the most part of the work about the Schwarz method, the Dirichlet transmission condition and the Robin transmission condition are mainly used. However, they are not the best ones. Actually, the domain of partial differential equations is not made up by different isolated subdomains and very sensitive about the boundary conditions. Especially, the parabolic problems have the infinite propagation speed. Therefore, if we introduce an artificial boundary condition, it is better to be a global one than the local conditions. With the pseudo-differential operator theory, researchers proposed that the constant coefficients in the Robin condition could not be competitive with a global operator. So the common transmission condition was extended by introducing a pseudo-differential operator. The second motivation of this change is that the convergence of classical Schwarz method is satisfied only when there are overlaps when Dirichlet conditions are used. This phenomenon is because there are no information updates on the artificial boundaries. Therefore, the new Schwarz method has the following formula:
With careful computation and proof, it was found that the best global operator
would be the Steklov-Poincare operator. It can produce the convergence with
least iterations. However, this operator costs too many resources in the real
computation process because it is a global one. Therefore, if the optimal results
can not be got, we can approximate it and get an optimized one. For example,
the operator can be approximated by a polynomial with one or two degrees. This
idea produces several versions of optimized Schwarz method with calculated coefficients.
As for the exact coefficients of the polynomial, see the reference (Gander
and Zhao, 2002).
MULTIPLICATIVE SCHWARZ AND ADDITIVE SCHWARZ
In this part, we will present the discrete versions of the Schwarz method which
are additive Schwarz and multiplicative Schwarz method. After the design of
the continuous theoretical situation, the actual implementations are also needed
to consider. With the discretization from the finite difference or finite element
methods, we can get a large sparse linear system like:
If we permutated the elements according to their positions in the physical domain, we can split the linear system into two part, if we just consider two subdomains. Therefore, similar to the continuous version, we can also construct the algebraic iterations. Before showing their formula, there are two conceptions called restriction matrices to explain. Their functions are to restrict the long vectors into shorter ones, like the projection operators. We use the symbol Rj to stand for them:
With these operators, we can define the following matrices:
They are actually the sub-blocks of the linear coefficient matrix and also the discrete versions of the continuous subproblems. We first present the following scheme:
This formula is called the multiplicative Schwarz. Actually, when the two matrices
satisfy the relationship ,
which means they are nonoverlapped, we can prove the multiplicative Schwarz
method is just Gauss-Seidel method broadly used in the linear algebra field.
In nature, the multiplicative Schwarz is also a sequential method. In order
to compute parallel, the method needs some change. In the following, we will
introduce the other versions of Schwarz method, which is the additive Schwarz
method. Its formula is as follows:
Here the two operators are the same as the ones introduced before. Similar with the multiplicative one, when they are nonoverlapped, the method is equivalent with the Jacobi method. However, if they are overlapped, by analyzing the spectrum of the iteration operator, we could found that the number-1 belongs to their eigenvalue. Therefore, that means the method is not convergent. The most usage of additive Schwarz method is to construct the preconditioner for linear algebra system. And the resulted matrix has a small conditioner relative with the grid mesh only.
RESTRICTED SCHWARZ METHOD
Because of the disadvantage of the divergence when there are overlaps, the restricted additive Schwarz method was proposed. Its formula is as follows:
Here, another two matrices ,
are introduced. Instead of using the same matrix in the both sides, the left
one was changed to the projection matrix from the whole vector space to the
subdomains subtracted the overlapped part. And they satisfy the relationship
The restricted Schwarz method has better convergence properties. This method
has been used broadly in the engineering fields. With a strict proof, the restricted
Schwarz method is equivalent with the continuous parallel Schwarz method, see
reference (Gander, 2006).
In this study, the information diffusion model is considered to solve the navigation
problems (Batalin et al., 2003; Yu
et al., 2001). For satisfying the users requirements, a potential
field of sensor network is constructed on the whole area by a diffusion equation
and then a variational formula is applied to smooth the field. The information
level of each node can be updated when the user is moving. Simultaneously, we
also reviewed the Schwarz method for solving the resulted time dependent partial
differential equations including the motivation and evolution process.