# Schwarz preconditioner with $H_{k}$-GenEO coarse space for the indefinite
Helmholtz problem

Victorita Dolean111CASA, TU Eindhoven<EMAIL_ADDRESS>Mark
Fry222Department of Mathematics and Statistics, University of Strathclyde,
Glasgow, G1 1XH, UK<EMAIL_ADDRESS><EMAIL_ADDRESS>Ivan G.
Graham333Department of Mathematical Sciences, University of Bath, Bath, BA2
7AY, UK<EMAIL_ADDRESS>Matthias Langer†

###### Abstract

GenEO (‘Generalised Eigenvalue problems on the Overlap’) is a method from the
family of spectral coarse spaces that can efficiently rely on local
eigensolves in order to build a robust parallel domain decomposition
preconditioner for elliptic PDEs. When used as a preconditioner in a conjugate
gradient, this method is extremely efficient in the positive-definite case,
yielding an iteration count completely independent of the number of subdomains
and heterogeneity. In a previous work this theory was extended to the cased of
convection–diffusion–reaction problems, which may be non-self-adjoint and
indefinite, and whose discretisations are solved with preconditioned GMRES.
The GenEO coarse space was then defined here using a generalised eigenvalue
problem based on a self-adjoint and positive definite subproblem. The
resulting method, called $\Delta$-GenEO becomes robust with respect to the
variation of the coefficient of the diffusion term in the operator and depends
only very mildly on variations of the other coefficients. However, the
iteration number estimates get worse as the non-self-adjointness and
indefiniteness of the operator increases, which is often the case for the high
frequency Helmholtz problems. In this work, we will improve on this aspect by
introducing a new version, called $H_{k}$-GenEO, which uses a generalised
eigenvalue problem based directly on the indefinite operator which will lead
to a robust method with respect to the increase in the wave-number. We provide
theoretical estimates showing the dependence of the size of the coarse space
on the wave-number. The new method is entirely robust with respect to $k$ and
this is confirmed by numerical results.

MSC Classes: 65N22, 65N55, 65F10
Keywords: elliptic PDEs, finite element methods, domain decomposition,
preconditioning, GMRES, Helmholtz, spectral coarse space, robustness

##  1 Introduction

This paper is concerned with the theory and implementation of two-level domain
decomposition preconditioners for finite element systems arising from the
indefinite version of Helmholtz boundary value problems with highly variable
coefficients defined on $\Omega\subset\mathbb{R}^{d}$, given by:

$\displaystyle-\operatorname{div}(A\nabla u)-k^{2}u$ $\displaystyle=f\qquad$
$\displaystyle\text{in }\Omega,$ (1.1a) $\displaystyle u$
$\displaystyle=0\qquad$ $\displaystyle\text{on }\partial\Omega.$ (1.1b)

The computational domain is supposed to be polygonal or Lipschitz polyhedral
domain $\Omega\subset\mathbb{R}^{d}$ ($d=2,3$). As well as a weak regularity
assumption on the coefficient matrix $A$ which is positive definite, we will
assume that (1.1) has a unique weak solution $u\in H^{1}(\Omega)$ for all
$f\in L^{2}(\Omega)$. A key parameter when solving this problem is the
wavenumber $k$; the indefiniteness of the problem increases with $k$, becoming
thus more challenging for linear solvers.

In overlapping domain decomposition methods, the global domain $\Omega$ is
covered by a set of overlapping subdomains $\Omega_{i}$, $i=1,\ldots,N$, and
the classical one-level additive Schwarz preconditioner is built from partial
solutions on each subdomain. Since this preconditioner is, in general, not
scalable as the number of subdomains grows, an additional global coarse solve
is usually added to enhance scalability, as well as robustness with respect to
coefficient heterogeneity or the increase in the wavenumber.

Aim of the paper and literature review. Coarse spaces are instrumental in
achieving robustness and scalability in domain decomposition methods. It is
now well known and commonly accepted that classical coarse spaces (piecewise
polynomials on a coarse grid, e.g., [9, 38]) are not robust for highly
heterogeneous problems. For that reason, different authors introduced
operator-dependent coarse spaces, which are better adapted to the
heterogeneity; see for example [23]. In the past decade a new idea has emerged
introducing the powerful concept of ‘spectral’ coarse spaces, which are now
built from well-chosen modes of local generalised eigenvalue problems defined
at a subdomain level. The use of spectral information for the solution of
multiscale PDEs, as a tool of achieving robust approximation techniques, is
not new [2, 15], but in domain decomposition preconditioning this was
introduced in [18, 19].

This paper focuses on a variant of the GenEO coarse space, which was
introduced for the first time in [37] for general coercive, self-adjoint
systems of PDEs. In this seminal paper, it was rigorously proved that (when
combined with a one-level method and using preconditioned conjugate gradients
as a Krylov iterative solver) the resulting algorithm is not only scalable
with respect to the number of subdomains but also robust with respect to
coefficient variation. More recent works include for example [1, 27, 3] and
[36], while more complete lists of contributions can be found in the
literature surveys in, e.g., [37] and [17].

While the theory for the above methods is very well established for SPD
(symmetric positive definite) problems since the behaviour and the properties
of local eigenfunctions are entirely known, for the indefinite or non-self-
adjoint problems, the progress has not been slower but mostly numerical. As an
example for Helmholtz, the first publications on spectral coarse space include
[12, 4], while a thorough comparison of the state-of-the-art coarse spaces can
be found in [5]. In this work, the resulting two level preconditioners are
compared for large scale high-frequency Helmholtz problems. From this
comparison it results that one of the most promising coarse spaces for
Helmholtz problems (also called ‘$H$-GenEO’ in [5, 6]) has good robustness
properties at high frequency, but, because of the non-self-adjoint nature of
the operators involved, the theory was out of reach. Later on, the similarity
between $H$-GenEO and $\Delta$-GenEO method observed numerically at lower
frequencies in [6] motivated the theoretical work in [7] where the authors
studied how well the GenEO technology works (both in theory and in practice)
for general non-self-adjoint and indefinite PDEs of the form (1.2):

$\displaystyle-\operatorname{div}(A\nabla u)+\mathbf{b}\cdot\nabla u+cu$
$\displaystyle=f\qquad$ $\displaystyle\text{in }\Omega,$ (1.2a) $\displaystyle
u$ $\displaystyle=0\qquad$ $\displaystyle\text{on }\partial\Omega.$ (1.2b)

The $\Delta$-GenEO method constructs a coarse space by solving a generalised
eigenvalue problem using a nearby SPD problem. Whilst the work cited has gone
a long way to show that the GenEO coarse space provides an improvement for
solving an SPD problem, and the $\Delta$-GenEO coarse space provides a similar
improvement with a non-self-adjoint and indefinite problem, both of these
scenarios are constructing the coarse space using an SPD operator. The work
being carried out in this paper is to develop the theory for the two-level
domain decomposition preconditioner, using the $H_{k}$-GenEO coarse space,
which is adaptation of the $H$-GenEO coarse space first mentioned in [5]. The
$H_{k}$-GenEO coarse space differs from previous methods as it uses the full
problem operator to build the coarse space. Because of this, the usual
estimates of the spectral properties are no longer applicable.

After discretisation by finite elements, the linear systems arising from (1.1)
are symmetric but indefinite. For this reason, we use GMRES as the iterative
solver, the convergence analysis relies on the ‘Elman theory’ ([16] or [38,
Lemma C.11]), which requires an upper bound for the norm of the preconditioned
matrix and a lower bound on the distance of its field of values from the
origin. As a result, the number of GMRES iterations to achieve a given error
tolerance is a function of these two bounds. Thus, the dependence of these
bounds on the parameters of the problem and of the preconditioner (e.g., mesh
size, subdomain size, overlap, heterogeneity, and wave-number) is of paramount
interest when analysing the robustness and scalability of the preconditioner.
The use of the Elman theory in domain decomposition goes back to Cai and
Widlund [10] (see also [38, Section 11]).

The main results of this paper. In our work, we have used two different sizes
of decomposition. One fine decomposition which is nested inside a larger
coarse decomposition. Where in previous studies, the same size was used for
both the fine and coarse decompositions. Our main theoretical result, Theorem
3.1, provides rigorous and $k$-explicit upper bounds on the fine mesh diameter
$H^{f}$ and on the ‘eigenvalue tolerance’ $\tau$ (for the local GenEO
eigenproblems) which ensure that GMRES enjoys robust and mesh-independent
convergence when applied to the preconditioned problem. We give here an
example of the impact of these quantities on GMRES: if we reduce $H^{f}$, we
increase the number of subdomains and these domains will become smaller. Not
to mention that even if the solution exhibits higher frequencies in the global
domain, on a fraction of it, the problem becomes simpler, low frequency or
might even become positive definite. The other quantity, $\tau$ is an
indicator of how many eigenfunctions are incorporated into the coarse space.
Optimal choices of $\tau$ and $H^{f}$ are very often determined empirically
but here we provide, for the first time, explicit limits depending on $k$.

Since the result of the paper is quite technical, we summarise it here when
applied to (1.1) and show the improvement with respect to the method
introduced in [7]. GenEO coarse spaces are usually based on the $m_{i}$
(dominant) eigenfunctions corresponding to the smallest eigenvalues
$\lambda^{i}_{1}\leq\lambda^{i}_{2}\leq\ldots\leq\lambda_{m_{i}}^{i}$ of the
generalised eigenvalue problem on the subdomain $\Omega_{i}$. To obtain a
robust rate of convergence for GMRES that depends only on $\Lambda$ (the
maximum number of times any point is overlapped by the subdomains
$\Omega^{f}_{i,j}$), we need some conditions on $H^{f}$ and the eigenvalue
tolerance $\tau\mathrel{\mathop{:}}=\min_{i=1}^{N}\lambda^{i}_{m_{i}+1}$,
where $N$ is the number of subdomains in the coarse mesh. In the equations
below, $C_{\textup{{stab}}}>0$ is the stability constant for the problem (1.1)
and is defined in Assumption 2.3. It blows up as the distance of $k^{2}$ from
an eigenvalue of the Dirichlet problem for $-\operatorname{div}(A\nabla u)$
decreases. The hidden constants usually depend only on $\Lambda$ and
$H=H^{c}=H^{f}$ is the diameter of the mesh used.

  * •

In [7, Theorem 4.1] it is proved that a robust rate is achieved if

$H\lesssim
k^{-2}\qquad\text{and}\qquad(1+C_{\textup{{stab}}})^{2}\,k^{8}\lesssim\tau.$
(1.3)

  * •

In [14] the authors show that the bounds from (1.3) can be improved:

$H\lesssim
k^{-1}\qquad\text{and}\qquad(1+C_{\textup{{stab}}})^{2}k^{4}\lesssim\tau.$
(1.4)

In this paper, we show that the conditions for robustness are:

$H^{f}\lesssim
k^{-1}\qquad\text{and}\qquad(1+C_{\textup{{stab}}})^{2}k^{2}\lesssim\tau.$
(1.5)

We thus show that, even though the theoretical bounds for the $\Delta$-GenEO
given in (1.4) are already an improvement with respect to the results in [7],
$H_{k}$-GenEO is still able to lead to better estimates than the
$\Delta$-GenEO coarse space. Using the $H_{k}$-GenEO coarse space means that a
significantly lower bound on $\tau$ can be used over the $\Delta$-GenEO. By
using two separate decompositions, we have also been able to remove one of the
constraints on the coarse space. The number of eigenvalues required for the
coarse space no longer has any requirements on the size of the coarse mesh.

In all experiments from [7] the condition on the eigenvalue tolerance in (1.3)
appears to be overly pessimistic, and the coarse space sizes necessary to
achieve full robustness are rather moderate in practical computations.

##  2 Useful Background

###  2.1 Problem formulation and discretisation

The weak formulation of (1.1) is to find $u\in H^{1}_{0}(\Omega)$ such that

$b(u,v)=(f,v)\qquad\text{for all}\ v\in H^{1}_{0}(\Omega),$ (2.1)

where $f\in L^{2}(\Omega)$ and $b(\cdot,\cdot):H^{1}_{0}(\Omega)\times
H^{1}_{0}(\Omega)\rightarrow\mathbb{R}$ is defined as

$b(u,v)=\int_{\Omega}(A\nabla u\cdot\nabla v-k^{2}uv)\,\mathrm{d}x.$

We shall be making use of the positive definite bilinear form
$a(\cdot,\cdot):H^{1}_{0}(\Omega)\times
H^{1}_{0}(\Omega)\rightarrow\mathbb{R}$,

$a(u,v)=\int_{\Omega}A\nabla u\cdot\nabla v\,\mathrm{d}x.$

If $a$ and $b$ are defined on a subdomain $\Omega^{\prime}$ of $\Omega$, we
employ the notations $a_{\Omega^{\prime}}$ and $b_{\Omega^{\prime}}$. The
following weak regularity assumptions are used throughout this work.

######  Assumption 2.1.

The coefficient $A$ and the right-hand side $f$ in problem (1.1) satisfy the
following assumptions.

  1. (i)

$A:\Omega\rightarrow\mathbb{R}^{d\times d}$ is symmetric with
$0<a_{\textup{min}}\leq a_{\textup{max}}$, s.t.

$a_{\textup{{min}}}|\bm{\xi}|^{2}\leq A(x)\bm{\xi}\cdot{\bm{\xi}}\leq
a_{\textup{{max}}}|\bm{\xi}|^{2}\qquad\text{for all}\
x\in\Omega,\bm{\xi}\in\mathbb{R}^{d}.$ (2.2)

  2. (ii)

Without loss of generality, $a_{\textup{{min}}}=1$ and the diameter,
$D_{\Omega}$, of the domain $\Omega$ satisfies $D_{\Omega}\leq 1$. (If this is
not the case, then the problem can be scaled accordingly.)

######  Notation 2.2.

For any subdomain $\Omega^{\prime}\subset\Omega$ we are using
$(\cdot,\cdot)_{\Omega^{\prime}}$ to denote the $L^{2}(\Omega^{\prime})$ inner
product and $\|\cdot\|_{\Omega}$ to denote the norm. When
$\Omega^{\prime}=\Omega$, we write $(\cdot,\cdot)$ and $\|\cdot\|$ for the
inner product and the norm respectively. We also introduce the norm induced by
the positive bilinear form $a$ and write
$\|u\|_{a,\Omega^{\prime}}\mathrel{\mathop{:}}=\sqrt{a_{\Omega^{\prime}}(u,u)}$.
When $\Omega^{\prime}=\Omega$ we abandon the subscript $\Omega$. We see that
$b(u,v)=a(u,v)-k^{2}(u,v)$. We are also using the $k$-inner product given by

$(u,v)_{1,k,\Omega^{\prime}}\mathrel{\mathop{:}}=a_{\Omega^{\prime}}(u,v)+k^{2}(u,v)_{\Omega^{\prime}},$

and we denote the induced $k$-norm by $\|u\|_{1,k,\Omega^{\prime}}$.

In all what follows solvability of (2.1) is assumed.

######  Assumption 2.3.

We assume that, for any $f\in L^{2}(\Omega)$, the problem (2.1) has a unique
solution $u\in H_{0}^{1}(\Omega)$ and there exists a constant
$C_{\textup{{stab}}}>0$ such that

$\|u\|_{1,k}\leq C_{\textup{{stab}}}\|f\|\qquad\text{for all}\ f\in
L^{2}(\Omega).$ (2.3)

The bilinear forms $a(\cdot,\cdot)$ and $(\cdot,\cdot)_{1,k}$ are SPD;
$b(\cdot,\cdot)$ is symmetric, but in general indefinite.

Let $\mathcal{T}_{h}$ be any shape regular triangular mesh over the domain
$\Omega$. For the purpose of this work, 2 or 3-dimensional simplices are
considered, but this could easily be applied to $d$-dimensional simplices,
where the maximum diameter is $h$. Let $V^{h}\subset H^{1}_{0}(\Omega)$ be any
conforming finite element space. The Galerkin approximation of (2.1) is to
find $u_{h}\in V^{h}$ such that

$b(u_{h},v)=(f,v)\qquad\text{for all}\ v\in V^{h}.$ (2.4)

If $n$ denotes the dimension of $V^{h}$, with a basis given by
$\\{\phi_{i}\\}_{i=1}^{n}$, then (2.4) can be represented by the linear system

$\mathbf{B}\mathbf{u}=\mathbf{f};$ (2.5)

the matrix $\mathbf{B}$ and the vector $\mathbf{f}$ are defined in terms of
the basis functions:
$(\mathbf{B})_{ij}\mathrel{\mathop{:}}=b(\phi_{j},\phi_{i})$ and
$(\mathbf{f})_{i}\mathrel{\mathop{:}}=(f,\phi_{i})$. Later we also need the
matrices $\mathbf{A}$ and $\mathbf{S}$ that correspond to $a$ and
$(\cdot,\cdot)$, namely,
$(\mathbf{A})_{ij}\mathrel{\mathop{:}}=a(\phi_{j},\phi_{i})$ and
$(\mathbf{S})_{ij}\mathrel{\mathop{:}}=(\phi_{j},\phi_{i})$ respectively.

The solvability of (2.4) is assured by the following lemma from [34, Theorem
2]. This is required due to the indefiniteness of (2.4).

######  Lemma 2.4 (Schatz and Wang, 1996).

Let Assumptions 2.1 and 2.3 hold. Then there exists an $h_{0}>0$ such that,
for each $h$ with $0<h<h_{0}$, the problem (2.4) has a unique solution
$u_{h}\in V_{H}$. Moreover, let $u$ be the unique solution of (2.1). Then, for
every $\varepsilon>0$ there exists $h_{1}=h_{1}(\varepsilon)>0$ such that, for
every $h\in(0,h_{1})$,

$\|u-u_{h}\|\leq\varepsilon\|u-u_{h}\|_{{H^{1}}(\Omega)}$ (2.6)

and

$\|u-u_{h}\|_{H^{1}(\Omega)}\leq\varepsilon\|f\|.$ (2.7)

Let us also recall the Friedrichs inequality [30, Theorem 13.19], which will
be used extensively throughout this work.

######  Lemma 2.5 (Friedrichs inequality).

Let $\Omega^{\prime}\subset\mathbb{R}^{d}$ be an open set that lies between
two parallel hyperplanes with and let $L$ be the distance between the two
hyperplanes. Then, for all $u\in H^{1}_{0}(\Omega^{\prime})$,

$\|u\|_{\Omega^{\prime}}\leq\frac{L}{\sqrt{2}\,}\|\nabla
u\|_{\Omega^{\prime}}.$ (2.8)

Combining (2.8) with Assumption 2.1 we obtain that, for any subdomain
$\Omega^{\prime}\subset\Omega$ with diameter $H$, the following estimate is
true:

$\|u\|_{\Omega^{\prime}}\leq\frac{H}{\sqrt{2}\,}\|\nabla
u\|_{\Omega^{\prime}}\leq\frac{H}{\sqrt{2}\,}\|u\|_{1,k,\Omega^{\prime}}\qquad\text{for
all}\ u\in H^{1}_{0}(\Omega^{\prime}).$ (2.9)

###  2.2 Abstract spectral theory for the generalised indefinite eigenvalue
problems

Due to the nature of the problem being analysed, and the type of spectral
coarse space we are going to develop, we will be dealing with indefinite
eigenvalue problems. The following lemma demonstrates certain properties that
we will be able to exploit.

######  Lemma 2.6.

Let $B$ and $C$ be self-adjoint operators acting on a finite dimensional
Hilbert space $V$, with symmetric forms defined as

$\texttt{b}(v,w):=(Bv,w),\qquad c(v,w):=(Cv,w),$

and

$C\geq 0,\qquad\ker B\cap\ker C=\\{0\\}.$ (2.10)

Consider the generalised eigenvalue problem

$Bv=\lambda Cv.$ (2.11)

The generalised eigenvalue problem (2.11) is non defective, i.e. it has a full
set of eigenvectors, and any $v\in V$ can be written as

$v=v_{0}+\sum_{i=1}^{r}\alpha_{i}p_{i}.$ (2.12)

###### Proof.

It follows from (2.10) that there exists $\gamma\geq 0$ such that

$\widetilde{B}\mathrel{\mathop{:}}=B+\gamma C$

is invertible. For $v\neq 0$ we have the following equivalences

$Bv=\lambda Cv\quad\Leftrightarrow\quad(B+\gamma
C)v=(\lambda+\gamma)Cv\quad\Leftrightarrow\quad\widetilde{B}^{-1}Cv=\frac{1}{\lambda+\gamma}c;$
(2.13)

note that $\lambda+\gamma\neq 0$ if the second equality holds. Set

$U\mathrel{\mathop{:}}=\widetilde{B}^{-1}C,\qquad\mu\mathrel{\mathop{:}}=\frac{1}{\lambda+\gamma}.$

Then the relations in (2.13) are equivalent to $Uv=\mu v$.

Now set

$\widetilde{b}(v,w)\mathrel{\mathop{:}}=(\widetilde{B}v,w),\qquad
c(v,w)\mathrel{\mathop{:}}=(Cv,w).$

Then

$\widetilde{b}(Uv,w)=(\widetilde{B}\widetilde{B}^{-1}Cv,w)=(Cv,w)=c(v,w)$
(2.14)

and hence

$\widetilde{b}(Uv,w)=(Cv,w)=(v,Cw)=(v,\widetilde{B}\widetilde{B}^{-1}Cw)=(\widetilde{B}v,Uw)=\widetilde{b}(v,Uw),$

i.e. $U$ is symmetric with respect to the form $\widetilde{b}$. Since the form
$c$ is positive semi-definite, we can apply the Cauchy–Schwarz inequality to
obtain

$|c(v,w)|^{2}\leq c(v,v)c(w,w).$ (2.15)

Now assume that $Uv=\mu v$ with $\mu\neq 0$ and $v\neq 0$. It follows from
(2.14) and (2.15) that, for arbitrary $w$,

$\displaystyle|\mu\widetilde{b}(v,w)|^{2}$ $\displaystyle=|\widetilde{b}(\mu
v,w)|^{2}=|\widetilde{b}(Uv,w)|^{2}=|c(v,w)|^{2}\leq c(v,v)c(w,w)$
$\displaystyle=\widetilde{b}(Uv,v)c(w,w)=\mu\widetilde{b}(v,v)c(w,w).$

Since $\widetilde{B}$ is invertible, we can find $w$ such that
$\widetilde{b}(v,w)\neq 0$, which implies that

$\mu\widetilde{b}(v,v)c(w,w)>0.$

Since $\widetilde{b}(v,v)c(w,w)\in\mathbb{R}$, this yields

$\mu\in\mathbb{R},\qquad\widetilde{b}(v,v)\neq 0,$ (2.16)

and consequently,

$c(v,v)=\widetilde{b}(Uv,v)=\mu\widetilde{b}(v,v)>0.$

In particular, all eigenvalues of $U$ are real.

Next we show that the non-zero eigenvalues are semi-simple. Assume that we
have a Jordan chain; then there exist $v\neq 0$, $\mu\neq 0$ and $\hat{v}$
such that

$Uv=\mu v,\qquad U\hat{v}-\mu\hat{v}=v.$

It follows that

$\widetilde{b}(v,v)=\widetilde{b}(U\hat{v}-\mu\hat{v},v)=\widetilde{b}(U\hat{v},v)-\mu\widetilde{b}(\hat{v},v)=\widetilde{b}(\hat{v},Uv)-\mu\widetilde{b}(\hat{v},v)=0,$

which contradicts (2.16). Hence $\mu$ is a semi-simple eigenvalue.

Let $\mu_{1},\mu_{2}$ be eigenvalues of $U$ with $\mu_{1}\neq\mu_{2}$ and
eigenvectors $v_{1},v_{2}$. Then

$\mu_{1}\widetilde{b}(v_{1},v_{2})=\widetilde{b}(\mu_{1}v_{1},v_{2})=\widetilde{b}(Uv_{1},v_{2})=\widetilde{b}(v_{1},Uv_{2})=\widetilde{b}(v_{1},\mu_{2}v_{2})=\mu_{2}\widetilde{b}(v_{1},v_{2}),$

which implies that $\widetilde{b}(v_{1},v_{2})=0$. From this we obtain

$c(v_{1},v_{2})=\widetilde{b}(Uv_{1},v_{2})=\mu_{1}\widetilde{b}(v_{1},v_{2})=0$

and hence $(Bv_{1},v_{2})=0$.

Now let $v_{0},v_{1},\ldots,v_{l}$ be a Jordan chain corresponding to the
eigenvalue $0$, i.e.

$Uv_{0}=0,\quad Uv_{1}=v_{0},\;\ldots,\;Uv_{l}=v_{l-1},$

and let $w$ be an eigenvector corresponding to the eigenvalue $\mu\neq 0$.
Then

$\mu^{j}\widetilde{b}(v_{j},w)=\widetilde{b}(v_{j},\mu^{j}w)=\widetilde{b}(v_{j},U^{j}w)=\widetilde{b}(U^{j}v_{j},w)=\widetilde{b}(v_{0},w)=0,$

and hence also $c(v_{j},w)=0$.

Let $X_{1}$ be the linear span of all eigenvectors corresponding to non-zero
eigenvalues and let $X_{0}$ be the algebraic eigenspace corresponding to the
eigenvalue $0$. Further, let us normalise the eigenvectors corresponding to
non-zero eigenvalues such that

$c(p_{i},p_{j})=\delta_{ij}.$

Every $v\in V$ can be written as

$v=v_{0}+\sum_{i=1}^{r}\alpha_{i}p_{i}$ (2.17)

with $v_{0}\in X_{0}$ and $\alpha_{i}\in\mathbb{C}$. ∎

We can now define projection operators that satisfy suitable stability
estimates. These projection operators are crucial in the analysis of the
proposed preconditioner.

######  Lemma 2.7.

Let b and $c$ be as defined in Lemma 2.6, where the eigenvalues,
$(\lambda_{l})_{l=1}^{n}$, and corresponding eigenvectors, $(p_{l})_{l=1}^{n}$
are from the generalised eigenvalue problem (2.11). Then, for any
$m\in\\{r+1,\ldots,n-s\\}$ such that $\lambda_{m+1}>0$, the local projector,
$\Pi$, defined as

$\Pi v=v_{0}+\sum_{l=1}^{m}\alpha_{l}p_{l},\qquad v\in V,$ (2.18)

satisfies

$c(v-\Pi v,v-\Pi v)\leq\frac{1}{\lambda_{m+1}}\texttt{b}(v-\Pi v,v-\Pi v).$
(2.19)

###### Proof.

With $v$ as in (2.12), then

$\displaystyle\textit{{b}}(v-\Pi v,v-\Pi v)$
$\displaystyle=\textit{{b}}\Biggl{(}\sum_{i=m+1}^{r}\alpha_{l}p_{l},\sum_{i=m+1}^{r}\alpha_{l}p_{l}\Biggr{)}=\sum_{i=m+1}^{r}|\alpha_{l}|^{2}\textit{{b}}(p_{l},p_{l})$
$\displaystyle=\sum_{i=m+1}^{r}|\alpha_{l}|^{2}(Bp_{l},p_{l})=\sum_{i=m+1}^{r}|\alpha_{l}|^{2}(\lambda_{l}Cp_{l},p_{l})=\sum_{i=m+1}^{r}\lambda_{l}|\alpha_{l}|^{2}c(p_{l},p_{l})$
$\displaystyle\geq\lambda_{m+1}\sum_{i=m+1}^{r}|\alpha_{l}|^{2}c(p_{l},p_{l})=\lambda_{m+1}c\Biggl{(}\sum_{i=m+1}^{r}\alpha_{l}p_{l},\sum_{i=m+1}^{r}\alpha_{l}p_{l}\Biggr{)}$
$\displaystyle=\lambda_{m+1}c(v-\Pi v,v-\Pi v).$

∎

###  2.3 Domain Decomposition

In order to construct the two-level Schwarz preconditioner, we first need to
partition the global domain, $\Omega$, into a set of first-level and coarse-
level (second-level) subdomains. We also need a method of how to expand the
partitioned subdomains so that they overlap.

######  Definition 2.8.

Given a subdomain $D^{\prime}\subset\Omega$, which is resolved by the chosen
mesh, the extension of $D^{\prime}$ by a layer of elements is

$D=\operatorname{Int}\\!\left(\bigcup_{\\{\ell\mid\operatorname{supp}(\phi_{\ell})\cap
D^{\prime}\not=\emptyset\\}}\operatorname{supp}(\phi_{\ell})\right)$

where $\operatorname{Int}(\cdot)$ is the interior of domain. Extension by
multiple layers can then be achieved by applying this recursively.

It is being assumed that the global mesh, $\mathcal{T}_{h}$, is sufficiently
fine to resolve the subdomains. To construct the coarse-level decomposition,
the global domain is partitioned into a set of $N$ subdomains,
$\\{{\Omega_{i}^{c}}^{\prime}\\}_{i=1}^{N}$. These domains are expanded by one
or more layers of mesh elements, in the sense of Definition 2.8, creating the
overlapping set of subdomains $\\{{\Omega_{i}^{c}}\\}_{i=1}^{N}$. The first-
level decomposition is constructed by taking a subdomain from the coarse
decomposition, ${\Omega_{i}^{c}}$, then partitioning this into a set of
$Q_{i}$ subdomains, which are expanded again using Definition 2.8 such that

${\Omega_{i}^{c}}=\bigcup_{j=1}^{Q_{i}}\Omega_{i,j}^{f},$

for each $i\in 1,\ldots,N$. For the domains ${\Omega_{i}^{c}}$ and
${\Omega_{i,j}^{f}}$, it is possible to define the spaces,

$\widetilde{V}_{i}^{c}\mathrel{\mathop{:}}=\bigl{\\{}v|_{\Omega_{i}^{c}}:v\in
V^{h}\bigr{\\}}\subset H^{1}(\Omega_{i}^{c})\qquad\text{and}\qquad
V_{i}^{c}\mathrel{\mathop{:}}=\bigl{\\{}v\in\widetilde{V}_{i}^{c}:v|_{\partial\Omega_{i}^{c}}=0\bigr{\\}}\subset
H^{1}_{0}(\Omega_{i}^{c}).$ (2.20)
$\widetilde{V}_{i,j}^{f}\mathrel{\mathop{:}}=\bigl{\\{}v|_{\Omega_{i,j}^{f}}:v\in
V^{h}\bigr{\\}}\subset H^{1}(\Omega_{i,j}^{f})\qquad\text{and}\qquad
V_{i,j}^{f}\mathrel{\mathop{:}}=\bigl{\\{}v\in\widetilde{V}_{i,j}^{f}:v|_{\partial\Omega_{i,j}^{f}}=0\bigr{\\}}\subset
H^{1}_{0}(\Omega_{i,j}^{f}).$ (2.21)

######  Notation 2.9.

To simplify notation, we will let D be either $\Omega_{i}^{c}$ or
$\Omega_{i,j}^{f}$, $\widetilde{V}_{D}$ be either $\widetilde{V}_{i}^{c}$ or
$\widetilde{V}_{i,j}^{f}$, and $V_{D}$ be either $V_{i}^{c}$ or $V_{i,j}^{f}$.

For each subdomain, ${\Omega_{i}^{c}}$ and ${\Omega_{i,j}^{f}}$, we denote its
diameter by $H_{i}^{c}$ and $H_{i,j}^{f}$, and we set
$H^{c}\mathrel{\mathop{:}}=\max_{i=1}^{N}H_{i}^{c}$ and
$H^{f}\mathrel{\mathop{:}}=\max_{i=1}^{N}\max_{j=1}^{Q_{i}}H^{f}_{i,j}$. For
any $u,v\in\widetilde{V}_{D}$, the local bilinear forms can be defined

$a_{D}(u,v)\mathrel{\mathop{:}}=\int_{D}A\nabla u\cdot\nabla
v\,\mathrm{d}x,\qquad b_{D}(u,v)\mathrel{\mathop{:}}=\int_{D}\bigl{(}A\nabla
u\cdot\nabla v-k^{2}uv\bigr{)}\,\mathrm{d}x,$ (2.22)

and, for $k>0$, the local norm $\|\cdot\|_{1,k,D}$ is induced by the scalar
product

$(u,v)_{1,k,D}\mathrel{\mathop{:}}=a_{D}(u,v)+k^{2}(u,v)_{D}.$

######  Remark 2.10.

Although $b_{D}(\cdot,\cdot)$ is generally indefinite, for small enough
diameter of D this will become positive definite. This is discussed in Lemma
3.7.

For any $v\in V_{D}$, let $E_{D}v$ denote its zero extension. For both the
fine-level and coarse-level, this will be the extension to the whole of the
domain, $\Omega$. Then,

$\begin{array}[]{ll}E_{i}^{c}:V_{i}^{c}\rightarrow V^{h},&i=1,\ldots,N,\\\
E^{f}_{i,j}:V^{f}_{i,j}\rightarrow V^{h},&j=1,\ldots,Q_{i},\end{array}$ (2.23)

The $L^{2}(\Omega)$ adjoint of the extension operator is called restriction
operator,

$\begin{array}[]{ll}R_{i}^{c}:V^{h}\rightarrow V_{i}^{c},&i=1,\ldots,N,\\\
R^{f}_{i,j}:V^{h}\rightarrow V^{f}_{i,j},&j=1,\ldots,Q_{i},\end{array}$

By use of the extension operator, the restriction of the bilinear forms to
$V_{D}$ can be written as

$a_{\Omega_{D}}(u,v)=a(E_{D}u,E_{D}v),\qquad
b_{\Omega_{D}}(u,v)=b(E_{D}u,E_{D}v),\qquad(u,v)_{\Omega_{D}}=(E_{D}u,E_{D}v)$

for all $u,v\in V_{D}$. The one-level additive Schwarz preconditioner can now
be given in matrix form as

$\mathbf{M}^{-1}_{AS,1}=\sum^{N}_{i=1}\sum_{j=1}^{Q_{i}}\mathbf{E}^{f}_{i,j}(\mathbf{B}^{f}_{i,j})^{-1}\mathbf{R}^{f}_{i,j},\quad\text{where
}\mathbf{B}^{f}_{i,j}=\mathbf{R}^{f}_{i,j}\mathbf{B}\mathbf{E}^{f}_{i,j}.$
(2.24)

Here, $\mathbf{E}_{i,j}^{f}$ and $\mathbf{R}_{i,j}^{f}$ denote the matrix
representations of $E_{i,j}^{f}$ and $R_{i,j}^{f}$ with respect to the basis
functions $\\{\phi_{i}\\}_{i=1}^{n}$ of $V^{h}$ and some basis functions of
$V_{i,j}^{f}$.

In order to improve the effectiveness of the preconditioner, a coarse space is
added. This improves the global exchange of information between the
subdomains. Let $V_{0}\subset V^{h}$ be such a coarse space, let
$E_{0}:V_{0}\rightarrow V^{h}$ be the natural embedding, and let $R_{0}$ be
the $L^{2}$ adjoint of $E_{0}$,

$(v_{0},R_{0}w)=(E_{0}v_{0},w)\qquad\text{for all}\ w\in V^{h},v_{0}\in
V_{0}.$

The two-level additive Schwarz preconditioner can now be given in matrix form
as,

$\mathbf{M}^{-1}_{AS,2}=\mathbf{E}_{0}\mathbf{B}^{-1}_{0}\mathbf{R}_{0}+\mathbf{M}^{-1}_{AS,1},\quad\text{where
}\mathbf{B}_{0}=\mathbf{R}_{0}\mathbf{B}\mathbf{E}_{0}.$ (2.25)

The preconditioned linear system from (2.5) reads as,

$\mathbf{M}^{-1}_{AS,2}\mathbf{B}=\mathbf{M}_{AS,2}^{-1}\mathbf{f}.$ (2.26)

It is now possible to define the projectors used in the analysis. For each
$i=1,\ldots,N$ and $j=1,\ldots,Q$, the projectors,
$T^{f}_{i,j}:V^{h}\rightarrow V^{f}_{i,j}$, are defined by,

$b_{\Omega^{f}_{i,j}}(T^{f}_{i,j}u,v)=b_{\Omega_{i}^{c}}(u,E^{f}_{i,j}v),\quad\forall
v\in V^{f}_{i,j}.$ (2.27)

The projector $T_{0}:V^{h}\rightarrow V_{0}$, is defined as

$b_{\Omega_{0}}(T_{0}u,v)=b(u,E_{0}v),\quad\forall v\in V_{0}.$ (2.28)

where $u\in V^{h}$ and $\Omega_{0}=\Omega$. Sufficient conditions for the
existence of $T^{f}_{i,j}$ are given in Lemmas 3.7 and 3.11.

Given the operators $T^{f}_{i,j}$ and $T_{0}$, the operator
$T:V^{h}\rightarrow V^{h}$ is defined as

$T=E_{0}T_{0}+\sum_{i=1}^{N}\sum_{j=1}^{Q_{i}}E^{f}_{i,j}T^{f}_{i,j}.$ (2.29)

This allows the two-level additive Schwarz preconditioner to be represented in
terms of the projector operator, $T$, as follows.

######  Proposition 2.11.

For any $u,v\in V^{h}$, with corresponding nodal vectors
$\mathbf{u},\mathbf{v}\in\mathbb{R}^{n}$,

$\langle\mathbf{M}_{AS,2}^{-1}\mathbf{B}\mathbf{u},\mathbf{v}\rangle_{\mathbf{D}_{k}}=(Tu,v)_{1,k},$
(2.30)

where $\langle\cdot,\cdot\rangle_{\mathbf{D}_{k}}$ is the inner product on
$\mathbb{R}^{n}$ and the matrix $\mathbf{D}_{k}$ given by

$\mathbf{D}_{k}\mathrel{\mathop{:}}=\mathbf{A}+k^{2}\mathbf{S}.$ (2.31)

###### Proof.

Let $\mathbf{T}^{f}_{i,j}$ be the representation of $T^{f}_{i,j}$ with respect
to the basis functions $\\{\phi_{i}\\}_{i=1}^{n}$ of $V^{h}$. In matrix form
equation (2.27) becomes

$(\mathbf{v}^{f}_{i,j})^{T}\mathbf{B}^{f}_{i,j}\mathbf{T}^{f}_{i,j}\mathbf{u}=(\mathbf{v}^{f}_{i,j})^{T}\mathbf{R}^{f}_{i,j}\mathbf{B}\mathbf{u}\quad\forall\mathbf{u},\mathbf{v}\in\mathbb{R}^{d}.$

meaning that $\mathbf{T}^{f}_{i,j}$ can be written as
$\mathbf{T}^{f}_{i,j}=(\mathbf{B}^{f}_{i,j})^{-1}\mathbf{R}^{f}_{i,j}\mathbf{B}$.
A similar result can be found for the $T_{0}$ operator,
$\mathbf{T}_{0}=(\mathbf{B}_{0})^{-1}\mathbf{R}_{0}\mathbf{B}$. By using the
definition of $\mathbf{T}$ this gives,

$\mathbf{T}=\mathbf{E}_{0}\mathbf{T}_{0}+\sum_{i=1}^{N}\sum_{j=1}^{Q_{i}}\mathbf{E}^{f}_{i,j}\mathbf{T}^{f}_{i,j}=\mathbf{E}_{0}(\mathbf{B}_{0})^{-1}\mathbf{R}_{0}\mathbf{B}+\sum_{i=1}^{N}\sum_{j=1}^{Q_{i}}\mathbf{E}^{f}_{i,j}(\mathbf{B}^{f}_{i,j})^{-1}\mathbf{R}^{f}_{i,j}\mathbf{B}=\mathbf{M}^{-1}_{AS,2}\mathbf{B}.$

Therefore

$\displaystyle(Tu,v)_{1,k}$
$\displaystyle=a(Tu,u)+k^{2}(Tu,u)=\mathbf{v}^{T}\bigl{(}\mathbf{A}\mathbf{T}+k^{2}\mathbf{S}\mathbf{T}\bigr{)}\mathbf{u}$
$\displaystyle=\mathbf{v}^{T}\bigl{(}\mathbf{A}+k^{2}\mathbf{S}\bigr{)}\mathbf{M}^{-1}_{AS,2}\mathbf{B}\mathbf{u}=\mathbf{v}^{T}\mathbf{D}_{k}\mathbf{M}^{-1}_{AS,2}\mathbf{B}\mathbf{u}=\langle\mathbf{M}^{-1}_{AS,2}\mathbf{B}\mathbf{u},\mathbf{v}\rangle_{\mathbf{D}_{k}}.$

∎

###  2.4 The $H_{k}$-GenEO coarse space

In order to use the $H_{k}$-GenEO coarse space, we need to recall some
definitions from [37].

######  Definition 2.12 ([37] Definition 3.2).

Given a subdomain $D$, which is formed from a union of elements from the whole
domain, let

$\overline{\operatorname{dof}}(D)\mathrel{\mathop{:}}=\bigl{\\{}\ell\mid
1\leq\ell\leq n\text{ and }\operatorname{supp}(\phi_{\ell})\cap
D\neq\emptyset\bigr{\\}}$

denote the set of degrees of freedom that are active in the subdomain $D$,
including ones on the boundary. In a similar manner, let

$\operatorname{dof}(D)\mathrel{\mathop{:}}=\bigl{\\{}\ell\mid 1\leq\ell\leq
n\text{ and }\operatorname{supp}(\phi_{\ell})\subset\overline{D}\bigr{\\}}$

denote the internal degrees of freedom.

######  Definition 2.13 (Partition of unity).

Let $D_{i}$ be an overlapping subdomain for $i=1,\ldots,L$, and let
$\operatorname{dof}(D_{i})$ be as in Definition 2.12. For any degree of
freedom, $l\in\\{1,\ldots,n\\}$, let $\mu_{l}$ denote the number of subdomains
for which $l$ is an internal degree of freedom, i.e.

$\mu_{l}\mathrel{\mathop{:}}=\\#\bigl{\\{}i\mid 1\leq i\leq
L,\,l\in\operatorname{dof}(D_{i})\bigr{\\}}$ (2.32)

Then the local partition of unity operator,
$\Xi_{D}:\widetilde{V}_{D}\rightarrow V_{D}$ is defined by

$\Xi_{D}(v)\mathrel{\mathop{:}}=\sum_{j\in\operatorname{dof}(D_{i})}\frac{1}{\mu_{l}}v_{l}\phi_{l}^{i}\qquad\text{for}\
v=\sum_{l\in\overline{\operatorname{dof}}(D_{i})}v_{l}\phi_{l}^{i}\in\widetilde{V}_{D}.$

The local generalised eigenvalue problem, solved on the coarse decomposition,
that is going to form the basis of the coarse space can now be introduced.

######  Definition 2.14.

For each $i\in\\{1,\ldots,N\\}$ we define the following generalised eigenvalue
problem. Find $p^{i}_{\ell}\in\widetilde{V}_{i}^{c}\setminus\\{0\\}$ and
$\lambda_{\ell}^{i}\in\mathbb{R}$ such that

$b_{\Omega_{i}^{c}}(p^{i}_{\ell},v)=\lambda_{\ell}^{i}\bigl{(}\Xi_{i}^{c}(p^{i}_{\ell}),\Xi_{i}^{c}(v)\bigr{)}_{1,k,\Omega_{i}^{c}}\qquad\text{for
all}\ v\in\widetilde{V}_{i}^{c}.$ (2.33)

######  Definition 2.15 ($H_{k}$-GenEO Coarse space).

Let $(p_{\ell}^{i},\lambda_{\ell}^{j})$ be as in Definition 2.14 and and let
$m_{i}$ be such that $\lambda_{m_{i}+1}^{i}>0$ for every
$i\in\\{1,\ldots,N\\}$. The coarse space, $V_{0}$, is given by

$V_{0}\mathrel{\mathop{:}}=\operatorname{span}\bigl{\\{}E_{i}^{c}\Xi_{i}^{c}(p_{\ell}^{i})\mid
l=1,\ldots,m_{i}\text{ and }i=1,\ldots,N\bigr{\\}}.$ (2.34)

We will also need the following notations

$\Lambda\mathrel{\mathop{:}}=\max_{T\in\mathcal{T}_{h}}\bigl{(}\\#\bigl{\\{}\Omega^{f}_{i,j}\mid
1\leq i\leq N,1\leq j\leq
Q,T\subset\Omega^{f}_{i,j}\bigr{\\}}\bigr{)},\qquad\tau\mathrel{\mathop{:}}=\min_{1\leq
i\leq N}\lambda^{i}_{m_{i}+1}.$ (2.35)

######  Remark 2.16.

The key difference between this generalised eigenvalue problem and the one
used in [37] and in the more recent work [7] is that this definition has an
indefinite left-hand side, meaning that the standard spectral theory used for
the eigenvalue problem is no longer applicable. Secondly the right-hand side
in Definition 2.14 is based on a $k$-weighted scalar product. As we shall see,
the use of a weighted scalar product and the induced norm is key in getting
rigorous $k$-dependent estimates. Another key difference is that we are using
two different sizes of domain decomposition for the one-level and coarse
space.

##  3 Statement of the main result and theoretical tools

We start this section with the statement of the main result and we continue by
providing a few technical lemmas needed in the proof of this result, which is
given in the next section.

######  Theorem 3.1 (GMRES convergence of the two-level preconditioned
system).

Let Assumptions 2.1 and 2.3 be satisfied and let $k>0$. Then there exists
$h_{1}>0$ such the following statements are true for all $h\in(0,h_{1})$. Let
$H^{f}$ and $\tau$ be such that, with $\Theta\mathrel{\mathop{:}}=\tau^{-1}$,

$s\mathrel{\mathop{:}}=2\Lambda^{2}\bigl{(}2+3\Lambda^{4}\Theta\bigr{)}\Bigl{(}2k\Theta^{\frac{1}{2}}(1+C_{\textup{{stab}}})+3kH^{f}\Bigr{)}<1.$
(3.1)

When GMRES is applied with the
$\langle\cdot,\cdot\rangle_{\mathbf{D}_{k}}$-inner product with
$\mathbf{D}_{k}$ as in (2.31) to solve the preconditioned system given by
(2.26), then after $m$ iterations, the norm of the residual,
$\mathbf{r}^{(m)}$, is bounded as follows:

$\|\mathbf{r}^{(m)}\|_{\mathbf{D}_{k}}^{2}\leq\bigl{(}1-\gamma^{2}\bigr{)}^{m}\|\mathbf{r}^{(0)}\|_{\mathbf{D}_{k}}^{2},$
(3.2)

where $\gamma$ is given by

$\gamma\mathrel{\mathop{:}}=\frac{1-s}{(2+3\Lambda^{4}\Theta)(18+8\Lambda^{3})}\,.$
(3.3)

######  Corollary 3.2.

Assume that $k\geq 1$. If (3.1) holds, then there exists $C>0$ such that

$H^{f}k\leq C\qquad\text{and}\qquad(1+C_{\textup{{stab}}})^{2}k^{2}\leq
C\tau.$ (3.4)

Conversely, if (3.4) holds for $C>0$ small enough so that

$2\Lambda^{2}\bigl{(}2+3\Lambda^{4}C\bigr{)}\bigl{(}2\sqrt{C}+3C\bigr{)}<1,$
(3.5)

then (3.1) is satisfied and $\gamma$ from (3.3) is bounded below by a positive
constant that depends only on $\Lambda$ and $C$ but not on the coefficient $A$
and the wave-number $k$, which leads to robust GMRES convergence.

###### Proof.

Assume first that (3.1) is satisfied. Since $\Lambda\geq 1$, we have

$2k\Theta^{\frac{1}{2}}(1+C_{\textup{{stab}}})+3kH^{f}\leq\frac{1}{4}$

and hence

$kH^{f}\leq\frac{1}{12}\qquad\text{and}\qquad\frac{(1+C_{\textup{{stab}}})^{2}k^{2}}{\tau}=(1+C_{\textup{{stab}}})^{2}k^{2}\Theta\leq\frac{1}{64}\,,$

which shows that (3.4) holds.

Conversely, assume that (3.4) is satisfied with $C>0$ such that (3.5) holds.
Since, by assumption, $k\geq 1$, we have

$\Theta=\frac{1}{\tau}\leq\frac{C}{(1+C_{\textup{{stab}}})^{2}k^{2}}\leq C.$

Hence

$\displaystyle s$
$\displaystyle=2\Lambda^{2}\bigl{(}2+3\Lambda^{4}\Theta\bigr{)}\Bigl{(}2k\Theta^{\frac{1}{2}}(1+C_{\textup{{stab}}})+3kH^{f}\Bigr{)}\leq
2\Lambda^{2}\bigl{(}2+3\Lambda^{4}C\bigr{)}\bigl{(}2\sqrt{C}+3C\bigr{)}<1,$

i.e. (3.1) is satisfied. Moreover, we obtain

$\gamma=\frac{1-s}{(2+3\Lambda^{4}\Theta)(18+8\Lambda^{3})}\geq\frac{1-2\Lambda^{2}\bigl{(}2+3\Lambda^{4}C\bigr{)}\bigl{(}2\sqrt{C}+3C\bigr{)}}{(2+3\Lambda^{4}C)(18+8\Lambda^{3})},$

which gives a lower bound for $\gamma$ that depends only on $\Lambda$ and $C$.
∎

In practice, conditions (3.4) will introduce a constraint in the size of the
subdomains, depending on $k$ and on the number of modes to be added in the
coarse space.

###  3.1 Properties of the $H_{k}$-GenEO coarse space

The first lemma is an adaptation of [7, Lemma 3.1] and [37, Lemma 2.11] to the
case of an indefinite problem. It gives an error estimate for the local
projection operator, which is used to approximate a function
$v\in\widetilde{V}_{i}^{c}$ in the space being spanned by the eigenfunctions
from Definition 2.14. We see that, despite the indefinite nature of the
bilinear form $b$, similar results hold.

######  Lemma 3.3.

Let $i\in\\{1,\ldots,N\\}$ and let $\\{(p_{\ell}^{i},\lambda_{\ell}^{i})\\}$
be the eigenpairs of the generalised eigenproblem, given in Definition 2.14.
Using the results of Lemma 2.6, suppose that $m_{i}\in\\{r+1,\ldots,n-s\\}$ is
such that $0<\lambda_{m_{i}+1}^{i}<\infty$. Then the local projector,
$\Pi_{m_{i}}^{c}$, defined by

$\Pi_{m_{i}}^{c}v\mathrel{\mathop{:}}=-\sum_{l=1}^{r}b_{\Omega_{i}^{c}}(v,p_{l})p_{l}+\sum_{l=r+1}^{m_{i}}\left(\Xi_{i}^{c}(v),\Xi_{i}^{c}(p_{l})\right)_{1,k,\Omega_{i}^{c}}p_{l},\qquad
v\in\widetilde{V}_{i}^{c},$ (3.6)

satisfies

$0\leq
b_{\Omega_{i}^{c}}(w,w)\leq\|v\|^{2}_{1,k,\Omega_{i}^{c}}\qquad\text{and}\qquad\|\Xi_{i}^{c}(w)\|^{2}_{1,k,\Omega_{i}^{c}}\leq\frac{1}{\lambda_{m_{i}+1}^{i}}b_{\Omega_{i}^{c}}(w,w)\qquad\text{for
all}\ v\in\widetilde{V}_{i}^{c},$ (3.7)

where $w=v-\Pi_{m_{i}}^{c}v$.

###### Proof.

The second inequality of (3.7) can be deduced from the results of Lemma 2.7 by
setting $\texttt{b}\mapsto b_{\Omega_{i}^{c}}$,
$c\mapsto\left(\Xi_{i}^{c}(\cdot),\Xi_{i}^{c}(\cdot)\right)_{1,k,\Omega_{i}^{c}}$
and $m\mapsto m_{i}$. In order to prove the first inequality of (3.7) by using
the projector property we see that

$\displaystyle b_{\Omega_{i}^{c}}\\!\left(v,v\right)$
$\displaystyle=b_{\Omega_{i}^{c}}\\!\left(w+\Pi_{m_{i}}^{c}v,w+\Pi_{m_{i}}^{c}v\right)=b_{\Omega_{i}^{c}}\\!\left(w,w\right)+b_{\Omega_{i}^{c}}\\!\left(\Pi_{m_{i}}^{c}v,\Pi_{m_{i}}^{c}v\right).$

Taking into account that
$b_{\Omega_{i}^{c}}(v,v)=\|v\|^{2}_{1,k,{\Omega_{i}^{c}}}-2k^{2}\|v\|^{2}_{\Omega_{i}^{c}}$
we have

$\displaystyle b_{\Omega_{i}}(w,w)$
$\displaystyle=b_{\Omega_{i}^{c}}\\!\left(v,v\right)-b_{\Omega_{i}^{c}}\\!\left(\Pi_{m_{i}}^{c}v,\Pi_{m_{i}}^{c}v\right)=\|v\|^{2}_{1,k,\Omega_{i}^{c}}-2k^{2}\|v\|^{2}_{\Omega_{i}^{c}}-(\|\Pi_{m_{i}}^{c}v\|^{2}_{1,k,{\Omega_{i}^{c}}}-2k^{2}\|\Pi_{m_{i}}^{c}v\|^{2}_{\Omega_{i}^{c}})$
$\displaystyle=\|v\|^{2}_{1,k,\Omega_{i}^{c}}-\|\Pi_{m_{i}}^{c}v\|^{2}_{1,k,{\Omega_{i}^{c}}}-2k^{2}(\|v\|^{2}_{\Omega_{i}^{c}}-\|\Pi_{m_{i}}^{c}v\|^{2}_{\Omega_{i}^{c}})\leq\|v\|^{2}_{1,k,{\Omega_{i}^{c}}},$

the last inequality results from the projector property
$\|v\|_{\Omega_{i}^{c}}\geq\|\Pi_{m_{i}}^{c}v\|_{\Omega_{i}}$. ∎

From these local error estimates, it is possible to build a global
approximation property.

######  Lemma 3.4 (Global approximation property).

Let $\lambda_{\ell}^{i}$, $m_{i}$ and $\Pi_{m_{i}}^{c}$ be as in Lemma 3.3 and
set

$\Theta\mathrel{\mathop{:}}=\max_{1\leq i\leq
N}\frac{1}{\lambda_{m_{i}+1}^{i}}.$

Further, let $v\in V^{h}$ and define

$z_{0}\mathrel{\mathop{:}}=\sum_{i=1}^{N}\sum_{j=1}^{Q_{i}}E^{f}_{i,j}\Xi^{f}_{i,j}R^{f}_{i,j}\bigl{(}\Pi_{m_{i}}^{c}{v|_{\Omega_{i}^{c}}}\bigr{)}\quad\text{and}\quad
z^{f}_{i,j}\mathrel{\mathop{:}}=\Xi^{f}_{i,j}R^{f}_{i,j}\bigl{(}{v|_{\Omega_{i}^{c}}}-\Pi_{m_{i}}^{c}{v|_{\Omega_{i}^{c}}}\bigr{)},$
(3.8)

for $i=1,\ldots,N$ and $j=1,\ldots,Q$. Then $z^{f}_{i,j}\in V^{f}_{i,j}$ for
$i\in\\{1,\ldots,N\\}$ and $j\in\\{1,\ldots,Q\\}$,

$\sum_{i=1}^{N}\sum_{j=1}^{Q_{i}}\|z^{f}_{i,j}\|_{1,k,\Omega^{f}_{i,j}}^{2}\leq\Lambda^{2}\Theta\|v\|_{1,k}^{2}$
(3.9)

and

$\inf_{z\in
V_{0}}\|v-z\|_{1,k}^{2}\leq\|v-z_{0}\|_{1,k}^{2}\leq\Lambda^{4}\Theta\|v\|^{2}_{1,k},$
(3.10)

###### Proof.

Using Lemma 3.3 and the observation that

$\sum_{i=1}^{N}\sum_{j=1}^{Q_{i}}\left\|z^{f}_{i,j}\right\|_{1,k,\Omega^{f}_{i,j}}^{2}\leq\Lambda\sum_{i=1}^{N}\left\|\Xi_{i}^{c}\bigl{(}{v|_{\Omega_{i}^{c}}}-\Pi_{m_{i}}^{c}{v|_{\Omega_{i}^{c}}}\bigr{)}\right\|_{1,k,\Omega_{i}}^{2},$

we obtain

$\displaystyle\sum_{i=1}^{N}\sum_{j=1}^{Q_{i}}\|z^{f}_{i,j}\|_{1,k,\Omega_{i}}^{2}$
$\displaystyle\leq\Lambda\sum_{i=1}^{N}\frac{1}{\lambda_{m_{i}+1}^{i}}b_{\Omega_{i}^{c}}\Bigl{(}\bigl{(}{v|_{\Omega_{i}^{c}}}-\Pi_{m_{i}}^{c}{v|_{\Omega_{i}^{c}}}\bigr{)},\bigl{(}{v|_{\Omega_{i}^{c}}}-\Pi_{m_{i}}^{c}{v|_{\Omega_{i}^{c}}}\bigr{)}\Bigr{)}$
$\displaystyle\leq\Lambda\sum_{i=1}^{N}\frac{1}{\lambda_{m_{i}+1}^{i}}\big{\|}v|_{\Omega_{i}^{c}}\big{\|}_{1,k,\Omega_{i}^{c}}^{2}\leq\Lambda\Theta\sum_{i=1}^{N}\big{\|}v|_{\Omega_{i}^{c}}\big{\|}_{1,k,\Omega_{i}^{c}}^{2}\leq\Lambda^{2}\Theta\|v\|_{1,k}^{2},$
(3.11)

which shows (3.9). From this we can deduce that

$\displaystyle\|v-z_{0}\|_{1,k}^{2}$
$\displaystyle=\Bigg{\|}\sum_{i=1}^{N}\sum_{j=1}^{Q_{i}}E^{f}_{i,j}\Xi^{f}_{i,j}R^{f}_{i,j}\bigl{(}v|_{\Omega_{i}^{c}}\bigr{)}-\sum_{i=1}^{N}\sum_{j=1}^{Q_{i}}E^{f}_{i,j}\Xi^{f}_{i,j}R^{f}_{i,j}\bigl{(}\Pi_{m_{i}}^{c}{v|_{\Omega_{i}^{c}}}\bigr{)}\Bigg{\|}_{1,k}^{2}$
$\displaystyle=\Bigg{\|}\sum_{i=1}^{N}\sum_{j=1}^{Q_{i}}E^{f}_{i,j}z^{f}_{i,j}\Bigg{\|}_{1,k}^{2}\leq\Lambda^{2}\sum_{i=1}^{N}\sum_{j=1}^{Q_{i}}\|z^{f}_{i,j}\|^{2}_{1,k,\Omega_{i}},$

which, together with (3.11), proves the second inequality in (3.10). Since
$z_{0}\in V_{0}$, also the first inequality in (3.10) follows. ∎

The following lemma shows that the GenEO coarse space, in combination with the
local finite element space, allows for a stable decomposition. This property
is a key component for bounding the condition number in the two-level Schwarz
preconditioner for positive definite cases, as used in [37]. It will be used
for the same purpose in this work for the indefinite case.

######  Lemma 3.5 (Stable decomposition).

Let $v\in V^{h}$ and define $z^{f}_{i,j}$, $i=1,\ldots,Q$, as in (3.8). Then
$v=z_{0}+\sum_{i=1}^{N}\sum_{j=1}^{Q_{i}}E^{f}_{i,j}z^{f}_{i,j}$ and

$\|z_{0}\|_{1,k}^{2}+\sum_{i=1}^{N}\sum_{j=1}^{Q_{i}}\|z^{f}_{i,j}\|_{1,k,\Omega^{f}_{i,j}}^{2}\leq\bigl{(}2+3\Lambda^{4}\Theta\bigr{)}\|v\|^{2}_{1,k}.$

###### Proof.

The relation $v=z_{0}+\sum_{i=1}^{N}\sum_{j=1}^{Q_{i}}E^{f}_{i,j}z^{f}_{i,j}$
follows easily from the definition of the partition of unity. From (3.10) we
obtain

$\|z_{0}\|_{1,k}^{2}\leq\Bigl{(}\|z_{0}-v\|_{1,k}+\|v\|_{1,k}\Bigr{)}^{2}\leq
2\Bigl{(}\|z_{0}-v\|_{1,k}^{2}+\|v\|_{1,k}^{2}\Bigr{)}\leq
2\bigl{(}1+\Lambda^{4}\Theta\bigr{)}\|v\|_{1,k}^{2}.$

Together with (3.9) we arrive at

$\|z_{0}\|_{1,k}^{2}+\sum_{i=1}^{N}\sum_{j=1}^{Q_{i}}\|z^{f}_{i,j}\|_{1,k,\Omega_{i}^{c}}^{2}\leq
2\bigl{(}1+\Lambda^{4}\Theta\bigr{)}\|v\|_{1,k}^{2}+\Lambda^{2}\Theta\|v\|_{1,k}^{2}\leq\bigl{(}2+3\Lambda^{4}\Theta\bigr{)}\|v\|_{1,k}^{2}$

since $\Lambda\geq 1$. ∎

It is convenient to introduce here the projection operators
$P^{f}_{i,j}:V^{h}\rightarrow V^{f}_{i,j}$, such that for each $i=1,\ldots,N$,
and $j=1,\ldots,Q$,

$(P^{f}_{i,j}u,v)_{1,k,\Omega^{f}_{i,j}}=(u,E^{f}_{i,j}v)_{1,k,\Omega}.\quad\forall
v\in V^{f}_{i,j}.$ (3.12)

In [38, Section 2.2] it is proved that these operators are well defined and
orthogonal projections. For the projector $P_{0}:V^{h}\rightarrow V^{0}$, this
is defined as

$(P_{0}u,v)_{1,k,\Omega^{f}_{i,j}}=(u,v),\quad\forall v\in V_{0}.$ (3.13)

Moreover, we define the operator $P:V^{h}\rightarrow V^{h}$ as

$P\mathrel{\mathop{:}}=E_{0}P_{0}+\sum_{i=1}^{N}\sum_{j=1}^{Q_{i}}E^{f}_{i,j}P^{f}_{i,j}.$
(3.14)

######  Proposition 3.6.

Under the same assumptions as in Lemma 3.5, any $u\in V^{h}$ satisfies

$\|u\|^{2}_{1,k}\leq\bigl{(}2+3\Lambda^{4}\Theta\bigr{)}(Pu,u)_{1,k}.$ (3.15)

###### Proof.

Using the definition of $P_{i}$, the Cauchy–Schwarz inequality and Lemma 3.5
we get

$\displaystyle\|u\|_{1,k}^{2}$
$\displaystyle=\Biggl{(}u,z_{0}+\sum_{i=1}^{N}\sum_{j=1}^{Q_{i}}E^{f}_{i,j}z^{f}_{i,j}\Biggr{)}_{1,k}=(u,z_{0})_{1,k}+\Biggl{(}u,\sum_{i=1}^{N}\sum_{j=1}^{Q_{i}}E^{f}_{i,j}z^{f}_{i,j}\Biggr{)}_{1,k}$
$\displaystyle=(P_{0}u,z_{0})_{1,k}+\sum_{i=1}^{N}\sum_{j=1}^{Q_{i}}(P^{f}_{i,j}u,z^{f}_{i,j})_{1,k,\Omega^{f}_{i,j}}\leq\|P_{0}u\|_{1,k}\|z_{0}\|_{1,k}+\sum_{i=1}^{N}\sum_{j=1}^{Q_{i}}\|P^{f}_{i,j}u\|_{1,k,\Omega^{f}_{i,j}}\|z^{f}_{i,j}\|_{1,k,\Omega^{f}_{i,j}}$
$\displaystyle\leq\left(\|P_{0}u\|_{1,k}^{2}+\sum_{i=1}^{N}\sum_{j=1}^{Q_{i}}\|P^{f}_{i,j}u\|_{1,k,\Omega^{f}_{i,j}}^{2}\right)^{\frac{1}{2}}(2+3\Lambda^{4}\Theta\bigr{)}^{\frac{1}{2}}\|u\|_{1,k}$
$\displaystyle=\left((E_{0}P_{0}u,u)_{1,k}+\sum_{i=1}^{N}\sum_{j=1}^{Q_{i}}(E^{f}_{i,j}P^{f}_{i,j}u,u)_{1,k}\right)^{\frac{1}{2}}(2+3\Lambda^{4}\Theta\bigr{)}^{\frac{1}{2}}\|u\|_{1,k}$
$\displaystyle=\left((E_{0}P_{0}u,u)_{1,k}+\left(\sum_{i=1}^{N}\sum_{j=1}^{Q_{i}}E^{f}_{i,j}P^{f}_{i,j}u,u\right)_{1,k}\right)^{\frac{1}{2}}(2+3\Lambda^{4}\Theta\bigr{)}^{\frac{1}{2}}\|u\|_{1,k}$
$\displaystyle=\left(E_{0}P_{0}u+\sum_{i=1}^{N}\sum_{j=1}^{Q_{i}}E^{f}_{i,j}P^{f}_{i,j}u,u\right)_{1,k}^{\frac{1}{2}}(2+3\Lambda^{4}\Theta\bigr{)}^{\frac{1}{2}}\|u\|_{1,k}=(Pu,u)_{1,k}^{\frac{1}{2}}\bigl{(}2+3\Lambda^{4}\Theta\bigr{)}^{\frac{1}{2}}\|u\|_{1,k}$

and the inequality in (3.15) follows. ∎

###  3.2 Solvability and stability of $T^{f}_{i,j}$, $i=1,\ldots,N$ and
$j=1,\ldots,Q$

The next lemma shows that $T^{f}_{i,j}$ is well defined for $i=1,\ldots,N$ and
$j=1,\ldots,Q$, if the subdomains are small enough with respect to $k$.

######  Lemma 3.7 ($T^{f}_{i,j}$ is well defined for $j=1,\ldots,Q$).

If $H^{f}k<\sqrt{2}$, then $b_{\Omega^{f}_{i,j}}(\cdot,\cdot)$ is positive
definite and the operators $T^{f}_{i,j}$, $j=1,\ldots,Q$ are well defined.

###### Proof.

Using the definition of $b_{\Omega^{f}_{i,j}}(\cdot,\cdot)$ and the Friedrichs
inequality we obtain

$b_{\Omega^{f}_{i,j}}(u,u)=a_{\Omega^{f}_{i,j}}(u,u)-k^{2}(u,u)_{\Omega^{f}_{i,j}}\geq\frac{2}{{H^{f}}^{2}}\|u\|_{\Omega^{f}_{i,j}}^{2}-k^{2}\|u\|_{\Omega^{f}_{i,j}}^{2}=\frac{2-{H^{f}}^{2}k^{2}}{{H^{f}}^{2}}\|u\|_{\Omega^{f}_{i,j}}^{2},$

and hence $b_{\Omega^{f}_{i,j}}(\cdot,\cdot)$ is positive definite. By the
Lax–Milgram Lemma, this ensures that $T^{f}_{i,j}$ is well defined. ∎

######  Remark 3.8.

Whilst this a sufficient condition for $T^{f}_{i,j}$ to be well defined, it is
not a necessary condition. In general, if $k$ is different from an eigenvalue
of $a_{\Omega^{f}_{i,j}}$, then $T^{f}_{i,j}$ will be well defined.

Before we proceed with the stability of $T_{i,j}^{f}$, we formulate useful
estimates for the forms $b$ and $b_{\Omega_{i}}$.

######  Lemma 3.9.

The following estimates are valid:

$\displaystyle|b(u,v)|$ $\displaystyle\leq\|u\|_{1,k}\|v\|_{1,k}\qquad$
$\displaystyle\text{for}\ u,v\in V^{h},$ $\displaystyle|b_{D}(u,v)|$
$\displaystyle\leq\|u\|_{1,k,D}\|v\|_{1,k,D}\qquad$
$\displaystyle\text{for}\,u,v,\in\widetilde{V}_{D}.$

###### Proof.

We only prove the first inequality; the proof of the second one is analogous.
Let $u,v\in V^{h}$. Using Cauchy–Schwarz inequalities we obtain

$\displaystyle|b(u,v)|$
$\displaystyle=|a(u,v)-k^{2}(u,v)|\leq|a(u,v)|+k^{2}|(u,v)|\leq\|u\|_{a}\|v\|_{a}+k\|u\|\,k\|v\|$
$\displaystyle\leq\sqrt{\|u\|_{a}^{2}+k^{2}\|u\|^{2}}\cdot\sqrt{\|v\|_{a}^{2}+k^{2}\|v\|^{2}}=\|u\|_{1,k}\|v\|_{1,k}.$

∎

In order to show the robustness of the additive Schwarz method, it is
necessary to prove the stability estimates for the operators $T^{f}_{i,j}$.

######  Lemma 3.10 (Stability of $T^{f}_{i,j}$, $j=1,\ldots,Q$).

Suppose that $H^{f}k\leq\frac{\sqrt{2}\,}{2}$. Then, for all $u\in V^{h}$,

$\|T^{f}_{i,j}u\|_{1,k,\Omega^{f}_{i,j}}\leq
2\big{\|}u|_{\Omega^{f}_{i,j}}\big{\|}_{1,k,\Omega^{f}_{i,j}}.$ (3.16)

###### Proof.

Using the definition of $T^{f}_{i,j}$ in (2.27), Lemma 3.9 and the Friedrichs
inequality (2.9) we obtain

$\displaystyle\|T^{f}_{i,j}u\|^{2}_{1,k,\Omega^{f}_{i,j}}$
$\displaystyle=b_{\Omega^{f}_{i,j}}(T^{f}_{i,j}u,T^{f}_{i,j}u)+2k^{2}\|T^{f}_{i,j}u\|_{\Omega_{i}}=b_{\Omega_{i}}\bigl{(}u|_{\Omega^{f}_{i,j}},T^{f}_{i,j}u\bigr{)}+2k^{2}\|T^{f}_{i,j}u\|_{\Omega^{f}_{i,j}}$
$\displaystyle\leq\big{\|}u|_{\Omega^{f}_{i,j}}\big{\|}_{1,k,\Omega^{f}_{i,j}}\|T^{f}_{i,j}u\|_{1,k,\Omega^{f}_{i,j}}+2k^{2}\|T^{f}_{i,j}u\|_{\Omega^{f}_{i,j}}$
$\displaystyle\leq\big{\|}u|_{\Omega^{f}_{i,j}}\big{\|}_{1,k,\Omega^{f}_{i,j}}\|T^{f}_{i,j}u\|_{1,k,\Omega^{f}_{i,j}}+k^{2}(H^{f})^{2}\|T^{f}_{i,j}u\|^{2}_{1,k,\Omega^{f}_{i,j}},$

which implies that

$\bigl{(}1-k^{2}(H^{f})^{2}\bigr{)}\|T^{f}_{i,j}u\|_{1,k,\Omega^{f}_{i,j}}\leq\big{\|}u|_{\Omega^{f}_{i,j}}\big{\|}_{1,k,\Omega^{f}_{i,j}}.$

Using the condition $H^{f}k\leq\frac{\sqrt{2}\,}{2}$ we can deduce the
required bound. ∎

###  3.3 Existence and stability of $T_{0}$

To ensure that $T_{0}$ is well defined, a condition on $\Theta$ is required.

######  Lemma 3.11 ($T_{0}$ is well defined).

Suppose that

$\sqrt{2}\,k\Lambda^{2}\Theta^{\frac{1}{2}}(1+C_{\textup{{stab}}})<1.$ (3.17)

Then there exists $h_{1}>0$ such that, for all $h\in(0,h_{1})$, the operator
$T_{0}$ is well defined.

###### Proof.

Assume that there exists an $w_{0}\in V_{0}\backslash\\{0\\}$ such that

$b(w_{0},z)=0\qquad\text{for all}\ z\in V_{0}.$ (3.18)

Let $w\in H^{1}_{0}(\Omega)$ be the solution of

$b(w,v)=(w_{0},v)\qquad\text{for all}\ v\in H^{1}_{0}(\Omega).$

Lemma 2.4 implies that there exists an $h_{1}>0$ such that, for all
$h\in(0,h_{1})$, there is a solution $w_{h}\in V^{h}$ of

$b(w_{h},v)=(w_{0},v)\qquad\text{for all}\ v\in V^{h}.$

This holds, in particular, for $v=w_{0}$. This, together with Lemma 3.9,
yields that, for all $z\in V_{0}$,

$\|w_{0}\|^{2}=b(w_{h},w_{0})=b(w_{h},w_{0})-b(z,w_{0})=b(w_{h}-z,w_{0})\leq\|w_{h}-z\|_{1,k}\|w_{0}\|_{1,k}.$

As this is true for all $z\in V_{0}$, we obtain

$\|w_{0}\|^{2}\leq\|w_{0}\|_{1,k}\inf_{z\in
V_{0}}\|w_{h}-z\|_{1,k}\leq\|w_{0}\|_{1,k}\Lambda\Theta^{\frac{1}{2}}\|w_{h}\|_{1,k}$
(3.19)

by Lemma 3.4. Equation (3.18) with $v=w_{0}$ implies that

$0=b(w_{0},w_{0})=\|w_{0}\|_{1,k}^{2}-2k^{2}\|w_{0}\|^{2},$

which, together with (3.19), yields

$\|w_{0}\|^{2}\leq\sqrt{2}\,k\|w_{0}\|\Lambda^{2}\Theta^{\frac{1}{2}}\|w_{h}\|_{1,k}.$
(3.20)

It is possible to combine (2.3) and (2.7) to obtain

$\displaystyle\|w_{h}\|_{1,k}$
$\displaystyle\leq\|w\|_{1,k}+\|w-w_{h}\|_{1,k}=\|w\|_{1,k}+\sqrt{\|w-w_{h}\|_{a}^{2}+k^{2}\|w-w_{h}\|\|^{2}}$
$\displaystyle\leq
C_{\textup{{stab}}}\|w_{0}\|+\sqrt{a_{\textup{{max}}}\|w-w_{h}\|_{H^{1}(\Omega)}^{2}+k^{2}\|w-w_{h}\|^{2}}$
$\displaystyle\leq
C_{\textup{{stab}}}\|w_{0}\|+\sqrt{a_{\textup{{max}}}\varepsilon^{2}\|w_{0}\|^{2}+k^{2}\varepsilon^{4}\|w_{0}\|^{2}}$
$\displaystyle\leq(C_{\textup{{stab}}}+1)\|w_{0}\|$ (3.21)

if $\varepsilon$ is chosen small enough. With (3.21) used in (3.20), we arrive
at

$\|w_{0}\|^{2}\leq\sqrt{2}\,k\Lambda^{2}\Theta^{\frac{1}{2}}(1+C_{\textup{{stab}}})\|w_{0}\|^{2}.$

Together with the condition in (3.17), this leads to a contradiction. ∎

Another requirement is to find the stability conditions for $T_{0}$, which is
done in the next lemma.

######  Lemma 3.12 (Stability of $T_{0}$).

Assume that (3.17) is satisfied. Then there exists $h_{1}>0$ such that, for
$h\in(0,h_{1})$,

$\|T_{0}u-u\|\leq\Lambda^{2}\Theta^{\frac{1}{2}}(1+C_{\textup{{stab}}})\|T_{0}u-u\|_{1,k}\qquad\text{for
all}\ u\in V_{h}.$ (3.22)

Suppose, in addition that,

$2k\Lambda^{2}\Theta^{\frac{1}{2}}(1+C_{\textup{{stab}}})\leq\frac{1}{2};$
(3.23)

then

$\|u-T_{0}u\|_{1,k}\leq 2\|u\|_{1,k}\qquad\text{for all}\ u\in V^{h}.$ (3.24)

###### Proof.

Under condition (3.17), Lemma 3.11 ensures the existence of $h_{1}>0$ such
that, for $h\in(0,h_{1})$, the operator $T_{0}:V^{h}\rightarrow V_{0}$ is well
defined. Consider the following auxiliary problem,

$\text{find }w_{h}\in V^{h}\text{ such that}\quad
b(w_{h},v)=\bigl{(}T_{0}u-u,v\bigr{)}\quad\text{for all}\ v\in V^{h}.$ (3.25)

Note that, by the definition of $T_{0}$, we have $b(T_{0}u-u,z)=0$ for all
$z\in V_{0}$. We can use $v=T_{0}u-u\in V^{h}$ in (3.25) and Lemma 3.9 to
obtain, for every $z\in V_{0}$,

$\displaystyle\|T_{0}u-u\|^{2}$
$\displaystyle=b(w_{h},T_{0}u-u)=b(w_{h},T_{0}u-u)-b(z,T_{0}u-u)$
$\displaystyle=b(w_{h}-z,T_{0}u-u)\leq\|w_{h}-z\|_{1,k}\,\|T_{0}u-u\|_{1,k}.$

Combining this with Lemma 3.4 we obtain

$\|T_{0}u-u\|^{2}\leq\|T_{0}u-u\|_{1,k}\inf_{z\in
V_{0}}\|w_{h}-z\|_{1,k}\leq\|T_{0}u-u\|_{1,k}\Lambda^{2}\Theta^{\frac{1}{2}}\|w_{h}\|_{1,k}.$
(3.26)

In a similar way as in the proof of Lemma 3.11, one can show that
$\|w_{h}\|_{1,k}\leq(1+C_{\textup{{stab}}})\|T_{0}u-u\|$ since $w_{h}$ is a
solution of (3.25), which, together with (3.26), proves (3.22).

We now focus on the proof of (3.24). By the definition of $P_{0}$ in (3.13) we
have

$(P_{0}u-u,v)_{1,k}=0,\qquad u\in V^{h},v\in V_{0}.$

Using $v=T_{0}u\in V_{0}$ in this relation we obtain
$(T_{0}u,P_{0}u-u)_{1,k}=0$. Since $P_{0}u-T_{0}u\in V_{0}$, the definition of
$T_{0}$ yields

$b(u-T_{0}u,P_{0}u-T_{0}u)=0.$ (3.27)

Now we can use (3.27), the link between the bilinear forms
$(\cdot,\cdot)_{1,k}$ and $b$, and the Cauchy–Schwarz inequality to obtain

$\displaystyle\|u-T_{0}u\|_{1,k}^{2}$
$\displaystyle=(u-T_{0}u,u-T_{0}u)_{1,k}=b(u-T_{0}u,u-T_{0}u)+2k^{2}(u-T_{0}u,u-T_{0}u)$
$\displaystyle=b(u-T_{0}u,u-T_{0}u)-b(u-T_{0}u,P_{0}u-T_{0}u)+2k^{2}(u-T_{0}u,u-T_{0}u)$
$\displaystyle=b(u-T_{0}u,u-P_{0}u)+2k^{2}(u-T_{0}u,u-T_{0}u)$
$\displaystyle=(u-T_{0}u,u-P_{0}u)_{1,k}-2k^{2}(u-T_{0}u,u-P_{0}u)+2k^{2}(u-T_{0}u,u-T_{0}u)$
$\displaystyle=(u-T_{0}u,u-P_{0}u)_{1,k}+2k^{2}(u-T_{0}u,P_{0}u-T_{0}u)$
$\displaystyle\leq\|u-T_{0}u\|_{1,k}\|u-P_{0}u\|_{1,k}+2k^{2}\|u-T_{0}u\|\|T_{0}u-P_{0}u\|$
$\displaystyle\leq\|u-T_{0}u\|_{1,k}\|u-P_{0}u\|_{1,k}+2k\|u-T_{0}u\|\|T_{0}u-P_{0}u\|_{1,k}$
$\displaystyle=\|u-T_{0}u\|_{1,k}\|u-P_{0}u\|_{1,k}+2k\|u-T_{0}u\|\|P_{0}(T_{0}u-u)\|_{1,k}$
$\displaystyle\leq\|u-T_{0}u\|_{1,k}\|u\|_{1,k}+2k\|u-T_{0}u\|\|T_{0}u-u\|_{1,k},$

where in the last step we used the fact that $P_{0}$ is an orthogonal
projection w.r.t. $(\cdot,\cdot)_{1,k}$. Dividing both sides by
$\|u-T_{0}u\|_{1,k}$ and using (3.22) and the assumption (3.23) we arrive at

$\displaystyle\|u-T_{0}u\|_{1,k}$
$\displaystyle\leq\|u\|_{1,k}+2k\|u-T_{0}u\|$
$\displaystyle\leq\|u\|_{1,k}+2k\Lambda^{2}\Theta^{\frac{1}{2}}(1+C_{\textup{{stab}}})\|u-T_{0}u\|_{1,k}$
$\displaystyle\leq\|u\|_{1,k}+\frac{1}{2}\|u-T_{0}u\|_{1,k},$

which proves (3.24). ∎

##  4 Proof of the main result

Before Theorem 3.1 can be proved, it is necessary to state and prove the
following lemma.

######  Lemma 4.1.

Let the assumptions in Theorem 3.1 be satisfied and set

$c_{1}\mathrel{\mathop{:}}=\frac{1-s}{2+3\Lambda^{4}\Theta},\qquad
c_{2}\mathrel{\mathop{:}}=18+8\Lambda^{3}.$

Then, for all $u\in V_{h}$,

$c_{1}\|u\|_{1,k}^{2}\leq(Tu,u)_{1,k},$ (4.1)

and

$\|Tu\|_{1,k}^{2}\leq c_{2}\|u\|_{1,k}^{2}.$ (4.2)

###### Proof.

To prove (4.1) and (4.2), let $u\in V^{h}$. We proceed in several steps.

Step 1. We start with (3.15) and then use (3.14), (2.27), (3.12) and (2.29) to
obtain

$\displaystyle(2+3\Lambda^{4}\Theta)^{-1}\|u\|_{1,k}^{2}\leq(Pu,u)_{1,k}=(u,Pu)_{1,k}=(u,E_{0}P_{0}u+\sum^{N}_{i=1}\sum^{Q_{i}}_{j=1}E^{f}_{i,j}P^{f}_{i,j}u)_{1,k}$
$\displaystyle=(u,E_{0}P_{0}u)_{1,k}+\sum^{N}_{i=1}\sum^{Q_{i}}_{j=1}(u,E^{f}_{i,j}P^{f}_{i,j}u)_{1,k}$
$\displaystyle=b(u,E_{0}P_{0}u)+2k^{2}(u,E_{0}P_{0}u)+\sum^{N}_{i=1}\sum^{Q_{i}}_{j=1}\left[b(u,E^{f}_{i,j}P^{f}_{i,j}u)+2k^{2}(u,E^{f}_{i,j}P^{f}_{i,j}u)\right]$
$\displaystyle=b(T_{0}u,P_{0}u)+2k^{2}(u,E_{0}P_{0}u)+\sum^{N}_{i=1}\sum^{Q_{i}}_{j=1}\left[b_{\Omega^{f}_{i,j}}(T^{f}_{i,j}u,P^{f}_{i,j}u)+2k^{2}(u,E^{f}_{i,j}P^{f}_{i,j}u)\right]$
$\displaystyle=(T_{0}u,P_{0}u)_{1,k}-2k^{2}(T_{0}u,P_{0}u)+2k^{2}(u,E_{0}P_{0}u)+\ldots$
$\displaystyle\ldots+\sum^{N}_{i=1}\sum^{Q_{i}}_{j=1}\left[(T^{f}_{i,j}u,P^{f}_{i,j}u)_{1,k,\Omega^{f}_{i,j}}-2k^{2}(T^{f}_{i,j}u,P^{f}_{i,j}u)_{\Omega^{f}_{i,j}}+2k^{2}(u,E^{f}_{i,j}P^{f}_{i,j}u)\right]$
$\displaystyle=(E_{0}T_{0}u,u)_{1,k}-2k^{2}(E_{0}T_{0}u,E_{0}P_{0}u)+2k^{2}(u,E_{0}P_{0}u)+\ldots$
$\displaystyle\ldots+\sum^{N}_{i=1}\sum^{Q_{i}}_{j=1}\left[(E^{f}_{i,j}T^{f}_{i,j}u,u)_{1,k}-2k^{2}(E^{f}_{i,j}T^{f}_{i,j}u,E^{f}_{i,j}P^{f}_{i,j}u)+2k^{2}(u,E^{f}_{i,j}P^{f}_{i,j}u)\right]$
$\displaystyle=\left[(E_{0}T_{0}u,u)_{1,k}+\sum^{N}_{i=1}\sum^{Q_{i}}_{j=1}(E^{f}_{i,j}T^{f}_{i,j}u,u)_{1,k}\right]-\ldots$
$\displaystyle\ldots-\left(2k^{2}(E_{0}T_{0}u-u,E_{0}P_{0}u)+\sum^{N}_{i=1}\sum^{Q_{i}}_{j=1}\left[2k^{2}(E^{f}_{i,j}T^{f}_{i,j}u-u,E^{f}_{i,j}P^{f}_{i,j}u)\right]\right)$
$\displaystyle=\left(E_{0}T_{0}u+\sum^{N}_{i=1}\sum^{Q_{i}}_{j=1}E^{f}_{i,j}T^{f}_{i,j}u,u\right)_{1,k}-\left(2k^{2}(E_{0}T_{0}u-u,E_{0}P_{0}u)+\sum^{N}_{i=1}\sum^{Q_{i}}_{j=1}\left[2k^{2}(E^{f}_{i,j}T^{f}_{i,j}u-u,E^{f}_{i,j}P^{f}_{i,j}u)\right]\right)$
$\displaystyle=(Tu,u)_{1,k}-\left(2k^{2}(E_{0}T_{0}u-u,E_{0}P_{0}u)+\sum^{N}_{i=1}\sum^{Q_{i}}_{j=1}\left[2k^{2}(E^{f}_{i,j}T^{f}_{i,j}u-u,E^{f}_{i,j}P^{f}_{i,j}u)\right]\right)$

which can be rewritten as

$\|u\|^{2}_{1,k}\leq(2+3\Lambda^{4}\Theta)(Tu,u)_{1,k}-(2+3\Lambda^{4}\Theta)\left(2k^{2}(E_{0}T_{0}u-u,E_{0}P_{0}u)+\sum^{N}_{i=1}\sum^{Q_{i}}_{j=1}\left[2k^{2}(E^{f}_{i,j}T^{f}_{i,j}u-u,E^{f}_{i,j}P^{f}_{i,j}u)\right]\right)$
(4.3)

Step 2. The next stage is to bound the sum in (4.3). We start with the term
for $i=0$. The operator $E_{0}$ should be considered as a natural embedding
like the identity operator (and hence $E_{i}T_{0}u=T_{0}u$ and
$E_{i}P_{0}u=P_{0}u$). Further, note that the assumption in (3.1) implies that
(3.23) is satisfied, and hence we can use (3.22), (3.24) and the projection
property of $P_{0}$ to obtain

$\displaystyle-k^{2}(E_{0}T_{0}u-u,E_{0}P_{0}u)$ $\displaystyle\leq
k^{2}\|E_{0}T_{0}u-u\|\|E_{0}P_{0}u\|=k^{2}\|T_{0}u-u\|\|P_{0}u\|$
$\displaystyle\leq k\|T_{0}u-u\|\|P_{0}u\|_{1,k}\leq
k\Lambda^{2}\Theta^{\frac{1}{2}}(1+C_{\textup{{stab}}})\|T_{0}u-u\|_{1,k}\|P_{0}u\|_{1,k}$
$\displaystyle\leq
2k\Lambda^{2}\Theta^{\frac{1}{2}}(1+C_{\textup{{stab}}})\|u\|_{1,k}\|P_{0}u\|_{1,k}$
$\displaystyle\leq
2k\Lambda^{2}\Theta^{\frac{1}{2}}(1+C_{\textup{{stab}}})\|u\|_{1,k}^{2}.$
(4.4)

Step 3. Next we estimate the terms in the sum (4.3) for
$i\in\\{1,\ldots,N\\}$, $j\in\\{1,\ldots,Q\\}$. The inequality in (3.1)
implies that the assumption $H^{\alpha}k\leq\frac{\sqrt{2}\,}{2}$ in Lemma
3.10 is satisfied. Hence we can use (2.9) and (3.16) to obtain

$\displaystyle-k^{2}(E^{f}_{i,j}T^{f}_{i,j}u-u,E^{f}_{i,j}P^{f}_{i,j}u)$
$\displaystyle=-k^{2}\bigl{(}T^{f}_{i,j}u-u|_{\Omega^{f}_{i,j}},P^{f}_{i,j}u\bigr{)}_{\Omega^{f}_{i,j}}\leq
k^{2}\big{\|}T^{f}_{i,j}u-u|_{\Omega^{f}_{i,j}}\big{\|}_{\Omega^{f}_{i,j}}\|P^{f}_{i,j}u\|_{\Omega^{f}_{i,j}}$
$\displaystyle\leq
k\bigl{\|}T^{f}_{i,j}u-u|_{\Omega^{f}_{i,j}}\big{\|}_{1,k,\Omega^{f}_{i,j}}\|P^{f}_{i,j}u\|_{\Omega^{f}_{i,j}}$
$\displaystyle\leq
k\bigl{\|}T^{f}_{i,j}u-u|_{\Omega^{f}_{i,j}}\big{\|}_{1,k,\Omega^{f}_{i,j}}\frac{H}{\sqrt{2}\,}\|P^{f}_{i,j}u\|_{1,k,\Omega^{f}_{i,j}}$
$\displaystyle\leq\frac{kH^{f}}{\sqrt{2}\,}\Bigl{(}\|T^{f}_{i,j}u\|_{1,k,\Omega_{i}}+\big{\|}u|_{\Omega^{f}_{i,j}}\big{\|}_{1,k,\Omega^{f}_{i,j}}\Bigr{)}\|P^{f}_{i,j}u\|_{1,k,\Omega^{f}_{i,j}}$
$\displaystyle\leq\frac{3kH^{f}}{\sqrt{2}\,}\big{\|}u|_{\Omega^{f}_{i,j}}\big{\|}_{1,k,\Omega^{f}_{i,j}}\|P^{f}_{i,j}u\|_{1,k,\Omega^{f}_{i,j}}\leq
3kH^{f}\big{\|}u|_{\Omega^{f}_{i,j}}\big{\|}_{1,k,\Omega^{f}_{i,j}}\|P^{f}_{i,j}u\|_{1,k,\Omega^{f}_{i,j}}.$

Taking the double sum over $i\in\\{1,\ldots,N\\}$ and $j\in\\{1,\ldots,Q\\}$,
applying the Cauchy–Schwarz inequality and the overlap property we arrive at

$\displaystyle-k^{2}\sum_{i=1}^{N}\sum_{j=1}^{Q_{i}}(E^{f}_{i,j}T^{f}_{i,j}u-u,E^{f}_{i,j}P^{f}_{i,j}u)$
$\displaystyle\leq
3kH^{f}\sum_{i=1}^{N}\sum_{j=1}^{Q_{i}}\big{\|}u|_{\Omega^{f}_{i,j}}\big{\|}_{1,k,\Omega^{f}_{i,j}}\|P^{f}_{i,j}u\|_{1,k,\Omega^{f}_{i,j}}$
$\displaystyle\leq
3kH^{f}\Biggl{(}\sum_{i=1}^{N}\sum_{j=1}^{Q_{i}}\big{\|}u|_{\Omega^{f}_{i,j}}\big{\|}_{1,k,\Omega^{f}_{i,j}}^{2}\Biggr{)}^{\frac{1}{2}}\Biggl{(}\sum_{i=1}^{N}\sum_{j=1}^{Q_{i}}\|P^{f}_{i,j}u\|_{1,k,\Omega^{f}_{i,j}}^{2}\Biggr{)}^{\frac{1}{2}}$
$\displaystyle\leq
3kH^{f}\Lambda\|u\|_{1,k}\Biggl{(}\sum_{i=1}^{N}\sum_{j=1}^{Q_{i}}\|P^{f}_{i,j}u\|_{1,k,\Omega^{f}_{i,j}}^{2}\Biggr{)}^{\frac{1}{2}}.$
(4.5)

In order to estimate the sum in (4.5), we consider

$\displaystyle\Bigg{\|}\sum_{i=1}^{N}\sum_{j=1}^{Q_{i}}E^{f}_{i,j}P^{f}_{i,j}u\Bigg{\|}_{1,k}^{2}$
$\displaystyle\leq\Lambda^{2}\sum_{i=1}^{N}\sum_{j=1}^{Q_{i}}\|E^{f}_{i,j}P^{f}_{i,j}u\|_{1,k}^{2}=\Lambda^{2}\sum_{i=1}^{N}\sum_{j=1}^{Q_{i}}(E^{f}_{i,j}P^{f}_{i,j}u,u)_{1,k}$
$\displaystyle=\Lambda^{2}\Biggl{(}\sum_{i=1}^{N}\sum_{j=1}^{Q_{i}}E^{f}_{i,j}P^{f}_{i,j}u,\,u\Biggr{)}_{1,k}\leq\Lambda^{2}\,\Bigg{\|}\sum_{i=1}^{N}\sum_{j=1}^{Q_{i}}E^{f}_{i,j}P^{f}_{i,j}u\Bigg{\|}_{1,k}\|u\|_{1,k},$

and hence

$\Bigg{\|}\sum_{i=1}^{N}\sum_{j=1}^{Q_{i}}E^{f}_{i,j}P^{f}_{i,j}u\Bigg{\|}_{1,k}\leq\Lambda^{2}\|u\|_{1,k},$

which, in turn, implies

$\displaystyle\sum_{i=1}^{N}\sum_{j=1}^{Q_{i}}\|P^{f}_{i,j}u\|_{1,k,\Omega^{f}_{i,j}}^{2}$
$\displaystyle=\sum_{i=1}^{N}\sum_{j=1}^{Q_{i}}(E^{f}_{i,j}P^{f}_{i,j}u,u)_{1,k}=\Biggl{(}\sum_{i=1}^{N}\sum_{j=1}^{Q_{i}}E^{f}_{i,j}P^{f}_{i,j}u,\,u\Biggr{)}_{1,k}$
$\displaystyle\leq\Bigg{\|}\sum_{i=1}^{N}\sum_{j=1}^{Q_{i}}E^{f}_{i,j}P^{f}_{i,j}u\Bigg{\|}_{1,k}\|u\|_{1,k}\leq\Lambda^{2}\|u\|_{1,k}^{2}.$

This, together with (4.5), leads to

$-k^{2}\sum_{i=1}^{N}\sum_{j=1}^{Q_{i}}(E^{f}_{i,j}T^{f}_{i,j}u-u,E^{f}_{i,j}P^{f}_{i,j}u)\leq
3kH^{f}\Lambda^{3}\|u\|_{1,k}^{2}.$ (4.6)

Step 4. We can now combine (4.3), (4.4) and (4.6) to obtain

$\displaystyle\|u\|_{1,k}^{2}$
$\displaystyle\leq(2+3\Lambda^{4}\Theta)(Tu,u)_{1,k}+2\Lambda^{2}(2+3\Lambda^{4}\Theta)\Bigl{(}2k\Theta^{\frac{1}{2}}(1+C_{\textup{{stab}}})+3kH^{f}\Bigr{)}\|u\|_{1,k}^{2}$
$\displaystyle=(2+3\Lambda^{4}\Theta)(Tu,u)_{1,k}-s\|u\|_{1,k}^{2},$

which can be rearranged to prove (4.1).

Step 5. In order to prove (4.2), we start with the following inequality (since
$E_{0}T_{0}u=T_{0}u$),

$\|Tu\|_{1,k}^{2}=\Bigg{\|}T_{0}u+\sum_{i=1}^{N}\sum_{j=1}^{Q_{i}}E^{f}_{i,j}T^{f}_{i,j}u\Biggr{\|}_{1,k}^{2}\leq
2\|T_{0}u\|_{1,k}^{2}+2\Bigg{\|}\sum_{i=1}^{N}\sum_{j=1}^{Q_{i}}E^{f}_{i,j}T^{f}_{i,j}u\Bigg{\|}_{1,k}^{2}$
(4.7)

For the first term we use the Cauchy–Schwarz inequality and (3.24) and obtain

$\displaystyle\|T_{0}u\|_{1,k}^{2}$
$\displaystyle=(T_{0}u,T_{0}u)_{1,k}=(T_{0}u-u,T_{0}u)_{1,k}+(u,T_{0}u)_{1,k}$
$\displaystyle\leq\|T_{0}u-u\|_{1,k}\|T_{0}u\|_{1,k}+\|u\|_{1,k}\|T_{0}u\|_{1,k}$
$\displaystyle\leq
2\|u\|_{1,k}\|T_{0}u\|_{1,k}+\|u\|_{1,k}\|T_{0}u\|_{1,k}=3\|u\|_{1,k}\|T_{0}u\|_{1,k}$

and hence

$\|T_{0}u\|_{1,k}\leq 3\|u\|_{1,k}.$ (4.8)

For the second term in (4.7) we use Lemma 3.10, which implies

$\Bigg{\|}\sum_{i=1}^{N}\sum_{j=1}^{Q_{i}}E^{f}_{i,j}T^{f}_{i,j}u\Bigg{\|}_{1,k}^{2}\leq\Lambda^{2}\sum_{i=1}^{N}\sum_{j=1}^{Q_{i}}\|T^{f}_{i,j}u\|_{1,k,\Omega^{f}_{i,j}}^{2}\leq\Lambda^{2}\sum_{i=1}^{N}\sum_{j=1}^{Q_{i}}4\big{\|}u|_{\Omega_{i}}\big{\|}_{1,k,\Omega^{f}_{i,j}}^{2}\leq
4\Lambda^{3}\|u\|_{1,k}^{2}.$ (4.9)

Combining (4.8) and (4.9) with (4.7) we arrive at

$\|Tu\|_{1,k}^{2}\leq 2\times 9\|u\|_{1,k}^{2}+2\times
4\Lambda^{3}\|u\|_{1,k}^{2}=(18+8\Lambda^{3})\|u\|_{1,k},$

which proves (4.2).

∎

It is now possible to continue with the proof for Theorem 3.1.

###### Proof of Theorem 3.1.

Using (4.1) with (2.30) we obtain

$c_{1}\|u\|_{1,k}^{2}\leq(Tu,u)_{k}=\bigl{\langle}\mathbf{M}_{AS,2}^{-1}\mathbf{B}\mathbf{u},\mathbf{u}\bigr{\rangle}_{\mathbf{D}_{k}},$

which can be written as

$c_{1}\leq\frac{\bigl{\langle}\mathbf{M}_{AS,2}^{-1}\mathbf{B}\mathbf{u},\mathbf{u}\bigr{\rangle}_{\mathbf{D}_{k}}}{\|\mathbf{u}\|_{\mathbf{D}_{k}}^{2}}.$

We can now use (4.2) again with (2.30) and get

$\|\mathbf{M}_{AS,2}^{-1}\mathbf{B}\mathbf{u}\|_{\mathbf{D}_{k}}^{2}=\|Tu\|_{1,k}^{2}\leq
c_{2}\|u\|_{1,k}^{2}=c_{2}\|\mathbf{u}\|^{2}_{\mathbf{D}_{k}},$

which implies

$\|\mathbf{M}_{AS,2}^{-1}\mathbf{B}\|_{\mathbf{D}_{k}}^{2}\leq c_{2}.$

The result follow directly from Elman theory [16] with
$\gamma=\frac{c_{1}}{c_{2}}$. ∎

## References

  * [1] E. Agullo, L. Giraud and L. Poirel, Robust preconditioners via generalized eigenproblems for hybrid sparse linear solvers, SIAM J. Matrix Anal. Appl. 40, 417–439, 2019.
  * [2] I. Babuska and R. Lipton, Optimal local approximation spaces for generalized finite element methods with application to multiscale problems, Multiscale Model. Simul. 9, 373–406, 2011.
  * [3] P. Bastian, R. Scheichl, L. Seelinger and A. Strehlow, Multilevel spectral domain decomposition, SIAM J. Sci. Comput. 45, S1–S26, 2023.
  * [4] N. Bootland, V. Dolean, On the Dirichlet-to-Neumann coarse space for solving the Helmholtz problem using domain decomposition. In Numerical Mathematics and Advanced Applications ENUMATH 2019; Vermolen, F. J., Vuik, C., Eds.; Springer: Cham, Switzerland, 2021; pp. 175–184.
  * [5] N. Bootland, V. Dolean, P. Jolivet and P.-H. Tournier, A comparison of coarse spaces for Helmholtz problems in the high frequency regime, Comput. Math. Appl. 98, 239–253, 2021.
  * [6] N. Bootland, V. Dolean, I. G. Graham, C. Ma, R. Scheichl, GenEO coarse spaces for heterogeneous indefinite elliptic problems. In Domain Decomposition Methods in Science and Engineering XXVI; Brenner, S., et al., Eds.; Springer: Cham, Switzerland, 2022; pp. 117–125.
  * [7] N. Bootland, V. Dolean, I. G. Graham, C. Ma, R. Scheichl, Overlapping Schwarz methods with GenEO coarse spaces for indefinite and non-self-adjoint problems. IMA J. Numer. Anal. 43, 1899–1936, 2023.
  * [8] S. Brenner and R. Scott, The Mathematical Theory of Finite Element Methods, Springer Science & Business Media, 2007.
  * [9] X.C. Cai and M. Sarkis, A restricted additive Schwarz preconditioner for general sparse linear systems, SIAM J. Sci. Comput. 21, 239–247, 1999.
  * [10] X.C. Cai and O.B. Widlund, Domain decomposition algorithms for indefinite elliptic problems, SIAM J. Sci. Stat. Comput. 13(1), 243–258, 1992.
  * [11] X.C. Cai and J. Zou, Some observations on the $l_{2}$ convergence of the additive Schwarz preconditioned GMRES method, Numer. Linear Algebra Appl. 9, 379–397, 2002.
  * [12] L. Conen, V. Dolean, R. Krause and F. Nataf, A coarse space for heterogeneous Helmholtz problems based on the Dirichlet-to-Neumann operator, J. Comput. Appl. Math. 271, 83–99, 2014.
  * [13] V. Dolean, P. Jolivet, and F. Nataf, An Introduction to Domain Decomposition Methods: Algorithms, Theory and Parallel Implementation, SIAM, Philadelphia, 2015.
  * [14] V. Dolean, M. Fry, I. G. Graham, M. Langer, Improvements to the theoretical estimates of the Schwarz preconditioner with $\Delta$-GenEO coarse space for the indefinite Helmholtz problem, https://arxiv.org/abs/2403.18378, 2024.
  * [15] Y. Efendiev, J. Galvis and T.-Y. Hou, Generalized multiscale finite element methods (GMsFEM), J. Comput. Phys. 251, 116–135, 2013.
  * [16] S.C. Eisenstat, H.C. Elman, and M.H. Schultz, Variational iterative methods for nonsymmetric systems of linear equations, SIAM J. Numer. Anal. 20, 345–357, 1983.
  * [17] J. Galvis, E.T. Chung, Y. Efendiev and W.T. Leung, On Overlapping Domain Decomposition Methods for High-Contrast Multiscale Problems. In: P. Bjørstad et al. (eds), Domain Decomposition Methods in Science and Engineering XXIV, _Lect. Notes Comput. Sci. Eng._ , vol 125, pp. 45–57. Springer, Cham, 2018.
  * [18] J. Galvis and Y. Efendiev, Domain decomposition preconditioners for multiscale flows in high-contrast media, Multiscale Model. Simul. 8, 1461–1483, 2010.
  * [19] J. Galvis and Y. Efendiev, Domain decomposition preconditioners for multiscale flows in high contrast media: reduced dimension coarse spaces, Multiscale Model. Simul. 8, 1621–1644, 2010.
  * [20] D. Gilbarg and N.S. Trudinger, Elliptic Partial Differential Equations of Second Order, Springer-Verlag, 2001.
  * [21] S. Gong, I.G. Graham and E.A. Spence, Domain decomposition preconditioners for high-order discretisations of the heterogeneous Helmholtz equation, IMA J. Numer. Anal. 41, 2139–2185, 2021.
  * [22] J. Gopalakrishnan and J. Pasciak, Overlapping Schwarz preconditioners for indefinite time harmonic Maxwell equations, Math. Comput. 72(241), 1–15, 2001.
  * [23] I.G. Graham, P.O. Lechner, and R. Scheichl, Domain decomposition for multiscale PDEs, Numer. Math. 106, 589–626, 2007.
  * [24] I.G. Graham, E.A. Spence and E. Vainikko, Domain decomposition preconditioning for high-frequency Helmholtz problems with absorption, Math. Comput. 86, 2089-2127, 2017.
  * [25] W. Hackbusch, Elliptic Differential Equations Theory and Numerical Treatment, Second Edition, Springer, 2017.
  * [26] F. Hecht, New development in FreeFem++, J. Numer. Math., 20(3–4), 251–266, 2012.
  * [27] A. Heinlein, A. Klawonn, J. Knepper, and O. Rheinbach, Adaptive GDSW coarse spaces for overlapping Schwarz methods in three dimensions, SIAM J. Sci. Comput. 41, A3045–A3072, 2019.
  * [28] P. Jolivet, V. Dolean, F. Hecht, F. Nataf, C. Prud’Homme, and N. Spillane, High performance domain decomposition methods on massively parallel architectures with FreeFEM++, J. Numer. Math., 20(3–4), 287–302, 2012.
  * [29] R. Lehoucq, D. Sorensen, and C. Yang, ARPACK users’ guide: solution of large-scale eigenvalue problems with implicitly restarted Arnoldi methods, SIAM, Philadelphia, 1998.
  * [30] G. Leoni, A First Course in Sobolev Spaces, American Mathematical Soc., 2017.
  * [31] F. Nataf and P.-H. Tournier, A GenEO domain decomposition method for saddle point problems, https://hal.archives-ouvertes.fr/hal-02343808, 2021.
  * [32] F. Nataf, H. Xiang, V. Dolean, and N. Spillane, A coarse space construction based on local Dirichlet-to-Neumann maps, SIAM J. Sci. Comput., 33(4), 1623–1642, 2011.
  * [33] A.H. Schatz, An observation concerning Ritz–Galerkin methods with indefinite bilinear forms, Math. Comput., 28(128), 959–962, 1974.
  * [34] A.H. Schatz and J.P. Wang, Some new error estimates for Ritz–Galerkin methods with minimal regularity assumptions, Math. Comput., 213(65), 19–27, 1996.
  * [35] B.F. Smith, P. Bjorstad, and W. Gropp, Domain Decomposition: Parallel Multilevel Methods for Elliptic Partial Differential Equations, Cambridge University Press, 1996.
  * [36] N. Spillane, Toward a new fully algebraic preconditioner for symmetric positive definite problems, https://hal.archives-ouvertes.fr/hal-03187092, 2021.
  * [37] N. Spillane, F. Nataf, V. Dolean, P. Hauret, C. Pechstein, and R. Scheichl, Abstract robust coarse spaces for systems of PDEs via generalized eigenproblems in the overlaps, Numer. Math. 4(126), 741–740, 2014.
  * [38] A. Toselli and O. Widlund, Domain Decomposition Methods: Algorithms and Theory, Springer Series in Computational Mathematics. Springer-Verlag, 2005.