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

1. Introduction. In [3], 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 [27]. The key point of these kind of methods is to choose an appropriate coarse space. The classical coarse space introduced by Nicolaides in [23] 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 [19]. 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 [1] 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 [5] 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 [22] 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 [11] and proved to be very robust in the case of small overlaps. The same idea was extended numerically to the heterogeneous Helmholtz problem in [9]. The authors of [21] 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 [12] as an extension of [13, 14]. Since some of the assumptions of the previous framework are hard to fulfil, the authors of [26] 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 [16]. 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.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 [24].

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]},

and the discrete problem reads:

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 [3]. 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 [3] 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 [16]. 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++ [17], which is a free software specialised in variational discretisations of partial differential equations. We use GMRES [25] as an iterative solver. Generalized eigenvalue problems to generate the coarse space are solved using ARPACK [20]. The overlapping decomposition into subdomains can be uniform (Unif) or generated by METIS (MTS) [18]. 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 [16] 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 [16], 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 [6]. 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 [16]. 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 [11]. 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 [16] 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 [16], 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 [16] 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 [16] 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 [16] 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 [16], 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 [16] 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

[1] 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.

[2] 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.

[3] 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.

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

[5] 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.

[6] 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.

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

[8] 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.

[9] 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.

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

[11] 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.

[12] 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.

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

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

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

[16] 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.

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

[18] 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.

[19] 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.

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

[21] 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.

[22] 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.

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

[24] 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.

[25] 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.

[26] 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.

[27] 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

Printer friendly Cite/link Email Feedback | |

Author: | Barrenechea, Gabriel R.; Bosy, Michal; Dolean, Victorita |
---|---|

Publication: | Electronic Transactions on Numerical Analysis |

Article Type: | Report |

Date: | Feb 1, 2018 |

Words: | 10273 |

Previous Article: | ADDITIVE AVERAGE SCHWARZ WITH ADAPTIVE COARSE SPACES: SCALABLE ALGORITHMS FOR MULTISCALE PROBLEMS. |

Next Article: | BDDC AND FETI-DP ALGORITHMS WITH A CHANGE OF BASIS FORMULATION ON ADAPTIVE PRIMAL CONSTRAINTS. |

Topics: |