Additive Schwarz method

Last updated September 09, 2019

In mathematics, the additive Schwarz method, named after Hermann Schwarz, solves a boundary value problem for a partial differential equation approximately by splitting it into boundary value problems on smaller domains and adding the results.

Mathematics Field of study concerning quantity, patterns and change

Mathematics includes the study of such topics as quantity, structure (algebra), space (geometry), and change. It has no generally accepted definition.

Karl Hermann Amandus Schwarz was a German mathematician, known for his work in complex analysis.

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 the differential equation which also satisfies the boundary conditions.

Overview

Partial differential equations (PDEs) 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 (BVP). Even if the reader is unfamiliar with the notation, the purpose is merely to show what a BVP looks like when written down.

Science is a systematic enterprise that builds and organizes knowledge in the form of testable explanations and predictions about the universe.

(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, f_xx and f_yy denote the second partial derivatives with respect to x and y, respectively.

Here, the domain is the square [0,1] × [0,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 samplef at regular intervals in the square [0,1] × [0,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. 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 would be to calculate the value of f at those 64 points, which seems easier than finding an abstract function of the square.

In mathematics, a (real) interval is a set of real numbers with the property that any number that lies between two numbers in the set is also included in the set. For example, the set of all numbers $x$ satisfying $0 \leq x \leq 1$ is an interval which contains $0$ and $1$ , as well as all numbers between them. Other examples of intervals are the set of all real numbers $, the set of all negative real numbers, and the empty set.$

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 significant, and they are sometimes identified by their position in an ordered tuple and sometimes by a letter, as in "the x-coordinate". The coordinates are taken to be real numbers in elementary mathematics, but may be complex numbers or elements of a more abstract system such as a commutative ring. The use of a coordinate system allows problems in geometry to be translated into problems about numbers and vice versa; this is the basis of analytic geometry.

A computer program is a collection of instructions that performs a specific task when executed by a computer. Most computer devices require programs to function properly.

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 or finite differences. We ignore these difficulties and concentrate on another aspect of the problem.

The finite element method (FEM) is a numerical method for solving problems of engineering and mathematical physics. Typical problem areas of interest include structural analysis, heat transfer, fluid flow, mass transport, and electromagnetic potential. The analytical solution of these problems generally require the solution to boundary value problems for partial differential equations. The finite element method formulation of the problem results in a system of algebraic equations. The method approximates the unknown function over the domain. To solve the problem, it subdivides a large system into smaller, simpler parts that are called finite elements. The simple equations that model these finite elements are then assembled into a larger system of equations that models the entire problem. FEM then uses variational methods from the calculus of variations to approximate a solution by minimizing an associated error function.

A finite difference is a mathematical expression of the form $f (x + b) - f (x + a)$ . If a finite difference is divided by $b - a$ , one gets a difference quotient. The approximation of derivatives by finite differences plays a central role in finite difference methods for the numerical solution of differential equations, especially boundary value problems.

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:

2a + 5b = 12 (*)

6a − 3b = −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 [0,1] × [0,1] into two subdomains [0,0.5] × [0,1] and [0.5,1] × [0,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 [0,1] × [0,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: 2a = 12

System 2: -3b = −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] × R and H₂ = [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 and x₂ = 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 )}₀ and u^{( 2 )}₀ of the PDE in subdomains H₁ and H₂ 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.

Related Research Articles

Numerical analysis study of algorithms that use numerical approximation for the problems of mathematical analysis

Numerical analysis is the study of algorithms that use numerical approximation for the problems of mathematical analysis. Numerical analysis naturally finds application in all fields of engineering and the physical sciences, but in the 21st century also the life sciences, social sciences, medicine, business and even the arts have adopted elements of scientific computations. The growth in computing power has revolutionized the use of realistic mathematical models in science and engineering, and subtle numerical analysis is required to implement these detailed models of the world. For example, ordinary differential equations appear in celestial mechanics ; numerical linear algebra is important for data analysis; stochastic differential equations and Markov chains are essential in simulating living cells for medicine and biology.

Partial differential equation differential equation that contains unknown multivariable functions and their partial derivatives

In mathematics, a partial differential equation (PDE) is a differential equation that contains unknown multivariable functions and their partial derivatives. PDEs are used to formulate problems involving functions of several variables, and are either solved by hand, or used to create a computer model. A special case is ordinary differential equations (ODEs), which deal with functions of a single variable and their derivatives.

Spectral methods are a class of techniques used in applied mathematics and scientific computing to numerically solve certain differential equations, potentially involving the use of the fast Fourier transform. The idea is to write the solution of the differential equation as a sum of certain "basis functions" and then to choose the coefficients in the sum in order to satisfy the differential equation as well as possible.

Numerical methods for ordinary differential equations are methods used to find numerical approximations to the solutions of ordinary differential equations (ODEs). Their use is also known as "numerical integration", although this term is sometimes taken to mean the computation of integrals.

In mathematics, to solve an equation is to find its solutions, which are the values that fulfill the condition stated by the equation, consisting generally of two expressions related by an equality sign. When seeking a solution, one or more free variables are designated as unknowns. A solution is an assignment of expressions to the unknown variables that makes the equality in the equation true. In other words, a solution is an expression or a collection of expressions such that, when substituted for the unknowns, the equation becomes an identity. A solution of an equation is often also called a root of the equation, particularly but not only for algebraic or numerical equations.

Differential equation mathematical equation that contains derivatives of an unknown function

A differential equation is a mathematical equation that relates some function with its derivatives. In applications, the functions usually represent physical quantities, the derivatives represent their rates of change, and the differential equation defines a relationship between the two. Because such relations are extremely common, differential equations play a prominent role in many disciplines including engineering, physics, economics, and biology.

Numerical partial differential equations is the branch of numerical analysis that studies the numerical solution of partial differential equations (PDEs).

In numerical analysis, Stone's method, also known as the strongly implicit procedure or SIP, is an algorithm for solving a sparse linear system of equations. The method uses an incomplete LU decomposition, which approximates the exact LU decomposition, to get an iterative solution of the problem. The method is named after Herbert L. Stone, who proposed it in 1968.

Numerical linear algebra is the study of how matrix operations can be used to create computer algorithms which efficiently and accurately provide approximate answers to mathematical questions. It is a subfield of numerical analysis, and a type of linear algebra. Because computers use floating-point arithmetic, they cannot exactly represent irrational data, and many algorithms increase that imprecision when implemented by a computer. Numerical linear algebra uses properties of vectors and matrices to develop computer algorithms that minimize computer error while retaining efficiency and precision.

In mathematics, numerical analysis, and numerical partial differential equations, domain decomposition methods solve a boundary value problem by splitting it into smaller boundary value problems on subdomains and iterating to coordinate the solution between adjacent subdomains. A coarse problem with one or few unknowns per subdomain is used to further coordinate the solution between the subdomains globally. The problems on the subdomains are independent, which makes domain decomposition methods suitable for parallel computing. Domain decomposition methods are typically used as preconditioners for Krylov space iterative methods, such as the conjugate gradient method or GMRES.

In numerical analysis, the balancing domain decomposition method (BDD) is an iterative method to find the solution of a symmetric positive definite system of linear algebraic equations arising from the finite element method. In each iteration, it combines the solution of local problems on non-overlapping subdomains with a coarse problem created from the subdomain nullspaces. BDD requires only solution of subdomain problems rather than access to the matrices of those problems, so it is applicable to situations where only the solution operators are available, such as in oil reservoir simulation by mixed finite elements. In its original formulation, BDD performs well only for 2nd order problems, such elasticity in 2D and 3D. For 4th order problems, such as plate bending, it needs to be modified by adding to the coarse problem special basis functions that enforce continuity of the solution at subdomain corners, which makes it however more expensive. The BDDC method uses the same corner basis functions as, but in an additive rather than multiplicative fashion. The dual counterpart to BDD is FETI, which enforces the equality of the solution between the subdomain by Lagrange multipliers. The base versions of BDD and FETI are not mathematically equivalent, though a special version of FETI designed to be robust for hard problems has the same eigenvalues and thus essentially the same performance as BDD.

In mathematics, Neumann–Neumann methods are domain decomposition preconditioners named so because they solve a Neumann problem on each subdomain on both sides of the interface between the subdomains. Just like all domain decomposition methods, so that the number of iterations does not grow with the number of subdomains, Neumann–Neumann methods require the solution of a coarse problem to provide global communication. The balancing domain decomposition is a Neumann–Neumann method with a special kind of coarse problem.

In mathematics, the Neumann–Dirichlet method is a domain decomposition preconditioner which involves solving Neumann boundary value problem on one subdomain and Dirichlet boundary value problem on another, adjacent across the interface between the subdomains. On a problem with many subdomains organized in a rectangular mesh, the subdomains are assigned Neumann or Dirichlet problems in a checkerboard fashion.

In numerical analysis, mortar methods are discretization methods for partial differential equations, which use separate finite element discretization on nonoverlapping subdomains. The meshes on the subdomains do not match on the interface, and the equality of the solution is enforced by Lagrange multipliers, judiciously chosen to preserve the accuracy of the solution. Mortar discretizations lend themselves naturally to the solution by iterative domain decomposition methods such as FETI and balancing domain decomposition In the engineering practice in the finite element method, continuity of solutions between non-matching subdomains is implemented by multiple-point constraints.

In computer algebra, a triangular decomposition of a polynomial system $S$ is a set of simpler polynomial systems $S 1, ..., S e$ such that a point is a solution of $S$ if and only if it is a solution of one of the systems $S 1, ..., S e$ .

In mathematics, an ordinary differential equation (ODE) is a differential equation containing one or more functions of one independent variable and the derivatives of those functions. The term ordinary is used in contrast with the term partial differential equation which may be with respect to more than one independent variable.

Fluid motion is governed by the Navier–Stokes equations, a set of coupled and nonlinear partial differential equations derived from the basic laws of conservation of mass, momentum and energy. The unknowns are usually the flow velocity, the pressure and density and temperature. The analytical solution of this equation is impossible hence scientists resort to laboratory experiments in such situations. The answers delivered are, however, usually qualitatively different since dynamical and geometric similitude are difficult to enforce simultaneously between the lab experiment and the prototype. Furthermore, the design and construction of these experiments can be difficult, particularly for stratified rotating flows. Computational fluid dynamics (CFD) is an additional tool in the arsenal of scientists. In its early days CFD was often controversial, as it involved additional approximation to the governing equations and raised additional (legitimate) issues. Nowadays CFD is an established discipline alongside theoretical and experimental methods. This position is in large part due to the exponential growth of computer power which has allowed us to tackle ever larger and more complex problems.

In mathematics, the walk-on-spheres method (WoS) is a numerical probabilistic algorithm, or Monte-Carlo method, used mainly in order to approximate the solutions of some specific boundary value problem for partial differential equations (PDEs). The WoS method was first introduced by Mervin E. Muller in 1956 to solve Laplace's equation, and was since then generalized to other problems.

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

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.