\documentstyle[a4]{artmy}
\textwidth 5in
\textheight 7in
\parindent 2em
\newcommand{\Lh}{\Lambda}
\newcommand{\eps}{\varepsilon}
\newcommand{\sm}{\setminus}
\newcommand{\wt}{\widetilde}
\newcommand{\wh}{\widehat}
\newcommand{\vf}{\varphi}
\newcommand{\ovl}{\overline}
\newcommand{\re}{\vspace{-0.25cm}}
\newcommand{\bc}{\begin{center}}
\newcommand{\ec}{\end{center}}
\newcommand{\be}{\begin{equation}}
\newcommand{\ee}{\end{equation}}
\newtheorem{theoRM}{Theorem}
\newtheorem{lemma}{Lemma}
\newenvironment{Theorem}{\begin{theoRM} \rm }{\end{theoRM}}
\newenvironment{Lemma}{\begin{lemma} \rm }{\end{lemma}}
\def\thetheoRM{\arabic{theoRM}.}
\def\thelemma{\arabic{lemma}.}
\pagestyle{empty}
\begin{document}
\sloppy
\normalsize
\baselineskip 13pt
\bc {\bf
PARALLEL DOMAIN DECOMPOSITION METHODS WITH THE
OVERLAPPING OF SUBDOMAINS FOR PARABOLIC PROBLEMS}
\ec
\small
\baselineskip 13pt
\bc
GRIGORII \ I.\,SHISHKIN \\
{\it Institute of Mathematics and Mechanics, Ural Branch of the Russian}\\
{\it Academy of Sciences, Ekaterinburg \ 620219, Russia}
\ec
\bc
PETER \ N.\,VABISHCHEVICH\\
{\it Institute for Mathematical Modelling, Russian Academy of Sciences},\\
{\it Moscow \ 125047, Russia}
\ec
\vspace{0.8in}
\begin{quotation}
\baselineskip 11pt
For a model two-dimensional boundary value problem for a second-order
parabolic equation finite difference schemes on the base of a
domain decomposition method, oriented on modern parallel computers, are
constructed. In the used finite difference schemes iterations at time
levels are not applied; some subdomains overlap. We study two classes of
schemes characterized by synchronous and asynchronous implementations.
It is shown that, under refining grids, the approximate solutions do
converge to the exact one in the uniform grid norm.
\end{quotation}
\normalsize
\baselineskip 13pt
\newsection{Introduction}
Methods based on decomposition of a domain onto separate subdomains are
considered as more progressive to develop computational algorithms for
parallel computers. Two basic classes of methods, with the overlapping of
subdomains and without it, with stating the corresponding
exchange (interface) conditions on the boundary of subdomains were studied
previously.$^{1-4}$
A traditional approach to the construction of schemes with domain decomposition
for nonstationary problems of mathematical physics is based on the use of
classical implicit schemes with converting grid elliptic operators by
domain decomposition methods.$^{4,\,5}$ \ The specific character of
nonstationary problems is reflected by iteration-free algorithms of
decomposition more completely. Such regional-additive finite difference schemes in different
variants were considered.$^{6-14}$ \ Decomposition methods with constructed
special approximations on interface surfaces (i.e. inhomogeneous schemes) were
discussed earlier.$^{15,\,16}$ \ The investigation of regional-additive finite
difference schemes is based on stability theory for difference schemes of
splitting in Hilbert grid spaces.$^{17,\,18}$
\textheight 7.8in
For a more restricted class of boundary value problems for second order
parabolic equations, the analysis of convergence of finite difference schemes
is often carried out on the base of the maximum principle.$^{17,\,18}$ \ In
this case closeness of the approximate solution to the exact one is
considered in the uniform norm. It is naturally to select a similar class of
regional-additive finite difference schemes.
In this paper we investigate two classes of such regional-additive finite
difference schemes with the overlapping of subdomains. The first class of them
is similar to usual schemes of component-wise decomposition,$^{17,\,19}$ \, and
it is treated as one-iteration synchronous (multiplicative) variant of the
classical alternating Schwarz method.$^{2,\,4}$ \ The second class of
regional-additive finite difference schemes corresponds to application of
additive-averaged finite difference schemes.$^{20,\,21}$ \ It can be considered
as one-iterative asynchronous (additive) variant of Schwarz' method.
Estimates of the convergence rate for decomposition finite difference schemes
under consideration are obtained; accuracy of the approximate solution with
respect to the overlapping of subdomains and different types of interface
boundary conditions is studied.
\newsection{Problem Formulation}
On the rectangle
$$
D=\{x:\ 00$, $c(x,t)\geq 0$, $p(x,t)\geq p_0>0$,
$(x,t)\in\ovl{G}$.
Suppose that on sets $S_0^*$, $S_1^*$, where
$$
S_0^*=\{(x,t):\ x\in\Gamma,\ t=0\},
$$
$$
S_1^*=\{(x,t):\ x\in\Gamma^*,\
t\in(0,T]\,\}
$$
and $\Gamma=\ovl{D}\setminus D,$ $\Gamma^*$ is a set of corner points of
the rectangle $D$, compatibility conditions are satisfied that provide
sufficient smoothness of the solution to problem (2.1),\,(2.2). Let
us assume that for the solution of the problem the following estimate
is fulfilled:
\be \label{2.3}
\left|\ \frac{\partial^{k+k_0}}{\partial x_1^{k_1}\partial x_2^{k_2}
\partial t^{k_0}}\,U(x,t)\ \right|\leq M,\ \ (x,t)\in\ovl{G}, \
k+2k_0\leq 4,\ k=k_1+k_2.
\ee
Let us expose a classical implicit finite difference scheme for problem
(2.1),(2.2). On the set $\ovl{G}$ we introduce the uniform rectangular grid
$$
\ovl{G}_{h \tau}=\ovl{D}_h\times \ovl{\omega}_\tau,
$$
where $\ovl{D}_h=\ovl{\omega}_1\times\ovl{\omega}_2$, $\ovl{\omega}_s$ is
a grid on the interval $[0,d_s]$, $s=1,2$, $\ovl{\omega}_\tau$ is a grid
on the interval $[0,T]$. Suppose
$h_s=d_sN_s^{-1}$, $s=1,2$, $\tau=TN_\tau^{-1}$, where
$N_s+1$ and $N_\tau+1$ is the number of nodes in the grids $\ovl{\omega}_s$ and
$\ovl{\omega}_\tau$ respectively. On the grid $\ovl{G}_{h\tau}$, we put
problem (2.1),(2.2) in correspondence with the finite difference scheme
\be \label{2.4}
\Lambda Z(x,t)=f(x,t),\ \ (x,t)\in G_{h \tau},\\[1ex]
\ee
\be \label{2.5}
Z(x,t)=\vf(x,t),\ \ (x,t)\in S_{h \tau}.
\ee
Here \ \ $G_{h \tau}=G\cap \ovl{G}_{h \tau}$, \ $S_{h \tau}=S\cap\ovl{G}_{h \tau}$,
$$
\Lambda\equiv \sum_{s=1}^2a_s(x,t)\delta_{xs\,\ovl{xs}}-
c(x,t)-p(x,t)\delta_{\ovl{t}},
$$
where $\delta_{xs\,\ovl{xs}}\,Z(x,t),\ \delta_{\ovl{t}}\,Z(x,t)$ are respectively
the second central and the first (backward) difference derivatives, for example:
$$
\delta_{x1\,\ovl{x1}}\,Z(x,t)=\frac{Z(x_1-h_1,x-2,t)-2Z(x_1,x_2,t)+
Z(x_1+h_1,x_2,t)}{h_1^2},
$$
$$
\delta_{\ovl{t}}\,Z(x,t)=\frac{Z(x,t)-Z(x,t-\tau)}{\tau}.
$$
For the boundary value problem (2.1),\,(2.2) and for the finite difference
scheme (2.4),\,(2.5) the maximum principle is valid.$^{17,\,18,\,22}$
As is well known from the theory of finite difference schemes,$^{17,\,18}$ \,
for $N,\ N_\tau\to\infty$, where $N=\min\,[N_1,N_2]$, the solution of problem
(2.4),(2.5) converges to the solution of problem (2.1),(2.2):
\be \label{2.6}
\mid U(x,t)-Z(x,t)\mid\leq M[\,h^2+\tau\,],\ \ (x,t)\in\ovl{G}_h,
\ee
where $h=\max\,[h_1,h_2]$.
%T\,h\,e\,o\,r\,e\,m \ 1. \ {\it
\begin{Theorem}
Let for the solution of boundary value
problem (2.1),(2.2) the estimate (2.3) be satisfied. Then the solution of grid
problem (2.4),(2.5) converges to the solution of problem
(2.1),(2.2), and for the approximate solution the estimate (2.6) holds.
\end{Theorem}
\noindent
{\bf Remark.} \ If for the solution of boundary value problem (2.1),(2.2)
the estimates
$$
\mid \frac{\partial}{\partial x_1}\,U(x,t)\mid,\ \
\mid \frac{\partial}{\partial t}\,U(x,t)\mid\leq M,\ \ (x,t)\in\ovl{G}
$$
are satisfied, and the coefficients of equation (2.2) are constant,
then for the solution of grid problem (2.4),(2.5) the following estimates
are valid
\be \label{2.7}
\mid \delta_{x_1}\,Z(x,t)\mid\leq M, \ \ (x,t)\in\ovl{G}_{h \tau},\ \ x_10.\ \ \
\ee
These estimates are used to study the rate of convergence when the second type
interface conditions are applied on the boundary.
\newsection{Regional-additive Schemes for the Continuous Problem}
We begin with consideration of an iteration-free scheme of domain decomposition
for problem (2.1),(2.2), i.e. only the time discretization will be applied.
Regional-additive schemes are constructed for which a transition
to new time level is realized by the solution of a set of problems
in the separate subdomains.
Let the set of subdomains
$$
D^k,\ \ k=1,2,\ldots,K
$$
with boundaries $\Gamma^k=\ovl{D}^{\,k}\setminus D^{k}$
form a covering of the set $D$:
$$
D=\bigcup\limits_{k=1}^K D^k.
$$
Here $D^k=\{x:\ d^k_{1\,s}0
\end{array} \right\},
$$
\be \label{3.3}
(x,t)\in S(t^n),\ \ n=0,1,\ldots,N_\tau-1.
\ee
On the layer $\ovl{G}(t^n)$ we find the function
$$
u(x,t;t^n),\ \ (x,t)\in\ovl{G}(t^n),\ \ t^n\in\ovl{\omega}_\tau,
$$
which is the approximate solution of the problem
\be \label{3.4}
Lu(x,t)=f(x,t),\ \ (x,t)\in G(t^n),
\ee
\be \label{3.5}
u(x,t)=u^0(x,t;t^n),\ \ (x,t)\in S(t^n).
\ee
The algorithm to find the function $u(x,t;t^n)$ on $\ovl{G}(t^n)$
is defined by the concrete variant of a regional-additive scheme.
Further, on the set $\ovl{G}$, $t\leq t^{n+1}$ we define the function
$u(x,t)$ by the relation
\be \label{3.6}
u(x,t)=\left\{
\begin{array}{l}
u(x,t;t^n),\ \ (x,t)\in\ovl{G}(t^n),\\[0.7ex]
u(x,t),\ \ (x,t)\in\ovl{G}\cap\{\,0\leq t0
\end{array} \right\}\, ,\ \
(x,t)\in S_h(t^n).
\ee
On the layer $\ovl{G}_h(t^n)$ we find the function
$$
z(x,t;t^n),\ \ (x,t)\in\ovl{G}_h(t^n),\ \ t^n\in\ovl{\omega}_\tau,
$$
which is the approximate solution of the grid problem
\be \label{5.4}
\Lh z(x,t)=f(x,t),\ \ (x,t)\in G_h(t^n),
\ee
\be \label{5.5}
z(x,t)=z^0(x,t;t^n),\ \ (x,t)\in S_h(t^n).
\ee
The algorithm of determination of the function $z(x,t;t^n)$ is defined
by the concrete variant of a regional-additive scheme.
On the set $\ovl{G}_{h\tau}$, $t\leq t^{n+1}$ we define the function $z(x,t)$
by the relation
\be \label{5.6}
z(x,t)=\left\{
\begin{array}{cl}
z(x,t;t^n), & (x,t)\in\ovl{G}_h(t^n),\\[0.8ex]
z(x,t), & (x,t)\in\ovl{G}_{h\tau}\cap \{0\leq t