Partial differential equations are used in all sciences to model phenomena. For the purpose of exposition, we give an example physical problem and the accompanying boundary value problem. Even if the reader is unfamiliar with the notation, the purpose is merely to show what a BVP looks like when written down. Here, the domain is the square × . This particular problem can be solved exactly on paper, so there is no need for a computer. However, this is an exceptional case, and most BVPs cannot be solved exactly. The only possibility is to use a computer to find an approximate solution.
Solving on a computer
A typical way of doing this is to samplef at regular intervals in the square × . For instance, we could take 8 samples in the x direction at x = 0.1, 0.2,..., 0.8 and 0.9, and 8 samples in the y direction at similar coordinates. We would then have 64 samples of the square, at places like and. The goal of the computer program would be to calculate the value of f at those 64 points, which seems easier than finding an abstract function of the square. There are some difficulties, for instance it is not possible to calculate fxx knowing f at only 64 points in the square. To overcome this, one uses some sort of numerical approximation of the derivatives, see for instance the finite element method or finite differences. We ignore these difficulties and concentrate on another aspect of the problem.
Solving linear problems
Whichever method we choose to solve this problem, we will need to solve a large linear system of equations. The reader may recall linear systems of equations from high school, they look like this: This is a system of 2 equations in 2 unknowns. If we solve the BVP above in the manner suggested, we will need to solve a system of 64 equations in 64 unknowns. This is not a hard problem for modern computers, but if we use a larger number of samples, even modern computers cannot solve the BVP very efficiently.
Which brings us to domain decomposition methods. If we split the domain × into two subdomains × and × , each has only half of the sample points. So we can try to solve a version of our model problem on each subdomain, but this time each subdomain has only 32 sample points. Finally, given the solutions on each subdomain, we can attempt to reconcile them to obtain a solution of the original problem on × .
Size of the problems
In terms of the linear systems, we're trying to split the system of 64 equations in 64 unknowns into two systems of 32 equations in 32 unknowns. This would be a clear gain, for the following reason. Looking back at system, we see that there are 6 important pieces of information. They are the coefficients of a and b, and the right hand side. On the other hand, if we take two "systems" of 1 equation in 1 unknown, it might look like this: We see that this system has only 4 important pieces of information. This means that a computer program will have an easier time solving two 1×1 systems than solving a single 2×2 system, because the pair of 1×1 systems are simpler than the single 2×2 system. While the 64×64 and 32×32 systems are too large to illustrate here, we could say by analogy that the 64×64 system has 4160 pieces of information, while the 32×32 systems each have 1056, or roughly a quarter of the 64×64 system.
Domain decomposition algorithm
Unfortunately, for technical reasons it is usually not possible to split our grid of 64 points into two grids of 32 points and obtain an answer to the 64×64 system. Instead, the following algorithm is what actually happens: There are two ways in which this can be better than solving the base 64×64 system. First, if the number of repetitions of the algorithm is small, solving two 32×32 systems may be more efficient than solving a 64×64 system. Second, the two 32×32 systems need not be solved on the same computer, so this algorithm can be run inparallel to use the power of multiple computers. In fact, solving two 32×32 systems instead of a 64×64 system on a single computer is unlikely to be efficient. However, if we use more than two subdomains, the picture can change. For instance, we could use four 16×16 problems, and there's a chance that solving these will be better than solving a single 64×64 problem even if the domain decomposition algorithm needs to iterate a few times.
A technical example
Here we assume that the reader is familiar with partial differential equations. We will be solving the partial differential equation We impose boundedness at infinity. We decompose the domain R² into two overlapping subdomains H1 = × R. In each subdomain, we will be solving a BVP of the form: where x1 = 1 and x2 = 0 and taking boundedness at infinity as the other boundary condition. We denote the solution u of the above problem by S. Note that S is bilinear. The Schwarz algorithm proceeds as follows:
Start with approximate solutions u0 and u0 of the PDE in subdomains H1 and H2 respectively. Initialize k to 1.
Calculate uk + 1 = Sk) with j = 1,2.
Increase k by one and repeat 2 until sufficient precision is achieved.
