TITLE: Equation for regions inside the triangle
QUESTION [0 upvotes]: Let $a,b,c$ be distinct point in $\mathbb{C}$.

Then, what would be an algebraic equation that designates this region inside the triangle including the boundary?
For example, $\{z\in \mathbb{C}: Re(z)^2 + Im(z)^2 \leq 1\}$ is an equation for a closed ball.
Likewise, what would it be for this case?
Is it $\{b+ t(c-b) + s(a-c): t,s\in [0,1]\}$?

REPLY [2 votes]: One way to describe this is as a convex combination of $a,b,c$:
$$T = \{\lambda_1a + \lambda_2b + \lambda_3c : \lambda_1+\lambda_2+\lambda_3 = 1, \  \lambda_i \geq 0\}$$
This is basically a weighted average, where the weights are non-negative.


text:
\begin{document}

\title{Optimized
  Schwarz waveform relaxation and discontinuous Galerkin time stepping for heterogeneous problems.}

 \author{Laurence Halpern \thanks{LAGA, Universit\'e Paris XIII,
 99 Avenue J-B Cl\'ement, 93430 Villetaneuse, France,
 \texttt{halpern@math.univ-paris13.fr}}
   \and  Caroline Japhet \thanks{LAGA, Universit\'e Paris XIII,
  99 Avenue J-B Cl\'ement, 93430 Villetaneuse, France, and
 CSCAMM, University of Maryland, College Park, MD 20742 USA,
 \texttt{japhet@cscamm.umd.edu}}
    \and J\'er\'emie Szeftel\thanks{D\'epartement de math\'ematiques et applications,
 Ecole Normale Sup\'erieure, 45 rue d'Ulm, 75230 Paris Cedex 05 France.
 \texttt{Jeremie.Szeftel@ens.fr}.
The first two authors are partially supported by french ANR (COMMA) and
GNR MoMaS}}

\maketitle

\begin{abstract}
We design and analyze Schwarz waveform relaxation algorithms for
domain decomposition of advection-diffusion-reaction problems with strong heterogeneities. These algorithms rely on optimized Robin or Ventcell transmission conditions, and can be used with curved interfaces. We analyze the semi-discretization in time with discontinuous Galerkin as well. We also show two-dimensional numerical results using generalized mortar finite elements in space.
\end{abstract}

\begin{keywords}
Coupling heterogeneous problems, domain decomposition, optimized Schwarz waveform relaxation,
time discontinuous Galerkin, nonconforming grids, error analysis.
\end{keywords}

\begin{AMS}
65 M 15, 65M50, 65M55.
\end{AMS}

\pagestyle{myheadings}
\thispagestyle{plain}
\markboth{L. Halpern, C. Japhet, J. Szeftel}{Schwarz Waveform relaxation and discontinuous Galerkin}

\section{Introduction}

In many fields of applications such as reactive transport, far field simulations of underground nuclear waste disposal or ocean-atmosphere coupling, models have to be coupled in different spatial zones, with very different space and time scales and possible complex geometries. For such problems with long time computations, a splitting of the time interval into windows is essential, with the possibility to use robust and fast solvers in each time window.

The Optimized Schwarz Waveform Relaxation (OSWR) method was introduced for linear parabolic and hyperbolic problems with constant coefficients in \cite{Gander:1999:OCO}. It was analyzed for advection diffusion equations, and applied to non constant advection, in \cite{martin:2005:AOS}. The algorithm computes independently in each subdomain over the whole time interval, exchanging space-time boundary data through optimized transmission operators. The operators are of Robin or Ventcell type, with coefficients optimizing a convergence factor, extending the strategy developed by F. Nataf and coauthors \cite{Charton:1991:MDD,japhet:1998:MDD}. The optimization problem was analyzed in \cite{gander:2007:OSW}, \cite{bennequin:2009:HBA}.

This method potentially applies to different space-time discretization in subdomains, possibly nonconforming and needs a very small number of iterations to converge. Numerical evidences of the performance of the method with variable smooth coefficients were given in \cite{martin:2005:AOS}. An extension to discontinuous coefficients was introduced in \cite{gander:2007:SWR}, with asymptotically optimized Robin transmission conditions in some particular cases.

The discontinuous Galerkin finite element method in time offers many advantages. Rigorous analysis can be made for any degree of accuracy and local time-stepping, and time steps can be adaptively controlled by a posteriori error analysis, see \cite{thomee:1997:FEM,johnson:1985:dgfirst,makridakis:2007:pea}. In a series of presentations in the regular domain decomposition meeting we presented the DG-OSWR method, using discontinuous Galerkin for the time discretization of the OSWR.
In \cite{blayo:2005:OSW}, \cite{halpern:2008:DGN}, we introduced the algorithm in one dimension with discontinuous coefficients.  In \cite{halpern:2009:DGN}, we extended the method to the two dimensional case. For the space discretization, we extended numerically the nonconforming approach in \cite{gander:2005:NZF} to advection-diffusion problems and optimized order 2 transmission conditions, to allow for non-matching grids in time and space on the boundary. The space-time projections between subdomains were computed with an optimal projection algorithm without any additional grid, as in \cite{gander:2005:NZF}. Two dimensional simulations were presented. In \cite{halpern:2010:DGN} we extended the proof of convergence of the OSWR algorithm to nonoverlapping subdomains with curved interfaces. Only sketches of proofs were presented.

The present paper intends to give a full and self-contained account of the method for the advection diffusion reaction equation with non constant coefficients.

In Section 2, we present the Robin and Ventcell algorithms at the continuous level in any dimension, and give in details the new proofs of convergence of the algorithms for nonoverlapping subdomains with curved interfaces.\\
Then in Section 3, we discretize in time with discontinuous Galerkin, and prove the convergence of the semi-discrete algorithms for flat interfaces. Error estimates are derived from the classical ones \cite{thomee:1997:FEM}. \\
The fully discrete problem is introduced in Section 4, using finite elements. The interfaces are treated by a new cement approach, extending the method in \cite{gander:2005:NZF}. Given the length of the paper, the numerical analysis will be treated in a forthcoming paper. \\
We finally present in Section 5 simulations for two subdomains, with piecewise smooth coefficients and a curved interface, for which no error estimates are available. We also include an application to the porous media equation.\\

Consider the advection-diffusion-reaction equation in $\Omega=\R^N$

\begin{equation}
  \label{eq:adall}
  \partial_t u +\div(\av u -\nu \nabla u)+c u=f  \quad \mbox{in } \Omega \times (0,T),
\end{equation}

with initial condition

\begin{equation}
  \label{eq:adu0}
  u(0,x)=u_0(x)  \quad x \in \Omega.
\end{equation}

The advection and diffusion coefficients $\av$ and $\nu$ , as well as
the reaction coefficient $c$, are piecewise smooth, the problem is
parabolic, i.e. $\nu \ge \nu_0 > 0$ \textit{a.e.} in $\R^N$ .

\begin{theorem}[Well-posedness and regularity, \cite{lions:1968:PAL}]\label{th,regall}
  Let $\Omega=\R^N$.  Suppose $\av\in (W^{1,\infty}(\Omega))^N$,
  $\nu \in W^{1,\infty}(\Omega)$ and $c \in L^{\infty}(\Omega)$. If
  the initial value $u_0$ is in $H^1(\Omega)$, and the right-hand side
  $f$ is in $L^2(0,T;L^2(\Omega))$, then there exists a unique solution $u$ of \eqref{eq:adall}, \eqref{eq:adu0} in
  $H^1(0,T;L^2(\Omega))$ $\cap$ $L^{\infty}(0,T;H^1(\Omega))$ $\cap$
  $L^{2}(0,T;H^2(\Omega))$.
\end{theorem}

We consider now a decomposition of $\Omega$ into nonoverlapping
subdomains $\Omega_i, i\in \inter{1,I}$, as depicted in Figure
\ref{fig:decompb}.  In all cases the boundaries
between the subdomains are supposed to be hyperplanes at infinity.

\begin{figure}[H]
  \centering
  \psfrag{Oj}{$ \Omega_i$}
  \begin{tabular}{cc}
  \includegraphics[width=0.17\textwidth]{subdomains.eps} \hspace{2cm}
  &
   \includegraphics[width=0.14\textwidth]{subdomainsband.eps}
   \end{tabular}
    \caption{Left: decomposition with possible corners (Robin
      transmission conditions), right: decomposition in bands (Ventcell transmission conditions)}
  \label{fig:decompb}
\end{figure}

Problem \eqref{eq:adall} is equivalent to solving $I$ problems in
subdomains $\Omega_i$, with transmission conditions on the interface
$\Gamma_{i,j} $ between two neighboring subdomains $\Omega_i$ and $\Omega_j$, given by the jumps $[u]=0$, $[(\nu\nabla u-\av)\cdot\nv_i]=0$. Here $\nv_i$ is the unit exterior normal to $\Omega_i$. As coefficients $\nu$ and $\av$ are possibly discontinuous on
the interface, we note, for $s \in \Gamma_{i,j}$,
$\nu_i(s)=\lim_{\varepsilon\rightarrow 0_+}\nu(s-\varepsilon \nv_i)$.
The same notation holds for $\av$ and $c$.

To any $i \in \inter{1,m}$, we associate the set ${\cal
  N}_i$ of indices of the neighbors of $\Omega_i$.

Following \cite{Charton:1991:MDD,Gander:1999:OCO,gander:2007:SWR}, we propose as preconditioner for (\ref{eq:adall}, \ref{eq:adu0}), the sequence of problems
\begin{subequations}\label{eq:algoorder2}
  \begin{align}
     &\partial_t u_i^k +\div(\av_i u_i^k-\nu_i\nabla u_i^k)+c_i u_i^k =f
      \mbox{ in }\Omega_i\times(0,T),\label{eq:algorogral1}\\[3mm]
     &\bigl(\nu_i \partial_{\nv_i}-\av_i\cdot\nv_i
      \bigr)\,u_i^{k} +\mathcal{S}_{i,j}u_i^{k} =
      \bigl(\nu_{j} \partial_{\nv_{i}}-\av_{j}\cdot
      \nv_{i}\bigr)\, u_{j}^{k-1} +\mathcal{S}_{i,j}u_{j}^{k-1}
      \mbox{ on }\Gamma_{i,j}, \, j\in {\cal N}_i. \label{eq:algogal2}
  \end{align}
\end{subequations}
The boundary operators $\mathcal{S}_{i,j}$, acting on the part $\Gamma_{i,j}$ of the boundary of $\Omega_i$ shared by the boundary of $\Omega_j$ are given by

\begin{equation}
  \label{eq:boundaryoperators}
     \mathcal{S}_{i,j}\phi=p_{i,j}\phi
    + q_{i,j} (\partial_t\phi+\divs{\Gamma_{i,j}}(\rv_{i,j}
    \phi  -s_{i,j} \grads{\Gamma{i,j}}\phi)).
\end{equation}

$\grads{\Gamma}$ and $\divs{\Gamma}$ are respectively the gradient
and divergence operators on $\Gamma$. $p_{i,j}, \ q_{i,j}, \ s_{i,j}$
are functions in $L^\infty(\Gamma_{i,j})$ and $\rv_{i,j}$ is in
$(L^\infty(\Gamma_{i,j}))^{N-1}$. The initial value is that of $u_0$ in each subdomain.  An initial guess $(g_{i,j})$ is given on
$L^2((0,T)\times \Gamma_{i,j})$ for $i\in \inter{1,I}, j \in {\cal
  N}_i$.  By convention for the first iterate, the right-hand side in \eqref{eq:algoorder2} is given by $g_{i,j}$.
Under regularity assumptions,
solving \eqref{eq:adall} is equivalent to solving

\begin{equation}\label{eq:dec}
\begin{array}{l}
    \partial_t u_i +\div(\av_i u_i-\nu_i\nabla u_i)+c_i u_i=f \mbox{ in } \Omega_i
    \times(0,T),  \\[0.5mm]

    \ds\bigl(\nu_i \partial_{\nv_i}
    -\av_i\cdot\nv_i \bigr)\, u_i +\mathcal{S}_{i,j}u_i =

    \bigl(\nu_{j}
    \ds\partial_{\nv_i} -\av_{j}\cdot\nv_{i} \bigr)\, u_{j}
    +\mathcal{S}_{i,j}u_{j} \mbox{ on }\Gamma_{i,j}\times (0,T), j\in {\cal N}_i,
\end{array}
\end{equation}

for $i\in \inter{1,I}$ with $u_i$ the restriction of $u$ to $\Omega_i$.

\section{Studying the algorithm for the P.D.E}

The first step of the study is to give a frame for the definition of the iterates.

\subsection{The local problem}

The optimized Schwarz waveform relaxation algorithm relies on the
resolution of the following initial boundary value problem in a
domain $\co$ with boundary $\Gamma$:

\begin{equation}\label{eq:pblim}
  \begin{array}{l}
     \partial_t w +\div(\av w -\nu \nabla w)+c w=f \mbox{ in }
    \co \times (0,T),\\
    \ds\nu\,\partial_{\nv} w - \av\cdot\nv \, w
    + \mathcal{S} w =g \mbox{ on }
    \Gamma \times (0,T),\\
    w(\cdot,0)=u_0 \mbox{ in }    \co,
  \end{array}
\end{equation}

where $\nv$ is the exterior unit normal to $\co$. The boundary operator $\mathcal{S}$ is defined on $\Gamma=\partial \co$ by

\begin{equation}\label{eq:boundaryoperator}
  \mathcal{S}w= p\,w + q\, (\partial_t w
  + \divs{\Gamma}(\rv w -s\grads{\Gamma}w)).
\end{equation}

The domain $\co$ has either form depicted in Figure \ref{fig:decompb}, left for $q=0$, right otherwise.

The functions $p,\,q$ and $s$ are in $L^\infty(\Gamma)$, and $\rv$ is in $(L^\infty(\Gamma))^{N-1}$. Either $q=0$, and the boundary condition is
of Robin type, or we suppose $q\ge q_0 >0$ and the operator will be referred to as Order 2 or Ventcell operator.  In the latter case, we
need the spaces

\begin{equation}\label{eq:sobtrace}
  H^s_s(\co)=\{v\in H^s(\co), v\trace{\Gamma}\in H^s(\Gamma)\},
\end{equation}

which are defined for $s>1/2$, and equipped with the scalar product

\begin{equation}\label{eq:sobtraceps}
  (w,v)_{H^s_s(\co)}=(w,v)_{H^s(\co)}+(qw,v)_{H^s(\Gamma)}.
\end{equation}

We define the bilinear forms $m$ on $H^1(\co)$ and $a$ on $ H^1_1(\co)$ by
\begin{equation}\label{eq:sobtraceps0}
 m(w,v)=(w,v)_{L^2(\co)}+(qw,v)_{L^2(\Gamma)},
\end{equation}
and

\begin{multline}
  \label{eq:formbilin}
  a(w,v):=
  \int_\co(\frac{1}{2}((\av\cdot\nabla w)v-(\av\cdot\nabla v)w))\, dx
  +\int_\co \nu \nabla w\cdot\nabla v \, dx + \int_\co (c+\frac{1}{2}\div\av) w v \, dx\\

  +\int_\Gamma \bigl((p-\frac{\av\cdot\nv}{2}+{q \over 2}\nabla_{\Gamma}
  \cdot\rv)w v+{q \over 2}(\nabla_{\Gamma} \cdot(\rv w)v-\nabla_{\Gamma} \cdot(\rv v)w)
  +qs\nabla_{\Gamma}w \cdot\nabla_{\Gamma} v \bigr)\, d \sigma,
\end{multline}

By the Green's formula, we can write a variational formulation of
\eqref{eq:pblim}:

\begin{equation}\label{eq:formvariat}
 \ds \frac{d\,}{dt}\,m(w, v)+a(w,v)
   = (f,v)_{L^2(\co)}+(g,v)_{L^2(\Gamma)}.
\end{equation}

The well-posedness is a generalization of results in
\cite{gander:2007:OSW,bennequin:2009:HBA,szeftel:2005:ABC}. It relies
on energy estimates and Gr\"{o}nwall's lemma.

\begin{theorem}\label{th:exfortefo}
  Suppose $\nu \in W^{1,\infty}(\co)$, $\av \in
  (W^{1,\infty}(\co))^N$, $c \in L^{\infty}(\co)$, $p \in L^{\infty}(\Gamma), \ q \in
  L^{\infty}(\Gamma)$, $\rv \in (W^{1,\infty}(\Gamma))^{N-1}$, $s \in
  W^{1,\infty}(\Gamma)$ with $s >0$ \textit{a.e}.

   \textbf{If $q=0$}, if $f$ is in $H^{1}(0,T;L^{2}(\co))$, $u_0$ is
   in $H^{2}(\co)$   and $g$ is in $H^1(0,T;L^2(\Gamma))\cap L^{\infty}(0,T;H^{1/2}(\Gamma))$, satisfying the compatibility condition
   $\ds\nu\,\partial_{\nv} u_0- \av\cdot\nv \, u_0
   + p u_0 =g$
, the
   subdomain problem \eqref{eq:pblim} has a unique solution $w$ in
   $L^\infty(0,T;H^{2}(\co))$ $\cap$ $W^{1,\infty}(0,T;L^2(\co))$.

  \textbf{If $q\ge q_0 >0 \ a.e.$}, if $f$ is in
  $H^{1}(0,T;L^{2}(\co))$, $u_0$ is in $H^{2}_2(\co)$, and $g$ is in
  $H^{1}((0,T);L^2(\Gamma))$, problem \eqref{eq:pblim}
  has a unique solution $w$ in $L^\infty(0,T;H^{2}_2(\co))$ $\cap$ $
  W^{1,\infty}(0,T;L^2(\co))$ with $\partial_tw\in L^\infty
  (0,T;L^2(\Gamma))$.
\end{theorem}

\begin{proof}
The existence result relies on a Galerkin method like in
\cite{szeftel:2003:ABC,szeftel:2005:ABC}. In the sequel, $\alpha,\beta,\cdots$ denote positive real  numbers depending only on the coefficients and the geometry. The basic
estimate is obtained by multiplying the equation by $w$ and
integrating by parts in the domain.  We set $\|w\|=\|w\|_{L^2(\co)}$
and $\|w\|_\Gamma=\|w\|_{L^2(\Gamma)}$.

\begin{equation*}
\ds \frac{1}{2}\frac{d}{dt} m(w,w)\ +\
  a(w,w)= (f,w)_{L^2(\co)} + (g,w)_{L^2(\Gamma)}.
\end{equation*}

With the assumptions on the coefficients, we have \\

\textbf{Case $q=0$.}

\begin{equation*}
\begin{array}{lcl}
  a(w,w)&=&\ds\int_\co \nu |\nabla w|^2 \, dx
           + \int_\co (c+\frac{1}{2}\div\av)w^2 \, dx
           + \int_\Gamma
                \bigl(
                 (p -\frac{\av\cdot\nv}{2}
                 \bigr) w^2\, d \sigma \\[3mm]
        &\ge &\ds \alpha(\|\nabla w\|^2
                -\beta (\|w\|^2+\|w\|_\Gamma^2)\\[3mm]
       &\ge &\ds \frac{\alpha}{2}\|\nabla w\|^2
                -\gamma \|w\|^2,
  \end{array}
\end{equation*}
the last inequality coming from the trace theorem

\begin{equation}\label{eq:tracetheorem}
\|w\|_\Gamma^2 \le C \|\nabla w\| \|w\|.
\end{equation}

 We obtain with the Cauchy-Schwarz inequality

\begin{equation*}
\begin{array}{lcl}
 \frac{1}{2} \frac{d}{dt} \|w\|^2\ +\
  \frac{\alpha}{4}\|\nabla w\|^2
               &\le& \eta \|w\|^2 +
          \delta (\|f\|^2+\|g\|_\Gamma^2).
  \end{array}
\end{equation*}

We now have with Gr\"{o}nwall's lemma

\begin{equation}\label{eq:estimatepblimRobin}
\begin{array}{l}
    \ds \|w(t)\|^2\ +\
    \frac{\alpha}{2}\int_0^t(\|\nabla w(s)\|^2 ds  \le\\[3mm]
    \hspace{10mm}
   \ds  e^{2\eta  T}
        ( \|u_0\|^2 +
              2 \delta (\|f\|_{L^2(0,T;L^2(\co))}^2
                        +\|g\|_{L^2(0,T;L^2(\Gamma))}^2)).
  \end{array}
\end{equation}

We apply \eqref{eq:estimatepblimRobin} to $w_t$:

\begin{equation*}
\begin{array}{l}
    \ds \|w_t(t)\|^2\ +
     \frac{\alpha}{2}\int_0^t\|\nabla w_t(s)\|^2 ds  \le\\[3mm]
    \hspace{10mm}
   \ds  e^{2\eta  T}
        ( \|{w_t}_0\|^2 +
              2 \delta (\|f_t\|_{L^2(0,T;L^2(\co))}^2
                        +\|g_t\|_{L^2(0,T;L^2(\Gamma))}^2)).
  \end{array}
\end{equation*}

Thanks to the compatibility condition, ${w_t}_0$ can be estimated,
using the equation, by $\|{w_t}_0\| \le \zeta(\|u_0\|_{H^2(\co)} +
\|f(0,\cdot)\|)$ , and we obtain

\begin{equation*}

\begin{array}{l}
    \ds \|w_t(t)\|^2\ +
    \frac{\alpha}{2}\int_0^t\|\nabla w_t(s)\|^2 ds  \le\\[3mm]
    \hspace{10mm}
   \ds \theta e^{2\eta  T}
        ( \|u_0\|_{H^2(\co)}  +
                (\|f\|_{H^1(0,T;L^2(\co))}^2
                        +\|g\|_{H^1(0,T;L^2(\Gamma))}^2)).
  \end{array}
\end{equation*}

\textbf{Case $q\ge q_0 >0$} \ \textit{a.e}.

\begin{equation*}
\begin{array}{lcl}
  a(w,w)&=&\ds\int_\co \nu |\nabla w|^2 \, dx
           + \int_\co (c+\frac{1}{2}\div\av)w^2 \, dx \\[2mm]
           & & \ds\quad
           + \int_\Gamma
                \bigl(
                 (p -\frac{\av\cdot\nv}{2}+
                 {q \over 2}\nabla_{\Gamma}\cdot\rv)w^2
                 +qs |\nabla_{\Gamma}w|^2
                 \bigr) \, d \sigma,\\[2mm]
        &\ge &\ds \alpha(\|\nabla w\|^2
               + \|\nabla_{\Gamma} w\|_{\Gamma}^2)
               -\beta m(w,w),
  \end{array}
\end{equation*}

and by the Cauchy-Schwarz inequality

\begin{equation*}
\int_\co (f,w)\,dx +
           \int_\Gamma (g,w)_\Gamma\,d\sigma
           \le
           \gamma m(w,w)
           + \delta (\|f\|^2+\|g\|_\Gamma^2).
\end{equation*}

Collecting these inequalities, we obtain

\begin{equation*}
\begin{array}{lcl}
 \frac{1}{2}\frac{d}{dt} m(w,w)\ +\
  \alpha(\|\nabla w\|^2
               + \|\nabla_{\Gamma} w\|_{\Gamma}^2)
               &\le& (\beta+\gamma) m(w,w) +
          \delta (\|f\|^2+\|g\|_\Gamma^2).
  \end{array}
\end{equation*}

We now integrate in time and use Gr\"{o}nwall's lemma to obtain for any $t$ in $(0,T)$

\begin{equation}\label{eq:estimatepblim}
\begin{array}{l}
    \ds m(w(t),w(t))\ +\
    2\alpha\int_0^t(\|\nabla w(s)\|^2
               + \|\nabla_{\Gamma} w(s)\|_{\Gamma}^2)ds  \le\\[3mm]
    \hspace{10mm}
   \ds  e^{(\beta+\gamma) T}
        ( m(u_0,u_0) +
              2 \delta (\|f\|_{L^2(0,T;L^2(\co))}^2
                        +\|g\|_{L^2(0,T;L^2(\Gamma))}^2)).
  \end{array}
\end{equation}

We apply \eqref{eq:estimatepblim} to $w_t$:

 \begin{equation*}
\begin{array}{l}
    \ds m(w_t(t),w_t(t))\ +\
    2\alpha\int_0^t(\|\nabla w_t(s)\|^2
               + \|\nabla_{\Gamma} w_t(s)\|_{\Gamma}^2)ds  \le\\[3mm]
    \hspace{10mm}
   \ds  e^{(\beta+\gamma) T}
        ( m({w_t}_0,{w_t}_0) +
              2 \delta (\|f_t\|_{L^2(0,T;L^2(\co))}^2
                        +\|g_t\|_{L^2(0,T;L^2(\Gamma))}^2) ).
  \end{array}
  \end{equation*}

We now use the equations at time 0 to estimate $m({w_t}_0,{w_t}_0)$.
From the equation in the domain, we deduce that

\[
\|{w_t}_0\|\le \zeta(\|{u}_0\|_{H^2(\co)}+ \|f(0,\cdot)\|),
\]
and from the boundary condition that
\[
\|{w_t}_0\|_{\Gamma}\le \eta(\|{u}_0\|_{H_2^2(\co)}+ \|g(0,\cdot)\|_{\Gamma}),
\]
which gives altogether

 \begin{equation}\label{eq:estimatepblim2}
\begin{array}{l}
    \ds m(w_t(t),w_t(t))\ +\
    2\alpha\int_0^t(\|\nabla w_t(s)\|^2
               + \|\nabla_{\Gamma} w_t(s)\|_{\Gamma}^2)ds  \le\\[3mm]
    \hspace{10mm}
   \ds  \theta e^{(\beta+\gamma) T}
        ( \|{u}_0\|_{H_2^2(\co)}^2+
          \|f\|_{H^1(0,T;L^2(\co))}^2
                        +\|g\|_{H^1(0,T;L^2(\Gamma))}^2) ).
  \end{array}
  \end{equation}

We can now apply the Galerkin method.  When $q=0$, we work in $H^1(0,T;H^{1}(\co))$ $\cap $ $W^{1,\infty}(0,T;L^2(\co))$ , while
if $q\geq q_0>0$ \textit{a.e} we consider $H^1(0,T;H^{1}_1(\co))$ $\cap$ $ W^{1,\infty}(0,T;L^2(\co))$ $\cap$ $W^{1,\infty}(0,T;L^2(\Gamma))$. This gives a unique solution $w$. The regularity
$H^2$ is obtained for $q=0$ by the usual regularity results for the
Laplace equation with Neumann boundary condition, since

\begin{equation*}
\begin{array}{l}
-\Delta w= \ds \frac{1}{\nu}
(f -w_t -\div(\av w)+ \nabla \nu \cdot \nabla w)
\in L^\infty(0,T;L^2(\co)),\\
\ds  \partial_{\nv} w =\ds \frac{1}{\nu}(\av\cdot\nv  -p ) w
+\frac{1}{\nu}g  \in L^\infty(0,T;H^{1/2}(\Gamma)).
\end{array}
\end{equation*}

In the other case, we have that

\begin{equation*}
\begin{array}{l}
-\Delta w= \ds \frac{1}{\nu}
(f -w_t -\div(\av w)+ \nabla \nu \cdot \nabla w) \in L^\infty(0,T;L^2(\co)),\\
\ds \nu \partial_{\nv}- qs\Delta_\Gamma w=\ds \frac{1}{\nu}(\av\cdot\nv -p
-q\, (\partial_t + \divs{\Gamma}\rv -(\divs{\Gamma}s)\grads{\Gamma}))) w

+\frac{1}{\nu}g
   \in L^\infty(0,T;L^{2}(\Gamma)),
\end{array}
\end{equation*}

and we conclude like in \cite{szeftel:2003:ABC,szeftel:2005:ABC}.
\end{proof}

\subsection{Convergence analysis for Robin transmission conditions}

We suppose here the coefficients $q_i$ to be zero everywhere. Given
initial guess $(g_{i,j})$ on $L^2((0,T)\times \Gamma_{i,j})$ for $i\in
\inter{1,I}, j \in {\cal N}_i$, the algorithm reduces in each
subdomain to

\begin{subequations}\label{eq:algorobin}
  \begin{align}
     &\partial_t u_i^k +\div(\av_i u_i^k-\nu_i \nabla u_i^k)+c_i u_i^k =f
      \mbox{ in }\Omega_i\times(0,T),\label{eq:algorobin1}\\[3mm]
     &\bigl(\nu_i \partial_{\nv_i}-\av_i\cdot\nv_i
      \bigr)\,u_i^{k} +p_{i,j}\,u_i^{k} =
      \bigl(\nu_{j} \partial_{\nv_{i}}-
      \av_j\cdot\nv_i\bigr)\, u_{j}^{k-1} +p_{i,j}\,u_{j}^{k-1}
      \mbox{ on }\Gamma_{i,j}, j\in {\cal N}_i. \label{eq:algorobin2}
  \end{align}
\end{subequations}

The well-posedness for the boundary value problem in the previous
section permits to define the sequence of iterates. We now consider
the convergence of this sequence.

\begin{theorem}\label{th:convcont}
  For coefficients $p_{i,j}$ such that
  $p_{i,j}+p_{j,i}>0 \ a.e.$, the sequence
  $(u_i^k)_{k\in \NN}$ of solutions of \eqref{eq:algorobin} converges
  to the solution $u$ of problem \eqref{eq:adall}.
\end{theorem}

\begin{proof}
By linearity, it is sufficient to prove that the sequence of iterates
converges to zero if $f=u_0=0$.

We multiply \eqref{eq:algorobin1} by $u_i^k$, integrate on $\Omega_i$,
and use the Green's formula. We obtain

\begin{multline}\label{eq:estcont1}
  \frac{1}{2}\frac{d\,}{dt}\|u_i^k(t,\cdot)\|^2_{L^2(\Omega_i)}
  +(\nu_i\nabla u_i^k,\nabla u_i^k)_{L^2(\Omega_i)}
+ ((c_i+\frac{1}{2}\div\av_i) u_i^k,u_i^k)_{L^2(\Omega_i)} \\ \hspace{-3cm}-\sum_{j\in{\cal
  N}_i}\int_{\Gamma_{i,j}} \bigl(\nu_i \partial_{\nv_i} u_i^k
  -\moit{\av_i\cdot\nv_i} u_i^k\bigr)\,u_i^k d\sigma = 0.
\end{multline}

We use now

\begin{multline}\label{tototiti}
  \bigl(\nu_i \partial_{\nv_i} u_i^k-\av_i\cdot\nv_i
  u_i^k+p_{i,j}u_i^k\bigr)^2
  -\bigl(\nu_i \partial_{\nv_i} u_i^k-\av_i\cdot\nv_i
  u_i^k-p_{j,i}u_i^k\bigr)^2 =\\
  2(p_{i,j}+p_{j,i})\bigl(\nu_i \partial_{\nv_i} u_i^k
  -\moit{\av_i\cdot\nv_i} u_i^k \bigr)u_i^k
  + (p_{i,j}+p_{j,i})(p_{i,j}-p_{j,i}-\av_i\cdot\nv_i)(u_i^k)^2.
\end{multline}

We replace the boundary term in \eqref{eq:estcont1}, and integrate in
time. Since the initial value vanishes, we have for any time $t$,

\begin{multline*}

  \|u_i^k(t)\|^2_{L^2(\Omega_i)}
  +2\int_{0}^t\bigl((\nu_i\nabla u_i^k,\nabla u_i^k)_{L^2(\Omega_i)}
       + ((c_i+\frac{1}{2}\div\av_i) u_i^k,u_i^k)_{L^2(\Omega_i)}\bigr) \,d\tau\\
  +\sum_{j\in{\cal N}_i}\int_{0}^t\int_{\Gamma_{i,j}}
\frac{1}{p_{i,j}+p_{j,i}}
  \bigl(\nu_i \partial_{\nv_i} u_i^k-{\av_i\cdot\nv_i}
  u_i^k-p_{j,i}u_i^k\bigr)^2 d\sigma \,d\tau \\
  =
  \sum_{j\in{\cal
  N}_i}\int_{0}^t\int_{\Gamma_{i,j}}
  \frac{1}{p_{i,j}+p_{j,i}}
  \bigl(\nu_i \partial_{\nv_i} u_i^k-{\av_i\cdot\nv_i}
  u_i^k+p_{i,j}u_i^k\bigr)^2d\sigma \,d\tau \\
  \hspace{-3cm}+\sum_{j\in{\cal
  N}_i}\int_{0}^t\int_{\Gamma_{i,j}}(p_{j,i}-p_{i,j} -\av_i\cdot\nv_i)
  (u_i^k)^2d\sigma \,d\tau.
\end{multline*}

Since the coefficients are all bounded, the last term in the
right-hand side can be handled by the trace theorem
\eqref{eq:tracetheorem} to be canceled with the terms in the
left-hand side like in the proof of Theorem \ref{th:convcont}.

We further insert the transmission condition in the right-hand side:

\begin{multline*}
  \|u_i^k(t)\|^2_{L^2(\Omega_i)}+\nu_0\int_{0}^t\|\nabla u_i^k\|^2_{L^2(
  \Omega_i)}\,d\tau
  +\sum_{j\in{\cal N}_i}\int_{0}^t\int_{\Gamma_{i,j}}
  \frac{1}{p_{i,j}+p_{j,i}}
  \bigl(\nu_i \partial_{\nv_i} u_i^k-\av_i\cdot\nv_i
  u_i^k-p_{j,i}u_i^k\bigr)^2 d\sigma\,d\tau \\
   \le
  \sum_{j\in{\cal N}_i}\int_{0}^t\int_{\Gamma_{i,j}}
  \frac{1}{p_{i,j}+p_{j,i}}
  (\nu_{j} \partial_{\nv_i} u_j^{k-1}-\av_{j}\cdot
  \nv_{i} u_{j}^{k-1}\, +p_{i,j}u_{j}^{k-1} \bigr)^2d\sigma\,d\tau +
  C_1\int_{0}^t\|u_i^k\|^2_{L^2(\Omega_{i})}.
\end{multline*}

We sum on the subdomains, and on the iterations, the boundary terms
cancel out except the first and last ones, and we obtain for any $t
\in (0,T)$,

\begin{multline}\label{eq:estcontal}
  \sum_{k\in \inter{1,K}}\sum_{i\in \inter{1,I}}\biggl(
  \|u_i^k(t)\|^2_{L^2(\Omega_i)}+\nu_0\int_{0}^t\|\nabla u_i^k\|^2_{L^2(
  \Omega_i)}\,d\tau
  \biggr)
  \le
  \alpha(t)
  + C_1\sum_{k\in \inter{1,K}}\sum_{i\in \inter{1,I}}\int_{0}^t\|u_i^k\|^2_{
  L^2(\Omega_{i})},
\end{multline}

with

\[
  \alpha(t)=
  \sum_{i\in \inter{1,I}} \sum_{j\in{\cal N}_i}
  \int_{0}^t\int_{\Gamma_{i,j}}
  \frac{1}{p_{i,j}+p_{j,i}}
  (\nu_{j} \partial_{\nv_i} u_{j}^{0}-\av_{j}\cdot
  \nv_{i} u_{j}^{0}\, +p_{i,j}u_{j}^{0} \bigr)^2 d\sigma\,d\tau.
\]

We now apply Gr\"{o}nwall's lemma and obtain that for any $K > 0$,

\[
 \ds\sum_{k\in \inter{1,K}}\sum_{i\in
  \inter{1,I}}\|u_i^k(t)\|^2_{L^2(\Omega_i)}
  \le
  \alpha(T) e^{C_1 T},
  \]

which proves that the sequence $u_i^k $ converges to zero in $L^2 ((0,T)\times \Omega_i) $ for each $i$, and concludes the proof of the theorem.
\end{proof}

\begin{remark}
  In the case $\div \av =0$, if $p_{j,i}-p_{i,j}-\av_i \cdot \nv_i=0$ and $c_i \ge \alpha_0 >0$,
  then $C_1=0$ in \eqref{eq:estcontal} and we conclude without using Gr\"{o}nwall's lemma.
\end{remark}

\subsection{Order 2 transmission conditions}

\leavevmode\par
\noindent\begin{theorem}\label{th:convcontorder2}
  Assume $p_{i,j} \in W^{1,\infty}(\Omega_i), \ p_{i,j}+p_{j,i}>0 \ a.e.$,
  $q_{i,j}=q > 0$, $\av_i\in (W^{1,\infty}(\Omega_i))^N$, $\nu_i\in
  W^{1,\infty}(\Omega)$, $\rv_{i,j}\in
  (W^{1,\infty}(\Omega_i))^{N-1}$, with $\rv_{i,j}=\rv_{j,i} \ on
  \ \Gamma_{i,j}$, $s_{i,j}\in W^{1,\infty}(\Omega_i)$, $s_{i,j}>0$
with $s_{i,j}=s_{j,i} \ on \ \Gamma_{i,j}$, and the domain is cut in bands as in Figure \ref{fig:decompb}, right. Then, the algorithm \eqref{eq:algoorder2} converges in each subdomain to the solution $u$ of problem \eqref{eq:adall}.
\end{theorem}

\begin{proof}
We first need some results in differential geometry. For any $i \in \inter{1,I}$,
For every $j \in {\cal N}_i$, the
normal vector $ \nv_{i}$ can be extended in a neighbourhood of
$\Gamma_{i,j}$ in $\Omega_i$ as a smooth function $\tilde{\nv}_{i}$
with length one. Let $\psi_{i,j} \in {\cal
  C}^\infty(\overline{\Omega_i})$, such that $\psi_{i,j} \equiv 1$ in
a neighbourhood of $\Gamma_{i,j}$, $\psi_{i,j} \equiv 0$ in a
neighbourhood of $\Gamma_{i,k}$ for $k \in {\cal N}_i, \, k \neq j$
and $\sum_{j \in {\cal N}_i}\psi_{i,j}>0$ on $\Omega_i$.  We can assume that
$\tilde{\nv}_{i}$ is  defined on a neighbourhood of the support of
$\psi_{i,j}$. We extend the tangential gradient and divergence
operators in the support of $ \psi_{i,j}$ by:

\begin{eqnarray}
\gradts{\Gamma_{i,j}}\phi:= \nabla \phi-(\partial_{\tilde{\nv}_{i}}\phi)\tilde{\nv}_{i},\quad
\divts{\Gamma_{i,j}}\xv:=\div(\xv-(\xv \cdot \tilde{\nv}_{i})\tilde{\nv}_{i}).\nonumber
\end{eqnarray}

It is easy to see that
$(\gradts{\Gamma_{i,j}}\phi)_{|\Gamma_{i,j}}=\grads{\Gamma_{i,j}}\phi$,
$(\divts{\Gamma_{i,j}}\xv)_{|\Gamma_{i,j}}=\divs{\Gamma_{i,j}}\xv$ and
for $\xv$ and $\chi$ with support in $supp(\psi_{i,j})$, we have

\begin{equation}\label{japhet_plenary_eq:divs}
\int_{\Omega_i} (\divts{\Gamma_{i,j}}\xv)\, \chi\, dx
=-\int_{\Omega_i} \xv \cdot \gradts{\Gamma_{i,j}} \chi\, dx.
\end{equation}

Now we prove Theorem \ref{th:convcontorder2}. We consider the
algorithm \eqref{eq:algoorder2} on the error, so we suppose
$f=u_0=0$. We set $\|\varphi\|_i=\|\varphi\|_{L^2(\Omega_i)}$,
$\interleave\varphi\interleave_i^2= \|\sqrt{\nu_i}\,\nabla
\varphi\|^2_i$,
$\|\varphi\|_{i,\infty}=\|\varphi\|_{L^{\infty}(\Omega_i)}$,
$\|\varphi\|_{i,1,\infty}=\|\varphi\|_{W^{1,\infty}(\Omega_i)}$ and
$\beta_{i,j}=\sqrt{\frac{p_{i,j}+p_{j,i}}{2}}$.
\vspace{3mm}

The proof is based on energy estimates containing the term

$$\int_0^t \int_{\Gamma_{i,j}} \left(\nu_i \partial_{\nv_i}u_i^k
-\av_i\cdot\nv_iu_i^k + \mathcal{S}_{i,j}
u_i^k\right)^2\,d\sigma\,d\tau,
$$

and that we derive by multiplying successively the first equation of
\eqref{eq:algoorder2} by the terms $\beta_i^2\,u_i^k$, $\partial_t
u_i^k$, $\divts{\Gamma_{i,j}}(\psi_{i,j}^2\rv_{i,j} u_i^k )$ and
$-\divts{\Gamma_{i,j}} (\psi_{i,j}^2 s_{i,j} \,\gradts{\Gamma_{i,j}}\,
u_i^k)$.

We multiply the first equation of \eqref{eq:algoorder2} by
$\beta_i^2\,u_i^k$, integrate on $(0,t)\times \Omega_i$ and
integrate by parts in space,

 \begin{multline}\label{eq:estcontorder2-1}
  \frac{1}{2}\|\beta_iu_i^k(t)\|^2_i
   +\int_0^t\interleave \beta_iu_i^k(\tau,\cdot)\interleave_i^2 \,d\tau
   -\int_0^t \int_{\Omega_i} \beta_i(\av_i \cdot \nabla \beta_i)(u_i^k)^2 \,dx\,d\tau
    \hspace{1cm}\\
   +\int_0^t \int_{\Omega_i} (c_i+\frac{1}{2}\div\av_i)\beta_i^2(u_i^k)^2 \,dx\,d\tau
   -  \int_0^t \int_{\Omega_i} \nu_i|\nabla \beta_i|^2(u_i^k)^2 \,dx\,d\tau \\
   -\int_0^t \int_{\Gamma_{i,j}} \beta_{i,j}^2(\nu_i\partial_{\nv_i} u_i^k
   - \frac{\av_i\cdot\nv_i}{2}u_i^k)\, u_i^k \, d\sigma\,d\tau
   =0.
 \end{multline}

We multiply the first equation of \eqref{eq:algoorder2} by $\partial_t
u_i^k$, integrate on $(0,t)\times \Omega_i$ and then integrate by
parts in space,

\begin{multline}\label{eq:estcontorder2-2}
  \hspace{-8mm}
   \int_0^t \|\partial_t u_i^k\|^2_{i} \,d\tau
 + \frac{1}{2}\interleave u_i^k(t)\interleave_i^2
 +\int_0^t\int_{\Omega_i}(c_iu_i^k+\div(\av_i u_i^k)) \, \partial_t  u_i^k
 \,dx\,d\tau
 - \int_0^t \int_{\Gamma_{i,j}} \nu_i\partial_{\nv_i} u_i^k
  \, \partial_t u_i^k \, d\sigma\,d\tau
 =0.
\end{multline}

We multiply the first equation of \eqref{eq:algoorder2} by
$\divts{\Gamma_{i,j}} (\psi_{i,j}^2\rv_{i,j} u_i^k )$ integrate on
$(0,t)\times \Omega_i$ and integrate by parts in space:

\begin{multline}\label{eq:estcontorder2-3-1}
  \int_0^t\int_{\Omega_i}\partial_t u_i^k
    \divts{\Gamma_{i,j}}(\psi_{i,j}^2\rv_{i,j} u_i^k)\,dx\,d\tau
   +\int_0^t\int_{\Omega_i}\div(\av_i u_i^k) \,
    \divts{\Gamma_{i,j}}(\psi_{i,j}^2\rv_{i,j} u_i^k)\,dx\,d\tau \\
   +\int_0^t\int_{\Omega_i} c_i u_i^k
       \divts{\Gamma_{i,j}}(\psi_{i,j}^2\rv_{i,j} u_i^k) \,dx\,d\tau\\
   + \int_0^t\int_{\Omega_i} \nu_i \nabla u_i^k \cdot
     \nabla\divts{\Gamma_{i,j}}(\psi_{i,j}^2\rv_{i,j} u_i^k)
      \,dx\,d\tau
  -\int_0^t\int_{\Gamma_{i,j}} \nu_i\partial_{\nv_i} u_i^k
     \, \divs{\Gamma_{i,j}}(\rv_{i,j} u_i^k)  \,d\sigma\,d\tau
   =0.
\end{multline}

We observe that

\begin{multline}\label{eq:estcontorder2-3-2}
 \int_0^t\int_{\Omega_i} \nu_i \nabla u_i^k \cdot
   \nabla\divts{\Gamma_{i,j}}(\psi_{i,j}^2\rv_{i,j} u_i^k)
    \,dx\,d\tau\\
= \int_0^t\int_{\Omega_i} \nu_i \nabla u_i^k \cdot
   \nabla(\divts{\Gamma_{i,j}}(\psi_{i,j}^2\rv_{i,j}) u_i^k)
    \,dx\,d\tau
+\int_0^t\int_{\Omega_i} \nu_i \nabla u_i^k \cdot
   \nabla (\psi_{i,j}^2\rv_{i,j} \cdot \gradts{\Gamma_{i,j}}\, u_i^k)
    \,dx\,d\tau,
\end{multline}

with

\begin{multline}\label{eq:estcontorder2-3-3}
  \int_0^t\int_{\Omega_i} \nu_i \nabla u_i^k \cdot
    \nabla (\psi_{i,j}^2\rv_{i,j} \cdot \gradts{\Gamma_{i,j}}\, u_i^k)
     \,dx\,d\tau\\
  \ge -{1 \over 4}\int_0^t \| \psi_{i,j}\sqrt{\nu_i\, s_{i,j}}\
  \nabla \gradts{\Gamma_{i,j}}\, u_i^k \|_i^2 \,d\tau
  -C \int_0^t\int_{\Omega_i} (\|\nabla u_i^k\|_i^2+\|u_i^k\|_i^2)
  \,dx\,d\tau.
\end{multline}

Replacing \eqref{eq:estcontorder2-3-3} in \eqref{eq:estcontorder2-3-2}
and then \eqref{eq:estcontorder2-3-2} in \eqref{eq:estcontorder2-3-1},
we obtain

\begin{equation}\label{eq:estcontorder2-3}
\begin{array}{l}
 \hspace{-4mm}{\small \mbox{$ \ds\int_0^t\int_{\Omega_i}\left(
  \partial_t u_i^k \divts{\Gamma_{i,j}}(\psi_{i,j}^2\rv_{i,j} u_i^k)
  + \div(\av_i u_i^k) \,
    \divts{\Gamma_{i,j}}(\psi_{i,j}^2\rv_{i,j} u_i^k)
    + c_i u_i^k
    \divts{\Gamma_{i,j}}(\psi_{i,j}^2\rv_{i,j} u_i^k) \right)\,dx\,d\tau$}} \\
  \ds\hspace{15mm} -{1 \over 4}\int_0^t \| \psi_{i,j}\sqrt{\nu_i\, s_{i,j}}\
  \nabla \gradts{\Gamma_{i,j}}\, u_i^k )\|_i^2 \,d\tau
  -\int_0^t\int_{\Gamma_{i,j}} \nu_i\partial_{\nv_i} u_i^k
   \, \divs{\Gamma_{i,j}}(\rv_{i,j} u_i^k)  \,d\sigma\,d\tau\\
  \ds\hspace{30mm}\le C \int_0^t\int_{\Omega_i} (\|\sqrt{\nu_i}\nabla u_i^k\|_i^2+\|\beta_iu_i^k\|_i^2)
  \,dx\,d\tau.
  \end{array}
\end{equation}

Now we multiply the first equation of \eqref{eq:algoorder2} by
$-\divts{\Gamma_{i,j}} (\psi_{i,j}^2 s_{i,j} \,\gradts{\Gamma_{i,j}}\,
u_i^k)$ integrate on $(0,t)\times \Omega_i$ and integrate by parts in
space:

\begin{multline}\label{eq:estconto2-4}
  \frac{1}{2} \| \psi_{i,j}\sqrt{s_{i,j}} \, \gradts{\Gamma_{i,j}} \,u_i^k (t)\|_i^2
   -\int_0^t\int_{\Omega_i}\div(\av_i u_i^k) \, \divts{\Gamma_{i,j}}
      (\psi_{i,j}^2 s_{i,j} \, \gradts{\Gamma_{i,j}}\, u_i^k)\,dx\,d\tau\\
    \hspace{-4mm}{\small \mbox{$ \ds+\int_0^t\int_{\Omega_i} \psi_{i,j}^2 s_{i,j} \gradts{\Gamma_{i,j}}( c_i u_i^k )
     \cdot\gradts{\Gamma_{i,j}}\, u_i^k \,dx\,d\tau
   - \int_0^t\int_{\Omega_i} \nu_i \nabla u_i^k \cdot
    \nabla (\divts{\Gamma_{i,j}}
     (\psi_{i,j}^2 s_{i,j} \, \gradts{\Gamma_{i,j}}\, u_i^k))
    \,dx\,d\tau$}}\\
   + \int_0^t\int_{\Gamma_{i,j}} \nu_i\partial_{\nv_i} u_i^k
    \, \divs{\Gamma_{i,j}}(s_{i,j} \,
    \grads{\Gamma_{i,j}}\, u_i^k)  \,d\sigma\,d\tau
   =0.
\end{multline}

We have,

\begin{align}\label{eq:estgradgrad}
  - \int_0^t\int_{\Omega_i} &\nu_i \nabla u_i^k \cdot
   \nabla (\divts{\Gamma_{i,j}}
       (\psi_{i,j}^2 s_{i,j} \, \gradts{\Gamma_{i,j}}\, u_i^k))
   \,dx\,d\tau \nonumber\\
  &\ge
    {1 \over 2}\int_0^t \| \psi_{i,j}\sqrt{\nu_{i}\, s_{i,j}}\
  \nabla \gradts{\Gamma_{i,j}}\, u_i^k )\|_i^2 \,d\tau
  - C_1 \int_0^t \|\nabla u_i^k \|_i^2 \,d\tau.
\end{align}

Replacing \eqref{eq:estgradgrad} in \eqref{eq:estconto2-4} leads to

\begin{multline}\label{eq:estcontorder2-4}
  \frac{1}{2} \| \psi_{i,j}\sqrt{s_{i,j}} \, \gradts{\Gamma_{i,j}} \,u_i^k (t)\|_i^2
  +{1 \over 2}\int_0^t \|\psi_{i,j}\sqrt{\nu_{i}\, s_{i,j}}\
  \nabla \gradts{\Gamma_{i,j}}\, u_i^k )\|_i^2 \,d\tau\\[-1mm]
    +\int_0^t\int_{\Omega_i}\psi_{i,j}^2 s_{i,j}\,c_i |\gradts{\Gamma_{i,j}}u_i^k|^2\,dx\,d\tau
  + \int_0^t\int_{\Gamma_{i,j}} \nu_i \partial_{\nv_i}u_i^k
     \, \divs{\Gamma_{i,j}}( s_{i,j} \,
    \grads{\Gamma_{i,j}}\, u_i^k)  \,d\sigma\,d\tau\\[-1mm]
\hspace{-0.5cm}
    \le
   \int_0^t\int_{\Omega_i}\div(\av_i u_i^k) \,
    \divts{\Gamma_{i,j}}
    (\psi_{i,j}^2  s_{i,j} \, \gradts{\Gamma_{i,j}}\, u_i^k)\,dx\,d\tau
  +C\int_0^t \|\sqrt{\nu_i}\nabla u_i^k\|_i^2\,d\tau.
\end{multline}

Multiplying \eqref{eq:estcontorder2-2}, \eqref{eq:estcontorder2-3} and
\eqref{eq:estcontorder2-4} by $q$, and adding the three equations with
\eqref{eq:estcontorder2-1}, we get

 \begin{multline*}
   \frac{1}{2} \left(
     \|\beta_iu_i^k(t)\|^2_i
     + q\interleave u_i^k(t)\interleave_i^2
     +q \| \psi_{i,j}\sqrt{s_{i,j}} \, \gradts{\Gamma_{i,j}} \,u_i^k (t)\|_i^2
     \right)
 + \int_0^t\interleave \beta_i u_i^k(\tau,\cdot)\interleave_i^2 \,d\tau\\
 +q \int_0^t \|\partial_t u_i^k\|^2_{i} \,d\tau
 +\frac{q}{4}
    \int_0^t \| \psi_{i,j}\sqrt{\nu_i \,s_{i,j}}\ \nabla
    \gradts{\Gamma_{i,j}}\, u_i^k \|_i^2 \,d\tau\\
 -\int_0^t \int_{\Gamma_{i,j}} \beta_i^2(\nu_i\partial_{\nv_i} u_i^k
   - \frac{\av_i\cdot\nv_i}{2}u_i^k)\, u_i^k
  \, d\sigma\,d\tau\\
 -q
    \int_0^t \int_{\Gamma_{i,j}} \nu_i\partial_{\nv_i} u_i^k
  \, \left(\partial_t u_i^k
  + \divs{\Gamma_{i,j}}(\rv_{i,j} u_i^k)
  - \divs{\Gamma_{i,j}}(s_{i,j} \, \grads{\Gamma_{i,j}}\, u_i^k)\right)
    \,d\sigma\,d\tau\\
\le
 q(\frac{1}{2}\|\av_i\|_{i,1,\infty}
  + \|\rv_{i,j}\|_{i,1,\infty})
 \int_0^t \|u_i^k\|_i \, \|\partial_t u_i^k \|_i \,d\tau\\
 + q(\|\av_i\|_{i,\infty}
    +\|\rv_{i,j}\|_{i,\infty})
  \int_0^t \|\nabla u_i^k\|_i \, \|\partial_t u_i^k \|_i
\,d\tau\\
 + \frac{q}{2} \|\av_i\|_{i,\infty}
   \int_0^t \|\nabla u_i^k\|_i \,
     \|\divts{\Gamma_{i,j}}
 (\psi_{i,j}^2 s_{i,j} \, \gradts{\Gamma_{i,j}}\, u_i^k)\|_i\,d\tau \\
 +  q(\frac{1}{2}\|\av_i\|_{i,1,\infty} +\|c_i\|_{i,\infty})
   \int_0^t \| u_i^k\|_i \,
     \|\divts{\Gamma_{i,j}}
 (\psi_{i,j}^2 s_{i,j} \, \gradts{\Gamma_{i,j}}\, u_i^k)\|_i\,d\tau \\
     +\frac{q}{2}(\|\av_i\|_{i,1,\infty} +\|c_i\|_{i,\infty})\|u_i^k(t)\|_i^2
 + C \left(\int_0^t \|\beta_iu_i^k\|_i^2 \,d\tau
    +q \int_0^t \|\sqrt{\nu_i}\nabla u_i^k\|_i^2 \,d\tau \right).
\end{multline*}

We bound the right-hand side by

\begin{multline*}
 {1 \over 2} \left(
 \frac{q}{2} \int_0^t \|\partial_t u_i^k \|_i^2 \,d\tau
 +\frac{q}{4} \int_0^t
     \|\psi_{i,j}\sqrt{\nu_i \, s_{i,j}} \ \nabla \gradts{\Gamma_{i,j}}\, u_i^k\|_i^2\,d\tau
  \right)\\
   +\frac{q}{2}(\|\av_i\|_{i,1,\infty} +\|c_i\|_{i,\infty})\|u_i^k(t)\|_i^2
 + C \left(\int_0^t \|\beta_iu_i^k\|_i^2 \,d\tau
    +q \int_0^t \|\sqrt{\nu_i}\nabla u_i^k\|_i^2 \,d\tau \right).
\end{multline*}

We simplify the terms which appear on both sides, and obtain

\begin{multline}\label{eq:estbtm4}
 \frac{1}{2} \left(
   \|\beta_iu_i^k(t)\|^2_i
   + q\interleave u_i^k(t)\interleave_i^2
   +q \| \psi_{i,j}\sqrt{s_{i,j}} \, \gradts{\Gamma_{i,j}} \,u_i^k (t)\|_i^2
   \right)
 + \int_0^t\interleave \beta_iu_i^k(\tau,\cdot)\interleave_i^2 \,d\tau\\
 +\frac{q}{2} \int_0^t \|\partial_t u_i^k\|^2_{i} \,d\tau
 +\frac{q}{8}
    \int_0^t \|\psi_{i,j} \sqrt{\nu_i \, s_{i,j}}\ \nabla
    \gradts{\Gamma_{i,j}}\, u_i^k \|_i^2 \,d\tau\\
 -\int_0^t \int_{\Gamma_{i,j}} \beta_i^2(\nu_i\partial_{\nv_i} u_i^k
   - \frac{\av_i\cdot\nv_i}{2}u_i^k)\, u_i^k
  \, d\sigma\,d\tau\\
 -q
    \int_0^t \int_{\Gamma_{i,j}} \nu_i\partial_{\nv_i} u_i^k
  \, \left(\partial_t u_i^k
+ \divs{\Gamma_{i,j}}(\rv_{i,j} u_i^k)
  - \divs{\Gamma_{i,j}}(s_{i,j} \, \grads{\Gamma_{i,j}}\, u_i^k)\right)
    \,d\sigma\,d\tau\\
\le
C \left(\int_0^t \|\beta_iu_i^k\|_i^2 \,d\tau
    +q \int_0^t \|\sqrt{\nu_i}\nabla u_i^k\|_i^2 \,d\tau \right).
\end{multline}

Recalling that $s_{i,j}=s_{j,i}$ on $\Gamma_{i,j}$ and
$\rv_{i,j}=\rv_{j,i}$ on $\Gamma_{i,j}$, we use now:

\begin{multline}\label{eq:esttransmcd}
  \left(\nu_i \partial_{\nv_i} u_i^k
   - \av_i\cdot\nv_i u_i^k + \mathcal{S}_{i,j} u_i^k\right)^2
- \left(\nu_i \partial_{\nv_i} u_i^k
   - \av_i\cdot\nv_i u_i^k - \mathcal{S}_{j,i} u_i^k\right)^2\\
\hspace{-4mm}{\small \mbox{$ \ds = 4\left(\beta_{i,j}^2( \nu_i \partial_{\nv_i} u_i^k
   - \frac{\av_i\cdot\nv_i}{2}u_i^k)u_i^k + q \nu_i \partial_{\nv_i} u_i^k
   (\partial_t u_i^k
+\divs{\Gamma_{i,j}}(\rv_{i,j} u_i^k)
-\divs{\Gamma_{i,j}}(s_{i,j} \, \grads{\Gamma_{i,j}}\, u_i^k))\right)$}}
\\
    +2q(p_{i,j}-p_{j,i}-2\av_i\cdot\nv_i)(\partial_t u_i^k
+\divs{\Gamma_{i,j}}(\rv_{i,j} u_i^k)
-\divs{\Gamma_{i,j}}(s_{i,j} \, \grads{\Gamma_{i,j}}\, u_i^k))u_i^k\\
+(p_{i,j}+p_{j,i})(p_{i,j}-p_{j,i}-\av_i\cdot\nv_i)(u_i^k)^2.
\end{multline}

Replacing \eqref{eq:esttransmcd} into \eqref{eq:estbtm4}, we
obtain

\vspace{-1.5mm}

\begin{multline}\label{eq:esttransmcd2}
  {1\over 2}\left(
   \|\beta_{i} u_i^k(t)\|^2_i
   + q\interleave u_i^k(t)\interleave_i^2
   +q \|\psi_{i,j}\sqrt{s_{i,j}} \, \gradts{\Gamma_{i,j}} \,u_i^k (t)\|_i^2
   \right)
 + \int_0^t\interleave \beta_{i}u_i^k(\tau,\cdot)\interleave_i^2 \,d\tau \\
 +\frac{q}{2} \int_0^t \|\partial_t u_i^k\|^2_{i} \,d\tau
 +\frac{1}{4}
   \int_0^t \int_{\Gamma_{i,j}}
    \left(\nu_i \partial_{\nv_i}u_i^k
  -\av_i\cdot\nv_i \, u_i^k - \mathcal{S}_{j,i} u_i^k\right)^2\,d\sigma\,d\tau \\
  +\frac{q}{8}
    \int_0^t \| \psi_{i,j}\sqrt{\nu_i \, s_{i,j}}\ \nabla
    \gradts{\Gamma_{i,j}}\, u_i^k \|_i^2 \,d\tau
  \le
\frac{1}{4}
   \int_0^t \int_{\Gamma_{i,j}}
    \left(\nu_i \partial_{\nv_i}u_i^k
  -\av_i\cdot\nv_i \, u_i^k + \mathcal{S}_{i,j} u_i^k\right)^2\,d\sigma\,d\tau \\
    + \int_0^t \int_{\Gamma_{i,j}}
 (p_{i,j}+p_{j,i})(-p_{i,j}+p_{j,i}+\av_i\cdot\nv_i)(u_i^k)^2 \,d\sigma\,d\tau
+\frac{q}{2}(\|\av_i\|_{i,1,\infty} +\|c_i\|_{i,\infty})\|u_i^k(t)\|_i^2   \\
+{q \over 2}\int_0^t \int_{\Gamma_{i,j}}
 (-p_{i,j}+p_{j,i}+2\av_i\cdot\nv_i)
(\partial_t u_i^k +\divs{\Gamma_{i,j}}(\rv_{i,j} u_i^k)
-\divs{\Gamma_{i,j}}(s_{i,j} \, \grads{\Gamma_{i,j}}\, u_i^k))\,u_i^k\,d\sigma\,d\tau\\
+ C \left(\int_0^t \|\beta_{i}u_i^k\|_i^2 \,d\tau
    +q \int_0^t \|\sqrt{\nu_i}\nabla u_i^k\|_i^2 \,d\tau \right).
\end{multline}

In order to estimate the fourth term in the right-hand side of
\eqref{eq:esttransmcd2}, we observe that

\begin{equation*}
\int_0^t \int_{\Gamma_{i,j}} (-p_{i,j}+p_{j,i}+2\av_i\cdot\nv_i)u_i^k
\,\partial_t u_i^k\,d\sigma\,d\tau
= {1 \over 2} \int_{\Gamma_{i,j}} (-p_{i,j}+p_{j,i}+2\av_i\cdot\nv_i)u_i^k (t)^2 \,d\sigma.
\end{equation*}

By the trace theorem in the right-hand side, we write:

\begin{equation*}
\int_0^t \int_{\Gamma_{i,j}} (-p_{i,j}+p_{j,i}+2\av_i\cdot\nv_i)u_i^k
\,\partial_t u_i^k\,d\sigma\,d\tau
\le C \|u_i^k (t)\|_i \|\sqrt{\nu_i}\nabla u_i^k (t)\|_i,
\end{equation*}

and
\vspace{-3mm}

\begin{equation}\label{eq:estut}
\|u_i^k (t)\|_i^2 = 2 \int_0^t \int_{\Omega_i} (\partial_t u_i^k)u_i^k
\le 2 \left(\int_0^t \|\partial_t u_i^k\|_i^2\right)^{1 \over 2}
      \left(\int_0^t \|u_i^k\|_i^2\right)^{1 \over 2},
\end{equation}

we obtain

\begin{multline}\label{eq:esttrace}
{q \over 2}\
\int_0^t \int_{\Gamma_{i,j}} (-p_{i,j}+p_{j,i}+2\av_i\cdot\nv_i) u_i^k
\,\partial_t u_i^k\,d\sigma\,d\tau\\
\le\frac{q}{8} \int_0^t \| \partial_t u_i^k\|_i^2 \,d\tau
+\frac{q}{4}\interleave u_i^k(t)\interleave_i^2
+C \left(\int_0^t  \| \beta_{i}u_i^k\|_i^2  \,d\tau
\right).
\end{multline}
\vspace{-1mm}

Moreover, integrating by parts and using the trace theorem, we have
\vspace{-1mm}

\begin{multline}\label{eq:estimtt1}
\ds  -\frac{q}{2} \int_0^t \int_{\Gamma_{i,j}}
     \divs{\Gamma_{i,j}}(s_{i,j} \, \grads{\Gamma_{i,j}}\, u_i^k)
    (-p_{i,j}+p_{j,i}+2\av_i\cdot\nv_i) u_i^k \,d\sigma\,d\tau \\
     \hspace{-1.5cm}
\ds \le \frac{q}{16} \int_0^t
         \|\psi_{i,j}\sqrt{\nu_i \, s_{i,j}}\ \nabla \gradts{\Gamma_{i,j}}\, u_i^k \|_i^2 \,d\tau
+ C (\int_0^t \| \gradts{\Gamma_{i,j}}\, u_i^k \|_i^2\,d\tau
+ \int_0^t \| \beta_{i} u_i^k \|_i^2\,d\tau).
\end{multline}

Using \eqref{eq:estut}, we estimate the third term in the right-hand
side of \eqref{eq:esttransmcd2} by

\begin{equation}\label{eq:esttrace2}
\frac{q}{2}(\|\av_i\|_{i,1,\infty} +\|c_i\|_{i,\infty})\|u_i^k(t)\|_i^2
\le\frac{q}{8} \int_0^t \| \partial_t u_i^k\|_i^2 \,d\tau
+C \int_0^t  \| \beta_{i}u_i^k\|_i^2  \,d\tau.
\end{equation}

Replacing \eqref{eq:estimtt1}, \eqref{eq:esttrace} and
\eqref{eq:esttrace2} in \eqref{eq:esttransmcd2}, then using
the transmission conditions, we have:

\begin{multline*}
  {1\over 2}\left(
   \|\beta_{i}  u_i^k(t)\|^2_i
   + \frac{q}{2}\interleave u_i^k(t)\interleave_i^2
   +q \| \psi_{i,j}\sqrt{s_{i,j}} \, \gradts{\Gamma_{i,j}} \,u_i^k (t)\|_i^2
   \right)\\
  + \int_0^t\interleave \beta_{i} u_i^k(\tau,\cdot)\interleave_i^2 \,d\tau
  +\frac{q}{4} \int_0^t \|\partial_t u_i^k\|^2_{i} \,d\tau
 +\frac{q}{16}
    \int_0^t \| \psi_{i,j}\sqrt{\nu_i\, s_{i,j}}\ \nabla \,
    \gradts{\Gamma_{i,j}}\, u_i^k \|_i^2 \,d\tau\\
 +\frac{1}{4}
   \int_0^t \int_{\Gamma_{i,j}}
    \left(\nu_i \partial_{\nv_i}u_i^k
  -\av_i\cdot\nv_i \, u_i^k - \mathcal{S}_{j,i} u_i^k\right)^2\,d\sigma\,d\tau\\
 \le
 \frac{1}{4}
   \int_0^t \int_{\Gamma_{i,j}}
    \left(\nu_j \partial_{\nv_i}u_j^{k-1}
  -\av_j\cdot\nv_i \, u_j^{k-1} +\mathcal{S}_{i,j}
     u_j^{k-1}\right)^2\,d\sigma\,d\tau\\
 + C \left(\int_0^t \|\beta_{i} u_i^k\|_i^2 \,d\tau
    +\frac{q}{2}  \int_0^t \|\sqrt{\nu_i}\,\nabla u_i^k\|_i^2 \,d\tau \right).
\end{multline*}

We now sum up over the interfaces $j \in {\cal N}_i$, then over the
subdomains for $1 \le i \le I$, and on the iterations for $1 \le k \le
K$, the boundary terms cancel out, and we obtain for any $t \in
(0,T)$,

\begin{multline}
\sum_{k\in \inter{1,K}}\sum_{i\in \inter{1,I}}
  \left(\|\beta_{i,j}u_i^k(t)\|^2_i+q \|\sqrt{\nu_i}\,\nabla u_i^k(t)\|_i^2
+\nu_0 \int_0^t \|\nabla (\beta_{i,j}u_i^k) \|_i^2 \,d\tau \right)\\
\le \alpha(t)+C \sum_{k\in \inter{1,K}}\sum_{i\in \inter{1,I}}
\left(\int_0^t \|\beta_{i,j}u_i^k\|_i^2 \,d\tau
    +q \int_0^t \|\sqrt{\nu_i}\,\nabla u_i^k\|_i^2 \,d\tau \right),
\end{multline}

with

\begin{equation}
\alpha(t)=\frac{1}{4}\sum_{i\in \inter{1,I}} \sum_{j\in{\cal N}_i}
 \int_0^t \int_{\Gamma_{i,j}}
  \left(\nu_j \partial_{\nv_i} u_i^0
  -\av_j\cdot\nv_i \, u_j^0 +\mathcal{S}_{i,j}
     u_j^0\right)^2\,d\sigma\,d\tau.
\end{equation}

We conclude with Gr\"{o}nwall's lemma as before.
\end{proof}

\section{The discontinous Galerkin time stepping for the Schwarz waveform relaxation algorithm}

\label{section:dgoswr}

In the following sections, in order to simplify the analysis, we suppose that $c+{1 \over 2}\div \av \ge \alpha_0> 0$ \textit{
  a.e.} in $\Omega$.\\

\subsection{Time discretization of the local problem: discontinuous Galerkin method}

We suppose that the coefficients are
restricted to $p -\frac{\av\cdot\nv}{2}+{q \over 2}\nabla_{\Gamma}
\cdot\rv >0$ \ \textit{a.e.} on $\Gamma$, $q \ge 0 \ a.e.$ and $s>0$ \textit{a.e.}. This implies that the bilinear form $a$  defined in \eqref{eq:formbilin}

is positive definite on $H^1(\co)$ when $q=0$, and
positive definite on $H^1_1(\co)$ when $q\ge q_0 >0$ a.e.

We recall the time-discontinuous Galerkin method, as presented in
\cite{johnson:1985:dgfirst}.  We are given a decomposition ${\cal T}$
of the time interval $(0,T)$, $I_n=(t_n,t_{n+1}]$, for $0 \le n \le N$,
the mesh size is $k_n=t_{n+1}-t_n$. For ${\cal B}$ a Banach space and
$I$ an interval of $\R$, define for any integer $d \ge 0$

\begin{eqnarray}
  \begin{array}{rcl}
    {\mathbf{P}}_{d}({\cal B})&=&\{\varphi:I\rightarrow {\cal B}, \ \varphi(t)=
    \displaystyle\sum_{i=0}^{d } \varphi_i t^i,
    \ \varphi_i \in {\cal B}\} , \\
    {\cal P}_d({\cal B},{\cal T})&=&\{\varphi:I\rightarrow {\cal B}, \
    \varphi_{\mid I_{n}} \in
    {\mathbf{P}}_{d}({\cal B}), \ 1 \le n \le N\}.
  \end{array} \nonumber
\end{eqnarray}

Let ${\cal B}=H_1^1(\co)$ if $q > 0$, ${\cal B}=H^1(\co )$ if $q = 0$.
We define an approximation $U$ of $u$, polynomial of degree lower than
$d$ on every subinterval $I_n$. For every point $t_n$, we define
$U(t_n^{-})=\lim_{t \rightarrow t_n-0} U(t)$, and note
$U(t_n^{+})=\lim_{t \rightarrow t_n+0} \uud(t)$. The time discretization of \eqref{eq:formvariat} leads to searching $U\in
{\cal P}_d({\cal B},{\cal T})$ such that

\begin{eqnarray}\label{eq:dGvariat}
  \left\{ \begin{array}{l}
      U(0,\cdot)=u_0, \\
      \forall \, V \in {\cal P}_d({\cal B},{\cal T})\colon
      \displaystyle
      \int_{I_{n}} (\,m(\dot{U},V ) +a(U,V))\,dt\\
      \hspace{20mm}+m(U(t_n^+,\cdot)-U(t_n^-,\cdot),V(t_n^+,\cdot))
      = \displaystyle\int_{I_{n}}L(V ) \,dt,
      \quad
    \end{array}\right.
\end{eqnarray}

with $L(V )= (f,V)_{L^2(\co)}+(g,V)_{L^2(\Gamma)}$.  Since $I_n$ is
closed at $t_{n+1}$, $U(t_{n+1}^-)$ is the value of $U$ at $t_{n+1}$.
Due to the discontinuous nature of the test and trial spaces, the
method is an implicit time stepping scheme, and $U\in
{\mathbf{P}}_d({\cal B},{\cal T})$ is obtained recursively on each
subinterval, which makes it very flexible.

\begin{theorem}\label{th:existdisc}
  If $p -\frac{\av\cdot\nv}{2}+{q \over 2}\nabla_{\Gamma} \cdot\rv >0$
  \ \textit{a.e.} on $\Gamma$, $q \ge 0 \ a.e.$ and $s>0 \ a.e.$,
  equation \eqref{eq:dGvariat} defines a unique solution.
\end{theorem}

\begin{proof}
The result relies on the fact that the bilinear form $a$ is definite
positive.  It is is most easily seen by using a basis of Legendre
polynomials.  $U\in {\cal P}_d(H_1^1(\Omega),{\cal T})$ is obtained
recursively on each subinterval. We introduce the Legendre polynomials
$L_n$, orthogonal basis in $L^2(-1,1)$, with $L_n(1)=1$. $L_n$ has the
parity of $n$, hence $L_n(-1)=(-1)^n$. A basis of orthogonal
polynomial on $I_n$ is given by $L_{n,k}(t)=L_k(\frac{2}{k_n}
(t-\frac{t_{n+1}+t_n}{2}))$.  Choose $V(t,x)=L_{n,j}(t)\Phi_j(x)$ in
\eqref{eq:dGvariat} with $\Phi_j\in H_1^1(\Omega)$, and expand $U$ on
$I_n$ as $U(t,x)=\sum_{k=0}^d U_k(x)L_{n,k}(t)$. Suppose $U$ to be
given on $(0,t_n]$. In order to determine $U$ on $I_n$, we must solve
  the system: for any $\Phi_j\in H_1^1(\Omega)$,

\[
  \begin{split}
    \sum_{k=0}^d\ \int_{I_{n}} \biggl(\dot{L}_{n,k}L_{n,j}m(U_k,\Phi_j) +
    L_{n,k}L_{n,j}a(U_k,\Phi_j) \biggr) \,dt\\
    + \sum_{k=0}^d L_{n,k}(t_n^+)L_{n,j}(t_n^+)m(U_k,\Phi_j)=
    \displaystyle\int_{I_{n}} L_{n,j} L(\Phi_j) \,dt.
  \end{split}
\]

It is an implicit scheme. We calculate the coefficients

\begin{align}
  &\int_{I_{n}} L_{n,k}L_{n,j}=\delta_{kj}\|L_{n,j}\|^2,\nonumber\\
  &\int_{I_{n}}\dot{L}_{n,k}L_{n,j}=
  \begin{cases}
    0 & \text{ if $k \le j$}\\
    1-(-1)^{k+j} & \text{ if $k > j$},
  \end{cases} \nonumber\\
  & \int_{I_{n}}\dot{L}_{n,k}L_{n,j}+ L_{n,k}(t_n^+)L_{n,j}(t_n^+)=
  \begin{cases}
    (-1)^{k+j} & \text{ if $k \le j$}\\
    1 & \text{ if $k > j$},
  \end{cases}
  \nonumber
\end{align}

which leads to

{\small
\begin{eqnarray}
 \|L_{n,j}\|^2 a(U_j, \Phi_j)+ m(U_j,\Phi_j)+ \sum_{k<j}(-1)^{k+j}
  m(U_k, \Phi_j)+
  \sum_{k>j}m(U_k, \Phi_j)= \nonumber
  \displaystyle\int_{I_{n}} L_{n,j} L(\Phi_j) \,dt . \nonumber
\end{eqnarray}
}

It is a square system of partial differential equations, of the type coercive $+$ compact.  By the Fredholm alternative, we only need to
prove uniqueness. Choose now $\Phi_j=U_j$, and obtain

\[
  \sum_j\|L_{n,j}\|^2a(U_j,U_j)+\sum_jm(U_j,U_j)
  +2\sum_j \sum_{\substack{k>j \\ k+j \ \mbox{even}}}m(U_k, U_j)= 0,
\]

and since $a$ is positive definite, we deduce that $U=0$.
\end{proof}

We will make use of the following remark
(\cite{makridakis:2007:pea}). We introduce the Gauss-Radau points,
$(0<\tau_1,\dotsc,\tau_{d+1}=1)$, defined such that the quadrature
formula

\[
  \int_0^1 f(t) dt\approx \sum_{j=1}^{d+1} w_q \ f(\tau_q)
\]

is exact in $\PP_{2d}$, and the interpolation operator ${\cal I}_n$ on
$[t_n,t_{n+1}]$ at points
$(t_n,t_n+\tau_1k_n,\dotsc,t_n+\tau_{d+1}k_n)$.  For any $\chi \in
\PP_{d}$, $\hat{\chi}={\cal I}_n\chi \in\PP_{d+1}$.

Let ${\cal I}: {\cal P}_d({\cal B},{\cal T}) \rightarrow {\cal
  P}_{d+1}({\cal B},{\cal T})$ be the operator whose restriction to
each subinterval is ${\cal I}_n$ and satisfies ${\cal
  I}U(t_n^+)=U(t_n^-)$.  By using the Gauss-Radau formula, which is
exact in $\PP_{2d}$, we have for all $\psi_{i,j} \in \PP_{d}$

\[
  \int_{I_n>}\dtq{{\cal I\chi}}\psi_{i,j} \, dt- \int_{I_n}\dtq{\chi}\psi_{i,j} \, dt=
  (\chi(t_{n}^+)-\chi(t_{n}^-)) \psi_{i,j}(t_{n}^+).
\]

As a consequence, we have a very useful inequality:

\begin{equation}\label{eq:interpradau2}
  \int_{I_n}\frac{d}{dt}({\cal I}\psi_{i,j})\psi_{i,j} dt
  \ge {1 \over 2}[\psi_{i,j}(t^-_{n+1})^2-\psi_{i,j}(t^-_{n})^2].
\end{equation}

Also, equation \eqref{eq:dGvariat} can be rewritten as

\begin{equation}\label{eq:dGvariatinterp}
  \int_{I_{n}} (\,m(\,\dtq{{\cal I} U },V ) +a(U,V))\,dt=
  \displaystyle\int_{I_{n}}L(V ) \,dt,
\end{equation}

or in  the strong formulation:

\begin{equation}\label{eq:dGstronginterp}
  \begin{array}{l}
    \partial_t ({\cal I} U ) +\div(\av U-\nu\nabla U)+cU= P f, \mbox{ in }
    \Omega\times (0,T) ,\\[2mm]
    \ds\bigl(\nu\,\partial_{\nv}- \av\cdot\nv \bigr)U +
    p\,U + q(\partial_t ({\cal I} U)   + \divs{\Gamma}(\rv U -s\grads{\Gamma}U))
    =Pg \mbox{ on } \Gamma\times (0,T). \\
  \end{array}
\end{equation}

Here $P$ is the projection $L^2$ in each subinterval of ${\cal T}$ on $\PP_d$.

\begin{theorem}[Thomee, \cite{thomee:1997:FEM}]
Let $\uud$ be the solution of \eqref{eq:dGvariat} and $\uu$ the solution of \eqref{eq:pblim}. Under the assumptions of Theorem \ref{th:exfortefo},  the estimate holds

\begin{align}
  \|\uu-\uud\|_{L^\infty(I_n,L^2(\Omega))}\le C k^{d+1}
  \|\partial_t^{d+1}\uu\|_{L^2(0,T;H_2^2(\Omega))},
\end{align}

with $k=\max_{0 \le n \le N} k_n$.
\end{theorem}

\subsection{The discrete in time optimized Schwarz waveform relaxation
algorithm with different subdomains grids}

In this part we present and analyse the discrete non conforming in
time optimized Schwarz waveform relaxation method.

The time partition in subdomain $\Omega_i$, is ${\cal T}_i$, with $N_i
+1$ intervals $I_n^i$, and mesh size $k_n^i$. In view of formulation
\eqref{eq:dGstronginterp}, we define interpolation operators ${\cal
  I}^i$ and projection operators $P^i$ in each subdomain,
i.e. $P^i$ is the projection $L^2$ in each subinterval of ${\cal T}_i$ on $\PP_d$,
and we solve

\begin{subequations}\label{eq:algosdorder2}
  \begin{align}
    & \partial_t ({\cal I}^iU_i^k)
     +\div(\av_i U_i^k -\nu_i\nabla U_i^k)
    +c_i\,U_i^k=P^if\mbox{ in }\Omega_i\times(0,T),\label{eq:algosdorder2-1}\\
    &\ds\bigl(\nu_i \partial_{\nv_i}
    -\av_i\cdot\nv_i \bigr)\,U_i^{k} +S_{i,j}U_i^{k} =

    P^i\bigl((\nu_{j} \partial_{\nv_i}
    -\av_{j}\cdot\nv_{i})\, U_{j}^{k-1}
    +\widetilde{S}_{i,j}U_{j}^{k-1}\bigr)
    \mbox{ on }\Gamma_{i,j}, j\in {\cal N}_i.\label{eq:algosdorder2-2}
  \end{align}
\end{subequations}

Here the operators are different on either part of the "equal" sign:

\begin{equation}
  \begin{array}{l}
    S_{i,j}U= p_{i,j}\,U + q_{i,j}\, (\partial_t ({\cal I}^i U)
    + \divs{\Gamma_{i,j}}(\rv_{i,j}U-s_{i,j}\grads{\Gamma_{i,j}}U)) \\
    \widetilde{S}_{i,j}U= p_{i,j}\,U + q_{i,j}\, (\partial_t ({\cal I}^j U)
    + \divs{\Gamma_{i,j}}(\rv_{i,j}U-s_{i,j}\grads{\Gamma_{i,j}}U)).
  \end{array}
\end{equation}

Formally, the sequence of problems \eqref{eq:algosdorder2} converges to the solution of

\begin{subequations}\label{eq:dgdiscreteall}
  \begin{align}
    & \partial_t ({\cal I}^iU_i)
     +\div(\av_i U_i -\nu_i\nabla U_i)
    +c_i\,U_i=P^if\mbox{ in }\Omega_i\times(0,T),\label{eq:dgdiscreteall-1}\\
    &\ds\bigl(\nu_i \partial_{\nv_i}
    -\av_i\cdot\nv_i \bigr)\,U_i +S_{i,j}U_i =

    P^i\bigl((\nu_{j} \partial_{\nv_i}
    -\av_{j}\cdot\nv_{i})\, U_{j}
    +\widetilde{S}_{i,j}U_{j}\bigr)
    \mbox{ on }\Gamma_{i,j}, j\in {\cal N}_i.\label{eq:dgdiscreteall-2}
  \end{align}
\end{subequations}

We present the analysis first with Robin transmission conditions
(e.g. $q_{i,j}=0$) and general decomposition, and then with order 2
transmission conditions and decomposition in strips.

\subsubsection{The Robin case}

We consider here a general decomposition of the domain, possibly
with corners.  We solve \eqref{eq:algosdorder2} with $q_{i,j}=0$, i.e.
$S_{i,j}U= \widetilde{S}_{i,j}U = p_{i,j}\,U $.

\begin{theorem}
  Assume $q_{i,j}=0$, $p_{j,i}-p_{i,j}-\av_i \cdot \nv_i=0,
  \ p_{i,j}-\frac{\av_i \cdot \nv_i}{2} > 0$. Problem \eqref{eq:dgdiscreteall}
  has a unique solution $(U_i)_{i \in I}$ , and $U_i$ is the limit of
  the iterates of algorithm \eqref{eq:algosdorder2}.
\end{theorem}

\begin{proof}
We first write energy estimates on \eqref{eq:algosdorder2} for $f\equiv 0$ and $u_0\equiv 0$. We start like in the proof of Theorem \ref{th:convcont}. We multiply
\eqref{eq:algosdorder2-1} by $U_i^k$, integrate on $\Omega_i$, then
integrate on the interval $(t_n^i, t_{n+1}^i)$ and use \eqref{eq:interpradau2}
and \eqref{tototiti}:

\begin{multline*}
  \|U_i^k(t^i_{n+1})\|^2_{L^2(\Omega_i)}-\|U_i^k(t^i_{n})\|^2_{L^2(\Omega_i)}\\
  +2\int_{I_n^i}\bigl((\nu_i\nabla U_i^k,\nabla U_i^k)_{L^2(\Omega_i)}
                    + ((c_i+{1 \over 2}\div \av_i) U_i^k,U_i^k)_{L^2(\Omega_i)}\bigr) \,d\tau\\
  +
   \sum_{j\in{\cal N}_i}\int_{I_n^i}\int_{\Gamma_{i,j}}
  \frac{1}{p_{i,j}+p_{j,i}}
  \bigl(\nu_i \partial_{\nv_i} u_i^k
  -{\av_i\cdot\nv_i} U_i^k-p_{j,i}U_i^k\bigr)^2 d\sigma\,d\tau \\
   \leq
  \sum_{j\in{\cal N}_i}\int_{I_n^i}\int_{\Gamma_{i,j}}
  \frac{1}{p_{i,j}+p_{j,i}}
  \bigl(\nu_i \partial_{\nv_i} u_i^k-{\av_i\cdot\nv_i}
  U_i^k +p_{i,j}U_i^k\bigr)^2d\sigma\,d\tau\\
  +\sum_{j\in{\cal N}_i}\int_{I_n^i}\int_{\Gamma_{i,j}}(p_{j,i}-p_{i,j}-\av_i \cdot \nv_i)
  (U_i^k)^2d\sigma \,d\tau.
\end{multline*}

We can not use Gr\"{o}nwall's Lemma like in the continuous case, due to the
presence of the global in time projection operator ${\cal P}^j$ in the transmission
conditions. Therefore we have to assume that $p_{j,i}-p_{i,j}-\av_i \cdot \nv_i=0$
everywhere, which cancels the last term.

We sum up over the time intervals, using the fact that the errors vanish at time 0:

\begin{multline*}
  \|U_i^k(T)\|^2_{L^2(\Omega_i)}
  +2\min(\nu_0,\alpha_0)\int_{0}^T\|U_i^k\|^2_{H^1(\Omega_i)}\,d\tau\\
  +\sum_{j\in{\cal N}_i}\int_{0}^T
   \int_{\Gamma_{i,j}}
  \frac{1}{p_{i,j}+p_{j,i}}
  \bigl(\nu_i \partial_{\nv_i} u_i^k
  -{\av_i\cdot\nv_i} U_i^k-p_{j,i}U_i^k\bigr)^2 d\sigma\,d\tau \\
  \le
  \sum_{j\in{\cal N}_i}\int_{0}^T\int_{\Gamma_{i,j}}
  \frac{1}{p_{i,j}+p_{j,i}}
  \bigl(\nu_i \partial_{\nv_i} u_i^k
  -{\av_i\cdot\nv_i} U_i^k+p_{i,j}U_i^k\bigr)^2d\sigma\,d\tau.
\end{multline*}

We now insert the transmission conditions

\begin{multline*}
  \|U_i^k(T)\|^2_{L^2(\Omega_i)}+2\min(\nu_0,\alpha_0)
  \int_{0}^T\|U_i^k\|^2_{H^1(\Omega_i)}\,d\tau\\
  +
   \sum_{j\in{\cal N}_i}\int_{0}^T\int_{\Gamma_{i,j}}
   \frac{1}{p_{i,j}+p_{j,i}}
   \bigl(\nu_i \partial_{\nv_i} u_i^k
  -{\av_i\cdot\nv_i} U_i^k-p_{j,i}U_i^k\bigr)^2 d\sigma\,d\tau \\
   \le
  \sum_{j\in{\cal N}_i}\int_{0}^T\int_{\Gamma_{i,j}}
  \frac{1}{p_{i,j}+p_{j,i}}
  \biggl(P^i \bigl(\nu_j
  \partial_{\nv_i}U_j^{k-1}-{\av_j\cdot\nv_i} U_j^{k-1}
  \, +p_{i,j}U_j^{k-1} \bigr)\biggr)^2d\sigma\,d\tau.
\end{multline*}

We use the fact that the projection operator is a contraction to obtain:

\begin{multline*}
  \|U_i^k(T)\|^2_{L^2(\Omega_i)}+2\min(\nu_0,\alpha_0)
   \int_{0}^T\|U_i^k\|^2_{H^1(\Omega_i)}
  \,d\tau\\
  + \sum_{j\in{\cal N}_i}\int_{0}^T\int_{\Gamma_{i,j}}
  \frac{1}{p_{i,j}+p_{j,i}}
  \bigl(\nu_i \partial_{\nv_i} u_i^k
  -{\av_i\cdot\nv_i} U_i^k-p_{j,i}U_i^k\bigr)^2 d\sigma\,d\tau \\
   \le
  \sum_{j\in{\cal N}_i}\int_{0}^T\int_{\Gamma_{j,i}}
  \frac{1}{p_{i,j}+p_{j,i}}
  \bigl(\nu_j \partial_{\nv_j}U_j^{k-1}
  -{\av_j \cdot\nv_j} U_j^{k-1}\, -p_{i,j}U_j^{k-1}\bigr)^2d
  \sigma\,d\tau.
\end{multline*}

We sum up over the subdomains, we define the boundary term

\[
  B^k=
  \sum_{i \in \inter{1,I}}\sum_{j\in{\cal N}_i}\int_{0}^T
  \int_{\Gamma_{i,j}} \frac{1}{p_{i,j}+p_{j,i}}
  \bigl(\nu_i \partial_{\nv_i} u_i^k
  -{\av_i\cdot\nv_i} U_i^k-p_{j,i}U_i^k\bigr)^2 d\sigma\,d\tau,
\]

we obtain

\begin{equation}\label{eq:est5b}
  \sum_{i \in \inter{1,I}}(\|U_i^k(T)\|^2_{L^2(\Omega_i)}
  +2\min(\nu_0,\alpha_0)\int_{0}^T\|U_i^k\|^2_{H^1(\Omega_i)}\,d\tau) +B^k \le   B^{k-1}.
\end{equation}

We first apply this inequality to prove the first part of the Theorem. \eqref{eq:dgdiscreteall} is a square discrete system, and proving well-posedness is equivalent to proving uniqueness. Dropping the superscript in \eqref{eq:est5b} gives the result.
As for the convergence, we proceed as in the continuous case by summing \eqref{eq:est5b} over the iterates to obtain that $\sum_{i \in \inter{1,I}}\|U_i^k(T)\|^2_{L^2(\Omega_i)}$ and
$\sum_{i \in \inter{1,I}}\int_{0}^T\|U_i^k\|^2_{H^1(\Omega_i)}\,d\tau$ tend to zero as $k$
tend to infinity.
\end{proof}

\subsubsection{The Order 2 case}

We restrict ourselves to a splitting of the domain into strips with parallel planar interfaces.

\begin{theorem}\label{th:convdiscRobin}
  We assume that $p_{i,j}=p>0$, $q_{i,j}=q>0$, $s_{i,j}=s>0$,
  $\av_i=0$ and $\rv_{i,j}=0$. Problem \eqref{eq:dgdiscreteall} has a
  unique solution $(U_i)_{i\in I}$, and $U_i$ is the limit of the
  iterates of algorithm \eqref{eq:algosdorder2}.
\end{theorem}

\begin{proof}
We consider the algorithm \eqref{eq:algosdorder2} on the error, so we
suppose $f=u_0=0$. As in the continuous case, the proof is based on energy estimates containing
the term

$$\int_{I_n^i} \int_{\Gamma_{i,j}}
    \left(\nu_i\partial_{\nv_i} u_i^k
  + \mathcal{S}_{i,j} U_i^k\right)^2\,d\sigma\,d\tau,
$$

and that we derive by multiplying successively the first equation of
\eqref{eq:algosdorder2} by the terms $\,U_i^k$, $\partial_t ({\cal
  I}^iU_i^k)$, and $-\Delta_{\Gamma_{i,j}}\, U_i^k$.  We set
$\interleave\varphi\interleave_i^2= \|\sqrt{\nu_i}\,\nabla
\varphi\|^2_{L^2(\Omega_i)} +
\|\sqrt{c_i}\,\varphi\|^2_{L^2(\Omega_i)}$.  We multiply the first
equation of \eqref{eq:algosdorder2} by $\,U_i^k$, we integrate on
$I_n^i \times \Omega_i$ then integrate by parts in space and use
\eqref{eq:interpradau2}:

\begin{multline}\label{eq:estdorder2-1}
 \frac{1}{2}\|U_i^k(t_{n+1}^-)\|^2_i
 +\int_{I_n^i}\interleave U_i^k(\tau,\cdot)\interleave_i^2 \,d\tau
 -\int_{I_n^i} \int_{\Gamma_{i,j}} \nu_i\partial_{\nv_i} u_i^k
 \, U_i^k \, d\sigma\,d\tau
 \le \frac{1}{2}\|U_i^k(t_{n}^-)\|^2_i.\hspace{5mm}
 \end{multline}

We multiply the first equation of \eqref{eq:algosdorder2} by
$\partial_t ({\cal I}^iU_i^k)$, integrate on $I_n^i \times \Omega_i$
and then integrate by parts in space and use \eqref{eq:interpradau2}:

\begin{multline}\label{eq:estdorder2-2}
\frac{1}{2}\interleave U_i^k(t_{n+1}^-)\interleave_i^2
 +\int_{I_n^i} \|\partial_t ({\cal I}^iU_i^k)\|^2_{i} \,d\tau
 - \int_{I_n^i} \int_{\Gamma_{i,j}} \nu_i\partial_{\nv_i} u_i^k
  \, \partial_t ({\cal I}^iU_i^k) \, d\sigma\,d\tau
 \le \frac{1}{2}\interleave U_i^k(t_{n}^-)\interleave_i^2.\hspace{5mm}
\end{multline}

Now we multiply the first equation of \eqref{eq:algosdorder2} by
$-\Delta_{\Gamma_{i,j}}\, U_i^k$ integrate on $I_n^i \times \Omega_i$
and integrate by parts in space and use \eqref{eq:interpradau2}:

\begin{multline}\label{eq:estdorder2-4}
\frac{1}{2}\|  \grads{\Gamma_{i,j}} U_i^k(t_{n+1}^-)\|_i^2
 +\int_{I_n^i}\interleave \grads{\Gamma_{i,j}} U_i^k(t,.) \interleave_i^2\\
 + \int_{I_n^i}\int_{\Gamma_{i,j}} \nu_i\partial_{\nv_i} u_i^k
   \, \Delta_{\Gamma_{i,j}}\, u_i^k  \,d\sigma\,d\tau
 \le \frac{1}{2}\| \grads{\Gamma_{i,j}} U_i^k(t_{n}^-)\|_i^2,
\end{multline}
where we have used the fact that $\Delta_{\Gamma_{i,j}}$ is a
constant coefficient operator.

Let

\begin{equation*}
  E^n(U_i^k)=  \frac{p}{2}\|U_i^k((t^i_{n})^-)\|^2_{i}
   + \frac{q}{2}
  \interleave U_i^k((t^i_{n})^-)\interleave_i^2
  +\frac{sq}{2} \|\grads{\Gamma_{i,j}}U_i^k((t^i_{n})^-)\|^2_{i}.
\end{equation*}

Multiplying \eqref{eq:estdorder2-1} by $p$, \eqref{eq:estdorder2-2} by
$q$ and \eqref{eq:estdorder2-4} by $sq$, and adding the three
equations with \eqref{eq:estdorder2-1}, we get

\begin{multline*}
 E^{n+1}(U_i^k)
 + \int_{I_n^i}[\,
 p\interleave U_i^k(t,\cdot)\interleave_i^2 \,
 +q\|\partial_t({\cal I}_n^iU_i^k)\|^2_{i}\,
 +sq \interleave \grads{\Gamma_{i,j}}U_i^k(t,\cdot)\interleave_i^2 \,]\, dt\\
 -\sum_{j\in {\cal N}_i}\int_{I_n^i}\int_{\Gamma_{ij}}
  \nu_i \partial_{\nv_i} u_i^k\, S_{ij} U_i^k
  dx_2\,dt
  \le E^n(U_i^k).
\end{multline*}

It can be rewritten as

\begin{multline*}
  E^{n+1}(U_i^k)
   +  \int_{I_n^i}[\,
   \interleave U_i^k(t,\cdot)\interleave_i^2 \,
   +q\|\partial_t({\cal I}_n^iU_i^k)\|^2_{i}\,
   +sq \interleave \grads{\Gamma_{i,j}}U_i^k(t,\cdot)\interleave_i^2 \,]\, dt\\

  + \frac{1}{4}\sum_{j\in {\cal N}_i}\int_{I_n^i}\int_{\Gamma_{ij}}
    (\nu_i \partial_{\nv_i} u_i^k-\,S_{ij}U_i^k)^2
     \le
  E^n(U_i^k)
  + \frac{1}{4}\sum_{j\in {\cal N}_i}\int_{I_n^i}\int_{\Gamma_{ij}}
    (\nu_i \partial_{\nv_i} u_i^k+\,S_{ij}U_i^k)^2.
\end{multline*}

We now sum in time for $0 \le n \le N$, and use the transmission
condition.  Since $E^0(U_i^{k})=0$, we obtain

\begin{multline*}
  E^{N+1}(U_i^k)
  + \int_0^T\,[\,
   \interleave U_i^{k}(t,\cdot)\interleave_i^2 \,
   +q\|\partial_t({\cal I}_n^iU_i^{k})\|^2_{i}\,
   +sq \interleave \grads{\Gamma_{i,j}}U_i^{k}(t,\cdot)\interleave_i^2 \,]\, dt\\
  + \frac{1}{4}\sum_{j\in {\cal N}_i}\int_{0}^T\int_{\Gamma_{ij}}
    (\nu_i \partial_{\nv_i} u_i^k-\,S_{ij}U_i^k)^2 \,dt
     \le
   \frac{1}{4}\sum_{j\in {\cal N}_i}\int_{0}^T\int_{\Gamma_{ij}}
    (P^i(-\nu_j \partial_{\nv_j}U_j^{k-1}
   +\,\widetilde{S}_{ij}U_j^{k-1}))^2\,dt.
\end{multline*}

We sum up over the subdomains and use the fact that the projection is a
contraction. Since we are in the case where $p_{ij}=p$, $q_{ij}=q$,
$r_{ij}=0$ and $s_{ij}=s$, we have $\widetilde{S}_{ij}=S_{ji}$. Thus,
we can sum up over the iterates, the boundary terms cancel out, and we
obtain

\begin{multline*}
  \sum_{k=1}^K \sum_{i=1}^I \left(
  E^{N+1}(U_i^k)+ \int_{0}^T[\,
   \interleave U_i^{k}(t,\cdot)\interleave_i^2 \,
   +q\|\partial_t({\cal I}_n^iU_i^{k})\|^2_{i}\,
   +sq \interleave \grads{\Gamma_{i,j}}U_i^{k}(t,\cdot)\interleave_i^2 \,]\, dt
   \right)\\
  + \frac{1}{4}\sum_{i=1}^I\int_{0}^T\int_{\Gamma_{i}}
    (\nu_i \partial_{\nv_i} u_i^k-\,{\cal S}_{ij}U_i^K)^2
    \le\frac{1}{4}\sum_{i=1}^I\int_{0}^T\int_{\Gamma_{i}}
    (\nu_i \partial_{\nv_i} U_i^0 -\,{\cal S}_{ij}U_i^{0})^2.
  \end{multline*}

We conclude as in the proof of Theorem \ref{th:convdiscRobin}.
\end{proof}

We now state the error estimate in the Robin case.

\subsection{Error estimates in the Robin case}

\begin{theorem}\label{th:errorestimate}
  If $\div \av=0$, $p_{i,j}-\frac{\av_i \cdot \nv_i}{2}=p_{j,i}-\frac{\av_j \cdot \nv_j}{2}=p>0$, and $q_{i,j}=0$, the error between
  $\uu$ and the solution $\uud_i$ of \eqref{eq:dgdiscreteall} is estimated by:

 \begin{equation}\label{eq:errestimatesubdomain1}
  \sum_{i=1}^I\|\uu-\uud_i\|^2_{L^\infty(0,T,L^2(\Omega_i))}\le C k^{2(d+1)}
  \|\partial_t^{d+1}\uu\|^2_{L^2(0,T;H^2(\Omega))}.
 \end{equation}

\end{theorem}

\begin{proof} We introduce the projection operator $P_i^-$ as

\begin{equation*}\label{eq:projcont}
\begin{split}
&\forall n \in \inter{1,N_i}, P_i^-\phi \in \PP_{d}(I_n^i),\\
&P_i^-\phi(t_{n+1}^i)=\phi(t_{n+1}^i),\quad \forall \psi_{i,j} \in \PP_{d-1}(I_n^i),
\int_{I_n^i} (P_i^-\phi-\phi)(t)\psi_{i,j}(t)\, dt=0.
\end{split}
\end{equation*}

We define $W_i=P_i^-(u|_{\Omega_i})$, $\Theta_i=\uud_i-W_i$ and
$\rho_i=W_i-u|_{\Omega_i}$. Classical projection estimates
(\cite{thomee:1997:FEM}) yield the estimate on $\rho_i$:

\[
\sum_{i=1}^I\|\rho_i\|^2_{L^\infty(0,T,L^2(\Omega_i))}\le C k^{2(d+1)}  \|\partial_t^{d+1}\uu\|^2_{L^2(0,T;L^2(\Omega))}.
\]

Thus, since $\uud_i-u|_{\Omega_i}=\Theta_i+\rho_i$, it suffices to
prove estimate \eqref{eq:errestimatesubdomain1} for $\Theta_i$. Now,
thanks to the equations on $u$ and $\uud_i$, and the identity
$\frac{d}{dt}\mathcal{I}^iP_i^-=\mathcal{P}^i\frac{d}{dt}$, $\Theta_i$
satisfies:

\begin{eqnarray}\label{toto}
    \begin{array}{c}
    \partial_t ({\cal I}^i\,\Theta_i) +\av\cdot\nabla \Theta_i-\nu\Delta \Theta_i+c\Theta_i
    = -\av\cdot\nabla \rho_i+\nu\Delta \rho_i-c\rho_i\\
    +(1-P^i)(\partial_tu-f) \mbox{ in } \Omega_i\times (0,T), \\
 \ds\bigl(\nu_i\,\partial_{\nv_i}- \av_i\cdot\nv_i \bigr)\Theta_i +
 p_{i,j}\,\Theta_i  =P^i(\bigl(\nu_j\,\partial_{\nv_i}- \av_j\cdot\nv_i \bigr)\Theta_j +
 p_{i,j}\,\Theta_j )\hspace{4.3cm}\\
 -(1-P^i)(\bigl(\nu_j\,\ds\partial_{\nv_i}- \av_j\cdot\nv_i \bigr)W_j +
 p_{i,j}\, W_j ) \mbox{ on } \Gamma_{ij}\times (0,T),\,j\in{\cal N}_i. \\
      \end{array}
\end{eqnarray}

Multiply the first equation of \eqref{toto} by $\,\Theta_i$, integrate
on $(t_n^i, t_{n+1}^i)\times \Omega_i$, using \eqref{eq:interpradau2}
and integrate by parts in space. Terminate with Cauchy Schwarz
inequality:

\begin{multline*}
 \frac{1}{2}\|\Theta_i((t^i_{n+1})^-)\|^2_{i}
 +\int_{I_n^i}\interleave\Theta_i(t,\cdot)\interleave_i^2 \,dt
  -\int_{I_n^i}\int_{\Gamma_{i}}(\nu_i\partial_{\nv_i}\Theta_i
  -\frac{\av_i\cdot\nv_i}{2}\Theta_i)\, \Theta_i  dx_2\,dt \\
   \le
  \frac{1}{2}\|\Theta_i((t^i_{n})^-)\|^2_{i}+C\int_{I_n^i}\|\rho_i(t,\cdot)\|^2_{H^2(\Omega_i)}\,dt.
  \end{multline*}

Rewriting the boundary integral using \eqref{tototiti}, we obtain

\begin{multline*}
 \frac{1}{2}\|\Theta_i((t^i_{n+1})^-)\|^2_{i}
 +\int_{I_n^i}\interleave\Theta_i(t,\cdot)\interleave_i^2 \,dt
  +\frac{1}{4p}\sum_{j\in {\cal N}_i}\int_{I_n^i}\int_{\Gamma_{ij}}
  (\nu_i\partial_{\nv_i}\Theta_i-\av_i\cdot\nv_i\Theta_i-p_{j,i}\Theta_i)^2\, dx_2\,dt \\
   \le
 \frac{1}{4p}\sum_{j\in {\cal N}_i}\int_{I_n^i}\int_{\Gamma_{ij}}
 (\nu_i\partial_{\nv_i}\Theta_i-\av_i\cdot\nv_i\Theta_i+p_{i,j}\Theta_i)^2\, dx_2+
 \frac{1}{2}\|\Theta_i((t^i_{n})^-)\|^2_{i}+C\int_{I_n^i}\|\rho_i(t,\cdot)\|^2_{H^2(\Omega_i)}\,dt.
\end{multline*}

Using the transmission condition in \eqref{toto} together with the
fact that $P^i$ and $1-P^i$ are orthogonal to each other
and have norm 1, we get by a trace theorem

\begin{multline}\label{toto3}
 \frac{1}{2}\|\Theta_i((t^i_{n+1})^-)\|^2_{i}
 +\int_{I_n^i}\interleave\Theta_i(t,\cdot)\interleave_i^2 \,dt
  +\frac{1}{4p}\sum_{j\in {\cal N}_i}\int_{I_n^i}\int_{\Gamma_{ij}}
  (\nu_i\partial_{\nv_i}\Theta_i-\av_i\cdot\nv_i\Theta_i-p_{j,i}\Theta_i)^2\, dx_2\,dt \\
   \hspace{1cm}\le
 \frac{1}{4p}\sum_{j\in {\cal N}_i}\int_{I_n^i}\int_{\Gamma_{ij}}
 (\nu_j\partial_{\nv_j}\Theta_j-\av_j\cdot\nv_j\Theta_j-p_{i,j}\Theta_i)^2\, dx_2+
 \frac{1}{2}\|\Theta_i((t^i_{n})^-)\|^2_{i}\\
 +C\int_{I_n^i}\|\rho_i(t,\cdot)\|^2_{H^2(\Omega_i)}\,dt
 +C\int_{I_n^i}\|(1-P^i)(u|_{\Omega_i})(t,\cdot)\|^2_{H^2(\Omega_i)}\,dt.\hspace{0.7cm}
\end{multline}

Classical error estimates \cite{thomee:1997:FEM}  imply:

\begin{equation*}\label{toto4}
  \int_0^T\|\rho_i(t,\cdot)\|^2_{H^2(\Omega_i)}\,dt
  +\int_0^T\|(1-P^i)(u|_{\Omega_i})(t,\cdot)\|^2_{H^2
  (\Omega_i)}\,\le C k^{2(d+1)}  \|\partial_t^{d+1}\uu\|^2_{L^2(0,T;H^{2}(\Omega_i))}.
\end{equation*}

Summing \eqref{toto3} in $i$ and $n$, and using the previous equation yields
\eqref{eq:errestimatesubdomain1}.
\end{proof}

config: arxiv


TITLE: Why variance must divide by population?
QUESTION [0 upvotes]: According to page 2 of this paper, if $X$ is an arbitrary measurement with mean $\mu$ and variance $\sigma^2$, and $\overline{x}$ is the sample mean from random samples of size n, then:
$$\displaystyle\sigma_{\overline{x}}^2 = \frac{\sigma^2}{n}.$$
This is not something obvious, and I wonder if it has a name or is stated formally somewhere.  Thanks.

REPLY [0 votes]: Most detailed and easy to understand explanation I can found is in this link:
$\textrm{var}(\bar{X})=\textrm{var}\left(\dfrac{X_1+X_2+\cdots+X_n}{n}\right)$
$=\textrm{var}\left(\dfrac{1}{n}X_1+\dfrac{1}{n}X_2+\cdots+\dfrac{1}{n}X_n\right)$
$=\dfrac{1}{n^2}\textrm{var}(X_1)+\dfrac{1}{n^2}\textrm{var}(X_2)+\cdots+\dfrac{1}{n^2}\textrm{var}(X_n)$
$=\dfrac{1}{n^2}[\sigma^2+\sigma^2+\cdots+\sigma^2]$
$=\dfrac{1}{n^2}[n\sigma^2]=\dfrac{\sigma^2}{n}$
Thus:
$$\textrm{var}(\bar{X})=\dfrac{\sigma^2}{n}$$


TITLE: Is there any "Cosmological Principle"?
QUESTION [17 upvotes]: The term "Cosmological Principle" is widely invoked in cosmology discussions. I
think the basic idea here is that one might guess that the Milky Way is not at a special location in the cosmos as a whole, and one might guess further that each place in the cosmos is much like any other place. This guess is then elevated to the status of
"Principle". However it is obvious that some places are unlike others (the centre of a neutron star is unlike a galactic void) so this "principle" is only being
invoked as a statement about averages at large scales. So really it is a "principle"
which says that after all the stars, galaxies and galaxy-clusters one will eventually
arrive at a scale where things are homogeneous on average, and this scale is a good
deal smaller than the size of observable universe.
Now it happens that the observable universe
is indeed like that (smooth to good approximation on the large scale). However, as
far as I am aware there is no principle which says it had to be like that. It is not a principle but an empirical observation. Before looking, we have no a priori justification for expecting homogeneity. The universe might have been structured like a tree, with structure at all scales above some minimum. Indeed, in view of all the other scales of structure, one might guess that it would be quite likely to come out like that.
If the tree-like structure were the case, then one would have the issue whether or not the Milky Way should be located at a special place in such a tree. It is obvious that the answer is yes, up to a point, because it has to be at a place where a galaxy can form.
So you see I begin to doubt that there is any "cosmological principle" in the sense of a principle of logic or of theoretical physics. It is a misnomer for an interesting and important empirical observation.
My question is, then: is there any argument coming either from logic or from physics more generally (not observations such as sky surveys and CMB measurements) which says the cosmos must be expected to be homogeneous? And if it were not homogeneous then is there any argument deserving the name "principle" whose conclusion is that the physical conditions allowing life might be equally well expected at one place as another?

REPLY [1 votes]: So you see I begin to doubt that there is any "cosmological principle" in the sense of a principle of logic or of theoretical physics. It is a misnomer for an interesting and important empirical observation.

No physical regularities can be derived entirely from logic alone. All physical regularities are ultimately empirical observations. As far as I can tell, a "principle" is simply an empirical regularity that happen to hold over a particularly broad range of regimes and situations. We are blessed to live in a universe that happens to contain empirical regularities, like the Schrodinger equation or the rules of special relativity, that seem to hold in a lot of different regimes. But of course we can't rule out the possibility that we'll eventually come across some patch of space where the Schrodinger equation or special relativity simply don't apply.
But I think the exact cutoff for what counts as a "principle" will always be somewhat subjective, and so I'd question the premise quoted above. It also depends on what you're trying to describe: a deep-ocean marine biologist could reasonably take it as a "principle" that the temperature is always 4 degrees Celsius, but a stellar astrophysicist cannot.

My question is, then: is there any argument coming either from logic or from physics more generally (not observations such as sky surveys and CMB measurements) which says the cosmos must be expected to be homogeneous?

No. It's an empirical observation that cannot be derived from "fundamental" (i.e. microscopic-scale) laws of physics.

And if it were not homogeneous, then is there any argument deserving the name "principle" whose conclusion is that the physical conditions allowing life might be equally well expected at one place as another?

No, I can't think of one.


text:
\section{Introduction}
The Delaunay subdivision of a set of points in~$\RR^d$ plays a central role in
computational geometry~\cite{Edelsbrunner2006}.  A few applications are:
nearest-neighbor search, pattern matching, clustering, and mesh generation.

Via stereographic projection, Delaunay subdivisions can be lifted to \emph{inscribed polytopes}
\cite{Brown1979}---those with all vertices on the unit sphere---in one dimension higher,
so that Delaunay triangulations lift to simplicial inscribed polytopes. The study of
inscribed polytopes, and in particular the problem of deciding whether a
polytope admits an inscribed realization, is a classical subject
\cite{Steiner1832}\cite{Steinitz1928}\cite{Rivin1994} in which many
fundamental questions are still open~\cite{GonskaZiegler2011}.

In this paper, we are interested in \emph{realization spaces} of a \emph{fixed
combinatorial type} of Delaunay
subdivision/inscribed polytope. For a configuration $A$ of $n$ points in
$\RR^d$, which we assume to be labeled by $[n]=\{1,\dots,n\}$, the cells of its
Delaunay subdivision are represented by a family $T$ of subsets of $[n]$. The
\emph{realization space} $\rsdel({T})$ is a parametrization of the set of
all configurations of $n$ labeled points whose Delaunay triangulation has the
combinatorial structure of $T$ (as a polytopal complex with vertex set $[n]$).

Analogously, $\rsins({P})$, the realization space of an inscribed polytope $P$,
is a parametrization of configurations of $n$ points in the unit sphere whose
convex hull has the same face lattice as $P$.

In dimension $2$, results of~\cite{Rivin1994} imply that both of
these realization spaces are homeomorphic to a polytope (that
depends on $T$ only).  This completely determines the topological
structure of both realization spaces.  For example, they are
always \emph{connected} and \emph{contractible}.

\subsection{Universality for Delaunay subdivisions}
Our main results show that, in higher dimensions,
the situation is completely different: the realization space
of a $d$-dimensional Delaunay subdivision (or triangulation) can be
arbitrarily complicated.

\begin{repthm}{thm:lawrence}
For every primary basic semi-algebraic set there is a Delaunay subdivision and an
inscribed polytope whose realization space is homotopy equivalent to $S$.
\end{repthm}
Said differently, realization spaces of inscribed polytopes
exhibit the \emph{topological universality} in the sense of Mnëv \cite{Mnev1988}.  We
also show that these realization spaces exhibit \emph{algebraic universality} (also
a notion from \cite{Mnev1988}).

\begin{repcor}{cor:lawrenceAlg}
For every finite field extension $F/\QQ$ of the rationals, there is a realizable
Delaunay subdivision (equivalently, an inscribed polytope)
that cannot be realized with coordinates in $F$.
\end{repcor}

\subsection{Universality for Delaunay triangulations}
The subdivisions constructed in proof of Theorem \ref{thm:lawrence} are far from being
triangulations. To insist on triangulations and simplicial polytopes requires
different tools. We adapt a recent proof of the Universality Theorem
for simplicial polytopes \cite{AdiprasitoPadrol2014} to obtain a weak universality
theorem for Delaunay triangulations.

\begin{repthm}{thm:neighborly}
For every open primary basic semi-algebraic set $S$ there is a (neighborly) Delaunay triangulation and an
inscribed simplicial (neighborly) polytope,
such that $S$ is a retract of their realization spaces, up to homotopy equivalence.

\end{repthm}

\subsection{Complexity}
The complete statements of these theorems provide
linear bounds for the number points of the triangulation and the dimension in terms
of the \emph{arithmetic complexity} of the corresponding semi-algebraic sets.
Moreover, $S$ is non-empty \emph{if and only if} $\rsdel(T)$ is. Such a triangulation
can be computed from $S$ in polynomial time, which shows that deciding whether a Delaunay
triangulation is realizable is hard. Indeed, the proof of Theorem~\ref{thm:neighborly}
shows that deciding realizability of Delaunay triangulations is as hard as deciding
realizability of rank~$3$ oriented matroids~\cite{Mnev1988}\cite{Shor1991}.

\begin{repcor}{cor:hard}
The {realizability problem for Delaunay triangulations and inscribed simplcial
polytopes} is polynomially equivalent to the \emph{existential theory of the
reals (ETR)}. In particular, it is NP-hard.
\end{repcor}

Another consequence of this effective bound is that the number of
connected components of the realization space of a $d$-dimensional Delaunay
triangulation can be exponential in~$d$.
\begin{repcor}{cor:asymptotic}
For every $m\geq 1$ there exist configurations of $O(m)$ points in general
position in $\RR^{O(m)}$ whose
realization spaces as Delaunay triangulations have at least $2^m$ connected
components.
\end{repcor}

Our smallest example of a triangulation with disconnected realization space is
in $\RR^{25}$, which leaves open the existence of these configurations in $\RR^d$ for each
$3\leq d\leq 24$.
\begin{repcor}{cor:small-config}
There is a $25$-dimensional configuration of $30$ points whose Delaunay
triangulation has
a disconnected realization space.
\end{repcor}

\subsection{Context and related work}
The realization spaces of $3$-dimensional inscribed polyhedra are well
understood.  On the other hand, there is a rich theory of the ``wildness'' of
realization spaces of higher-dimensional polyhedra can be quite wild.  Here is
the background and connection with our results.

\subsubsection{Dimension $2$ and inscribable polyhedra}
Theorems \ref{thm:lawrence} and \ref{thm:neighborly} and their corollaries
should be contrasted with fundamental results of Rivin
\cite{Rivin1994}\cite{Rivin1996}\cite{Rivin2003} that connect $2$-dimensional
Delaunay subdivisions with metric properties of hyperbolic $3$-dimensional
polyhedra.

Rivin's work in particular entailed that: (1) whether a (combinatorial) planar
graph has a drawing as a Delaunay triangulation can be tested in polynomial
time; (2) that the realization space of a planar Delaunay triangulation is
homeomorphic to a polyhedron of so-called \emph{angle structures} (see
\cite{FuterGueritaud11} for an elementary introduction to the method), and, in
particular, connected.

In the language of polyhedra, (1) says that whether a graph is the $1$-skeleton of an
inscribable polyhedron is efficiently
checkable; and (2) says that the set of inscribed realizations is convex (and in particular
contractible) in the parameterization by dihedral angles.

The question of whether every polyhedron is inscribable had been first raised
by Steiner in 1832~\cite{Steiner1832}, with the first negative examples
given by Steinitz in 1928~\cite{Steinitz1928}. This makes such a sharp
characterization
of the inscribable types and their realization spaces a surprising breakthrough.
In contrast, Theorems~\ref{thm:lawrence} and \ref{thm:neighborly}
suggest that a polynomial time characterization for all dimensions is, under
standard conjectures, not possible.

\subsubsection{Higher dimensions and universality}
A general principle in the theory of realization spaces for (semi-)algebraically defined
objects is succinctly put in \cite{Vakil06}:  ``Unless there is some a priori reason otherwise,
the deformation space may be as bad as possible.''

Underlying a large number of these kinds of phenomena is a paradigmatic result
of Mn\"ev. The Universality Theorem states that for every [open] primary basic
semi-algebraic set there is a [uniform] oriented matroid of rank~$3$ whose
realization space is stably equivalent to it. (The survey
\cite{RichterGebert1998} provides an accessible presentation of this and related
results and their proofs, and a more computationally oriented approach can be
found in \cite{Shor1991}.)

The Universality Theorem in particular entails a negative answer to Ringel's 1956
\emph{isotopy problem}, which asked whether, given two point configurations $A_0$ and $A_1$
with the same oriented matroid (order type), is it always possible to find a continuous path
of point configurations $\{A_t\}_{0\leq t\leq 1}$ with the same oriented matroid?  (This
weaker result also follows via examples from
\cite{JaggiManiLevitskaSturmfelsWhite1989}
\cite{RichterGebert1996}
\cite{Suvorov1988}
\cite{Tsukamoto2013}
\cite{Vershik1988}
\cite{White1989}.)
Actually, the Universality Theorem shows that there are oriented matroids
that have realization spaces with arbitrarily many components.

Another straightforward consequence of the Universality Theorem is that
determining realizability
of oriented matroids is polynomially equivalent to the \emph{existential theory
of the reals}, and in particular NP-hard \cite{Mnev1988}\cite{Shor1991}.

Via a reduction given in \cite{Mnev1988}, realization spaces of polytopes also
exhibit universality: for every semi-algebraic variety $S\subset \RR^s$, there
is a polytope $P$ whose realization space is stably equivalent to~$S$. Here, the
realization space of a polytope $P$ is the set of point configurations whose
convex hull is combinatorially equivalent to $P$. In principle, this polytope
might be of a very high dimension. However,
Richter-Gebert~\cite{RichterGebert1997} made a breakthrough when he proved that
there is universality already in realization spaces of $4$-dimensional
polytopes.  Again, there is a contrast with $3$-polytopes, which have
contractible realization spaces (see, e.g.,~\cite[Part IV]{RichterGebert1997}).

When the semi-algebraic sets are open, one can furthermore require the polytopes
to be simplicial (and even neighborly), although only in arbitrarily high
dimensions~\cite{AdiprasitoPadrol2014}\cite{Mnev1988}.
Universality for simplicial polytopes in fixed dimension remains wide open.

However, the existence of Delaunay triangulations with a disconnected
realization space is not a direct consequence of the results of Richter-Gebert
and Mn\"ev. Indeed, even if $P$ is a polytope with a disconnected realization
space, it could be that the variety $\rssphere$ that certifies that all the
vertices lie on the unit sphere does not intersect with all its connected
components---or any of them. Hence, to present a
Delaunay triangulation with a disconnected realization space, one has to show
that $\rssphere$ hits at least two of these connected components or that the
intersection of $\rssphere$ with a connected component is disconnected.

On the other hand, some universality phenomena from the theory of general polytopes
are already known to carry over to the case of inscribed polytopes; for instance, there are infinitely many
projectively unique {inscribed} polytopes even in \emph{bounded} dimension, and
every inscribed polytope is the face of some projectively unique inscribed polytope,
cf.\ \cite{AdiprasitoZiegler2014}.

\subsection{Open problem: universality in fixed dimension}

Theorems~\ref{thm:lawrence} and \ref{thm:neighborly} are the first step towards
a universality theory for Delaunay triangulations and leave several open questions.
First of all, a strong version of Theorem~\ref{thm:neighborly} should state homotopy equivalence
between the realization space of the Delaunay triangulation and the semi-algebraic set.

The main challenge is to prove a Universality Theorem for Delaunay Triangulations in fixed dimension.
Recall that polytopes present universality already in dimension~$4$ (for simplicial
polytopes this is also conjectured). Since the results here run more or less in parallel
with the development of the theory for polytopes, the strongest conjecture we can make is:

\begin{conj}\label{conj:universality}
For every [open] primary basic semi-algebraic set $S$ defined over $\ZZ$
there is a $3$-dimensional Delaunay [triangulation] subdivision whose realization space
is homotopy equivalent to~$S$.
\end{conj}

Since connected sums, the main ingredient of Richter-Gebert's proof of the Universality Theorem for
$4$-polytopes~\cite{RichterGebert1997}, do not behave well with respect to inscribability, it seems that
a new set of tools will be needed to prove our conjecture.

\subsection{Reading guide}
The rest of this paper is organized as follows:
Section~\ref{sec:preliminaries} introduces some necessary notation.
Section~\ref{sec:inscribed} is devoted to the Universality Theorem for inscribed
polytopes and Delaunay subdivisions. Simplicial polytopes and triangulations
require different tools, and are studied in Section~\ref{sec:simpinscribed}.


TITLE: Determine the missing number in a grid of numbers
QUESTION [0 upvotes]: I met this question yesterday while solving an I.Q test. It took me around 1 hour to come up with a solution that I'm not certain is the correct one.
Alright, without further ado, here's the puzzle:

What is the number that you should put instead of the dot?

****SPOILER ALERT****
MY INCOMPLETE SOLUTION
As you can see, every row is divided into 1 big number on the left, followed by four 1-digit numbers on the right.
So my idea is that if you take the sum of the first and second small numbers, then you take the sum of the third and fourth small numbers, and then you take the sum of the digits of both of the sums, then the result will be equal to the sum of the digits of the big number.
For example, take the third row:
The big number: 153
The four 1-digit numbers: 2, 1, 8, 7
The sum of 1st and 2nd = 2 + 1 = 3
The sum of 3rd and 4th = 8 + 7 = 15
The sum of the digits of both of the sums = 3 + 1 + 5 = 9
The sum of the digits of the big number = 1 + 5 + 3 = 9
However, this works for all rows, except the first one at the top. That's the closest I could get to the solution. Should a person find the complete solution, I'll be extremely grateful.

NOTE: it is entirely possible that the person who wrote this puzzle is playing "mind-games" with us, and that he included the first row just to deceive us, thus making the question even harder. But let's not make any assumptions here.
It is also worth noting that the choices that came with the puzzle were as follows:
A) 110
B) 128
C) 164
D) 92
Maybe the idea of the question is to choose the most different choice. the sum of the digits of all of these choices is 11, except for 110:
1 + 2 + 8 = 1 + 6 + 4 = 9 + 2 = 11
1 + 1 + 0 = 2

REPLY [0 votes]: If you assume a linear model $y=\sum_{j=1}^4 \beta_j x_j$ with no intercept and ignore the first row, you get a perfect fit $\beta=(1, 1, 10, 10)$, as others have proposed, yielding 128.
If you assume a linear model $y=\beta_0+\sum_{j=1}^4 \beta_j x_j$ with intercept and include the first row, you get a perfect fit $\beta=(744, 56, -91, 252, 171)/26$, yielding $3340/26=128.462$.  Close enough?