In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, the additive Schwarz method, named after
Hermann Schwarz
Karl Hermann Amandus Schwarz (; 25 January 1843 – 30 November 1921) was a German mathematician, known for his work in complex analysis.
Life
Schwarz was born in Hermsdorf, Silesia (now Jerzmanowa, Poland). In 1868 he married Marie Kummer, ...
, solves a
boundary value problem
In mathematics, in the field of differential equations, a boundary value problem is a differential equation together with a set of additional constraints, called the boundary conditions. A solution to a boundary value problem is a solution to t ...
for a
partial differential equation
In mathematics, a partial differential equation (PDE) is an equation which imposes relations between the various partial derivatives of a Multivariable calculus, multivariable function.
The function is often thought of as an "unknown" to be sol ...
approximately by splitting it into boundary value problems on smaller domains and adding the results.
Overview
Partial differential equations (PDEs) are used in all
science
Science is a systematic endeavor that builds and organizes knowledge in the form of testable explanations and predictions about the universe.
Science may be as old as the human species, and some of the earliest archeological evidence for ...
s to
model
A model is an informative representation of an object, person or system. The term originally denoted the plans of a building in late 16th-century English, and derived via French and Italian ultimately from Latin ''modulus'', a measure.
Models c ...
phenomena. For the purpose of exposition, we give an example physical problem and the accompanying boundary value problem (BVP). Even if the reader is unfamiliar with the notation, the purpose is merely to show what a BVP looks like when written down.
:(Model problem) The heat distribution in a square metal plate such that the left edge is kept at 1 degree, and the other edges are kept at 0 degree, after letting it sit for a long period of time satisfies the following boundary value problem:
::''f''
''xx''(''x'',''y'') + ''f''
''yy''(''x'',''y'') = 0
::''f''(0,''y'') = 1; ''f''(''x'',0) = ''f''(''x'',1) = ''f''(1,''y'') = 0
:where ''f'' is the unknown
function
Function or functionality may refer to:
Computing
* Function key, a type of key on computer keyboards
* Function model, a structured representation of processes in a system
* Function object or functor or functionoid, a concept of object-oriente ...
, ''f''
''xx'' and ''f''
''yy'' denote the second
partial derivative
In mathematics, a partial derivative of a function of several variables is its derivative with respect to one of those variables, with the others held constant (as opposed to the total derivative, in which all variables are allowed to vary). Part ...
s with respect to ''x'' and ''y'', respectively.
Here, the
domain
Domain may refer to:
Mathematics
*Domain of a function, the set of input values for which the (total) function is defined
**Domain of definition of a partial function
**Natural domain of a partial function
**Domain of holomorphy of a function
* Do ...
is the square
,1×
,1
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 ''sample'' ''f'' at regular
intervals
Interval may refer to:
Mathematics and physics
* Interval (mathematics), a range of numbers
** Partially ordered set#Intervals, its generalization from numbers to arbitrary partially ordered sets
* A statistical level of measurement
* Interval e ...
in the
square
In Euclidean geometry, a square is a regular quadrilateral, which means that it has four equal sides and four equal angles (90-degree angles, π/2 radian angles, or right angles). It can also be defined as a rectangle with two equal-length adj ...
,1×
,1 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
In geometry, a coordinate system is a system that uses one or more numbers, or coordinates, to uniquely determine the position of the points or other geometric elements on a manifold such as Euclidean space. The order of the coordinates is sig ...
. We would then have 64 samples of the square, at places like (0.2,0.8) and (0.6,0.6). The goal of the
computer program
A computer program is a sequence or set of instructions in a programming language for a computer to execute. Computer programs are one component of software, which also includes documentation and other intangible components.
A 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 ''f''
''xx''(0.5,0.5) 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
The finite element method (FEM) is a popular method for numerically solving differential equations arising in engineering and mathematical modeling. Typical problem areas of interest include the traditional fields of structural analysis, heat ...
or
finite difference
A finite difference is a mathematical expression of the form . If a finite difference is divided by , one gets a difference quotient. The approximation of derivatives by finite differences plays a central role in finite difference methods for t ...
s. 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
In mathematics, a system of linear equations (or linear system) is a collection of one or more linear equations involving the same variables.
For example,
:\begin
3x+2y-z=1\\
2x-2y+4z=-2\\
-x+\fracy-z=0
\end
is a system of three equations in ...
. The reader may recall linear systems of equations from high school, they look like this:
:2''a'' + 5''b'' = 12 (*)
:6''a'' − 3''b'' = −3
This is a system of 2 equations in 2 unknowns (''a'' and ''b''). 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.
Domain decomposition
Which brings us to domain decomposition methods. If we split the domain
,1×
,1into two ''subdomains''
,0.5×
,1and
.5,1×
,1 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
,1×
,1
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'' (2,5 on the first line and 6,−3 on the second line), and the right hand side (which we write as 12,−3). On the other hand, if we take two "systems" of 1 equation in 1 unknown, it might look like this:
:System 1: 2''a'' = 12
:System 2: -3''b'' = −3
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 (a 64×64 system of linear equations) into two grids of 32 points (two 32×32 systems of linear equations) and obtain an answer to the 64×64 system. Instead, the following algorithm is what actually happens:
:1) Begin with an approximate solution of the 64×64 system.
:2) From the 64×64 system, create two 32×32 systems to improve the approximate solution.
:3) Solve the two 32×32 systems.
:4) Put the two 32×32 solutions "together" to improve the approximate solution to the 64×64 system.
:5) If the solution isn't very good yet, repeat from 2.
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 in ''parallel'' to use the power of multiple computers.
In fact, solving two 32×32 systems instead of a 64×64 system on a single computer (without using parallelism) 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
:''u''
''xx'' + ''u''
''yy'' = ''f'' (**)
We impose boundedness at infinity.
We decompose the domain R² into two overlapping subdomains H
1 = (
− ∞,1] × R and H
2 =
[0,+ ∞) × R. In each subdomain, we will be solving a BVP of the form:
:''u''
( ''j'' )''xx'' + ''u''
( ''j'' )''yy'' = ''f'' in H
''j''
:''u''
( ''j'' )(''x''
''j'',''y'') = ''g''(''y'')
where ''x''
1 = 1 and ''x''
2 = 0 and taking boundedness at infinity as the other boundary condition. We denote the solution ''u''
( ''j'' ) of the above problem by S(''f'',''g''). Note that S is bilinear.
The Schwarz algorithm proceeds as follows:
#Start with approximate solutions ''u''
( 1 )0 and ''u''
( 2 )0 of the PDE in subdomains H
1 and H
2 respectively. Initialize ''k'' to 1.
#Calculate ''u''
( ''j'' )''k'' + 1 = S(''f'',''u''
(3 − ''j'')''k''(''x''
''j'')) with ''j'' = 1,2.
#Increase ''k'' by one and repeat 2 until sufficient precision is achieved.
See also
*Domain decomposition method
*Schwarz alternating method
References
* Barry Smith, Petter Bjørstad, William Gropp, Domain Decomposition, Parallel Multilevel Methods for Elliptic Partial Differential Equations, Cambridge University Press 1996
* Andrea Toselli and Olof Widlund, Domain Decomposition Methods - Algorithms and Theory, Springer Series in Computational Mathematics, Vol. 34, 2004
External links
The official Domain Decomposition Methods page
{{Numerical PDE
Domain decomposition methods