# NUMERICAL ASSESSMENT OF TWO-LEVEL DOMAIN DECOMPOSITION PRECONDITIONERS FOR INCOMPRESSIBLE STOKES AND ELASTICITY EQUATIONS.

1. Introduction. In , one-level domain decomposition methods for Stokes equations were introduced in conjunction with non-standard interface conditions. However, they present a lack of scalability with respect to the number of subdomains. It means that splitting the problem domain into a larger number of subdomains leads to an increase in size of the plateau region in the convergence of an iterative method (see Figure 1.1) when using the one-level domain decomposition methods. This is caused by the lack of global information, as subdomains can only communicate with their neighbours. Hence, when the number of subdomains increases in one direction, the length of the plateau also increases. Even in cases where the local problems are of the same size, the iteration count grows with the increase of the number of subdomains. This can be also observed in all the experiments in this manuscript in the case of one-level methods.

The remedy for this is the use of a second level in the preconditioner, or a coarse space correction, that adds the necessary global information. Two-level algorithms have been analysed for several classes of problems in . The key point of these kind of methods is to choose an appropriate coarse space. The classical coarse space introduced by Nicolaides in  for a Poisson problem is defined by vectors whose support is in each subdomain, and its dimension is equal to the number of subdomains. Flow problems or linear elasticity in mixed form require a construction of a different type of coarse space as seen for example in . The latter is based on a coarse grid correction and it uses the underlying properties of saddle point problems. Another type of coarse space has been introduced in  by using eigenvectors of local Dirichlet-to-Neumann maps. In a similar spirit, we introduce a spectral coarse space by enriching the global information to be shared by the subdomains, that generalises the classical one while allowing to attain a prescribed convergence of the two-level algorithm. As we will see in the following, this approach can help to deal with strongly heterogeneous problems. This idea was introduced for the first time in  in the case of multigrid methods. It relies on solving local generalised eigenvalue problems, allowing to choose suitable vectors for the coarse space.

For overlapping domain decomposition preconditioners, a similar idea was introduced in the case of Darcy equations in [13, 14]. The authors of  considered also the heterogeneous Darcy equation and presented a different generalised eigenvalue problem based on local Dirichlet-to-Neumann maps. The method has been analysed in  and proved to be very robust in the case of small overlaps. The same idea was extended numerically to the heterogeneous Helmholtz problem in . The authors of  apply the coarse space associated with low-frequency eigenfunctions of the subdomain Dirichlet-to-Neumann maps for the generalisation of the optimised Schwarz methods, named 2-Lagrange multiplier methods.

The first attempt to extend this spectral approach to general symmetric positive definite problems was made in  as an extension of [13, 14]. Since some of the assumptions of the previous framework are hard to fulfil, the authors of  proposed a slightly different approach for symmetric positive definite problems. Their idea of constructing a partition of unity operator associated with the degrees of freedom allows to work with various finite element spaces. An overview of different kinds of two-level methods can be found in [10, Chapters 5 and 7].

Despite the fact that all these approaches provide satisfactory results, there is no universal treatment to build efficient coarse spaces in the case of non-definite problems, such as Stokes equations. The spectral coarse spaces that we use in this work are inspired by those proposed in . The authors introduced and tested numerically symmetrised two-level preconditioners for overlapping algorithms which use Robin interface conditions between the subdomains; see (5.1) for details. They have applied these preconditioners to the solution of saddle point problems, such as nearly incompressible elasticity and Stokes problems discretised by Taylor-Hood finite elements. In our case, we use non-standard interface conditions. Therefore the use of spectral coarse spaces could lead to an important gain.

In this work, we test this improvement in case of nearly incompressible elasticity and Stokes equations that are discussed in Section 2. They are discretised by the Taylor-Hood [15, Chapter II, Section 4.2] and hybrid discontinuous Galerkin methods [7, 8], presented in Section 3. In Section 4, we introduce the two-level domain decomposition preconditioners. Sections 5 and 6 present the two and three dimensional numerical experiments, respectively. Finally, a summary is outlined in Section 7.

2. The differential equations. Let [OMEGA] be an open polygon in [R.sup.2] or an open Lipschitz polyhedron in [R.sup.3], with Lipschitz boundary [GAMMA] := [partial derivative][OMEGA].The dimension of the space is denoted by d = 2, 3. We use bold face letters for tensor or vector variables. In addition, we denote the normal and tangential components as [u.sub.n] := u * n and [u.sub.t] := u - [u.sub.n]n, where n is the outward unit normal vector to the boundary [GAMMA].

For D [subset] [OMEGA], we use the standard space [L.sup.2](D) and the space [C.sup.0]([bar.D]), which denotes the set of all continuous functions on the closure of a set D. Let us define the following Sobolev spaces

[mathematical expression not reproducible]

where, for [alpha] = ([[alpha].sub.1],..., [[alpha].sub.d]) [member of] [N.sup.d] and |[alpha]| = [[summation].sup.d.i=1] [[alpha].sub.i], we let [mathematical expression not reproducible] and tr : [H.sup.1]([OMEGA]) [right arrow] [H.sup.[1/2]] ([partial derivative][OMEGA]) denote the trace operator. In addition, we use the following notation for the space including boundary and average conditions

[mathematical expression not reproducible]

where [??] [subset] [partial derivative]D. If [??] = [partial derivative]D, then [H.sup.1.sub.[??]](D) is denoted as [H.sup.1.sub.0](D).

Now we present the two differential problems considered in this work.

2.1. Stokes equation. Let us start with the d-dimensional (d = 2,3) Stokes problem

(2.1) [mathematical expression not reproducible]

where u : [bar.[OMEGA]] [right arrow] [R.sup.d] is the velocity field, p : [bar.[OMEGA]] [right arrow] R the pressure, [nu] > 0 the viscosity, which is considered to be constant, and f [member of] [[[L.sup.2] ([OMEGA])].sup.d] is a given function. We define the stress tensor [sigma] := [nu][nabla]u - pI and the flux as [[sigma].sub.n] := [sigma] n. For [u.sub.D] [member of] [[[H.sup.[1/2]]([GAMMA])].sup.d] and g [member of] [L.sup.2]([GAMMA]) we consider three types of boundary conditions:

* Dirichlet (non-slip)

(2.2) u = [u.sub.D] on [GAMMA];

* tangential-velocity and normal-flux (TVNF)

(2.3) [mathematical expression not reproducible]

* normal-velocity and tangential-flux (NVTF)

(2.4) [mathematical expression not reproducible]

The third type of boundary condition has already been considered for the Stokes problem in .

2.2. Nearly incompressible elasticity equation. From a mathematical point of view, the nearly incompressible elasticity problem is very similar to the Stokes equations. The difference is that instead of considering the gradient [nabla]v, the symmetric gradient [epsilon](v) := [1/2]([nabla]v + [[nabla].sup.T]v) is used. We want to solve the following d-dimensional (d = 2, 3) problem

(2.5) [mathematical expression not reproducible]

where u : [bar.[OMEGA]] [right arrow] [R.sup.d] is the displacement field, p : [OMEGA] [right arrow] R the pressure, f [member of] [[[L.sup.2] ([OMEGA])].sup.D] is a given function, [lambda] and [mu] are the Lame coefficients, defined by

[lambda] = [E[nu]/(1 + [nu])(1 - 2[nu])], [mu] = [E/2(1 + [nu])]

where E is the Young modulus and v the Poisson ratio. We define the stress tensor as [[sigma].sup.sym] := 2[micro][epsilon](u) - pI and its normal component as [[sigma].sup.sym.sub.n] := [[sigma].sup.sym]n. For g [member of] [L.sup.2](r) we consider three types of boundary conditions:

* mixed: for [GAMMA] = [[GAMMA].sub.D] [union] [[GAMMA].sub.N] with [[GAMMA].sub.D] [intersection] [[GAMMA].sub.N] = [??], we impose

(2.6) [mathematical expression not reproducible]

* tangential-di placement and normal-normal- tre (TDNNS)

(2.7) [mathematical expression not reproducible]

* normal-displacement and tangential-normal-stress (NDTNS)

(2.8) [mathematical expression not reproducible]

The second type of boundary condition has already been considered for linear elasticity equation in .

3. The numerical methods. Let [{[T.sub.h]}.sub.h>0] be a regular family of triangulations of [OMEGA] made of simplices. For each triangulation [T.sub.h], [E.sub.h] denotes the set of its facets (edges for d = 2, faces for d = 3). In addition, for each element K [member of] [T.sub.h], [h.sub.K] := diam(K), and we set [mathematical expression not reproducible]. We define the following broken Sobolev spaces on the set of all edges in [E.sub.h] (for d =2)

[L.sup.2]([E.sub.h]):= {v : v[|.sub.E] [member of] [L.sup.2](E), [for all] E [member of] [E.sub.h]}.

Moreover, for D [subset] [OMEGA], [P.sub.k](D) denotes the space of polynomials of total degree smaller than (or equal to) k on the set D.

We now present the two discretisations that will be used in the numerical experiments.

3.1. Taylor-Hood discretisation. We first consider the Taylor-Hood discretisation using the following approximation spaces

[mathematical expression not reproducible]

where k [greater than or equal to] 2; see [15, Chapter II, Section 4.2].

If (2.1) is supplied with the homogeneous boundary conditions (2.2), then the discrete problem reads:

Find ([u.sub.h], [p.sub.h]) [member of] (T[H.sup.k.sub.h] [intersection] ([[H.sup.1.sub.0]([OMEGA])].sup.d]) x ([R.sup.k-1.sub.h] [intersection] [L.sup.2.sub.0]([OMEGA]))

s.t. for all ([u.sub.h], [p.sub.h]) [member of] (T[H.sup.k.sub.h] [intersection] ([[H.sup.1.sub.0]([OMEGA])].sup.d]) x ([R.sup.k-1.sub.h] [intersection] [L.sup.2.sub.0]([OMEGA]))

[mathematical expression not reproducible]

In case of TVNF boundary conditions (2.3), we define [V.sub.t] := {v [member of] [[[H.sup.1] ([OMEGA])].sup.D] : [v.sub.t] = 0 on [GAMMA]}, and the discrete problem reads:

Find ([u.sub.h], [p.sub.h]) [member of] (T[H.sup.k.sub.h] [intersection] [V.sub.t]) x [R.sup.k-1.sub.h]

s.t. for all ([u.sub.h], [q.sub.h]) [member of] (T[H.sup.k.sub.h] [intersection] [V.sub.t]) x [R.sup.k-1.sub.h]

[mathematical expression not reproducible]

If NVTF boundary conditions (2.4) are used, then we define the space

[V.sub.n] := {v [member of] [[[H.sup.1]([OMEGA])].sup.d] : [v.sub.n] = 0 on [GAMMA]},

Find ([u.sub.h], [p.sub.h]) [member of] (T[H.sup.k.sub.h] [intersection] [V.sub.n]) x ([R.sup.k-1.sub.h] [intersection] [L.sup.2.sub.0]([OMEGA]))

s.t. for all ([u.sub.h], [p.sub.h]) [member of] (T[H.sup.k.sub.h] [intersection] [V.sub.n]) x ([R.sup.k-1.sub.h] [intersection] [L.sup.2.sub.0]([OMEGA]))

[mathematical expression not reproducible]

In a similar way, if the problem (2.5) is supplied with the boundary conditions (2.6), then the discrete problem reads

Find [mathematical expression not reproducible]

s.t. for all [mathematical expression not reproducible]

[mathematical expression not reproducible]

The other discrete problems associated with (2.5), equipped with either TDNNS boundary conditions (2.7) or NDTNS boundary conditions (2.8), are similar to (3.1) or (3.2), respectively.

3.2. Hybrid discontinuous Galerkin discretisation. We restrict the discussion to the two dimensional case d = 2. This method has been presented and analysed in . The velocity is approximated using the Brezzi-Douglas-Marini spaces (see [4, Section 2.3.1]) of degree k given by

[BDM.sup.k.sub.h] := {[v.sub.h] [member of] H(div, [OMEGA]) : [v.sub.h][|.sub.k] [member of] [[[P.sub.k] (K)].sup.2], [for all]K [member of] [T.sub.h]},

[BDM.sup.k.sub.h,[??]] := {[v.sub.h] [member of] H(div, [OMEGA]) : [v.sub.h][|.sub.k] [member of] [[[P.sub.k] (K)].sup.2], [for all]K [member of] [T.sub.h], [([v.sub.h]).sub.n] = 0 on [??]},

where [??] [subset] [partial derivative][OMEGA]. If [??] = [partial derivative][OMEGA], then [BDM.sup.k.sub.h,[??]] is denoted [BDM.sup.k.sub.h,0].

The pressure is approximated in the space

[Q.sup.k-1.sub.h] := {[q.sub.h] [member of] [L.sup.2] ([OMEGA]) : [q.sub.h][|.sub.K] [member of] [P.sub.k-1] (K), [for all]K [member of] [T.sub.h]}.

Finally, we introduce a Lagrange multiplier, aimed at approximating the tangential component of the velocity. The space where this multiplier is sought is given by

[M.sup.k-1.sub.h] := {[[??].sub.h] [member of] [L.sup.2] ([E.sub.h]) : [[??].sub.h][|.sub.E] [member of] [P.sub.k-1] (E), [for all]E [member of] [E.sub.h]},

[M.sup.k-1.sub.h,[??]] := {[[??].sub.h] [member of] [M.sup.k-1.sub.h] : [[??].sub.h] = 0 on [??]},

where [??] [subset] [partial derivative][OMEGA]. The latter space incorporates some boundary conditions and, if [??] = [partial derivative][OMEGA], then [M.sup.k-1.sub.h,[??]] is denoted [M.sup.k-1.sub.h,0]. Furthermore, we introduce for all E [member of] [E.sub.h] the [L.sup.2](E)-projection [[PHI].sup.k-1.sub.E]: [L.sup.2] (E) [right arrow] [P.sub.k-1] (E), defined by

[mathematical expression not reproducible]

and we set [[PHI].sup.k-1] : [L.sup.2] ([E.sub.h]) [right arrow] [M.sup.k-1.sub.h], defined as [[PHI].sup.k-1][|.sub.E] := [[PHI].sup.k-1.sub.E] for all E [member of] [E.sub.h].

If (2.1) is supplied with the homogeneous boundary conditions (2.2), then the discrete problem reads:

Find ([u.sub.h], [[??].sub.h], [p.sub.h]) [member of] [BDM.sup.k.sub.h,0] x [M.sup.k-1.sub.h,0] x ([Q.sup.k-1.sub.h] [intersection] [L.sup.2.sub.0]([OMEGA]))

s.t for all ([u.sub.h], [[??].sub.h], [q.sub.h]) [member of] [BDM.sup.k.sub.h,0] x [M.sup.k-1.sub.h,0] x ([Q.sup.k-1.sub.h] [intersection] [L.sup.2.sub.0]([OMEGA])),

[mathematical expression not reproducible]

where

[mathematical expression not reproducible]

[tau] > 0 is a stabilisation parameter, and

(3.3) [mathematical expression not reproducible]

If TVNF boundary conditions (2.3) are used, then the discrete problemreads:

Find ([u.sub.h], [[??].sub.h], [p.sub.h]) [member of] [BDM.sup.k.sub.h] x [M.sup.k-1.sub.h,0] x [Q.sup.k-1.sub.h]

s.t. for all ([u.sub.h], [[??].sub.h], [q.sub.h]) [member of] [BDM.sup.k.sub.h] x [M.sup.k-1.sub.h,0] x [Q.sup.k-1.sub.h],

(3.4) [mathematical expression not reproducible]

In case of NVTF boundary conditions (2.4), the discrete problem reads:

Find ([u.sub.h], [[??].sub.h], [p.sub.h]) [member of] [BDM.sup.k.sub.h,0] x [M.sup.k-1.sub.h] x ([Q.sup.k-1.sub.h] [intersection] [L.sup.2.sub.0]([OMEGA]))

s.t. for all ([u.sub.h], [[??].sub.h], [q.sub.h]) [member of] [BDM.sup.k.sub.h,0] x [M.sup.k-1.sub.h] x ([Q.sup.k-1.sub.h] [intersection] [L.sup.2.sub.0]([OMEGA])),

(3.5) [mathematical expression not reproducible]

In a similar way, if the problem (2.5) is supplied with the mixed boundary conditions (2.6), then the discrete problem reads:

Find [mathematical expression not reproducible]

s.t. for all [mathematical expression not reproducible],

[mathematical expression not reproducible]

where

[mathematical expression not reproducible]

b is defined by (3.3), and

c([r.sub.h],[q.sub.h]) := -[1/[lambda]] [[integral].sub.[OMEGA]][r.sub.h][q.sub.h] ds.

The other discrete problems associated with (2.5), equipped with either TDNNS boundary conditions (2.7) or NDTNS boundary conditions (2.8), are similar to (3.4) or (3.5), respectively.

4. The domain decomposition preconditioners. Let us assume that we have to solve the following linear system AU = F, where A is the matrix arising from the discretisation of the Stokes or linear elasticity equation on the domain [OMEGA], U is the vector of unknowns, and F is the right-hand side. To accelerate the performance of an iterative Krylov method [10, Chapter 3] applied to this system, we will consider domain decomposition preconditioners which are naturally parallel. They are based on an overlapping decomposition of the computational domain.

Let [{[T.sub.h,i]}.sup.N.sub.i=1] be a partition of the triangulation [T.sub.h]; see examples in Figure 4.1. For an integer value l [greater than or equal to] 0, we set [T.sup.0.sub.h,i] = [T.sub.h,i] and define an overlapping decomposition [{[T.sup.l.sub.h,i]}.sup.N.sub.i=1] such that [T.sup.l.sub.h,i] is a set of all triangles from [T.sup.l-1.sub.h,i] and all triangles from [T.sub.h]\[T.sup.l-1.sub.h,i] that have non-empty intersection with [T.sup.l-1.sub.h,i]. With this definition, the width of the overlap will be 2l. Furthermore, if [W.sub.h] stands for the finite element space associated to [T.sub.h], let [W.sup.l.sub.h,i] be the local finite element space on [T.sup.l.sub.h,i], which is a triangulation of [[OMEGA].sub.i].

Let N be the set of indices of degrees of freedom of [W.sub.h] and [N.sup.l.sub.i] the set of indices of degrees of freedom of [W.sup.l.sub.h,i] for l [greater than or equal to] 0. Moreover, we define the restriction operator [R.sub.i] : [W.sub.h] [right arrow] [W.sup.l.sub.h,i] as a rectangular matrix of size |[N.sup.l.sub.i]| x |N|, such that if V is the vector of degrees of freedom of [v.sub.h] [member of] [W.sub.h], then [R.sub.i]V is the vector of degrees of freedom of [W.sup.l.sub.h,i] in [[OMEGA].sub.i]. The extension operator from [W.sup.l.sub.h,i] to [W.sub.h] and its associated matrix are both given by [R.sup.T.sub.i]. In addition, we introduce a partition of the unity [D.sub.i] as a diagonal matrix of size |[N.sup.l.sub.i| x |[N.sup.l.sub.i]|, such that

Id = [N.summation over (i=1)][R.sup.T.sub.i][D.sub.i][R.sub.i],

where Id [member of] [R.sup.|N|x|N|] is the identity matrix.

We first recall the Modified Restricted Additive Schwarz (MRAS) preconditioner introduced in  for the Stokes equation. This preconditioner is given by

(4.1) [M.sup.-1.sub.M RAS] = [N.summation over (i=1)][R.sup.T.sub.i][D.sub.i][B.sup.-1.sub.i][R.sub.i],

where [B.sub.i] is the matrix associated to a discretisation of the Stokes equation (2.1) in [[OMEGA].sub.i] where we impose either TVNF (2.3) or NVTF (2.4) boundary conditions on [partial derivative][[OMEGA].sub.i] [intersection] [OMEGA].In the case of a discretisation of the elasticity equation (2.5) in [[OMEGA].sub.i], we impose either TDNNS (2.7) or NDTNS (2.8) boundary conditions on [partial derivative][[OMEGA].sub.i] [intersection] [OMEGA].

We now introduce a symmetrised variant of (4.1), called Symmetrised Modified Restricted Additive Schwarz (SMRAS), given by

(4.2) [M.sup.-1.sub.SM RAS] = [N.summation over (i=1)][R.sup.T.sub.i][D.sub.i][B.sup.-1.sub.i][D.sub.i][R.sub.i].

4.1. Two-level methods. A two-level version of the SMRAS and MRAS preconditioners will be based on a spectral coarse space obtained by solving the following local generalised eigenvalue problems

Find [mathematical expression not reproducible]

(4.3) [[??].sub.j][V.sub.jk] = [[lambda].sub.jk][B.sub.j][V.sub.jk].

Here, the [[??].sub.j] are local matrices associated to a discretisation of a local Neumann boundary value problem in [[OMEGA].sub.j], where the Neumann boundary conditions are imposed only on the interface between the subdomains and not on the physical boundary. For example, in the case of the Stokes problem (2.1) with Dirichlet boundary conditions (2.2), we consider the following local problem

[mathematical expression not reproducible]

Let [theta] > 0 be a user-defined threshold. We define [Z.sub.GenEO] [subset] [R.sup.|N|] as the vector space spanned by the family of vectors [mathematical expression not reproducible], corresponding to eigenvalues smaller than [theta]. The value of [theta] is chosen such that, for a given problem and preconditioner, the behaviour of the method is robust, in the sense that its convergence does not depend, or depends very weakly, on the number of subdomains.

We are now ready to introduce the two-level method with coarse space [Z.sub.GenEO]. Let [P.sub.0] be the A-orthogonal projection onto the coarse space [Z.sub.GenEO]. The two-level SMRAS preconditioner is defined as

[M.sup.-1.sub.SM RAS,2] = [P.sub.0][A.sup.-1] + (Id - [P.sub.0])[M.sup.-1.sub.SM RAS] (Id - [P.sup.T.sub.0]).

Furthermore, if [R.sub.0] is a matrix whose rows are a basis for the coarse space [Z.sub.GenEO], then

[P.sub.0][A.sup.-1] = [R.sup.T.sub.0] [([R.sub.0][AR.sup.T.sub.0]).sup.-1] [R.sub.0].

In a similar way, we can introduce the two-level MRAS preconditioner

[M.sup.-1.sub.M RAS,2] = [P.sub.0][A.sup.-1] + (Id - [P.sub.0])[M.sup.-1.sub.M RAS] (Id - [P.sup.T.sub.0]).

5. Numerical results for two dimensional problems. In this section we assess the performance of the preconditioners defined in Section 4.1. We compare the newly introduced ones with that of ORAS and SORAS, introduced in . This kind of preconditioners are associated with the Robin interface conditions and require an optimised parameter, as it can be seen in (5.1) below. The big advantage of the SMRAS and MRAS preconditioners from the previous section is that they are parameter-free. We consider the partial differential equation model for nearly incompressible elasticity and Stokes flow as problems of similar mixed formulation. Each of these problems is discretised by using the Taylor-Hood method from Section 3.1 and the hdG discretisation from Section 3.2.

Our experiments are based on the classical weak scaling test. This test is built as follows. A domain [??] is split into a triangulation [[??].sub.h]. For each of element K [member of] [[??].sub.h], [h.sub.k] = diam(K), and we denote the mesh size by [mathematical expression not reproducible]. Then, this triangulation is split into overlapping subdomains of size H, in such a way that remains constant. In the absence of a second level in the preconditioner, if the number of subdomains grows then the convergence gets slower. A coarse space provides global information and leads to more robust behaviour.

The simplest way to build a coarse space is to consider the zero energy modes. More precisely, they are the eigenvectors associated with the zero eigenvalues of (4.3) on a floating subdomains. Here, by a floating subdomain we mean a subdomain without Dirichlet boundary condition on any part of the boundary. Then the matrix on the left-hand side of (4.3) is singular and there are zero eigenvalues. These zero energy modes are the rigid body motions (three in two dimensions, six in three dimensions) for the elasticity problem, and the constants (two in two dimensions, three in three dimensions) for the Stokes equations. Unfortunately, for some cases this choice is not sufficient, so we have collected the smallest M eigenvalues for each subdomain and build a coarse space by including the eigenvectors associated to them. The different values of M are presented in the table in brackets.

All experiments have been made by using FreeFem++ , which is a free software specialised in variational discretisations of partial differential equations. We use GMRES  as an iterative solver. Generalized eigenvalue problems to generate the coarse space are solved using ARPACK . The overlapping decomposition into subdomains can be uniform (Unif) or generated by METIS (MTS) . In each of the examples, we consider decompositions with two layers of mesh size h in the overlap. Tables show the number of iterations needed to achieve a relative [l.sup.2]-norm of the error smaller than [10.sup.-6], that is, [mathematical expression not reproducible], where U is the solution of the global problem produced by a direct solver, and [U.sub.m] denotes the mth iteration of the iterative solver. In addition, DOF stands for number of degrees of freedom and N for the number of subdomains in all tables.

5.1. Taylor-Hood discretisation. In this section we consider the Taylor-Hood discretisation from Section 3.1, with different values of k [greater than or equal to] 2 for nearly incompressible elasticity and Stokes equations.

5.1.1. Nearly incompressible elasticity. Since we consider the preconditioners with various interface conditions, we need to comment the way of imposing them. ORAS and SORAS preconditioners follow  and use Robin interface conditions. This means that the weak formulation of the linear elasticity problem contains the following term

(5.1) [mathematical expression not reproducible],

where again, following , we choose [alpha] = 10. Fortunately, the MRAS and SMRAS preconditioners are parameter-free. In this section, for all the associated numerical experiments we use the zero vector as an initial guess for the GMRES iterative solver. Moreover, the overlapping decomposition into subdomains is generated by METIS.

TEST CASE 5.1 (The L-shaped domain problem). We consider the L-shaped domain [OMEGA] = [(-1, 1).sup.2] \ {(0, 1) x (-1, 0)} clamped on the left side and partly from the top and the bottom, as depicted in Figure 5.1(a). This example is similar to the one in . The associated boundary value problem is

(5.2) [mathematical expression not reproducible]

The physical parameters are E = [10.sup.5] and v = 0.4999, hence the problem is nearly incompressible. In Figure 5.1(b) we plot the mesh of the bent domain.

We choose k = 3 for the Taylor-Hood discretisation. In Figure 5.2 we plot the eigenvalues of one floating subdomain. The clustering of small eigenvalues of the generalised eigenvalue problem defined in (4.3) suggests the number of eigenvectors to be added to the coarse space. The three zero eigenvalues correspond to the zero energy modes.

The results of Table 5.1 show a clear improvement in the scalability of the two-level preconditioners over the one-level ones. In fact, using five eigenvectors per subdomain, the number of iterations is virtually unaffected by the number of subdomains. All two-level preconditioners show a comparable performance. For this case, increasing the dimension of the coarse space beyond 5 x N eigenvectors does not seem to improve the results dramatically.

TEST CASE 5.2 (The heterogeneous beam problem). We consider a heterogeneous beam with ten layers of steel and rubber. Five layers are made from steel, with the physical parameters E = 210, [10.sup.9] and v = 0.3, and five are made from rubber, with the physical parameters E = [10.sup.8] and v = 0.4999, as depicted in Figure 5.3(a). A similar example was considered in . The computational domain is the rectangle [OMEGA] = (0, 5) x (0, 1). The beam is clamped on its left side, hence we consider the following problem

(5.3) [mathematical expression not reproducible]

In Figure 5.3(b) we plot the mesh of the bent beam. Because of the heterogeneity of the problem, we do not notice a clear clustering of the eigenvalues; see Figure 5.4. In such case, it is well-known that a coarse space including only three zero energy modes is not sufficient . That is why we consider a coarse space built using 5 or 7 eigenvectors per subdomain.

As in the previous example, the introduction of a coarse space provides a significant improvement in the number of iterations needed for convergence. Due to the high heterogeneity of this problem, more eigenvectors per subdomain are needed to obtain scalable results. We notice an important improvement of the convergence when using two-level methods (see Table 5.2), although we get a stable number of iterations only when considering a coarse space which is sufficiently big.

5.1.2. Stokes equation. We now turn to the Stokes discrete problem given in Sections 3.1. Once again in case of ORAS and SORAS we choose [alpha] =10 as in  for the Robin interface conditions (5.1). In the first case we consider a random initial guess for the GMRES iterative solver. Later, with the second example, we will use the zero vector as initial guess.

TEST CASE 5.3 (The driven cavity problem). We consider the following problem on the unit square [OMEGA] = [(0, 1).sup.2]

(5.4) [mathematical expression not reproducible]

In Figure 5.5 we depict the discrete velocity and pressure.

We start with two energy modes only; see Figure 5.6. This already provides some improvement. Then, we add more eigenvectors to see if they bring a further improvement.

The conclusions remain the same as for the L-shaped domain problem for the nearly incompressible elasticity equation discretised by Taylor-Hood method ([TH.sup.3.sub.h], ), since Tables 5.3 and 5.1 show similar results.

TEST CASE 5.4 (The T-shaped domain problem). Finally, we consider a T-shaped domain [OMEGA] = (0, 1.5) x (0, 1) [union] (0.5, 1) x (-1, 1), and we impose Dirichlet boundary conditions given by

(5.5) [mathematical expression not reproducible]

The numerical solution of this problem is depicted in Figure 5.7. The overlapping decomposition into subdomains is generated by METIS.

Once again a clustering of small eigenvalues of generalised eigenvalue problem defined in (4.3) is a motivation of the size of the coarse space; see Figure 5.8.

As in all examples for Taylor-Hood discretisation, we notice an important improvement in the convergence when two-level methods are used, although from Table 5.4 we can see that the coarse spaces containing five eigenvectors seem to be sufficient.

5.2. hdG discretisation. In this section we discretise the nearly incompressible elasticity equation and the Stokes flow by using the lowest order hdG discretisation (k = 1) introduced in Section 3.2.

5.2.1. Nearly incompressible elasticity. In case of ORAS and SORAS we consider the Robin interface conditions as in , with [alpha] = 10. For all numerical experiments in this section we use the zero vector as an initial guess for the GMRES iterative solver. Moreover, the overlapping decomposition into subdomains is generated by METIS.

TEST CASE 5.5 (The L-shaped domain problem). We consider the L-shaped domain for the discrete problem (5.2).

Table 5.5 shows an important improvement in the convergence that is brought by the two-level methods. We cannot conclude that SMRAS preconditioners are much better than SORAS, although we can note that coarse space improvement is visible for MRAS preconditioners and not for ORAS. For symmetric preconditioners (SMRAS and SORAS), five eigenvectors seem to lead already to satisfactory results, while for the non-symmetric ones a bigger coarse space is required. On the other hand, we state the fact that the new preconditioners are parameter-free, which makes them easier to use.

TEST CASE 5.6 (The heterogeneous beam problem). We consider the heterogeneous beam with ten layers of steel and rubber defined as in the problem (5.3).

We notice an improvement only when using a coarse space that is sufficiently large; see Table 5.6. Furthermore, we get a stable number of iterations only for the symmetric preconditioners (SMRAS and SORAS), and the coarse space improvement in case of ORAS preconditioner is much less visible than in case of MRAS preconditioners. This may be due to the fact we have not chosen an optimized parameter in the Robin interface conditions (5.1).

5.2.2. The Stokes equation. We now turn to the Stokes discrete problem given in Section 3.2. Once again in case of ORAS and SORAS we choose [alpha] =10 as in  for the Robin interface conditions (5.1). In the first case, we consider a random initial guess for the GMRES iterative solver. Later, with the second example, we will use the zero vector as initial guess.

TEST CASE 5.7 (The driven cavity problem). We consider the driven cavity defined as in the problem (5.4). The conclusions remain the same as in the case of the nearly incompressible elasticity equation for the L-shaped domain, although Table 5.7 shows that the coarse spaces containing five eigenvectors seem to decrease the number of iterations even in the case of MRAS preconditioners that are not fully scalable.

TEST CASE 5. 8 (The T-shaped domain problem). Finally, we consider a T-shaped domain [OMEGA] = (0, 1.5) X (0, 1) [union] (0.5, 1) X (-1, 1), and we impose mixed boundary conditions (5.5). The numerical solution of this problem is depicted in Figure 5.7.

In this case, scalable results can only be observed for the preconditioners associated with the non-standard interface conditions (MRAS and SMRAS), and when using a coarse space that is sufficiently large; see Table 5.8. In the case of ORAS or SORAS, one possibility is to choose a different parameter [alpha], but the proof of this, as well as the question of whether this would have a positive impact, are open problems.

6. Numerical results for three dimensional problems. In this section we again assess the performance of the preconditioners as in Section 5, but this time in case of three dimensional problems. We consider the three-dimensional analogues of the Stokes and nearly incompressible elasticity problems considered in last section. Both problems are discretised by using the Taylor-Hood methods from Section 3.1. In addition, we use the same tools as in Section 5. For both test cases we use the zero vector as initial guess.

6.1. Taylor-Hood discretisation. In this section we consider the Taylor-Hood discretisation from Section 3.1, with k = 2, for nearly incompressible elasticity and Stokes equations.

6.1.1. Nearly incompressible elasticity. In the three dimensional space, ORAS and SORAS preconditioners also require an optimized parameter. We follow  and use Robin interface conditions (5.1) with [alpha] =10.

TEST CASE 6.1 (The homogeneous beam problem). We consider a homogeneous beam with the physical parameters E = [10.sup.8] and v = 0.4999. The computational domain is the rectangle [OMEGA] = (0, 5) x (0, 1) x (0, 1). The beam is clamped on one side, hence we consider the following problem

The results of Table 6.1 show a clear improvement in the scalability of the two-level preconditioners over the one-level ones. In fact, using only zero energy modes, the number of iterations is virtually unaffected by the number of subdomains. All two-level preconditioners show a comparable performance. For this case, increasing the dimension of the coarse space beyond 6 x N eigenvectors does not seem to improve the results significantly.

6.1.2. The Stokes equation. We now turn to the Stokes discrete problem given in Section 3.1. Once again, in the case of ORAS and SORAS we choose [alpha] =10 as in  for the Robin interface conditions (5.1).

TEST CASE 6.2 (The driven cavity problem). The test case is the three-dimensional version of the driven cavity problem. We consider the following problem on the unit cube [OMEGA] = [(0, 1).sup.3]

The conclusions remain the same as for the homogeneous beam example for the nearly incompressible elasticity equation discretised by Taylor-Hood method ([TH.sup.3.sub.h], [R.sup.2.sub.h]), since Tables 6.1 and 6.2 show similar results.

7. Conclusion. We tested numerically two-level preconditioners with spectral coarse spaces for nearly incompressible elasticity and Stokes equations. We considered two finite element methods, namely, Taylor-Hood (Section 3.1) and the hdG (Section 3.2) discretisations.

In the case of the homogeneous nearly incompressible elasticity the two-level methods coupled with the SORAS preconditioner, defined in , and the SMRAS preconditioner, defined by (4.2), allowed us to achieve good scalability results for both discretisations. Furthermore, for these symmetric preconditioners coarse spaces containing only zero energy modes seem to be sufficient for two and three dimensional problems. For the heterogeneous problem we also achieved scalability for two-level SORAS and SMRAS preconditioners, but, as expected, only in the case when the size of the coarse space is sufficiently large.

The improvement in convergence, in the case of the Stokes flow, is visible only when the coarse space contains more eigenvectors than only constants. For the Taylor-Hood discretisation, taking a sufficiently large coarse space we were able to achieve good scalability for all preconditioners. It is remarkable that these good results occur even when using the hdG discretisation, despite the fact that the optimized parameter to be used in SORAS and ORAS is not available.

We can conclude that the two-level preconditioners associated with non-standard interface conditions are at least as good as the two-level ones in conjunction with Robin interface conditions using optimised parameters. This shows an important advantage of the newly introduced preconditioners, as they are parameter-free. This allows a more flexible use of them, since they do not need a discretisation-based tuning. In fact, no change needs to be made in their implementation when changing from a continuous to a discontinuous discretisation.

Numerical tests have shown that the coarse spaces bring an important improvement in the convergence, but the size of the coarse space depends on the problem. Building as small as possible coarse spaces is important from a computational point of view. Thus, it is necessary to investigate what could be an optimal criterion for choosing the eigenvectors for a coarse space.

As the authors of  pointed out, an appropriate theory for obtaining a user-prescribed convergence rate when using spectral coarse spaces, in the same spirit as the one developed for SPD problems, remains an open problem and does not seem to be an easy task. The main theoretical arguments that apply for the latter, that is the Fictitious Space Lemma, cannot be extended easily to saddle point problems. Our purpose was then to limit the analysis of our preconditioner to numerical arguments by providing extensive results on different standard test cases.

Acknowledgements. The work by Michal Bosy was partially funded by the Engineering and Physical Sciences Research Council of Great Britain under the Numerical Algorithms and Intelligent Software (NAIS) for the evolving HPC platform grant EP/G036136/1. We thank Frederic Nataf and Pierre-Henri Tournier for many helpful discussions and insightful comments, and Ryadh Haferssas and Fr6d6ric Hecht for their assistance with the FreeFem++ codes.

REFERENCES

 H. ALCIN, B. KOOBUS, O. ALLAIN, AND A. DERVIEUX, Efficiency and scalability of a two-level Schwarz algorithm for incompressible and compressible flows, Internat. J. Numer. Methods Fluids, 72 (2013), pp. 69-89.

 B. AYUSO DE DIOS, F. BREZZI, L. D. MARINI, J. XU, AND L. ZIKATANOV, A simple preconditioner for a discontinuous Galerkin method for the Stokes problem, J. Sci. Comput., 58 (2014), pp. 517-547.

 G. R. BARRENECHEA, M. BOSY, V. DOLEAN, F. NATAF, AND P.-H. TOURNIER, Hybrid discontinuous Galerkin discretisation and domain decomposition preconditioners for the Stokes problem, Comput. Methods Appl. Math. (2018). Available online, DOI:10.1515/cmam-2018-0005.

 D. BOFFI, F. BREZZI, AND M. FORTIN, Mixed Finite Element Methods and Applications, Springer, Heidelberg, 2013.

 M. BREZINA, C. I. HEBERTON, J. MANDEL, AND P. VANEK, An iterative method with convergence rate chosen a priori, Tech. Rep. UCD/CCM Report 140, Center for Computational Mathematics, University of Colorado at Denver, Denver, 1999.

 C. CARSTENSEN AND M. SCHEDENSACK, Medius analysis and comparison results for first-order finite element methods in linear elasticity, IMA J. Numer. Anal., 35 (2015), pp. 1591-1621.

 B. COCKBURN AND J. GOPALAKRISHNAN, The derivation of hybridizable discontinuous Galerkin methods for Stokes flow, SIAM J. Numer. Anal., 47 (2009), pp. 1092-1125.

 B. COCKBURN, J. GOPALAKRISHNAN, AND R. LAZAROV, Unified hybridization of discontinuous Galerkin, mixed, and continuous Galerkin methods for second order elliptic problems, SIAM J. Numer. Anal., 47 (2009), pp. 1319-1365.

 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 (2014), pp. 83-99.

 V. DOLEAN, P. JOLIVET, AND F. NATAF, An Introduction to Domain Decomposition Methods, SIAM, Philadelphia, 2015.

 V. DOLEAN, F. NATAF, R. SCHEICHL, AND N. SPILLANE, Analysis of a two-level Schwarz method with coarse spaces based on local Dirichlet-to-Neumann maps, Comput. Methods Appl. Math., 12 (2012), pp. 391-414.

 Y. EFENDIEV, J. GALVIS, R. LAZAROV, AND J. WILLEMS, Robust domain decomposition preconditioners for abstract symmetric positive definite bilinear forms, ESAIM Math. Model. Numer. Anal., 46 (2012), pp. 1175-1199.

 J. GALVIS AND Y. EFENDIEV, Domain decomposition preconditioners for multiscale flows in high-contrast media, Multiscale Model. Simul., 8 (2010), pp. 1461-1483.

--, Domain decomposition preconditioners for multiscale flows in high contrast media: reduced dimension coarse spaces, Multiscale Model. Simul., 8 (2010), pp. 1621-1644.

 V. GIRAULT AND P.-A. RAVIART, Finite element methods for Navier-Stokes equations, Springer, Berlin, 1986.

 R. HAFERSSAS, P. JOLIVET, AND F. NATAF, An additive Schwarz method type theory for Lions's algorithm and a symmetrized optimized restricted additive Schwarz method, SIAM J. Sci. Comput., 39 (2017), pp. A1345-A1365.

 F. HECHT, New development in FreeFem++, J. Numer. Math., 20 (2012), pp. 251-265.

 G. KARYPIS AND V. KUMAR, METIS--A software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices, Tech. Rep., University of Minnesota, Department of Computer Science and Engineering, Army HPC Research Center, Minneapolis, 1998.

 A. KLAWONN AND L. F. PAVARINO, Overlapping Schwarz methods for mixed linear elasticity and Stokes problems, Comput. Methods Appl. Mech. Engrg., 165 (1998), pp. 233-245.

 R. B. LEHOUCQ, D. C. SORENSEN, AND C. YANG, ARPACK users' guide, SIAM, Philadelphia, 1998.

 S. LOISEL, H. NGUYEN, AND R. SCHEICHL, Optimized Schwarz and 2-Lagrange multiplier methods for multiscale elliptic PDEs, SIAM J. Sci. Comput., 37 (2015), pp. A2896-A2923.

 F. NATAF, H. XIANG, AND V. DOLEAN, A two level domain decomposition preconditioner based on local Dirichlet-to-Neumann maps, C. R. Math. Acad. Sci. Paris, 348 (2010), pp. 1163-1167.

 R. A. NICOLAIDES, Deflation of conjugate gradients with applications to boundary value problems, SIAM J. Numer. Anal., 24 (1987), pp. 355-365.

 A. PECHSTEIN AND J. SCHOBERL, Tangential-displacement and normal-normal-stress continuous mixed finite elements for elasticity, Math. Models Methods Appl. Sci., 21 (2011), pp. 1761-1782.

 Y. SAAD AND M. H. SCHULTZ, GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Statist. Comput., 7 (1986), pp. 856-869.

 N. SPILLANE, V. DOLEAN, P. HAURET, F. NATAF, C. PECHSTEIN, AND R. SCHEICHL, Abstract robust coarse spaces for systems of PDEs via generalized eigenproblems in the overlaps, Numer. Math., 126 (2014), pp. 741-770.

 A. TOSELLI AND O. WIDLUND, Domain Decomposition Methods--Algorithms and Theory, Springer, Berlin, 2005.

GABRIEL R. BARRENECHEA ([dagger]), MICHAL BOSY ([dagger][double dagger]), AND VICTORITA DOLEAN ([dagger][section])

(*) Received July 26, 2017. Accepted January 9, 2018. Published online on April 20, 2018. Recommended by Marcus Sarkis.

([dagger]) Department of Mathematics and Statistics, University of Strathclyde, 26 Richmond Street, G1 1XH Glasgow, United Kingdom ({Gabriel.Barrenechea,Victorita.Dolean}@strath.ac.uk).

([double dagger]) Dipartimento di Matematica "F. Casorati", Universita degli Studi di Pavia, Via Adolfo Ferrata 5, 27100 Pavia, Italy (Michal.Bosy@unipv.it).

([section]) University Cote d'Azur, CNRS, LJAD, 06108 Nice Cedex 02, France.

DOI: 10.1553/etna_vol49s41
```TABLE 5.1 Comparison of preconditioners for Taylor-Hood discretisation
([TH.sup.3.sub.h], [R.sup.2.sub.h]) - the L-shaped domain problem.

One-level
DOF         N    ORAS   SORAS   NDTNS-MRAS                  NDTNS-SMRAS

124 109    4    26     60      26                           60
478 027   16    57    131      69                          143
933 087   32    84    180     109                          221
1 899 125   64   130    293     181                          362
3 750 823  128   209    412     302                          568
Two-level (3 eigenvectors)
DOF         N    ORAS   SORAS   NDTNS-MRAS                  NDTNS-SMRAS

124 109     4    18     40      19                           36
478 027    16    37     52      40                           57
933 087    32    49     57      56                           67
1899 125    64    65     64      70                           75
3750 823   128    83     64      74                           77
Two-level (5 eigenvectors)
DOF         N    ORAS   SORAS   NDTNS-MRAS                   NDTNS-SMRAS

124 109    4    15     32      17                           35
478 027   16    31     41      31                           47
933 087   32    40     48      38                           52
1 899 125   64    49     51      45                           53
3 750 823  128    69     54      49                           54
Two-level (7 eigenvectors)
DOF          N    ORAS   SORAS   NDTNS-MRAS                  NDTNS-SMRAS

124 109    4    14     33      16                           30
478 027   16    26     41      25                           38
933 087   32    31     43      25                           42
1 899 125   64    39     47      30                           39
3 750 823  128    58     49      30                           43

DOF        TDNNS-MRAS   TDNNS-SMRAS

124 109    30           59
478 027    65          140
933 087   104          211
1 899 125   161          312
3 750 823   251          510

DOF        TDNNS-MRAS   TDNNS-SMRAS
124 109     24           41
478 027     46           56
933 087     53           66
1899 125     61           74
3750 823     75           72

DOF         TDNNS-MRAS   TDNNS-SMRAS
124 109    24           37
478 027    42           47
933 087    53           51
1 899 125    64           56
3 750 823    70           53

DOF         TDNNS-MRAS   TDNNS-SMRAS
124 109    24           35
478 027    42           44
933 087    49           46
1 899 125    59           50
3 750 823    61           50

TABLE 5.2 Comparison of preconditioners for Taylor-Hood discretisation
([TH.sup.3.sub.h], [R.sup.2.sub.h])--the heterogeneous beam.

One-level
DOF           N    ORAS   SORAS   NDTNS-MRAS   NDTNS-SMRAS   TDNNS-MRAS

44 963     8     168     301          160           267     177
87 587    16     226     490          245           462     229
177 923    32     373     711          447           684     440
347 651    64     615   >1000          728         >1000     746
707 843   128     973   >1000        >1000         >1000   >1000
1 385 219   256   >1000   >1000        >1000         >1000   >1000

Two-level (5 eigenvectors)
DOF           N    ORAS   SORAS   NDTNS-MRAS   NDTNS-SMRAS   TDNNS-MRAS

44 963     8     109     160        136           147       148
87 587    16     136     204        192           200       181
177 923    32     193     291        296           275       326
347 651    64     260     304        363           282       491
707 843   128     412     356        420           369       601
1 385 219   256     379     414        448           400       711

Two-level (7 eigenvectors)
DOF           N    ORAS   SORAS   NDTNS-MRAS   NDTNS-SMRAS   TDNNS-MRAS

44 963     8      76     118        124           115       133
87 587    16     106     146        166           138       159
177 923    32     157     202        203           185       302
347 651    64     178     191        225           170       326
707 843   128     140     114        153           112       266
1 385 219   256     119      86        118            77       259

DOF         TDNNS-SMRAS

44 963     264
87 587     424
177 923     672
347 651   >1000
707 843   >1000
1 385 219   >1000

DOF         TDNNS-SMRAS

44 963     136
87 587     184
177 923     276
347 651     299
707 843     346
1 385 219     317

DOF         TDNNS-SMRAS

44 963     103
87 587     123
177 923     214
347 651     182
707 843     122
1 385 219      94

TABLE 5.3 Comparison of preconditioned for Taylor-Hood discretisation
([TH.sup.2.sub.h], [R.sup.1.sub.r])--the driven cavity problem.

One-level
DOF           N        ORAS            SORAS    NVTF-MRAS     NVTF-SMRAS
Unif     MTS   Unif    MTS  Unif    MTS    Unif   MTS

91 003     4      12      17     24     34    22    22      34    40
362 003    16      28      35     56     67    52    53      90   106
813 003    36      39      75     92    103    85    91     165   185
1 444 003    64      53      91    120    144   120   135     254   283
2 728 003   121      80     278    180    212   182   280     412   580
5 768 003   256   >1000   >1000    271    317   303   452     917   955
Two-level
(2 eigenvectors)
DOF           N        ORAS           SORAS    NVTF-MRAS     NVTF-SMRAS
Unif     MTS   Unif    MTS  Unif   MTS     Unif   MTS

91 003     4      10      14     18     22    19    17      26    30
362 003    16      20      25     32     37    33    34      50    62
813 003    36      27      33     36     44    47    49      62    86
1 444 003    64      31      42     38     53   104    66      85   114
2 728 003   121      39     103     39     51    74    81      85   133
5 768 003   256     300     849     46     54   109   108     146   132

Two-level
(5 eigenvectors)
DOF           N        ORAS            SORAS       NVTF-MRAS  NVTF-SMRAS
Unif     MTS   Unif    MTS   Unif  MTS    Unif   MTS

91 003     4       9      12     13     16    16    15      18    20
362 003    16      16      20     21     24    27    22      28    37
813 003    36      23      27     25     26    33    30      39    40
1 444 003    64      26      36     27     29    40    34      35    45
2 728 003   121      35      41     29     32    43    38      34    48
5 768 003   256      66      60     32     33    56    41      60    49

DOF         TVNF-MRAS   TVNF-SMRAS
Unif   MTS   Unif   MTS

91 003     22    25     30    40
362 003     54    53     70    84
813 003     91    88    118   136
1 444 003    132   132    169   206
2 728 003    199   213    251   439
5 768 003    322   319    397   695

DOF          TVNF-MRAS    TVNF-SMRAS
Unif   MTS   Unif   MTS

91 003     27    20     21    26
362 003     60    40     42    51
813 003     79    53     59    63
1 444 003     85    52     62    79
2 728 003     92    86     62    93
5 768 003     91    78     63    90

DOF               TVNF-MRAS     TVNF-SMRAS
Unif   MTS   Unif   MTS

91 003     25    20     16    18
362 003     56    37     26    35
813 003     65    41     28    37
1 444 003     77    45     28    42
2 728 003     84    72     29    47
5 768 003     88    61     29    44

TABLE 5.4 Comparison of preconditioners for Taylor-Hood discretisation
([TH.sup.3.sub.h], [Rh.sup.2.sub.h])--the T-shaped problem.

One-level
DOF           N   ORAS   SORAS  NVTF-MRAS         NVTF-SMRAS  TVNF-MRAS

33 269     4   13      20     12                19          13
138 316    16   36      51     33                52          31
269 567    32   59      85     52                85          49
553 103    64   92     132     83               136          78
1 134 314   128   46     208    132               223         117
2 201 908   256   32     328    209               357         189
Two-level
(2 eigenvectors)
DOF          N    ORAS   SORAS  NVTF-MRAS         NVTF-SMRAS  TVNF-MRAS

33 269     4   10     14       9                15          12
138 316    16   21     27      19                24          22
269 567    32   29     35      30                38          25
553 103    64   35     45      34                43          33
1 134 314   128   42     52      47                58          34
2 201 908   256   47     56      69                76          38
Two-level
(5 eigenvectors)
DOF          N    ORAS   SORAS  NVTF-MRAS         NVTF-SMRAS  TVNF-MRAS

33 269     4    8      13      8                13          12
138 316    16   15     16      14                16          20
269 567    32   14     19      20                22          24
553 103    64   16     20      18                19          29
1 134 314   128   17     22      23                24          30
2 201 908   256   16     21      34                37          35

DOF         TVNF-SMRAS

33 269    19
138 316    45
269 567    75
553 103   115
1 134 314   188
2 201 908   293

DOF         TVNF-SMRAS

33 269    15
138 316    24
269 567    30
553 103    35
1 134 314    41
2 201 908    45

DOF         TVNF-SMRAS

33 269    14
138 316    18
269 567    19
553 103    20
1 134 314    22
2 201 908    24

TABLE 5.5 Comparison of preconditioners for hdG discretisation--the
L-shaped domain problem.

One-level
DOF          N   ORAS   SORAS  NDTNS-MRAS       NDTNS-SMRAS  TDNNS-MRAS

238 692    8     61   158     64                174           77
466 094   16    123   232    101                259          109
948 921   32    267   331    160                415          179
1 874 514   64    622   477    243                685          254
3 856 425  128  >1000   752    479              >1000          523
Two-level
(3 eigenvectors)
DOF         N    ORAS   SORAS  NDTNS-MRAS       NDTNS-SMRAS  TDNNS-MRAS

238 692    8     48    98     52                 98           61
466 094   16     89    99     71                123           75
948 921   32    250   130    110                158          118
1 874 514   64    535   135    135                155          129
3 856 425  128  >1000   152    172                176          181
Two-level
(5 eigenvectors)
DOF         N    ORAS   SORAS  NDTNS-MRAS       NDTNS-SMRAS  TDNNS-MRAS

238 692    8     43    81     44                 74           61
466 094   16     77    82     51                 92           63
948 921   32    197   100     79                119           96
1 874 514   64    429   103    102                122          110
3 856 425  128  >1000   118    122                129          141
Two-level
(7 eigenvectors)
DOF         N    ORAS   SORAS  NDTNS-MRAS       NDTNS-SMRAS  TDNNS-MRAS

238 692    8    35     67     38                  71           44
466 094   16    61     79     47                  80           51
948 921   32   153     90     58                  95           74
1 874 514   64   423     95     71                  93           72
3 856 425  128   934    110     79                 104          108

DOF

238 692
466 094
948 921
1 874 514
3 856 425

DOF         TDNNS-SMRAS
238 692
466 094       177
948 921       306
1 874 514       473
3 856 425       657
>1000

DOF
TDNNS-SMRAS
238 692       116
466 094       148
948 921       173
1 874 514       159
3 856 425       192

DOF         TDNNS-SMRAS

238 692        94
466 094       103
948 921       121
1 874 514       138
3 856 425       167

TDNNS-SMRAS

82
95
115
111
133

TABLE 5.6 Comparison of preconditioners for hdG discretisation--the
heterogeneous beam.

One-level
DOF         N    ORAS   SORAS    NDTNS-MRAS   NDTNS-SMRAS

46 777    8    196    440      189           402
88 720   16    317    602      330           582
179 721   32    537  >1000      574         >1000
353 440   64    899  >1000      847         >1000
704 329  128  >1000  >1000    >1000         >1000
1 410 880  256  >1000  >1000    >1000         >1000
Two-level
(5 eigenvectors)
DOF         N    ORAS   SORAS    NDTNS-MRAS   NDTNS-SMRAS

46 777    8    168    255        162          230
88 720   16    244    313        273          299
179 721   32    385    525        442          458
353 440   64    514    444        551          526
704 329  128    835    557        782          684
1 410 880  256  >1000    567      >1000          694

Two-level
(7 eigenvectors)
DOF         N     ORAS   SORAS    NDTNS-MRAS   NDTNS-SMRAS

46 777    8    148    197      149           192
88 720   16    205    201      286           187
179 721   32    318    337      385           301
353 440   64    403    262      397           247
704 329  128    490    168      447           182
1 410 880  256  >1000    116      387           138

DOF        TDNNS-MRAS   TDNNS-SMRAS

46 777    186          463
88 720    326          666
179 721    587        >1000
353 440    846        >1000
704 329  >1000        >1000
1 410 880  >1000        >1000

DOF        TDNNS-MRAS   TDNNS-SMRAS

46 777    161          275
88 720    262          346
179 721    469          587
353 440    590          558
704 329    765          832
1 410 880    844          821

DOF        TDNNS-MRAS   TDNNS-SMRAS

46 777    158         231
88 720    283         273
179 721    433         419
353 440    460         389
704 329    558         443
1 410 880    473         298

TABLE 5.7 Comparison of preconditioners for hdG discretisation--the
driven cavity problem.

DOF          N         ORAS              SORAS          NVTF-MRAS
Unif      MTS     Unif      MTS   Unif       MTS

93 656     4     17         18      37       38    24        22
373 520    16     76        122      75       84    52        54
839 592    36    152        327     120      133    91        96
1 491 872    64    261        587     162      176   130       143
2 819 432   121    364      >1000     229      256   199       213
5 963 072   256    592      >1000     367      398   326       477
Two-level
(2 eigenvectors)
DOF          N         ORAS                SORAS        NVTF-MRAS
Unif         MTS    Unif      MTS   Unif       MTS

93 656     4     12         14     30        28    18        18
373 520    16     81         80     47        57    36        40
839 592    36    236        228     61        60    57        65
1 491 872    64    395        463     67        71    79        85
2 819 432   121    840      >1000     73        86   113       127
5 963 072   256  >1000      >1000     80        87   171       179
Two-level
(5 eigenvectors)
DOF           N        ORAS            SORAS          NVTF-MRAS
Unif       MTS    Unif       MTS  Unif       MTS

93 656     4     10         12     25        24    14        16
373 520    16     27         35     38        37    27        29
839 592    36    135         84     45        41    35        37
1 491 872    64    278        212     49        45    44        42
2 819 432   121    607        584     56        49    46        56
5 963 072   256  >1000      >1000     62        55    52        64

DOF           NVTF-SMRAS       TVNF-MRAS    TVNF-SMRAS
Unif      MTS    Unif   MTS   Unif   MTS

93 656      44      44      32     25     48     50
373 520     107     111      68     67    122    126
839 592     194     200     112    115    206    210
1 491 872     294     303     159    158    292    286
2 819 432     504     649     238    251    628    643
5 963 072   >1000   >1000     392    404    995    740

DOF            NVTF-SMRAS      TVNF-MRAS  TVNF-SMRAS
Unif    MTS      Unif   MTS   Unif   MTS

93 656      33      32      40     23     38     37
373 520      61      73     100     49     85     82
839 592      97     104     132     66    112    107
1 491 872     139     129     142     70    128    122
2 819 432     188     178     157     86    127    139
5 963 072     283     287     167    108    132    148

DOF          NVTF-SMRAS      TVNF-MRAS    TVNF-SMRAS
Unif    MTS     Unif   MTS   Unif   MTS

93 656      23      22      52     22     29     26
373 520      38      41     117     39     53     53
839 592      51      50     145     49     64     61
1 491 872      58      55     157     59     64     64
2 819 432      58      62     162     81     65     75
5 963 072      57      69     166     75     65     75

TABLE 5.8 Comparison of preconditioners for hdG discretisation--the
T-shaped problem.

One-level
DOF          N     ORAS    SORAS   NVTF-MRAS           NVTF-SMRAS

38 803     4      22      45      36                   49
154 606    16     111      98      83                  172
311 369    32     265     144     133                  262
616 772    64     568     238     212                  410
1 246 136   128   >1000     494     333                  665
2 451 365   256   >1000     712     464                >1000
Two-level
(2 eigenvectors)
DOF           N    ORAS    SORAS   NVTF-MRAS           NVTF-SMRAS

38 803     4      16      35      31                   37
154 606    16     113      69      73                   75
311 369    32     254      99     103                  176
616 772    64     510     153     171                  273
1 246 136    128  >1000     221     242                  252
2 451 365    256  >1000     286     343                  515
Two-level
(5 eigenvectors)
DOF           N    ORAS    SORAS   NVTF-MRAS           NVTF-SMRAS

38 803     4      14      30      27                   27
154 606    16     155      54      54                   45
311 369    32     159      55      72                   59
616 772    64     426      88     106                   83
1 246 136   128     955     113     115                   99
2 451 365   256   >1000     182     138                  101

DOF         TVNF-MRAS   TVNF-SMRAS

38 803      22          51
154 606      83         182
311 369     130         266
616 772     195         412
1 246 136     313         602
2 451 365     477         889

DOF         TVNF-MRAS   TVNF-SMRAS

38 803      21          38
154 606      38          75
311 369      93         162
616 772     121         140
1 246 136     155         138
2 451 365     189         231

DOF         TVNF-MRAS   TVNF-SMRAS

38 803      28          30
154 606      25          44
311 369      29          52
616 772      37          76
1 246 136      43          72
2 451 365      54          73

TABLE 6.1 Comparison of preconditioners for Taylor-Hood discretisation
([TH".sup.2.sub.H], [Rh.sup.1.sub.H])--the homogeneous beam.

One-level
DOF        N     ORAS   SORAS   NDTNS-MRAS    NDTNS-SMRAS

32 446     8     21      45      29             36
73 548    16     31      70      38             64
139 794    32     43      99      74             94
299 433    64     55     143     161            140
549 396   128    78      192     314            192
Two-level
(6 eigenvectors)
DOF       N     ORAS   SORAS   NDTNS-MRAS   NDTNS-SMRAS

32 446     8     10      17      13             18
73 548    16     11      22      16             25
139 794    32     13      26      25             28
299 433    64     15      27      19             27
549 396   128     17      28      20             25
Two-level
(8 eigenvectors)
DOF       N     ORAS   SORAS   NDTNS-MRAS   NDTNS-SMRAS

32 446     8      9      16      12             17
73 548    16     10      19      15             24
139 794    32     11      21      17             23
299 433    64     14      24      17             24
549 396   128     16      27      18             23

DOF         TDNNS-MRAS   TDNNS-SMRAS

32 446        27           37
73 548        26           67
139 794        66           91
299 433       149          139
549 396       229          199

DOF        TDNNS-MRAS   TDNNS-SMRAS

32 446          12           17
73 548          16           22
139 794          17           26
299 433          24           28
549 396          21           26

DOF        TDNNS-MRAS   TDNNS-SMRAS

32 446          12           16
73 548          14           20
139 794          17           21
299 433          21           23
549 396          20           22

TABLE 6.2 Comparison of preconditioners for Taylor-Hood discretisation
([TH.sup.2.sub.h], [R.sup.1.sub.h])--the driven cavity problem.

One-level
DOF        N     ORAS   SORAS   NVTF-MRAS   NVTF-SMRAS

38 229     8    12     24      12          22
76 542    16    18     34      18          31
158 818    32    23     45      20          45
325 293    64    28     60      36          64
643 137   128    37     79      64          91

Two-level (3 eigenvectors)
DOF        N     ORAS   SORAS   NVTF-MRAS   NVTF-SMRAS

38 229     8    10     17      10          18
76 542    16    11     20      11          19
158 818    32    13     24      13          24
325 293    64    15     27      15          27
643 137   128    18     31      17          32
Two-level (7 eigenvectors)
DOF       N     ORAS   SORAS   NVTF-MRAS   NVTF-SMRAS

38 229     8     9     16       9          16
76 542    16    10     17      10          18
158 818    32    11     19      11          20
325 293    64    13     19      13          21
643 137   128    15     21      16          22

DOF       TVNF-MRAS   TVNF-SMRAS

38 229   11          23
76 542   15          31
158 818   19          45
325 293   25          60
643 137   33          88

DOF       TVNF-MRAS   TVNF-SMRAS

38 229    11          18
76 542    14          19
158 818    16          23
325 293    19          26
643 137    22          31

DOF       TVNF-MRAS   TVNF-SMRAS

38 229    12          17
76 542    15          17
158 818    17          20
325 293    20          20
643 137    22          22
```
COPYRIGHT 2018 Institute of Computational Mathematics
No portion of this article can be reproduced without the express written permission from the copyright holder.