1. Introduction
The discretization of several partial differential equations relevant in applications, such as the Helmholtz equation, the timeharmonic Maxwell equations or the reactionconvectiondiffusion equation, yields linear systems whose matrices are not symmetric/selfadjoint or indefinite. The rigorous analysis of the convergence of preconditioned iterative methods for such problems is harder than for symmetric positive definite (SPD) problems. Indeed, in the SPD problem case, Hilbert space theorems such as the Fictitious Space lemma (see
[23, 16]) yield a powerful general framework of spectral analysis for domain decomposition preconditioners. In addition, in the general problem case the conjugate gradient method cannot be used, and the analysis of the spectrum of the preconditioned matrix is not sufficient for iterative methods such as GMRES suited for nonselfadjoint matrices. In fact, as stated in [15], “any nonincreasing convergence curve can be obtained with GMRES applied to a matrix having any desired eigenvalues”. In the literature, GMRES convergence estimates are based for instance on the field of values
[11, 10, 3] or on the pseudospectrum (see [26] and references therein) of the preconditioned operator. For example, field of values bounds were derived for overlapping domain decomposition preconditioners for the highfrequency Helmholtz [13, 14] and timeharmonic Maxwell [4] equations.Here, by generalizing the work of [14], we analyze for general problems the convergence of the preconditioned GMRES method in its weighted version [12]. We identify a list of assumptions and estimates that are sufficient to obtain an upper bound on the norm of the preconditioned matrix, and a lower bound on the distance of its field of values from the origin. This analysis applies to a class of onelevel overlapping domain decomposition preconditioners, with Robintype or more general absorbing transmission conditions on the interfaces between subdomains. This type of preconditioners with the basic Robintype transmission conditions was first introduced in ([20], 2007) for the Helmholtz equation and called OBDDH (Overlapping Balancing Domain Decomposition for Helmholtz). It was later studied in ([18], 2015) for general symmetric positive definite problems and viewed as a symmetric variant of the ORAS preconditioner ([25], 2007), hence called SORAS (Symmetrized Optimized Restricted Additive Schwarz). Note that in [20] several onelevel and twolevel versions, with a coarse space based on plane waves, were tested numerically, and only later the onelevel OBDDH version was rigorously analyzed in [14], for the Helmholtz equation. In [18] a twolevel version, with a spectral coarse space, was rigorously analyzed for general SPD problems.
We apply our general framework to the case of convectiondiffusion equations for the analysis of onelevel overlapping domain decomposition preconditioners with Robintype transmission conditions. For these equations, the twolevel overlapping case with Dirichlet transmission conditions was analyzed in [6, 7], where a coarse space is built from a coarse mesh whose elements are sufficiently small. As for the non overlapping case, it was studied with Robin or more general transmission conditions in e.g. [21, 22], see also [19] for some numerical results. In a different spirit, the Neumann–Neumann algorithm [5] was generalized to convectiondiffusion equations in [1], and a coarse space not based on a coarse mesh was proposed in [2] although without convergence analysis.
The paper is structured as follows. In section 2 we first describe in detail the considered class of domain decomposition preconditioners and introduce notation for the global and local inner products and norms. In section 3 we state and prove the main theorem, which provides a general and practical tool for the rigorous convergence analysis of the preconditioner. This framework is applied in section 4 to the case of the heterogeneous reactionconvectiondiffusion equation. After specifying the global and local bilinear forms, inner products and norms and the discretization, we prove estimates for the assumptions of the theorem for this equation, without making any a priori assumption on the regime of the physical coefficients nor of the numerical parameters. Finally, we discuss for a particular regime the resulting lower bound on the field of values.
2. Setting
Let denote the (potentially complexvalued) matrix arising from the discretization of the problem to be solved, posed in an open domain . The matrix is not necessarily positive definite nor selfadjoint. This means that here we do not necessarily require , where ; note that “selfadjoint matrix” is a synonym for “Hermitian matrix”. In particular, if is realvalued this means that here it does not need to be symmetric.
The definition of the preconditioner is based on a set of overlapping open subdomains , such that and each is a union of elements of the mesh of . Then we consider the set of the unknowns on the whole domain, so , and its decomposition into the non disjoint subsets corresponding to the different overlapping subdomains , with . Then one builds the following matrices (see e.g. [9, §1.3]):

the restriction matrices from to the subdomain : they are Boolean matrices whose entry equals if the th unknown in is the th one in and vanishes otherwise;

the extension by zero matrices from the subdomain to , which are Boolean matrices given by ;

the partition of unity matrices , which are diagonal matrices with real non negative entries such that . They can be seen as matrices that properly weight the unknowns belonging to the overlap between subdomains;

the local matrices , of size , arising from the discretization of subproblems posed in , with for instance Robintype or absorbing^{1}^{1}1Absorbing boundary conditions are approximations of transparent boundary conditions. Basic absorbing boundary conditions are Robintype boundary conditions, which consist in a weighted combination of Neumanntype and Dirichlettype boundary conditions. Their precise definition depends on the specific problem. For instance, for Maxwell equations impedance boundary conditions are Robintype absorbing boundary conditions. transmission conditions on the interfaces .
Finally, the onelevel SORAS preconditioner is defined as
Note that here the preconditioner is not selfadjoint when is not selfadjoint, even if we maintain the SORAS name, where S stands for ‘Symmetrized’. In fact, this denomination was introduced in [18] for SPD problems, since in that case the SORAS preconditioner is a symmetric variant of the ORAS preconditioner .
The weighted GMRES method [12]
differs from the standard one in the norm used for the residual minimization, which is not the standard Hermitian norm but a more general weighted norm. For vectors of degrees of freedom
, using the notation to indicate the Hermitian inner product, given a selfadjoint positive definite matrix , we consider the weighted normLocally, on the subdomain , we consider a weighted norm represented by a selfadjoint positive definite matrix : for vectors of degrees of freedom local to , we define
Typically is a Neumanntype matrix on , that is, coming from an inner product at the continuous level with no boundary integral.
3. General theory
In order to apply Elmantype estimates for the convergence of weighted GMRES [12], such as [13, Theorem 5.1] or its improvement [4, Theorem 5.3], we need to prove an upper bound on the weighted norm of the preconditioned matrix, and a lower bound on the distance of its weighted field of values from the origin. Recall that the field of values (or numerical range) of a matrix with respect to the inner product induced by a matrix is the set defined as
(Note that the convergence estimate for GMRES based on the field of values can be used only when this latter does not contain .)
The following theorem, which generalizes the theory for the Helmholtz equation developed in [14], identifies assumptions that are sufficient to obtain the two bounds. In particular, the proof was inspired by the one of [14, Theorem 3.11] and by the analysis in subsection [14, §3.2].
We will need the notation for the commutator .
Theorem 3.1.
For , assume that for all global vectors of degrees of freedom and local vectors of degrees of freedom in
(3.1) 
Suppose that there exists such that for all local vectors of degrees of freedom in , , we have
(3.2) 
and such that for all global vectors of degrees of freedom
(3.3) 
For , suppose also that there exist such that for all local vectors of degrees of freedom in
(3.4)  
(3.5) 
and that satisfies the following infsup condition: there exists such that for all local vectors of degrees of freedom
(3.6) 
Then, we obtain the following upper bound on the norm of the preconditioned matrix:
(3.7) 
If in addition, for , for all global vectors of degrees of freedom and local vectors of degrees of freedom in
(3.8) 
and there exists such that for all local vectors of degrees of freedom in
(3.9) 
then we obtain the following lower bound on the distance of the field of values of the preconditioned matrix from the origin:
(3.10) 
Remark 3.2.
Proof.
To obtain both bounds an important quantity is
For its estimate, for any vector of degrees of freedom local to , write
where assumption (3.1) was used. Thus we have found that is the solution to a local problem with a righthand side involving the commutator between the partition of unity and the local matrix. So by the stability bound (3.6), we have:
Moreover by assumption (3.5)
Therefore
(3.11) 
Together with (3.11), a direct consequence of (3.11) itself and assumption (3.4) will be also used repeatedly:
(3.12) 
Now, it is easy to obtain the upper bound (3.7): for we have
where we have indicated above each inequality sign which equation was used.
The derivation of the lower bound (3.10) is more involved. First of all write
where, beside applying assumption (3.8), we have used the fact that the partition of unity matrices are realvalued and diagonal, hence symmetric, and the restriction matrices satisfy . Now, we make appear the commutator between the partition of unity and the local inner product matrix, and also the quantity :
Therefore
(3.13) 
For the first term in (3.13) we use the partition of unity property and assumption (3.2) with :
so
For the second term in (3.13), we use first the CauchySchwarz inequality:
Finally for the third term in (3.13) we write
In conclusion, inserting these estimations in (3.13) we obtain the lower bound (3.10).
∎
Note that the lower bound on the field of values (3.10) is interesting only if the positive term dominates the negative ones. The result could be improved by designing a suitable coarse space to add a second level to the standard SORAS preconditioner. For general problems this constitutes a real challenge currently; for symmetric positive definite problems, we refer to [18] for the definition of a coarse space and a twolevel SORAS preconditioner leading to a robust lower bound on the spectrum.
3.1. Comments on the assumptions of Theorem 3.1
Assumptions (3.1) and (3.8) may appear unconventional at first glance, but they are satisfied for quite natural choices of the local sesquilinear form and continuous norm on the subdomains. More precisely, if the th entry of the diagonal of is not zero, assumption (3.1) requires that the th rows of and are equal; likewise assumption (3.8) requires that the th rows of and are equal. First of all, note that typically the entries corresponding to of the partition of unity are zero. Moreover, arises from the discretization of a local sesquilinear form that usually is like the global sesquilinear form yielding but with the integrals on instead of and with an additional boundary integral on . In this case assumption (3.1) is satisfied. Likewise, assumption (3.8) is satisfied if the local continuous norm yielding is obtained from the global continuous norm yielding just by replacing with in the integration domain. As an illustration, see the bilinear forms , and the continuous norms , defined in §4 for the reactionconvectiondiffusion equation and the proof of Lemma 4.7.
Assumptions (3.2) and (3.3) are classical inequalities in the domain decomposition framework. Inequality (3.2) is dubbed in [14] ‘a kind of converse to the stable splitting result’, and it can be viewed as a continuity property of the reconstruction operator . In [14, Lemma 3.6] the inequality is proved at the continuous level for the Helmholtz energy norm (see [14, eq. (1.15)]) with
(3.14) 
in other words, is the maximum number of neighboring subdomains. Note that the proof in [14, Lemma 3.6] (essentially consisting in the one in [13, eq. (4.8)]) is more generally valid, for instance whenever the local continuous norm can be obtained from the global continuous norm just by replacing with in the integration domain, as before.
When the local and the global continuous norms are related as above again, it is immediate to prove inequality (3.3) with
(3.15) 
that is is the maximal multiplicity of the subdomain intersection (this constant is like the one defined in [9, Lemma 7.13] and is slightly more precise than that was used in [14, eq. (2.10)]). Therefore and are geometric constants, related to the decomposition into overlapping subdomains.
4. The reactionconvectiondiffusion equation
As an illustration of the general theory, we apply Theorem 3.1 to the case of the heterogeneous reactionconvectiondiffusion equation; recall that the convergence theory for the (homogeneous) Helmholtz equation was developed in [14]. Let be an open bounded polyhedral domain. We study the heterogeneous reactionconvectiondiffusion problem in conservative form, with Robintype and Dirichlet boundary conditions:
(4.1) 
where , is the outwardpointing unit normal vector to , , a.e. in , , , and there exist , such that
, , , a.e. in . In this case all quantities are realvalued. Note that the appropriate Robintype boundary condition here is not simply ; we will comment below about a possible choice of , see (4.2). Now, set . In order to find the variational formulation, multiply the equation by a test function and integrate over :
For the first divergence term use the identity , while for the second integrate by parts:
and, also by integration by parts,
Therefore, imposing the boundary conditions, the variational formulation is: find such that
where is a non symmetric bilinear form defined as
and
With the notation
we write
Suppose that there exist , such that
where the positiveness of is a classical assumption in reactionconvectiondiffusion equation literature, and define the weighted scalar product and norm
On each subdomain we consider the local problem with bilinear form
where we impose absorbing transmission conditions on the subdomain interface : for instance, we can choose a zerothorder Taylor approximation of transparent conditions given by
(4.2) 
(see e.g. [19] and the references therein). We define the local weighted scalar product and norm
which would correspond to Neumanntype boundary conditions on . Set
Remark 4.1.
For , if or are supported in and thus vanish on , then
For the finite element discretization, let be a family of conforming simplicial meshes of that are uniformly shape regular as the mesh diameter tends to zero. We consider finite elements of order
Consider nodal basis functions (for example Lagrange basis functions), in duality with the degrees of freedom associated with nodes , that is
. Thus we can define the standard nodal Lagrange interpolation operator
. Assume that satisfies the standard interpolation error estimate (see e.g. [8, §3.1]): for , provided(4.3) 
Assume that the subdomains are polyhedra with characteristic length scale , which means
Definition 4.2 (Characteristic length scale).
A domain has characteristic length scale if its diameter , its surface area , and its volume , where means uniformly bounded from below and above.
For each , denote by the space of functions in restricted to . So, , , , are defined as the matrices arising, respectively, from the finite element discretization of , on , and , on : for with vectors of degrees of freedom , and for with vectors of degrees of freedom
(4.4)  
(4.5) 
Consider partition of unity functions , , such that in , and , so in particular they are zero on . Assume that
(4.6) 
where is the size of the overlap between subdomains, and is required to be independent of the simplex and of the derivative multiindex . The diagonal matrices are constructed by interpolation of the functions , so the vector of degrees of freedom of is .
Next we need to introduce a technical ingredient, namely socalled multiplicative trace inequalities. Such estimates can be found e.g. in [17].
Lemma 4.3 (Multiplicative trace inequality, [17, last eq. on page 41]).
For any bounded Lipschitz open subset there exists such that, for all , we have .
Although the constant above does a priori depend on the shape of , it does not depend on its diameter (it is invariant under homothety). In the sequel we shall assume that there exists a fixed constant such that we have . This holds for example if the subdomains are assumed to be uniformly starshaped i.e. there exists a fixed constant such that, for each there exists satisfying
(4.7)  
Assumption 4.4.
The multiplicative trace estimates of Lemma 4.3 hold uniformly for all subdomains.
This assumption allows to derive uniform upper bounds for the continuity modulus of the bilinear forms and .
Comments
There are no comments yet.