Domain decomposition methods: Difference between revisions

Revision as of 04:09, 27 December 2012

Latest revision as of 14:45, 13 June 2025

(20 intermediate revisions by 16 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]], and [[LOBPCG]].

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 14:

==Example 1: 1D Linear BVP==

<math display="block">\begin{cases}

<math> u''(x)-u(x)=0 </math><br>

<math> u''(0x) =0, u(1x)=1, </math><br>\\

u(0) = 0, \\

The exact solution is:<br>

u(1) = 1.

<math> u(x)=\frac{e^x-e^{-x}}{e^{1}-e^{-1}} </math><br>

\end{cases} </math>

Subdivide the ___domain into two subdomains, one from <math>[0,\frac{1}{2}]</math> and another from <math>[\frac{1}{2},1]</math>. In each of these two subdomains define interpolating functions <math> v_1(x) </math> and <math> v_2 (x) </math> At the interface between these two subdomains the following inferface conditions shall be imposed:<br>

The exact solution is:<br>

<math> v_1\left(\frac{1}{2}\right)=v_2 \left(\frac{1}{2}\right) </math><br>

<math display="block"> v_1'\leftu(x)=\frac{1e^x-e^{-x}{2}\right)=v_2'\left(\frac{e^{1}-e^{2-1}\right)} </math><br>

Subdivide the ___domain into two subdomains, one from <math>\left[0,\fractfrac{1}{2}\right]</math> and another from <math>\left[\fractfrac{1}{2},1\right]</math>. In eachthe ofleft thesesubdomain twodefine subdomains definethe interpolating functionsfunction <math> v_1(x) </math> and in the right define <math> v_2 (x) </math>. At the interface between these two subdomains the following inferfaceinterface conditions shall be imposed:<br>

<math display="block">\begin{align}

<math> v_1{\left(\frac{1}{2}\right)} &=v_2 v_2{\left(\frac{1}{2}\right)} </math><br>\\

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}

<math> v_1 (x) =\sum_{n=0}^{N} u_{n} C_n (y_1(x)) </math><br>

<math> v_2 v_1(x) &= \sum_{n=0}^{N} u_{n+N} C_nT_n (y_2y_1(x)) </math><br>\\

<math> v_1 v_2(x) &= \sum_{n=0}^{N} u_{n+N} C_nT_n (y_1y_2(x)) </math><br>\\

<math> y_1(x)=4x-1 </math><br>

<math> y_2 y_1(x) &= 4x-31 </math><br>\\

y_2(x) &= 4x-3

Where <math> T_n (y) </math> is the nth cardinal function of the chebyshev polynomials of the first kind with input argument y.<br>

\end{align} </math>

If N=4 then the following approximation is obtained by this scheme:<br>

Where <math> T_n (y) </math> is the nth cardinal function of the chebyshevChebyshev polynomials of the first kind with input argument y.<br>

<math> u_1 =0.06236 </math><br>

<math> u_2 =0.21495 </math><br>

If ''N''=4 then the following approximation is obtained by this scheme:<br>

<math> u_3 =0.37428 </math><br>

<math display="block">\begin{align}

<math> u_4 =0.44341 </math><br>

u_1 &= 0.06236, &

<math> u_5 =0.51492 </math><br>

u_2 &= 0.21495, \\

<math> u_6 =0.69972 </math><br>

u_3 &= 0.37428, &

<math> u_7 =0.90645 </math><br>

u_4 &= 0.44341, \\

This was obtained with the following MATLAB code. <br>

u_5 &= 0.51492, &

<source lang="matlab">

u_6 &= 0.69972, \\

u_7 &= 0.90645.

\end{align}</math>

This was obtained with the following MATLAB code. <br>

<sourcesyntaxhighlight 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>

</source>

==See also==

* [[Multigrid method]]

== Related Books ==

{{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

*| [http://www.___domain-decomposition.comtitle = 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

}}

{{Numerical PDE}}

{{DEFAULTSORT:Domain Decomposition Methods}}

[[Category:Domain decomposition methods| ]]

[[Category:Articles with example MATLAB/Octave code]]