{'fraction_non_alphanumeric': 0.049610340239498195, 'fraction_numerical': 0.017043654565038334, 'mean_word_length': 4.128005198180637, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Semi-convergence of the APSS method for a class of nonsymmetric three-by-three singular saddle point problems

For nonsymmetric block three-by-three singular saddle point problems arising from the Picard iteration method for a class of mixed finite element scheme, recently Salkuyeh et al. in (D.K. Salkuyeh, H. Aslani, Z.Z. Liang, An alternating positive semi-definite splitting preconditioner for the three-by-three block saddle point problems, Math. Commun. 26 (2021) 177-195) established an alternating positive semi-definite splitting (APSS) method. In this work, we analyse the semi-convergence of the APSS method for solving a class of nonsymmetric block three-by-three singular saddle point problems. The APSS induced preconditioner is applied to improve the semi-convergence rate of the flexible GMRES (FGMRES) method. Experimental results are designated to support the theoretical results. These results show that the served preconditioner is efficient compared with FGMRES without a preconditioner.


Introduction
We are interested in solving the following large and sparse block three-by-three saddle point system by iteration methods, where A ∈ R n×n , B ∈ R m×n and C ∈ R l×m . Here f ∈ R n , g ∈ R m and h ∈ R l are known and x = (x; y; z) is an unknown vector that has to be determined. The coefficient matrix of the system (2) is of order n = m + n + l. Many practical applications produce linear systems of the form (2); for example in application of the Picard iteration method for a class of mixed finite element scheme for stationary magnetohydrodynamics models [17] and finite element method to solve the time-dependent Maxwell equations having discontinuous coefficients in polyhedral domains with Lipschitz boundary. References [14,26] provide additional instances and references therein.
In this paper, we make an attempt to solve the following system, which is an equivalent form of (1). Note that the coefficient matrix in (1) is symmetric, however, A is nonsymmetric. Nevertheless, A has some good properties. For instance, A is positive semi-definite. It means that A + A T is Symmetric Positive Semi-Definite (SPSD). This property can greatly improve the performance of the GMRES method for solving the system. Some other features are available in [20]. Consider the two-by-two block saddle point problem The matrixÃ ∈ R p×p is assumed to be a Symmetric Positive Definite (SPD),B ∈ R p×q with p > q is a matrix that rank(B) = r < q (i.e.,B is a rank-deficient matrix),f ∈ R p and g ∈ R q . Thereby, the linear system (3) leads to a two-by-two singular saddle point problem.
In the context of the two-by-two singular saddle point problem, Bai [4] established the HSS method for singular saddle point problem and also derived some conditions for guaranteeing the semi-convergence of the HSS method. Li et al. [22] generalized the HSS method for solving non-Hermitian, positive semi-definite, and singular linear systems. They studied semiconvergence analysis of the Generalized HSS (GHSS) method. In addition, an upper bound for the semi-convergence factor was derived. In [12] a Generalized Preconditioned Hermitian and skew-Hermitian splitting method (GPHSS) was considered to solve the singular saddle point problems. The semi-convergence of the GPHSS scheme was proved under some conditions. In addition, the authors obtained the induced preconditioner and discussed the eigenvalues of the preconditioned matrix. Then, the Local Hermitian and skew-Hermitian (LHSS) method and the Modified LHSS (MLHSS) method were established in [20]. They also gave the semiconvergence conditions. Motivated by the Uzawa method, Chao et al. [11] designed the Uzawa-SOR method for singular saddle point problems. Generalization of the Uzawa-SOR method was investigated in [31]. The authors established the Uzawa-AOR scheme to solve (3). The distribution of the eigenvalues of the iteration matrix and the semi-convergence properties were given. Numerical results indicate that the Uzawa-AOR method outperforms the Uzawa method [2], the parameterized Uzawa method [35], and the Uzawa-SOR method [11]. Some other efficient methods for the singular saddle point problem of the form (3) were studied in [24,33,34]. Note that some partitioning techniques can be employed to represent the three-by-three coefficient matrix in (2) as: which are the standard two-by-two saddle point problem. Many available preconditioning schemes for (3), can not be implemented for solving (1). This is because of different properties in two problems. Note that the matrix A described in (2) is nonsingular if A is SPD and the matrices B and C are of full row rank (see [18,19,28]). In recent years, many researchers have considered the three-by-three saddle point problem. Huang et al. [20] arranged a block diagonal preconditioner for solving the nonsingular system of the form (2). The exact and inexact versions of the preconditioner were also studied. Then, in [10] the shift splitting (SS) and the relaxed shift splitting (RSS) method were designated. Xie et al. [30] considered three efficient preconditioners. The authors analyzed the eigenvalues of the corresponding preconditioned matrices. Aslani et al. [3] presented a new method for solving (2) when A is SPD and B, C are full row rank matrices. Convergence properties of the method was derived. Moreover, the spectral properties of the preconditioned matrix were discussed. Abdolmaleki et al. [1] from another perspective organized a block three-by-three diagonal preconditioner for (2). A suitable estimation strategy for lower and upper bounds of eigenvalues of the preconditioned matrix was considered. In [29] an exact parameterized block SPD preconditioner and its inexact version for a class of block three-by-three saddle point problems was proposed. The authors also estimated the eigenvalue bounds for the preconditioned matrix.
In [21], Liang and Zhang proposed the Alternating Positive Semi-definite Splitting (APSS) iteration method for double saddle point problems. Using the idea of [21], Salkuyeh et al. in [27] applied the APSS method for solving the problem (2) and proved its convergence. In the case of C being rank-deficient, the coefficient matrix (2) is singular. Accordingly, the linear system (2) is labeled as a singular three-by-three saddle point problem. In this work, the three-by-three large, sparse, and singular saddle point problem is considered and the semi-convergence analysis of the APSS method is discussed.
The structure of this paper is as follows. The paper is started with a review of the APSS method and its corresponding induced preconditioner. In Section 2, we focus on the semiconvergence properties of the APSS method for solving (2). Unconditionally semi-convergent for the APSS iteration method are derived in Section 3. A strategy is given to estimate the parameter of the proposed method in Section 4. Section 5 is devoted to give some numerical tests to support the theoretical results. The end of the paper will be companied by some brief conclusions.

Review of the APSS method
Let us first give a brief study of the APSS method. Consider the following decomposition for the coefficient matrix A in (2): where Let α > 0 be a given parameter. Based on the decomposition (4), the following splittings for the matrix A can be stated where I is the identity matrix of order n. Now, by using these splittings the APSS method can be written as where x (0) ∈ R n is an initial guess. By eliminating x (k+ 1 2 ) , the iteration scheme can be rewritten as the stationary form with and Similar to the Hermitian and Skew-Hermitian splitting (HSS) iteration method [5], if we set From now on, we use M α = (αI + A 1 )(αI + A 2 ) as the APSS preconditioner, since the pe-factor 1 2α has no effect on the preconditioned matrix. So, the saddle point system (2) can be preconditioned from the left as M α where

The semi-convergence of APSS iteration method
In this section, we will analyze the semi-convergence properties of the APSS iteration method for solving the double saddle point problem (2). First, let us give some related definitions, lemmas and theorems. (6) is said to be semiconvergent if for any initial guess x (0) , the iteration sequence {x (k) } produced by (6) converges to a solution of linear systems Ax = b.

Theorem 1. [7] The iteration method (6) is semi-convergent if and only if
is called the pseudo-spectral radius of T α . Moreover, the limit of the sequence can be written as .

Remark 1. For the saddle point matrix of the form
if A is singular, we can easily see that at least one of the sets null(B T )∩null(C) and null(C T ) is nontrivial, i.e., the dimension of one of the two sets is at least one.
Noticing that it is easy to see that the matrix T α is similar to Now, since the matrices A 1 and A 2 are both positive semi-definite, then using the Kellogg's lemma we have Thus, it holds that L α x = x if and only if L * α x = x, for any x ∈ C n×n [4]. As a result the index of index(I − L α ) = 1. Eventually, since two similar matrices have the same index, we see that index(I − T α ) = 1.

Theorem 2.
Suppose that A ∈ R n×n is symmetric positive definite, B ∈ R m×n is an arbitrary matrix and C ∈ R l×m is rank-deficient. Then, for the decomposition (4) of the matrix A, the pseudo-spectral radius of T α is less than one, i.e., ϑ(T α ) < 1, ∀α > 0.
Proof. First of all note that the matrix αI − A 2 is non-singular, and the equalities 10 and 11 hold. Hence, the matrix T α is similar to . Let x ∈ C n be any eigenvector of the matrix P α and λ be the eigenvalue of matrix P α corresponding to eigenvector x, i.e., P α x = λx. Without loss of generality, we assume that x 2 = 1. Now, we prove the theorem according to the following four cases: and By combining (14) and (15), we have P α x = x. Thus, λ = 1.
Here, if B T v = 0, then we see that v = 0, because B is a full row rank matrix. It is immediate to conclude that A 1 x = 0, which is a contradiction with the assumption x / ∈ null(A 1 ). Thereby, from (20) it holds e ıθ = −1. Substituting the equality e ıθ = −1 into (21) and (22), results in v = 0 and p = 0, respectively. So w = 0. Consequently, we have x = (αI+A 1 )w = 0, which contradicts with the fact that x is an eigenvector. Therefore, |λ| < 1.

Theorem 3.
Suppose that the assumptions of Theorem 2 hold. Then, the APSS iteration method (6) is semi-convergent for any α > 0.

Estimation strategy for the parameter α
Finding the optimal parameter α of the APSS method is generally hard. In this section, we propose an appropriate strategy for estimating α in the APSS method, which has been studied by Cao [9]. Notably, from (8) it is anticipated that M α is as close as conceivable to A when N α ≈ 0. In this way, having Eq. (9) in mind, the function can be characterized. Minimizing Ψ(α) with respect to α leads to the estimation parameter α est being set to Since the matrix A is SPD (in this case, A 1 = 0), one can conclude that α est > 0. In the following section, the efficiency of this choice will be verified.

Numerical experiments
To indicate the efficiency of the APSS preconditioner, we have conducted some numerical tests. We provide two examples and each one is scaled by a symmetric diagonal matrix. To this end, the coefficient matrix A is replaced by the matrix D − 1 2 AD − 1 2 , in which D = diag ( A 1 2 , . . . , A n 2 ). In addition, the jth column of the matrix A is represented by A j .
For all the examples, a zero vector was used as the initial guess, and the iteration was terminated once or the specified number of iteration steps, maxit = 2000, is exceeded. Note that x (k) stands for the computed solution at the kth iteration. The right hand side vector b was chosen such that the exact solution of (2) was a vector of all ones. In the following, we apply the complete version of FGMRES method with right preconditioning technique in conjunction with APSS preconditioner M α . For the APSS preconditioner, we need to solve two SPD linear systems including αI + A + 1 α B T B and α 2 I + CC T as sub-tasks. To solve these linear systems, we employ the conjugate gradient (CG) method without preconditioning and the iteration was stopped when the residual 2-norm is reduced by a factor of 10 3 or the maximum number of inner iteration is reached to 200.
In the tables below, we use "CPU", "IT" and "RES" to represent the elapsed CPU time to converge in second, iteration counts and relative residual, respectively. In addition, Degree of freedom (DOF) is defined as DOF = n + m + l = n. Finally, a dagger ( †), means that more than the maximum number of iterations are needed to converge. All the examples were performed in Matlab-R2019a. All the numerical results were obtained by a Laptop by the following features: intel (R), Core(TM) i5-8265U, CPU @ 1.60 GHz, 8 GB.

Example 1. Consider the two dimensional leaky lid-driven cavity problem
−∆u + ∇p = 0, in Ω, in which a suitable boundary conditions are applied on the side and bottom points. u and p symbolized the velocity vector field and the pressure scalar field, respectively. In addition, ∆ and ∇ refer to the vector Laplacian in R 2 and the gradient, respectively. This problem is called the Stokes problem. For the saddle point problem (2), the matrices A and B come from the Stokes problem. To obtain these matrices, we use the IFISS package by Elman et al. [15]. Note that the stablized Q 1 − P 0 and Q 2 − P 1 finite element method (FEM) is employed to discretize the Stokes equation (35). The grid parameters are chosen as h = 1 8 , 1 16 , . . . , 1 256 , for all uniform or stretched grid points. Now, the matrix C is taken to be the form This example is a technical variant of Example 1 in [29]. The results are given in Tables 1-4. From these tables, we can observe that the FGMRES method in conjunction with the APSS preconditioner M α is strongly more efficient than the FGMRES without a preconditioner. As we can see from Figure 1, the preconditioner M α is efficient to cluster the eigenvalues of the original coefficient matrix. Another observation which can be posed here is that the number of iterations of the FGMRES method with the APSS preconditioner remains almost constant when the size of the problem is increased, whereas this is not the case for FGMRES without preconditioning. [20,30] as follows:

Example 2. Consider a technical modification of Example 1 in
where and c 1 = e T ; 0 T C 1 , c 2 = 0 T ; e T C 1 , e T = 1; 1; 1; · · · , 1 ∈ R    6.4e-08 3.5e-08 3.1e-08 6.5e-08 9.0e-08 3.1e-08   and E = diag 1, p + 1, 2p + 1, . . . , p 2 − p + 1 in which the Kronecker product is denoted by ⊗, while the discretization mesh size is represented by h = 1/(p + 1). Table 5 reports the result of the FGMRES method and the FGMRES in conjunction with the proposed preconditioner M α , with respect to IT, CPU and RES. Table 5 shows that the suggested preconditioner requires significantly less iteration numbers and CPU time than the FGMRES without a preconditioner. We also see that when the size of the problem is increased, the number of iterations of the FGMRES without preconditioning increase drastically, whereas for the FGMRES with the preconditioner M α increases moderately. Figure 2 illustrates that the preconditioned matrix works well in clustering the eigenvalues.

Conclusions
In this paper, the APSS method was employed to solve a class of nonsymmetric three-bythree singular saddle point problems. We have applied the induced preconditioner, M α , to improve the semi-convergence rate ,when it is conjucted with FGMRES. We have proved that if C is rank-deficient the APSS method is unconditionally semi-convergent. Numerical tests prove our theoretical claims.

Declaration
There is no conflict of interest.