Hussam Al Daas

Laura Grigori

Une classe de préconditionneurs efficaces construits localement basés sur les espaces grossiers

Keywords: préconditionneurs, solveur linéaires itératifs, décomposition de domaine preconditioners, iterative linear solvers, domain decomposition

Ce papier présente une classe de deux-niveaux préconditioneurs totalement algébrique et efficaces pour les matrices SPD. Nous introduisons la notion de la séparation local et algébrique SPSD d'une matrice SPD et nous characterisons tout les séparations possibles. Cette séparation aide à construire algéebriquement et localement une classe d'espaces grossiers efficaces qui bornent le conditionement spectral du système préconditioné par un numbre défini a priori. Nous introduisons ainsi les espaces de τ -filtering. Ces derniers permettent à comparer les dimensions des espaces grossiers. Certains préconditioneurs qui dépendendent de l'EDP font l'objet d'un cas particulier de la classe intorduite. Les exemples des espace grossiers algébriques dans ce papier ne sont pas pratiques suite à la construction chère de la séparation algébrique. Nous proposon une approximation heuristique qui n'est pas chèr. Les résultats numériques montrent l'efficacité de la méthode proposée.

Introduction

The conjugate gradient method CG [START_REF] Hestenes | Methods of conjugate gradients for solving linear systems[END_REF] is a widely known Krylov iterative method, for solving large linear systems of equations of the form

Ax = b, (1)
where A ∈ R n×n is a symmetric positive definite matrix, b ∈ R n is the right-hand side, and x ∈ R n is the vector of unknowns. It finds at iteration j the approximate solution x j that minimizes the norm of the error x * -x j A , where x * is the exact solution of (1) and . A is the A-norm.

The convergence of this method is well studied in the literature [START_REF] Saad | Iterative Methods for Sparse Linear Systems[END_REF]. The rate of convergence depends on the condition number of the matrix A. Let κ = λn λ1 be the spectral condition number of A, where λ n and λ 1 are the largest and the smallest eigenvalues of A respectively, the error at iteration j satisfies the following inequality

x * -x j A ≤ x * -x 0 A √ κ -1 √ κ + 1 j , (2)
where x 0 is the initial solution. We suppose that the graph of the matrix is partitioned into a number of subdomains by using a k-way partitioning method [START_REF] Karypis | Multilevelk-way partitioning scheme for irregular graphs[END_REF]. To enhance the convergence, it is common to solve the preconditioned system

M -1 Ax = M -1 b. (3)
Block Jacobi, additive Schwarz, restricted additive Schwarz, etc., are widely used preconditioners. These preconditioners are called one-level preconditioners. They correspond to solving subproblems on subdomains. In [START_REF] Chan | Domain decomposition algorithms[END_REF][START_REF] Victorita Dolean | An introduction to domain decomposition methods[END_REF] the authors prove that the largest eigenvalue of the preconditioned system by the additive Schwarz preconditioner is bounded by a number that is independent of the number of subdomains. However, no control is guaranteed for the smallest eigenvalue of the preconditioned matrix. Furthermore, when the number of subdomains increases, the smallest eigenvalue might become even smaller. Thus, the number of iterations to reach convergence typically increases. This occurs since this type of preconditioner employs only local information and does not include global information. For this reason, these preconditioners are usually combined with a second-level preconditioner, which corresponds to a coarse space correction or deflation. In principle, it is meant to annihilate the impact of the smallest eigenvalues of the operator. Different strategies exist in literature to add this level. In [START_REF] Tang | Comparison of two-level preconditioners derived from deflation, domain decomposition and multigrid methods[END_REF], the authors compare different strategies of applying two-level preconditioners. In [START_REF] Chan | Domain decomposition algorithms[END_REF][START_REF] Toselli | Domain Decomposition Methods -Algorithms and Theory[END_REF][START_REF] Nataf | A coarse space construction based on local dirichlet-to-neumann maps[END_REF][START_REF] Spillane | Automatic spectral coarse spaces for robust finite element tearing and interconnecting and balanced domain decomposition algorithms[END_REF][START_REF] Victorita Dolean | An introduction to domain decomposition methods[END_REF][START_REF] Grigori | Robust algebraic Schur complement preconditioners based on low rank corrections[END_REF][START_REF] Li | Low-rank correction methods for algebraic domain decomposition preconditioners[END_REF], the authors propose different methods for constructing a coarse space correction. Coarse spaces can be categorized in two types, analytic and algebraic. Analytic coarse spaces depend on the underlying problem from which the matrix A is issued. Algebraic coarse spaces depend only on the coefficient matrix A and does not require information from the underlying problem from which it arises. Based on the underlying PDE and its discretization, several methods that propose analytic coarse spaces are described in literature [START_REF] Victorita Dolean | An introduction to domain decomposition methods[END_REF][START_REF] Chan | Domain decomposition algorithms[END_REF][START_REF] Toselli | Domain Decomposition Methods -Algorithms and Theory[END_REF][START_REF] Nataf | A coarse space construction based on local dirichlet-to-neumann maps[END_REF][START_REF] Spillane | Automatic spectral coarse spaces for robust finite element tearing and interconnecting and balanced domain decomposition algorithms[END_REF].

In most cases, a generalized (or standard) eigenvalue problem is solved in each subdomain. Every subdomain then contributes to the construction of the coarse space by adding certain eigenvectors. These methods are efficient in several applications. Nevertheless, the dependence on the analytic information makes it impossible to be made in a pure algebraic way. Algebraic coarse space correction can be found in literature [START_REF] Grigori | Robust algebraic Schur complement preconditioners based on low rank corrections[END_REF][START_REF] Li | Low-rank correction methods for algebraic domain decomposition preconditioners[END_REF]. However, the construction of the coarse space can be even more costly than solving the linear system [START_REF] Achdou | Low frequency tangential filtering decomposition[END_REF]. In this paper we discuss a class of robust preconditioners that are based on locally constructed coarse spaces. We characterize the local eigenvalue problems that allow to construct an efficient coarse space related to the additive Schwarz preconditioner. The paper is organized as follows. In 2 we review general theory of one-and two-level preconditioners, in 3 we present our main result. We introduce the notion of algebraic local SPSD splitting of an SPD matrix. For a simple case, given the block SPD matrix where * represents a non-zero block matrix such that B = B 1 + B 2 . We characterize all possible local SPSD splittings. Then we introduce the τ -filtering subspace. Given two SPSD matrices A, B, a τ -filtering subspace Z makes the following inequality hold

(u -P u) B (u -P u) ≤ u Au, ∀u,
where P is an orthogonal projection on Z. Based on the local SPSD splitting and the τ -filtering subspace, we propose in 4 an efficient coarse space, which bounds the spectral condition number by a given number defined a priori. Furthermore, we show how the coarse space can be chosen such that its dimension is minimal. The resulting spectral condition number depends on three parameters. The first parameter depends on the sparsity of the matrix, namely, the minimum number of colours k c needed to colour subdomains such that two subdomains of the same colour are disjoint, see Lemma 7 [2, Theorem 12]. The second parameter k m depends on the algebraic local SPSD splitting. It is bounded by the number of subdomains. For a special case of splitting it can be chosen to be the maximal number of subdomains that share a degree of freedom. The third parameter is chosen such that the spectral condition number is bounded by the user-defined upper bound. In all stages of the construction of this coarse space, no information is necessary but the coefficient matrix A and the desired bound on the spectral condition number. We show how the coarse space constructed analytically by the method GenEO [START_REF] Spillane | Abstract robust coarse spaces for systems of pdes via generalized eigenproblems in the overlaps[END_REF][START_REF] Victorita Dolean | An introduction to domain decomposition methods[END_REF] corresponds to a special case of our characterization. We also discuss the extreme cases of the algebraic local SPSD splitting and the corresponding coarse spaces. We explain how these two choices are expensive to construct in practice. Afterwards, we propose a practical strategy to compute efficiently an approximation of the coarse space. In 5 we present numerical experiments to illustrate the theoretical and practical impact of our work. At the end, we give our conclusion in 6.

To facilitate the comparison with GenEO we follow the presentation in [START_REF] Victorita Dolean | An introduction to domain decomposition methods[END_REF]Chapter 7].

Notation

Let A ∈ R n×n denote a symmetric positive definite matrix. We use MATLAB notations. Let S 1 , S 2 ⊂ {1, . . . , n } be two sets of indices. The concatenation of S 1 and S 2 is represented by [S 1 , S 2 ]. We note that the order of the concatenation is important. A(S 1 , :) is the submatrix of A formed by the rows whose indices belong to S 1 . A(:, S 1 ) is the submatrix of A formed by the columns whose indices belong to S 1 . A(S 1 , S 2 ) := (A(S 1 , :)) (:, S 2 ). The identity matrix of size n is denoted I n . We suppose that the graph of A is partitioned into N non-overlapping subdomains, where N n. The coefficient matrix A is represented as (a ij ) 1≤i,j≤n . Let N = {1, . . . , n} and let N i,0 for i ∈ {1, . . . , N } be the corresponding subsets of N such that N i,0 stands for the subset of the degrees of freedom, DOF, in the subdomain i. We refer to N i,0 as the interior DOF in subdomain i. Let ∆ i for i ∈ {1, . . . , N } be the subset of N that represents the neighbors DOF of the subdomain i, i.e., the DOFs of distance = 1 from the subdomain i through the graph of A. We refer to ∆ i as the overlapping DOF in the subdomain i. We denote N i,1 = [N i,0 , ∆ i ], ∀i ∈ Inria {1, . . . , N }, the concatenation of the interior and the overlapping DOF of subdomain i. We denote C i , ∀i ∈ {1, . . . , N }, the complementary of N i,1 in N , i.e., C i = N \ N i,1 . We note n i,0 the cardinality of the set N i,0 , δ i the cardinality of ∆ i and n i,1 the cardinality of the set N i,1 , ∀i ∈ {1, . . . , N }. Let R i,0 ∈ R ni,0×n be defined as R i,0 = I n (N i,0 , : ). Let R i,δ ∈ R δi×n be defined as

R i,δ = I n (∆ i , : ). Let R i,1 ∈ R ni,1×n be defined as R i,1 = I n ([N i,0 , ∆ i ], : ). Let R i,c ∈ R (n-ni,1)×n be defined as R i,c = I n (C i , : ). Let P i = I n ([N i,0 , ∆ i , C i ], : ) ∈ R n×n
, be a permutation matrix associated to the subdomain i, ∀i ∈ {1, . . . , N }. We denote D i ∈ R ni,1,×ni,1 , i = 1, . . . , N , any non-negative diagonal matrix such that

I n = N i=1 R i,1 D i R i,1 . (4)
We refer to (D i ) 1≤i≤N as the algebraic partition of unity. Let n 0,1 be a positive integer, n 0,1 n. Let V 0 ∈ R n×n0,1 be a tall and skinny matrix of full rank. We denote S the subspace generated by the columns of V 0 . This subspace will stand for the coarse space. We denote R 0,1 the projection operator on S. We denote R 0,1 the interpolation operator from S to the global space. The subscript 1 in R 0,1 is to be compatible with other restriction operators R i,1 , for i = 1, . . . , N . We note that subscripts 0 and 1 in R i,. , N i,. , n i,. refer to the interior and the interior-andoverlapping items respectively. Let R 1 be the operator defined by : R 1 :

N i=1 R ni,1 → R n (u i ) 1≤i≤N → N i=1 R i,1 u i . (5)
In the same way we define R 2 by taking into account the coarse space correction

R 2 : N i=0 R ni,1 → R n (u i ) 0≤i≤N → N i=0 R i,1 u i . (6)
We note that the subscripts 1 and 2 in R 1 and R 2 refer to one-level and two-level interpolation operators respectively. The following example of two-subdomains-partitioned A illustrates our notation. Let A be given as The restriction operator on the interior DOF of subdomains is

A =    
R 1,0 = 1 0 0 0 0 1 0 0 , R 2,0 = 0 0 1 0 0 0 0 1 .
The restriction operator on the overlapping DOF of subdomains is

R 1,δ = 0 0 1 0 , R 2,δ = 0 1 0 0 .
The restriction operator on the concatenation of the interior DOF and the overlapping DOF is

R 1,1 =   1 0 0 0 0 1 0 0 0 0 1 0   , R 2,1 =   0 0 1 0 0 0 0 1 0 1 0 0   .
The permutation matrix associated with each subdomain is

P 1 =     1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1     , P 2 =     0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0     .
The permuted matrix associated with each subdomain is Finally, the algebraic partition of unity can be defined as

P 1 AP 1 =    
D 1 =   1 0 0 0 1 2 0 0 0 1 2   , D 2 =   1 2 0 0 0 1 0 0 0 1 2   .
We note that the reordering of lines in the partition of unity matrices (D i ) 1≤i≤N has to be adapted with the lines reordering of (R i,1 ) 1≤i≤N such that (4) holds.

Background

In this section, we start by presenting three lemmas that help compare two symmetric positive definite (or semidefinite) matrices. Then, we review generalities of one-and two-level additive Schwarz preconditioners.

Auxiliary lemmas

The Lemma 1 can be found in [START_REF] Victorita Dolean | An introduction to domain decomposition methods[END_REF]Lemma 7.3,p. 164]. This lemma helps prove the effect of the additive Schwarz preconditioner on the largest eigenvalues of the preconditioned operator.

Lemma 1 Let A 1 , A 2 ∈ R n×n be two symmetric positive definite matrices. Suppose that there is a constant c u > 0 such that,

v A 1 v ≤ c u v A 2 v, ∀v ∈ R n . ( 7
)
Then the eigenvalues of A -1 2 A 1 are strictly positive and bounded from above by c u . The Lemma 2 is widely known in the community of domain decomposition by the Fictitious subspace lemma.

Inria

Lemma 2 (Fictitious subspace lemma) Let A ∈ R n A ×n A , B ∈ R n B ×n B be two symmetric positive definite matrices. Let R be an operator defined as

R : R n B → R n A v → Rv, (8)
and let R be its transpose. Suppose that the following conditions hold :

1. The operator R is surjective.

2. There exists c u > 0 such that

(Rv) A (Rv) ≤ c u v Bv, ∀v ∈ R n B . (9)
3. There exists c l > 0 such that

∀v n A ∈ R n A , ∃v n B ∈ R n B |v n A = Rv n B and c l v n B Bv n B ≤ (Rv n B ) A (Rv n B ) = v n A Av n A . (10)
Then, the spectrum of the operator

RB -1 R A is contained in the segment [c l , c u ].
Proof 1 We refer the reader to [3, Lemma 7.4 p.164] or [START_REF] Nepomnyaschikh | Decomposition and fictitious domains methods for elliptic boundary value problems[END_REF][START_REF] Nepomnyaschikh | Mesh theorems of traces, normalizations of function traces and their inversions[END_REF][START_REF] Griebel | On the abstract theory of additive and multiplicativeschwarz algorithms[END_REF] for a detailed proof.

We note that there is a general version of Lemma 2 for infinite dimensions. This lemma plays a crucial role in bounding the condition number of our preconditioned operator. The operator R will stand for the interpolation operator. The matrix B will stand for the block diagonal operator of local subdomain problems. It is important to note that in the finite dimension the existence of the constants c u and c l are guaranteed. This is not the case in the infinite dimension spaces. In the finite dimension case, the hard part in the fictitious subspace lemma is to find R such that c u /c l is independent of the number of subdomains. When R and B are chosen to form the oneor two-level additive Schwarz operator, the first two conditions are satisfied for an upper bound c u independent of the number of subdomains. An algebraic proof which depends only on the coefficient matrix can be found in [START_REF] Victorita Dolean | An introduction to domain decomposition methods[END_REF]. However, the third condition is still an open question if no information from the underlying PDE is used. In this paper we address the problem of defining algebraically a surjective interpolation operator of the two-level additive Schwarz operator such that the third condition holds for a c l independent of the number of subdomains. This is related to the stable decomposition property which was introduced in [START_REF] Xu | Theory of Multilevel Methods[END_REF]. Later, in [START_REF] Victorita Dolean | An introduction to domain decomposition methods[END_REF], the authors proposed a stable decomposition with the additive Schwarz. This decomposition was based on the underlying PDE. Thus, when only the coefficient matrix A is known, this decomposition is not possible to be computed. The two following lemmas will be applied to choose the local vectors that contribute to the coarse space. They are based on low rank corrections. In [START_REF] Victorita Dolean | An introduction to domain decomposition methods[END_REF], the authors present two lemmas [3, Lemma 7.6 p.167, Lemma 7.7 p.168] similar to the following lemmas. The rank correction proposed in their version is not of minimal rank. We modify these two lemmas to obtain the smallest rank correction. Lemma 3 Let A, B ∈ R m×m be two symmetric positive matrices. Let ker(A), range(A) denote the null space and the range of A respectively. Let ker(B) denote the kernel of B. Let L = ker(A) ∩ ker(B), we note L ⊥ ker(A) the orthogonal complementary of L in ker(A). Let P 0 be an orthogonal projection on range(A). Let τ be a strictly positive real number. Consider the following generalized eigenvalue problem,

Find (u k , λ k ) ∈ range(A) × R such that P 0 BP 0 u k = λ k Au k . ( 11
)
Let P τ be an orthogonal projection on the subspace

Z = L ⊥ ker(A) ⊕ span {u k | λ k > τ } ,
then, the following inequality holds :

(u -P τ u) B (u -P τ u) ≤ τ u Au, ∀u ∈ R m . ( 12
)
Furthermore, Z is the subspace of smallest dimension such that (12) holds.

Proof 2 Let m A = dim(range(A)). Let λ 1 ≤ . . . ≤ λ mτ ≤ τ < λ mτ +1 ≤ . . . ≤ λ m A
be the eigenvalues of the generalized eigenvalue problem [START_REF] Li | Low-rank correction methods for algebraic domain decomposition preconditioners[END_REF]. Let

u 1 , . . . , u mτ , u mτ +1 , . . . , u m A be the corresponding eigenvectors, A-orthonormalized. Let k B = dim(ker(B) ∩ ker(A)), k A = dim(ker(A)) = m -m A . Let v 1 , . . . , v k B be an orthogonal basis of L and let v k B +1 , . . . , v k A be an orthogonal basis of L ⊥ ker(A) such that v 1 , . . . , v k A is an orthogonal basis of ker(A).
The symmetry of A and B permits to have

u i Au j = δ ij , 1 ≤ i, j ≤ m A , u i Bu j = λ i δ ij , 1 ≤ i, j ≤ m A , v i v j = δ ij , 1 ≤ i, j ≤ k A , L = span {v 1 , . . . , v k B } , L ⊥ ker(A) = span {v k B +1 , . . . , v k A } ,
where δ ij stands for the Kronecker symbol. For a vector u ∈ R m we can write :

P 0 u = m A k=1 (u k AP 0 u)u k .
Then, we have

P τ u = u -P 0 u - k B k=1 (v k u)v k + m A k=mτ +1 (u k AP 0 u)u k .
Thus,

u -P τ u = k B k=1 (v k u)v k + mτ k=1 (u k AP 0 u)u k .

Inria

Hence, the left side of (12) can be written as :

(u -P τ u) B (u -P τ u) = k B k=1 (v k u)v k + mτ k=1 (u k AP 0 u)u k B k B k=1 (v k u)v k + mτ k=1 (u k AP 0 u)u k , = k B k=1 (v k u)v k + mτ k=1 (u k AP 0 u)u k mτ k=1 λ k (u k AP 0 u)Au k , = k B k=1 (v k u)Av k + mτ k=1 (u k AP 0 u)Au k mτ k=1 λ k (u k AP 0 u)u k , = mτ k=1 (u k AP 0 u)Au k mτ k=1 λ k (u k AP 0 u)u k , =   k|λ k ≤τ (u k AP 0 u)u k     k|λ k ≤τ λ k (u k AP 0 u)Au k   , =   k|λ k ≤τ j|λj ≤τ (u k AP 0 u)u k λ j (u j AP 0 u)Au j   , = k|λ k ≤τ (u k AP 0 u) 2 λ k .
We obtain (12) by remarking that.

k|λ k ≤τ (u k AP 0 u) 2 λ k ≤ τ m A k=1 (u k AP 0 u) 2 , = τ m A k=1 (u k AP 0 u)(u k AP 0 u), = τ (P 0 u) AP 0 u, = τ u Au.
There remains the minimality of the dimension of Z. First, remark that u Bu > τ u Au, ∀u ∈ Z.

To prove the minimality, suppose that there is a subspace Z 1 of dimension less than the dimension of Z. By this assumption, there is a non-zero vector w

∈ (Z ∩ Z 1 ) ⊥ Z , where (Z ∩ Z 1 ) ⊥ Z is the orthogonal complementary of (Z ∩ Z 1 ) in Z, such that w ⊥ Z 1 .
By construction, we have w Bw > τ w Aw. Lemma 4 Let A ∈ R m×m be a symmetric positive matrix and B ∈ R m×m be an SPD matrix. Let ker(A), range(A) denote the null space and the range of A respectively. Let P 0 be an orthogonal projection on range(A). Let τ be a strictly positive real number. Consider the following generalized eigenvalue problem,

Find (u k , λ k ) ∈ R m × R such that RR n°9184 Au k = λ k Bu k . ( 13
)
Let P τ be an orthogonal projection on the subspace

Z = span u k | λ k < 1 τ ,
then, the following inequality holds :

(u -P τ u) B (u -P τ u) ≤ τ u Au ∀u ∈ R m . ( 14
)
Z is the subspace of smallest dimension such that (14) holds.

Proof 3 Let u 1 , . . . , u m0 be an orthogonal basis vectors of ker(A). Let

0 < λ m0+1 ≤ . . . ≤ λ mτ < 1 τ ≤ λ mτ +1 ≤ . . . ≤ λ m
be the eigenvalues strictly larger than 0 of the generalized eigenvalue problem [START_REF] Nepomnyaschikh | Mesh theorems of traces, normalizations of function traces and their inversions[END_REF]. Let u m0+1 , . . . , u mτ , u mτ +1 , . . . , u m be the corresponding eigenvectors A-orthonormalized. We can suppose that

u i Au j = δ ij , m 0 + 1 ≤ i, j ≤ m, u i Bu j = 1 λ i δ ij , m 0 + 1 ≤ i, j ≤ m, u i u j = δ ij , 1 ≤ i, j ≤ m 0 ,
where δ ij stands for the Kronecker symbol. We can write

P 0 u = m k=m0+1 (u k AP 0 u)u k .
Then, we have

P τ u = u -P 0 u + mτ k=m0+1 (u k AP 0 u)u k .
Thus,

u -P τ u = m k=mτ +1 (u k AP 0 u)u k , = k|λ k ≥ 1 τ (u k AP 0 u)u k .

Inria

Hence, the left side of (14) can be written

(u -P τ u) B (u -P τ u) =   k|λ k ≥ 1 τ (u k AP 0 u)u k   B   k|λ k ≥ 1 τ (u k AP 0 u)u k   , =   k|λ k ≥ 1 τ (u k AP 0 u)u k     k|λ k ≥ 1 τ 1 λ k (u k AP 0 u)Au k   , =   k|λ k ≥ 1 τ j|λj ≥ 1 τ (u k AP 0 u)u k 1 λ j (u j AP 0 u)Au j   , = k|λ k ≥ 1 τ (u k AP 0 u) 2 1 λ k .
We obtain (14) by remarking that.

k|λ k ≥ 1 τ (u k AP 0 u) 2 1 λ k ≤ τ m k=1 (u k AP 0 u) 2 , = τ m k=m0+1 (u k AP 0 u)(u k AP 0 u), = τ (P 0 u) AP 0 u, = τ u Au.
There remains the minimality of Z. First, remark that u Bu > τ u Au, ∀u ∈ Z.

To prove the minimality, suppose that there is a subspace Z 1 of dimension less than the dimension of Z. By this assumption, there is a non-zero vector w ∈ (Z ∩ Z 1 ) ⊥ Z , where (Z ∩ Z 1 ) ⊥ Z is the orthogonal complementary of (Z ∩ Z 1 ) in Z, such that w ⊥ Z 1 . By construction, we have w Bw > τ w Aw.

The previous lemmas are general and algebraic and not directly related to the preconditioning. In the following section we will review the one-and two-level additive Schwarz preconditioner.

One-and two-level additive Schwarz preconditioner

In this section we review the definition and general properties of one-and two-level additive Schwarz preconditioners, ASM, ASM 2 respectively. We review, without proving, several lemmas introduced in [START_REF] Chan | Domain decomposition algorithms[END_REF][START_REF] Victorita Dolean | An introduction to domain decomposition methods[END_REF]. These lemmas show how the elements of ASM 2 without any specific property of the coarse space S verify the conditions 1 and 2 of the fictitious subspace Lemma 2.

The two-level preconditioner ASM 2 with coarse space S is defined as

M -1 ASM,2 = N i=0 R i,1 R i,1 AR i,1 -1 R i,1 . (15)
If n 0,1 = 0, i.e., the subspace S is trivial, the term

R 0,1 R 0,1 AR 0,1 -1 R 0,1 = 0 by convention.
The following lemma gives the additive Schwarz method a matrix representation as in [START_REF] Victorita Dolean | An introduction to domain decomposition methods[END_REF].

Lemma 5

The additive Schwarz operator can be represented as :

M -1 ASM,2 = R 2 B -1 R 2 , ( 16
)
where R 2 is the operator adjoint of R 2 and B is a block diagonal operator defined as the following

B : N i=0 R ni,1 → N i=0 R ni,1 (u i ) 0≤i≤N → R i,1 AR i,1 u i 0≤i≤N (17)
where R i,1 AR i,1 for 0 ≤ i ≤ N is the i th diagonal block.

Proof 4

The proof follows directly from the definition of B and R 2 .

We note that the dimension of the matrix representation of B is larger than the dimension of A.

More precisely, B has the following dimension

n B = N i=0 n i,1 = n + n 0,1 + i=1 δ i .
The one-level additive Schwarz preconditioner can be defined in the same manner. It corresponds to the case where the subspace S is trivial. The following Lemma 6, [3, Lemma 7.10, p. 173] states that the operator R 2 is surjective without any specific assumption about the coarse space S.

Lemma 6 The operator R 2 as defined in (6) is surjective.

Proof 5

The proof follows from the definition of R 2 [START_REF] Grigori | Robust algebraic Schur complement preconditioners based on low rank corrections[END_REF] and the definition of the partition of unity (4).

Lemma 6 shows that the interpolation operator R 2 seen as a matrix verifies the condition 1 in Lemma 2. The following Lemma 7 guarantees that the matrix representation of the additive Schwarz verifies condition 2 in Lemma 2.

Lemma 7 Let k c be the minimum number of distinct colours so that span{R i,1 } 1≤i≤N of the same colour are mutually A-orthogonal. Then, we have

(R 2 u B ) A (R 2 u B ) ≤ (k c + 1) N i=0 u i R i,1 AR i,1 u i , ∀u B = (u i ) 0≤i≤N ∈ N i=0 R ni,1 . (18)
Proof 6 We refer the reader to [2, Theorem 12 p.93] for a detailed proof.

We note that Lemma 7 is true for any coarse space S, especially when this subspace is trivial. This makes the lemma applicable also for the one-level additive Schwarz preconditioner (the constant on the right-hand side in Lemma 7 becomes k c ). Lemma 8 is the first step to obtain a reasonable constant c l that verifies the third condition in Lemma 2

Inria Lemma 8 Let u A ∈ R n A and u B = (u i ) 0≤i≤N ∈ N i=0 R ni,1 such that u A = R 2 u B .
The additive Schwarz operator without any other restriction on the coarse space S verifies the following inequality

N i=0 u i R i,1 AR i,1 u i ≤ 2 u A Au A + (2k c + 1) N i=1 u i R i,1 AR i,1 u i , (19)
where k c is defined in Lemma 7.

Proof 7

We refer the reader to [3, Lemma 7.12, p. 175] to view the proof in detail.

In order to apply the fictitious subspace Lemma 2, the term 19) must be bounded by a factor of u A Au A . For this aim, the next section presents an algebraic local decomposition of the matrix A. Combining this decomposition with the Lemma 3 or Lemma 4 (depending on the definiteness) defines a class of local generalized eigenvalue problems. By solving them, we can define a coarse space S. The additive Schwarz preconditioner combined with S satisfy the three conditions of the fictitious subspace Lemma 2. Hence, we can control the condition number of the preconditioned system.

N i=1 u i R i AR i u i in the right-hand side of the (

Algebraic local SPSD splitting of an SPD matrix

In this section we present our main contribution. We introduce the algebraic local SPSD splitting of an SPD matrix related to a subdomain. Then, we characterize all the algebraic local SPSD splittings of A that are related to each subdomain. We give a non-trivial bound from below for the energy norm of a vector by a locally determined quantity.

We start by defining the algebraic local SPSD splitting of a matrix related to a subdomain.

Definition 1 (Algebraic local SPSD splitting of A related to a subdomain) Following the previous notations, let Ãi be the matrix defined as

P i Ãi P i =   R i,0 AR i,0 R i,0 AR i,δ R i,δ AR i,0 Ãδ 0   , (20)
where Ãδ ∈ R δi×δi . We say that Ãi is an algebraic local SPSD splitting of A related to the subdomain i if the following condition holds

0 ≤ u Ãi u ≤ u Au, ∀u ∈ R n . ( 21
) Lemma 9 Let m 1 , m 2 , m 3 be integers and m = m 1 + m 2 + m 3 , let B ∈ R m×m be a 3 × 3 block tridiagonal SPD matrix B =   B 11 B 12 B 21 B 22 B 23 B 32 B 33   , (22)
where

B ii ∈ R mi×mi is non-trivial matrix for i ∈ {1, 2, 3}. Let B1 ∈ R m×m be B1 =   B 11 B 12 B 21 B22 0   , (23)
where B22 ∈ R m2×m2 is a symmetric matrix verifying the following inequalities

u B 21 B -1 11 B 12 u ≤ u B22 u ≤ u B 22 -B 23 B -1 33 B 32 u, ∀u ∈ R m2 , (24)
then, the following inequality holds

0 ≤ u B1 u ≤ u Bu, ∀u ∈ R m . ( 25
)
Proof 8 Consider the difference matrix F = B -B1 . Let F 2 ∈ R (m2+m3)×(m2+m3) be the lowest 2 × 2 sub-block diagonal matrix of F , i.e.,

F 2 = B 22 -B22 B 23 B 32 B 33 .
F 2 admits the following decomposition,

F 2 = I B 23 B -1 33 I B 22 -B22 -B 23 B -1 33 B 32 B 33 I B -1 33 B 32 I . ( 26
)
Since B22 satisfies, by assumption, the inequality (24), F 2 satisfies the following inequality

0 ≤ u F 2 u ∀u ∈ R (m2+m3) ,
This proves the right inequality in (25).

Let E ∈ R (m1+m2)×(m1+m2) be the upper 2×2 sub-block diagonal of B1 . E admits the following decomposition,

E = I B 21 B -1 11 I B 11 B22 -B 21 B -1 11 B 12 I B -1 11 B 12 I . ( 27
)
The positivity of B1 follows directly from (24).

Lemma 10 Using the notations from Lemma 9, the following holds -The condition (24) in Lemma 9 is not trivial, i.e., the set of matrices B1 that verify the condition (24) is not empty -There exist matrices, B22 , that verify the condition (24) with strict inequalities -The left inequality in condition (24) is optimal, i.e., if there exists a non-zero vector

u 2 ∈ R m2 that verifies u 2 B 21 B -1 11 B 12 u 2 > u 2 B22 u 2 .
Then, there exists a non-zero vector u ∈ R m such that u B1 u < 0 -The right inequality in condition (24) is optimal, i.e., if there exists a non-zero vector u 2 ∈ R m2 that verifies

u 2 B22 u 2 > u 2 B 22 -B 23 B -1 33 B 32 u 2 .
Then, there exists a non-zero vector u ∈ R m such that u B1 u > u Bu Inria Proof 9 First we prove the non-triviality of the set of matrices verifying (24). Indeed, let S(B 22 ) be the Schur complement of B 22 in B, namely

S(B 22 ) = B 22 -B 21 B -1 11 B 12 -B 23 B -1 33 B 32 .
Set B22 := 1 2 S(B 22 ) + B 21 B -1 11 B 12 . Then we have,

B22 -B 21 B -1 11 B 12 = B 22 -B 23 B -1 33 B 32 -B22 = 1 2 S(B 22 ),
which is an SPD matrix. Hence, the strict inequalities in (24) follow. Let u 2 ∈ R m2 be a vector such that

u 2 B 21 B -1 11 B 12 u 2 > u 2 B22 u 2 ,
The block-LDLT factorization (27) shows that

u B1 u = u 2 B22 -B 21 B -1 11 B 12 u 2 < 0,
where u is defined as

u = I B -1 11 B 12 I -1 0 u 2 .
In the same manner we verify the optimality mentioned in the last point.

Remark 1 We note that the matrix

B 11 B 12 B 21 B22 defines a seminorm in R m1+m2 . Furthermore, if B22
is set such that the left inequality in (24) is strict, then the seminorm becomes a norm.

For i ∈ {1, . . . , N }, the matrix P i AP i has the form of a block tridiagonal matrix (the permutation matrix P i is defined in the section Notation). The first diagonal block corresponds to the interior DOF of the subdomain i, the second diagonal block corresponds to the overlapping DOF in the subdomain i, and the third block diagonal is associated to the rest of the DOF. This means that we can apply Lemma 9 on each subdomain by considering its interior DOF, overlapping DOF and the rest of the DOF. Proposition 1 For each subdomain i ∈ {1, . . . , N }, let Ãi ∈ R n×n be defined as

P i Ãi P i =   R i,0 AR i,0 R i,0 AR i,δ R i,δ AR i,0 Ãi δ 0   , (28)
where Ãi δ ∈ R δi×δi satisfies the following conditions

∀u ∈ R δi , -u R i,δ AR i,0 R i,0 AR i,0 -1 R i,0 AR i,δ u ≤ u Ãi δ u -u Ãi δ u ≤ u R i,δ AR i,δ -R i,δ AR i,c R i,c AR i,c -1 R i,c AR i,δ u.
Then, ∀i ∈ {1, . . . , N } the matrix Ãi is an algebraic local SPSD splitting of A related to the subdomain i. Moreover, the following inequality holds,

0 ≤ N i=1 u Ãi u ≤ k m u Au ∀u ∈ R n , (29)
where k m is a number bounded by N .

Proof 10 Lemma 9 shows that Ãi is an algebraic local SPSD splitting of A related to the subdomain i. The inequality (29) holds with the constant N for all algebraic local SPSD splittings of A. Thus, depending on the SPSD splitting related to each subdomain there exists a number k m ≤ N such that the inequality holds.

We note that the matrix Ãi is considered local since it has non-zero elements only in the overlapping subdomain i. More precisely,

∀ j, k ∈ N | j / ∈ N i,1 ∨ k / ∈ N i,1 , Ãi (j, k) = 0.
Proposition 1 shows that the A-norm of a vector v ∈ R n can be bounded from below by a sum of local seminorms, Remark 1.

4 Algebraic stable decomposition with R 2

In the previous section we introduced the algebraic local SPSD splitting of A. In this section we present the τ -filtering subspace that is associated with each SPSD splitting. In each subdomain a τ -filtering subspace will contribute to the coarse space. We show how this leads to a class of stable decomposition with R 2 . We note that the previous results of 2 hold for any coarse space S. Those results are sufficient to determine the constant c u in the second condition of the fictitious subspace lemma, Lemma 2. However, they do not allow to control the constant c l of the third condition of the same lemma.

As we will see, the GenEO coarse space [START_REF] Spillane | Abstract robust coarse spaces for systems of pdes via generalized eigenproblems in the overlaps[END_REF][START_REF] Victorita Dolean | An introduction to domain decomposition methods[END_REF] corresponds to a special SPSD splitting of A. Therefore, we follow the presentation in [START_REF] Victorita Dolean | An introduction to domain decomposition methods[END_REF] in the construction of the coarse space. We note that the proof of Theorem 1 is similar to the proof of [START_REF] Victorita Dolean | An introduction to domain decomposition methods[END_REF]Theorem 7.17,p.177]. We present it for the sake of completeness.

Definition 2 Let Ãi be an algebraic local SPSD splitting of A related to the subdomain i, for i = 1, . . . , N . Let τ > 0. Let Zi ⊂ R ni,1 be a subspace and let Pi be an orthogonal projection on Zi . We say that Zi is a τ -filtering subspace if

u i R i,1 AR i,1 u i ≤ τ (R i,1 u) R i,1 Ãi R i,1 (R i,1 u) , ∀u ∈ R n , where u i = D i I ni,1 -Pi R i,1
u and D i is the partition of unity, for i = 1, . . . , N .

After the characterization of the local SPSD splitting of A related to each subdomain, we characterize the associated smallest τ -filtering subspace.

Lemma 11 Let Ãi be an algebraic local SPSD splitting of A related to the subdomain i, for i = 1, . . . , N . Let τ > 0. For all subdomains 1 ≤ i ≤ N , let

Gi = D i R i,1 AR i,1 D i ,
where D i is the partition of unity. Let P0,i be the projection on range

(R i,1 Ãi R i,1 ) parallel to ker(R i,1 Ãi R i,1 ). Let K = ker(R i,1 Ãi R i,1 ), L = ker( Gi ) ∩ K, and L ⊥ K the orthogonal comple- mentary of L in K.
-If Gi is indefinite, consider the following generalized eigenvalue problem

Find (u i,k , λ i,k ) ∈ range(R i,1 Ãi R i,1 ) × R such that P0,i Gi P0,i u i,k = λ i,k R i,1 Ãi R i,1 u i,k . Set Zτ,i = L ⊥ K ⊕ span {u i,k | λ i,k > τ } . ( 30
)
Inria -If Gi is definite, consider the following generalized eigenvalue problem

Find (u i,k , λ i,k ) ∈ R ni,1 × R such that R i,1 Ãi R i,1 u i,k = λ i,k Gi u i,k . Set Zτ,i = span u i,k | λ i,k < 1 τ . ( 31
)
Then, Zτ,i is the smallest dimension τ -filtering subspace and the following inequality holds

u i R i,1 AR i,1 u i ≤ τ (R i,1 u) R i,1 Ãi R i,1 (R i,1 u) ,
where

u i = D i I ni,1 -Pτ,i R i,1 u
, and Pτ,i is the orhtogonal projection on Zτ,i .

Proof 11 Direct application of Lemma 3 and Lemma 4.

We will refer to the smallest dimension τ -filtering subspace as Zτ,i and to the projection on it as Pτ,i . Note that for each algebraic local SPSD splitting of A related to a subdomain i, the τ -filtering subspace Zτ,i defined in Definition 2 changes. Thus, the projection Pτ,i depends on the algebraic local SPSD splitting of A related to the subdomain i.

In the rest of the paper, the notations Zτ,i and Pτ,i will be used according to the algebraic local SPSD splitting of A that we deal with and following Lemma 11. Definition 2 leads us to bound the sum in ( 19) by a sum of scalar products associated to algebraic SPSD splittings of A. Therefore, a factor, which depends on the value of τ , of the scalar product associated to A will bound the inequality in [START_REF] Stewart | A krylov-schur algorithm for large eigenproblems[END_REF].

Definition 3 (Coarse space based on algebraic local SPSD splitting of A, ALS) Let Ãi be an algebraic local SPSD splitting of A related to the subdomain i, for i = 1, . . . , N . Let Zτ,i be the subspace associated to Ãi as defined in Lemma 11. We define S the coarse space based on the algebraic local splitting of A related to each subdomain, as the sum of expanded weighted τ -filtering subspaces associated to the algebraic local splitting of A related to each subdomain,

S = N i=1 R i,1 D i Zτ,i . ( 32
)
Let Z0 be a matrix whose columns form a basis of S. We denote its transpose by R 0,1 = Z 0 .

As mentioned previously, the key point to apply the fictitious subspace lemma, Lemma 2, is to find a coarse space that induces a relatively large c l in the third condition of the lemma. The following theorem proves that ALS satisfies this.

Theorem 1 Let Ãi be an algebraic local SPSD splitting of A related to the subdomain i, for i = 1, . . . , N . Let Zτ,i be the τ -filtering subspace associated to Ãi , and Pτ,i be the projection on Zτ,i as defined in Lemma 11. Let u ∈ R n and let

u i = D i I ni,1 -Pτ,i R i,1 u for i = 1, . . . , N .
Let u 0 be defined as,

u 0 = R 0,1 R 0,1 -1 R 0,1 N i=1 R i,1 D i Pτ,i R i,1 u . RR n°9184 Let c l = (2 + (2k c + 1)k m τ ) -1 . Then, u = N i=0 R i,1 u i , and
c l N i=0 u i R i,1 AR i,1 u i ≤ u Au. Proof 12 Since ∀y ∈ S, y = R 0,1 R 0,1 R 0,1 -1 R 0,1 y, the relation u = N i=0 R i,1 u i = R 2 (u i ) 0≤i≤N , follows directly. Lemma 8 shows that N i=0 u i R i,1 AR i,1 u i ≤ 2u Au + (2k c + 1) N i=1 u i R i,1 AR i,1 u i .
By using Lemma 11 we can write

N i=0 u i R i,1 AR i,1 u i ≤ 2u Au + (2k c + 1)τ N i=1 (R i,1 u) R i,1 Ãi R i,1 (R i,1 u) .
Since Ãi is local, we can write

N i=0 u i R i,1 AR i,1 u i ≤ 2u Au + (2k c + 1)τ N i=1 u Ãi u.
Then, by applying Proposition 1, we can write

N i=0 u i R i,1 AR i,1 u i ≤ 2u Au + (2k c + 1)k m τ u Au, N i=0 u i R i,1 AR i,1 u i ≤ (2 + (2k c + 1)k m τ ) u Au.
Theorem 2 Let M ALS be the two-level ASM preconditioner combined with ALS. The following inequality holds,

κ M -1 ALS A ≤ (k c + 1) (2 + (2k c + 1)k m τ )
Proof 13 Lemma 6, Lemma 7, and Theorem 1 show that the two-level preconditioner associated with ALS verifies the conditions of the fictitious subspace lemma, Lemma 2. Hence, the eigenvalues of M -1 ALS A verify the following inequality,

1 2 + (2k c + 1)k m τ ≤ λ M -1 ALS A ≤ (k c + 1),
and the result follows.

Inria

Remark 2 Since any τ -filtering subspace Zi can replace Zτ,i in Theorem 1, the Theorem 2 applies for coarse spaces of the form S = N i=1 R i,1 D i Zi . The difference is that the dimension of the coarse space is minimal by choosing Zτ,i , see Lemma 11. We note that the previous theorem, Theorem 2, shows that the spectral condition number of the preconditioned system does not depend on the number of subdomains. It depends only on k c , k m , and τ . k c is bounded by the maximum number of neighbors of a subdomain. k m is a number bounded by the number of subdomains. It depends on the algebraic local SPSD splitting of each subdomain. Partitioned graphs of sparse matrices have structures such that k c is small. The parameter τ can be chosen small enough such that ALS has a relatively small dimension.

GenEO coarse space

In [START_REF] Victorita Dolean | An introduction to domain decomposition methods[END_REF], the authors present the theory of one-and two-level additive Schwarz preconditioners. To bound the largest eigenvalue of the preconditioned system they use the algebraic properties of the additive Schwarz preconditioner. However, to bound the smallest eigenvalue, they benefit from the discretization of the underlying PDE. In the environment of the finite element method, they construct local matrices corresponding to the integral of the operator in the overlapping subdomain. For each subdomain, the expanded matrix has the form

P i Ãi P i =   R i,0 AR i,0 R i,0 AR i,δ R i,δ AR i,0 Ãi δ 0   ,
where Ãi δ corresponds to the integral of the operator in the overlapping region with neighbors of the subdomains i. This matrix is SPSD since the global operator is SPD. Since the integral over the subdomain is always smaller than the integral over the global domain (positive integrals), the following inequality holds

0 ≤ u Ãi u ≤ u Au, ∀u ∈ R n .
Hence, Lemma 10 confirms that the matrix Ãi corresponds to an algebraic local SPSD splitting of A related to the subdomain i. Thus, GenEO is a member of the class of preconditioners that are based on the algebraic local SPSD splitting of A. We note that the parameter k m , defined in (29), with the algebraic local SPSD splitting of A corresponding to GenEO can be shown to be equal to the maximum number of subdomains sharing a DOF.

Extremum efficient coarse space

In this section we discuss the two obvious choices to have algebraic local SPSD splitting of A. We show how in practice these two choices are costly. However, they have two advantages. The first is that one of these choices gives an answer to the following question that appears in domain decomposition. How many local vectors must be added to the coarse space in order to bound the spectral condition number by a number defined a priori ? We are able to answer this question in the case where the additive Schwarz preconditioner is to be used. We note that the answer is given without any analytic information. Only the coefficients of the matrix A have to be known. The second advantage is that both choices give an idea of constructing a non-costly algebraic approximation of an ALS.

In the following discussion we disregard the impact of the parameter k m . Numerical experiments in 5 demonstrate that the impact of this parameter can be negligible. We note that this parameter depends only on the algebraic local SPSD splitting and it is bounded by N . Suppose that we have two SPSD splittings of A related to a subdomain i,

Ã(1) i , Ã(2) i , such that : u Ã(1) i u ≤ u Ã(2) i u, ∀u ∈ R n .
We want to compare the number of vectors that contribute to the coarse space for each SPSD splitting. It is clear that a τ -filtering subspace associated to Ã

i is a τ -filtering subspace associated to Ã(2) i . Thus, the following inequality holds,

dim( Z(1) τ,i ) ≥ dim( Z(1) τ,i ),
where

Z(1) τ,i , Z (2)
τ,i are the smallest τ -filtering subspaces associated to

Ã(1) i , Ã (2)
i , respectively. Therefore, Lemma 10 shows that closer we are to the upper bound in (24) less vectors will contribute to ALS. Moreover, closer we are to the lower bound in (24) more vectors will contribute to ALS. Indeed, the set of algebraic local SPSD splitting of A related to a subdomain i admits a relation of partial ordering.

M 1 ≤ M 2 ⇐⇒ u M 1 u ≤ u M 2 u, ∀u. This set admits obviously a smallest and a largest element defined by the left and the right bounds in (24), respectively.

Hence, the best ALS corresponds to the following algebraic local SPSD splitting of A, for i = 1, . . . , N ,

P i Ãi P i =    R i,0 AR i,0 R i,0 AR i,δ R i,δ AR i,0 R i,δ AR i,δ -R i,δ AR i,c R i,c AR i,c -1 R i,c AR i,δ 0    . (33)
The dimension of the subspace Zτ,i associated to Ãi (33) is minimal over all possible algebraic local SPSD splittings of A related to the subdomain i. We remarke that this splitting is not a choice in practice since it includes inverting the matrix R i,c AR i,c which is of large size (approximately corresponding to N -1 subdomains). We will refer to (33) as the upper bound SPSD splitting, the associated coarse space will be referred to as the upper ALS.

In the same manner, we can find the worst ALS. The corresponding algebraic local SPSD splitting of A related to the subdomain i is the following

P i Ãi P i =    R i,0 AR i,0 R i,0 AR i,δ R i,δ AR i,0 R i,δ AR i,0 R i,0 AR i,0 -1 R i,0 AR i,δ 0    . (34)
On the contrary of the best splitting (33), this splitting is not costly. It includes inverting the matrix R i,0 AR i,0 which is considered small. However, the dimension of Zτ,i associated to Ãi (34) is maximal. It is of dimension δ i at least. Indeed, a block-LDLT factorization of R i,1 Ãi R i,1

shows that its null space is of dimension δ i . We will refer to (34) as the lower bound SPSD splitting the associated coarse space will be referred to as the lower ALS. We refer to it as α-convex SPSD splitting, We refer to the corresponding ALS as the α-convex ALS.

In the following section we propose a strategy to compute an approximation of reasonable ALS that is not costly. ASM increases by increasing the number of subdomains. However, we remark that the iteration number of the CG preconditioned by ALS is robust when the number of subdomain increases.

In Table 5 we compare three ALS, the upper bound, α 1 -convex, and α 2 -convex, where α 1 = 0.75 and α 2 = 0.25. Table 5 shows the efficiency of three ALS related to different SPSD splittings.

To illustrate the impact of the parameter k m , when increasing the number of subdomains, on bounding the spectral condition number, we do the following. We choose τ as

τ = ( κ 2k c -2)(2k c + 1) -1 ,
i.e., we suppose that k m has no impact on τ . The resulting spectral condition number will be effected only by the parameter k m see Table 5. Table 5 and Table 5 present results for ALS variants when κ = 100. We perform this test on the elasticity problem where we could also compare against the GenEO coarse space [START_REF] Spillane | Abstract robust coarse spaces for systems of pdes via generalized eigenproblems in the overlaps[END_REF][START_REF] Victorita Dolean | An introduction to domain decomposition methods[END_REF]. Table 5 shows the dimension of ALS of each variant as well as the iteration number for preconditioned CG to reach the convergence tolerance. On the other hand, Table 5 shows an estimation of the spectral condition number of the preconditioned system. This estimation is performed by computing an approximation of the largest and the smallest eigenvalues of the preconditioned operator by using the Krylov-Schur method [START_REF] Stewart | A krylov-schur algorithm for large eigenproblems[END_REF] in MATLAB. The same tolerance τ is applied for GenEO. In order to avoid a large-dimension coarse space, 30 vectors at max are deflated per subdomain. We note that results in Table 5 satisfy the discussion in 4.2. Indeed the upper bound ALS has the minimum dimension, 0.75-and 0.25-convex ALS follow the upper bound ALS respectively.

Table 5 demonstrates the impact of k m on the bound of the spectral condition number. We notice that its effect increases when α is closer to 1. In Figure 1 with ALS variants and GenEo coarse space, results correspond to Table 5, N is the number of subdomains, the subscript uC refers to the upper bound ALS, α refers to the coefficient in the convex ALS, α 1 = 0.75 and α 2 = 0.25, the subscript Gen stands for the GenEO coarse space. subdomain contributes to the coarse space is not necessarily equal. In the case of α 2 -convex ALS, most subdomains reach the maximum number of deflated vectors, 30, that we fixed. Moreover, Figure 2 compares the number of deflated vectors in each subdomain for the GenEO subspace and the upper bound ALS. This figure illustrates the relation of partial ordering between the SPSD splitting as discussed in 4.2.

In Table 5 we show the impact of the approximation strategy that we proposed in 4.3. The distance parameter related to the approximation, see 4.3, is fixed for each matrix. It is obtained by tuning. The convex linear combination is chosen as α = 0.01. Each subdomain contributes 20 vectors to the coarse space. We remark that the approximation strategy gives interesting results with the conviction-diffusion problem matrices SKY2D and SKY3D. With a small factor of the local dimension d = 2 and d = 3, respectively, the approximate ALS is able to perform relatively as efficient as the upper bound ALS. For the elasticity problem with a larger factor d = 5, the approximate ALS reduces the iteration number, however, we remark that the latter increases by increasing the number of subdomains.

Conclusion

In this paper we reviewed generalities of one-and two-level additive Schwarz preconditioner. We introduced the algebraic local SPSD splitting of an SPD matrix A. We characterized all possible algebraic local SPSD splitting. To study the minimality of the dimension of the coarse space, we introduced the τ -filtering subspaces. Based on the algebraic local SPSD splitting and inspired by the GenEO method [START_REF] Spillane | Abstract robust coarse spaces for systems of pdes via generalized eigenproblems in the overlaps[END_REF][START_REF] Victorita Dolean | An introduction to domain decomposition methods[END_REF], we introduced a class of algebraic coarse spaces that are constructed locally, ALS. The characterization of algebraic local SPSD splitting of A and the associated τ -filtering subspaces makes an algebraic framework for studying the coarse spaces The signmeans that the method did not converge in fewer than 150 iteration.

Inria related to the additive Schwarz method. We proved that the coarse space of GenEO corresponds to a special case of the SPSD splitting. We discussed different types of ALS and suggested a simple method to approximate a valuable coarse space. For matrices issued from the conviction-diffusion problem, the simple method that we proposed gave very interesting results.

Table des matières

12 B 21 B

 1221 22 B 23 B 32 B 33   , the local SPSD splitting of B with respect to the first block means finding two SPSD matrices B 1 , B 2 of the form B 1 =

a 11 a 12 a 21 a 22 a 23 a 32 a 33 a 34 a 43 a 44

 44 = {1, 2, 3, 4}. The sets of interior DOF of subdomains are N 1,0 = {1, 2 }, N 2,0 = {3, 4}. The sets of overlapping DOF of subdomains are ∆ 1 = {3}, ∆ 2 = {2}. The sets of concatenation of the interior DOF and the overlapping DOF of subdomains are N 1,1 = {1, 2, 3 }, N 2,1 = {3, 4, 2}.

Remark 3 A

 3 convex linear combination of the lower bound and the upper bound of the SPSD splitting is also an algebraic local SPSD splitting. α × the upper bound SPSD splitting + (1 -α) × the lower bound SPSD splitting

Figure 1 -Figure 2 -

 12 Figure 1 -Histogram of the number of deflated vectors by each subdomain for different ALS, GenEO ; uC, the upper bound ALS ; α 1 -convex ALS, α 1 = 0.75 ; α 2 -convex ALS, α 2 = 0.25

1 11 3 13 4

 11113 Auxiliary lemmas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 One-and two-level additive Schwarz preconditioner . . . . . . . . . . . . . . . . . Algebraic local SPSD splitting of an SPD matrix Algebraic stable decomposition with R 2 16 4.1 GenEO coarse space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.2 Extremum efficient coarse space . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.3 Approximate ALS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

Table 1 -

 1 Matrices used for tests. n is the size of the matrix, N nZ is the number of non-zero elements. HPD stands for Hermitian Positive Definite. κ is the condition number related to the second norm.

	Inria

Table 2 -

 2 Comparison between ASM 2 with the upper ALS and one-level additive Schwarz, n is the dimension of the problem, N is the number of subdomains, n uC is the iteration number of CG preconditioned by ASM 2 , and n ASM is the iteration number of CG preconditioned by one-level ASM . The signmeans that the method did not converge in fewer than 100 iteration.

	Inria

Table 3 -

 3 Comparison between ALS variants, the upper bound ALS, the α 1 -convex ALS, and the α 2 -convex CosBALSS, n is the dimension of the problem, N is the number of subdomains, the subscript uC refers to the upper bound ALS, n . is the iteration number of ASM 2 , α refers to the coefficient in the convex linear combination, α 1 = 0.75 and α 2 = 0.25.

Table 4 -

 4 we present a histogram of the number of deflated vectors by each subdomain. We remark that the number of vectors that each Matrix El3D, ALS variants and GenEo coarse space with the minimum number of deflated vectors disregarding the parameter k m , N is the number of subdomains, the subscript uC refers to the upper bound ALS. dim . is the dimension of ALS, n . is the iteration number of ASM 2 , α refers to the coefficient in the convex ALS, α 1 = 0.75 and α 2 = 0.25, the subscript Gen stands for the GenEO coarse space. See Table5

	N	dim uC n uC	dim α1 n α1	dim α2 n α2	dim Gen n Gen
	4	82	20	92	19	120	18	106	20
	8	179	23	209	20	240	20	229	24
	16	304	37	394	30	480	28	391	38
	32	447	53	583	45	960	36	614	42
	64	622	84	769	73	1920	51	850	55
	128	969	131	1096	112	3834	77	1326	61
			N	κ uC	κ α1	κ α2	κ Gen
			4	5	4	4	5
			8	8	5	5	7
			16	15	10	9	15
			32	34	25	15	18
			64	100	67	30	31
			128	231	178	86	39

Table 5 -

 5 Estimation of the spectral condition number of matrix El3D preconditioned by ASM 2

Table 6 -

 6 Comparison between the upper bound ALS and the approximation strategy presented in 4.3, n is the dimension of the problem, N is the number of subdomains, n uC is the iteration number of CG preconditioned by ASM 2 with the upper bound ALS, d stands for the factor of local dimension to approximate the upper bound SPSD splitting, as explained in 4.3, and n ap is the iteration number of CG preconditioned by ASM 2 with approximation of ALS, the convex linear combination is chosen as (0.01 × approximation of the upper bound + 0.99 × lower bound).

	Matrix	n	N	n uC	d n ap
			4	22	22
			8	23	23
	SKY3D	8000	16	24	2 22
			32	22	22
			64	24	22
			128	22	44
			4	17	17
			8	18	18
	SKY2D	10000 16	20	3 19
			32	22	22
			64	26	59
			128	31	90
			4	27	54
			8	36	56
	EL3D	15795 16	37	5 77
			32	43	136
			64	61	-
			128	83	-

RR n°9184

rue Simone Iff -CS 42112

Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

Approximate ALS

As mentioned in 4.2, the extremum cases of ALS are not practical choices. Nevertheless, the ALS can be approximated by considering the following strategy. We restrict the matrix R i,c AR i,c to the neighbors DOF of the subdomain i through the graph of A such that the restriction of the matrix R i,c AR i,c has a dimension dim i ≤ d × n i,1 , where d is a fixed integer. Then we can take a convex linear combination of the lower bound SPSD splitting and the approximation of the upper bound SPSD splitting. For instance, the error bound on this approximation is still an open question. Numerical experiments show that d does not need to be large.

Numerical experiments

In this section we present numerical experiments for ALS. We denote ASM ALS the two-level additive Schwarz combined with ALS. If it is not specified, the number of vectors deflated by subdomain is fixed to 15. We use the preconditioned CG implemented in MATLAB 2017R to compare the preconditioners. The threshold of convergence is fixed to 10 -6 . Our test matrices arise from the discretization of two types of challenging problems : linear elasticity and diffusion problems [START_REF] Grigori | Enlarged Krylov Subspace Conjugate Gradient Methods for Reducing Communication[END_REF][START_REF] Achdou | Low frequency tangential filtering decomposition[END_REF][START_REF] Niu | Modified tangential frequency filtering decomposition and its fourier analysis[END_REF]. Our set of matrices are given in Table 1. The matrices SKY2D and SKY3D arise from the boundary value problem of the diffusion equation on Ω, the (2-D) unit square and the (3-D) unit cube, respectively :

They correspond to skyscraper problems. The domain Ω contains several zones of high permeability. These zones are separated from each other. The tensor κ is given by the following relation :

Ω is a unit cube (3-D). The matrix El3D corresponds to this equation discretized using a triangular mesh with 30 × 5 × 5 vertices. Γ D is the Dirichlet boundary, Γ N is the Neumann boundary, f is a force, u is the unknown displacement field. The Cauchy stress tensor σ(.) is given by Hooke's law : it can be expressed in terms of Young's modulus E and Poisson's ration ν. n denotes the exterior normal vector to the boundary of Ω. We consider discontinuous E and ν : (E 1 , ν 1 ) = (2 × 10 11 , 0.45), (E 2 , ν 2 ) = (10 7 , 0.25). Data elements of this problem are obtained by the application FreeFem++ [START_REF] Hecht | New development in freefem++[END_REF]. Table 5 presents a comparison between one-level ASM and ASM 2 with the upper bound ALS. As it is known, the iteration number of CG preconditioned by