Content deleted Content added
coarse problem |
No edit summary |
||
| (38 intermediate revisions by 20 users not shown) | |||
Line 1:
[[File:Ddm original logo.png|thumb|Domain decomposition methods]]
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 [[preconditioner]]s for [[Krylov space]] [[iterative method]]s, such as the [[conjugate gradient method]] or [[GMRES]].▼
▲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 [[preconditioner]]s for [[Krylov space]] [[iterative method]]s, such as the [[conjugate gradient method]]
In overlapping ___domain decomposition methods, the subdomains overlap by more than the interface. Overlapping ___domain decomposition methods include the [[Schwarz alternating method]] and the [[additive Schwarz method]]. Many ___domain decomposition methods can be written and analyzed as a special case of the [[abstract additive Schwarz method]].
Line 8 ⟶ 10:
[[Mortar method]]s are discretization methods for partial differential equations, which use separate 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. In the engineering practice in the finite element method, continuity of solutions between non-matching subdomains is implemented by [[multiple-point constraint]]s.
Finite element simulations of moderate size models require solving linear systems with millions of unknowns. Several hours per time step is an average sequential run time, therefore, parallel computing is a necessity. Domain decomposition methods embody large potential for a parallelization of the finite element methods, and serve a basis for distributed, parallel computations.
==Example 1: 1D Linear BVP==
<math display="block">\begin{cases}
u''(x) = u(x), \\
u(0) = 0, \\
u(1) = 1.
\end{cases} </math>
The exact solution is:
<math display="block"> u(x)=\frac{e^x-e^{-x}}{e^{1}-e^{-1}} </math>
Subdivide the ___domain into two subdomains, one from <math>\left[0,\tfrac{1}{2}\right]</math> and another from <math>\left[\tfrac{1}{2},1\right]</math>. In the left subdomain define the interpolating function <math> v_1(x) </math> and in the right define <math> v_2 (x) </math>. At the interface between these two subdomains the following interface conditions shall be imposed:
<math display="block">\begin{align}
v_1{\left(\frac{1}{2}\right)} &= v_2{\left(\frac{1}{2}\right)} \\
v_1'{\left(\frac{1}{2}\right)} &= v_2'{\left(\frac{1}{2}\right)}
\end{align}</math>
Let the interpolating functions be defined as:<br>
<math display="block">\begin{align}
v_1(x) &= \sum_{n=0}^{N} u_{n} T_n (y_1(x)) \\
v_2(x) &= \sum_{n=0}^{N} u_{n+N} T_n (y_2(x)) \\
y_1(x) &= 4x-1 \\
y_2(x) &= 4x-3
\end{align} </math>
Where <math> T_n (y) </math> is the nth cardinal function of the Chebyshev polynomials of the first kind with input argument y.
If ''N''=4 then the following approximation is obtained by this scheme:
<math display="block">\begin{align}
u_1 &= 0.06236, &
u_2 &= 0.21495, \\
u_3 &= 0.37428, &
u_4 &= 0.44341, \\
u_5 &= 0.51492, &
u_6 &= 0.69972, \\
u_7 &= 0.90645.
\end{align}</math>
This was obtained with the following MATLAB code.
<syntaxhighlight lang="matlab">
clear all
N = 4;
a1 = 0; b1 = 1/2;
[T D1 D2 E1 E2 x xsub] = cheb(N,a1,b1); % the diff matrices on [0,1/2] are the same
%as those on [1/2 1].
I = eye(N+1);
H = D2-I;
H1 = [[1 zeros(1,N)]; H(2:end-1,:); [zeros(1,N) 1]];
H1 = [H1 [zeros(N,N+1); -[1 zeros(1,N)]]];
H2 = [D1(1,:); H(2:end-1,:); [zeros(1,N) 1]];
H2 = [[-D1(N+1,:); zeros(N,N+1)] H2];
K = [H1; H2];
F = [zeros(2*N+1,1); 1];
u = K\F;
xx = -cos(pi*(0:N)'/N);
x1 = 1/4*(xx+1); x2 = 1/4*(xx+3);
x = [x1; x2];
uex = (exp(x)-exp(-x))./(exp(1)-exp(-1));
</syntaxhighlight>
==See also==
* [[Multigrid method]]
== Related Books ==
{{Template:Numerical PDE}}▼
{{refbegin}}
* Barry Smith, Petter Bjørstad, and William Gropp: ''Domain Decomposition: Parallel Multilevel Methods for Elliptic Partial Differential Equations'', Cambridge Univ. Press, ISBN 0-521-49589-X (1996).
{{refend}}
== External links ==
* [http://www.ddm.org The official Domain Decomposition Methods page]
* {{cite web
| title = Domain Decomposition - Numerical Simulations page
| url = http://www.___domain-decomposition.com/
| url-status = dead
<!-- COMMENT: Note: as of April 2023, if one tries to use -- or "click on" -- [a link to] the URL shown in the value of the "url" field here then it does not work; also, if one tries to "click on" a link to even one of the "archive dot org" copies of old versions of that web page, then ... a web page might well come up, but -- at least for the most recent few instances -- e.g., those for 2022 -- what comes up seems to be some bogus or "parked" web page, that does NOT seem to have *** anything to do with *** "Domain Decomposition Methods", in the sense of the usual meaning of the title of this Wikipedia article.
*** HENCE, *** the value of "dead" [was chosen] for this ("url-status") field of this "cite web" template instance. -->
| archive-url = https://web.archive.org/web/20210126091945/http://www.___domain-decomposition.com/
| archive-date = 2021-01-26
}}
[[Category:Domain decomposition methods| ]]
[[Category:Articles with example MATLAB/Octave code]]
| |||