Domain decomposition methods

<h2 id="example-1-1d-linear-bvp">Example 1: 1D Linear BVP</h2>
<p>
  
    
      
        
          
            {
            
              
                
                  
                    u
                    ″
                  
                  (
                  x
                  )
                  =
                  u
                  (
                  x
                  )
                  ,
                
              
              
                
                  u
                  (
                  0
                  )
                  =
                  0
                  ,
                
              
              
                
                  u
                  (
                  1
                  )
                  =
                  1.
                
              
            
            
          
        
      
    
    {\displaystyle {\begin{cases}u''(x)=u(x),\\u(0)=0,\\u(1)=1.\end{cases}}}

The exact solution is:

u
        (
        x
        )
        =
        
          
            
              
                e
                
                  x
                
              
              −
              
                e
                
                  −
                  x
                
              
            
            
              
                e
                
                  1
                
              
              −
              
                e
                
                  −
                  1
                
              
            
          
        
      
    
    {\displaystyle u(x)={\frac {e^{x}-e^{-x}}{e^{1}-e^{-1}}}}

Subdivide the domain into two subdomains, one from 
  
    
      
        
          [
          
            0
            ,
            
              
                
                  1
                  2
                
              
            
          
          ]
        
      
    
    {\displaystyle \left[0,{\tfrac {1}{2}}\right]}
  
 and another from 
  
    
      
        
          [
          
            
              
                
                  1
                  2
                
              
            
            ,
            1
          
          ]
        
      
    
    {\displaystyle \left[{\tfrac {1}{2}},1\right]}
  
. In the left subdomain define the interpolating function 
  
    
      
        
          v
          
            1
          
        
        (
        x
        )
      
    
    {\displaystyle v_{1}(x)}
  
 and in the right define 
  
    
      
        
          v
          
            2
          
        
        (
        x
        )
      
    
    {\displaystyle v_{2}(x)}
  
. At the interface between these two subdomains the following interface conditions shall be imposed:

v
                  
                    1
                  
                
                
                  
                    (
                    
                      
                        1
                        2
                      
                    
                    )
                  
                
              
              
                
                =
                
                  v
                  
                    2
                  
                
                
                  
                    (
                    
                      
                        1
                        2
                      
                    
                    )
                  
                
              
            
            
              
                
                  v
                  
                    1
                  
                  ′
                
                
                  
                    (
                    
                      
                        1
                        2
                      
                    
                    )
                  
                
              
              
                
                =
                
                  v
                  
                    2
                  
                  ′
                
                
                  
                    (
                    
                      
                        1
                        2
                      
                    
                    )
                  
                
              
            
          
        
      
    
    {\displaystyle {\begin{aligned}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{aligned}}}

Let the interpolating functions be defined as:

v
                  
                    1
                  
                
                (
                x
                )
              
              
                
                =
                
                  ∑
                  
                    n
                    =
                    0
                  
                  
                    N
                  
                
                
                  u
                  
                    n
                  
                
                
                  T
                  
                    n
                  
                
                (
                
                  y
                  
                    1
                  
                
                (
                x
                )
                )
              
            
            
              
                
                  v
                  
                    2
                  
                
                (
                x
                )
              
              
                
                =
                
                  ∑
                  
                    n
                    =
                    0
                  
                  
                    N
                  
                
                
                  u
                  
                    n
                    +
                    N
                  
                
                
                  T
                  
                    n
                  
                
                (
                
                  y
                  
                    2
                  
                
                (
                x
                )
                )
              
            
            
              
                
                  y
                  
                    1
                  
                
                (
                x
                )
              
              
                
                =
                4
                x
                −
                1
              
            
            
              
                
                  y
                  
                    2
                  
                
                (
                x
                )
              
              
                
                =
                4
                x
                −
                3
              
            
          
        
      
    
    {\displaystyle {\begin{aligned}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{aligned}}}

Where 
  
    
      
        
          T
          
            n
          
        
        (
        y
        )
      
    
    {\displaystyle T_{n}(y)}
  
 is the nth cardinal function of the Chebyshev polynomials of the first kind with input argument y.
</p><p>If <i>N</i>=4 then the following approximation is obtained by this scheme:

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.
              
            
          
        
      
    
    {\displaystyle {\begin{aligned}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{aligned}}}

This was obtained with the following MATLAB code.
</p>
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));

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Multigrid_method/6FTEwkja">Multigrid method</a></li></ul>
<h2 id="related-books">Related Books</h2>

<ul><li>Barry Smith, Petter Bjørstad, and William Gropp: <i>Domain Decomposition: Parallel Multilevel Methods for Elliptic Partial Differential Equations</i>, Cambridge Univ. Press, ISBN 0-521-49589-X (1996).</li></ul>

<h2 id="external-links">External links</h2>
<ul><li><a href="http://www.ddm.org">The official Domain Decomposition Methods page</a></li>
<li><a href="https://web.archive.org/web/20210126091945/http://www.domain-decomposition.com/">"Domain Decomposition - Numerical Simulations page"</a>. Archived from <a href="http://www.domain-decomposition.com/">the original</a> on 2021-01-26.</li></ul>

Domain decomposition methods open-in-new

Domain decomposition methods