Diffusion Model with Schwarz Method in Information Potential Field

One active application of the wireless sensor networks is the mobile vehicle navigation. In this study, we propose a new potential field method based upon diffusion equation and gradient descent algorithm to achieve more flexibility and adaptability in searching the best path. Based on the mathematical model obtained, Schwarz methods are introduced. We give a short survey of Schwarz method for partial differential equations, including the motivation, its evolution process such as continuous and discrete versions and recent achievements.

INTRODUCTION

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.

Fig. 1:	The definition domain with corners (Appended in page)

Fig. 2:	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 subproblems, respectively.

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:

where, 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.

Fig. 3:	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 don’t 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 don’t 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:

And

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:

Au = f

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 R_j 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).

CONCLUSION

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.