A simplified HSS preconditioner for generalized saddle point problems

Abstract

For generalized saddle point problems, we propose a simplified Hermitian and skew-Hermitian splitting (SHSS) preconditioner which is much closer to the generalized saddle point matrix than the HSS preconditioner. It is proved that all eigenvalues of the SHSS preconditioned matrix are real and nonunit eigenvalues are located in a positive interval. We also study the eigenvector distribution and the degree of the minimal polynomial of the preconditioned matrix. Numerical examples of a model Stokes problem show the effectiveness of the SHSS preconditioner.

1 Introduction

We consider the iterative solution of the generalized saddle point problem

$$\begin{aligned} \mathscr {A}\bar{u}\equiv \left[ \begin{array}{c@{\quad }c} A &{} B^T \\ -B &{} C \end{array}\right] \left[ \begin{array}{c} x \\ y \end{array}\right] = \left[ \begin{array}{c} f \\ -g \end{array}\right] \equiv b, \end{aligned}$$

(1.1)

where $A\in \mathbb {R}^{n\times n}$ is symmetric positive definite, $B\in \mathbb {R}^{m\times n}$ ($m\le n$) has full row rank, $C\in \mathbb {R}^{m\times m}$ is symmetric positive semi-definite, and $f\in \mathbb {R}^{n}$ and $g\in \mathbb {R}^{m}$ are given vectors. The above assumptions show that the generalized saddle point matrix $\mathscr {A}$ is nonsymmetric positive semi-definite and nonsingular. The generalized saddle point problem (1.1) arises in many areas of scientific computing and engineering applications, such as computational fluid dynamics [25], mixed finite element discretization of elliptic PDEs [18], element-free Galerkin discretization of elasticity problem [12, 22, 37], data interpolation [23], constrained optimization, constrained least-squares problem [31], and so on; see also [1, 15] and the references therein.

Many efficient solvers have been studied in the past decades for solving the saddle point problem (1.1). In many cases, A, B and C are large sparse matrices and iterative techniques are preferable for solving (1.1). And Krylov subspace iterative methods are a class of effective methods for solving such systems of linear equations. Since $\mathscr {A}$ is nonsymmetric and often ill-conditioned, preconditioning is in most cases indispensable for the iterative solution of (1.1). A high-quality preconditioner plays a crucial role in guaranteeing the fast convergence rate of Krylov subspace methods. The preconditioner usually reduces the number of iteration steps required for convergence. On the other hand, it doesn’t significantly increase the computational cost for each iteration. A lot of preconditioners have been investigated for the generalized saddle point problem (1.1), such as block diagonal and block triangular preconditioners [1, 10, 20, 29], constraint preconditioners [11, 38], HSS preconditioner and its variants [5, 8, 9, 14], and so on.

Applying the HSS iteration method in [8], Benzi and Golub in [14] discussed the following HSS preconditioner

$$\begin{aligned} \hat{\mathscr {P}}_{HSS}&=\frac{1}{2\alpha }(\alpha I+\mathscr {H})(\alpha I+\mathscr {S})\nonumber \\&=\frac{1}{2\alpha }\left[ \begin{array}{c@{\quad }c} \alpha I+A &{} 0\\ 0 &{} \alpha I+C \end{array} \right] \left[ \begin{array}{c@{\quad }c} \alpha I &{} B^T\\ -B &{} \alpha I \end{array} \right] \end{aligned}$$

(1.2)

for the saddle point problem (1.1), where $\alpha >0$ is a given constant, I is the identity matrix, and

$$\begin{aligned} \mathscr {H}=\left[ \begin{array}{c@{\quad }c} A &{} 0\\ 0 &{} C \end{array} \right] \quad \mathrm{and} \quad \mathscr {S}=\left[ \begin{array}{c@{\quad }c} 0 &{} B^T\\ -B &{} 0 \end{array} \right] \end{aligned}$$

are the Hermitian and the skew-Hermitian parts of $\mathscr {A}$, respectively. The HSS preconditioner $\hat{\mathscr {P}}_{HSS}$ in (1.2) is induced by the HSS iteration method

$$\begin{aligned} \left\{ \begin{array}{l} (\alpha I+\mathscr {H})\bar{u}^{k+\frac{1}{2}}=(\alpha I-\mathscr {S})\bar{u}^{k}+b,\\ (\alpha I+\mathscr {S})\bar{u}^{k+1}=(\alpha I-\mathscr {H})\bar{u}^{k+\frac{1}{2}}+b, \end{array}\right. \quad k=0,1,2,\ldots . \end{aligned}$$

(1.3)

The authors in [14] have proved that the HSS iteration method (1.3) converges unconditionally to the unique solution of the generalized saddle point problem (1.1). It is noted that the HSS iteration method was first proposed by Bai et al. [8] for solving non-Hermitian positive definite linear systems and they proved the unconditionally convergent property of this method. The iteration scheme (1.3) is indeed a special case of the original HSS iteration method. Due to the elegant mathematical properties, the HSS iteration method has attracted much attention and there are many papers devoted to the various aspects of this method. Based on the idea of the HSS iteration, many effective iterative methods and the corresponding preconditioners were proposed for saddle point problems. In [5], the accelerated HSS iteration method was proposed by introducing another parameter. For saddle point problems from time-harmonic eddy current models, the block alternating splitting implicit iteration method [3] and the alternating positive semi-definite splitting method [33] were proposed. For the saddle point matrix from two dimensional Navier–Stokes problem, the deteriorated positive and skew-Hermitian splitting preconditioner [32], the dimensional split preconditioner [16], and the modified dimensional split preconditioner [21] were presented by making use of the special structure of the coefficient matrix. In order to get a better approximation to the saddle point matrix, some relaxed preconditioners were also proposed for the saddle point matrix; see [17, 19, 22]. In addition, the authors in [7, 24, 27, 36] have studied spectral properties of the HSS-based preconditioned matrix. Since the spectral distribution of the preconditioned matrix relates closely to the convergence rate of Krylov subspace methods, it is expected that the preconditioned saddle point matrix has desired eigenvalue distribution like tightly clustered spectra or positive real spectra; see [4, 34].

In this paper, we propose a simplified Hermitian and skew-Hermitian splitting (SHSS) preconditioner for the generalized saddle point problem (1.1), which is based on the HSS preconditioner. The SHSS preconditioner is much closer to the generalized saddle point matrix $\mathscr {A}$ than the HSS preconditioner, but it is no longer induced by an alternating direction iteration method. The SHSS preconditioner is much easier to be implemented than the HSS preconditioner. Theoretical analysis shows that all eigenvalues of the SHSS preconditioned saddle point matrix are real and the nonunit eigenvalues are located in a positive interval. We also obtain the eigenvector distribution and an upper bound of the degree of the minimal polynomial of the preconditioned matrix. In addition, we present a practical choice of the parameter involved, which leads to excellent numerical results.

The remainder of this paper is organized as follows. In Sect. 2, we propose the SHSS preconditioner and compare the computational costs of the HSS and SHSS preconditioners. In Sect. 3, some properties of the SHSS preconditioned matrix are analyzed. Numerical examples are given to show the effectiveness of the SHSS preconditioner in Sect. 4. Finally, in Sect. 5 we end this paper with a few of concluding remarks.

2 A simplified HSS preconditioner

In this section, we present a simplified variant of the HSS perconditioner for the generalized saddle point problem (1.1). When the HSS splitting matrix $\hat{\mathscr {P}}_{HSS}$ in (1.2) is served as a preconditioner, the pre-factor has no effect on the preconditioned system. For convenience, we replace it by the following HSS preconditioner

$$\begin{aligned} \mathscr {P}_{HSS}&=\frac{1}{\alpha }(\alpha I+\mathscr {H})(\alpha I+\mathscr {S})\nonumber \\&=\frac{1}{\alpha }\left[ \begin{array}{c@{\quad }c} \alpha I+A &{} 0\\ 0 &{} \alpha I+C \end{array} \right] \left[ \begin{array}{c@{\quad }c} \alpha I &{} B^T\\ -B &{} \alpha I \end{array} \right] . \end{aligned}$$

(2.1)

By direct computation, we know that the HSS preconditioner $\mathscr {P}_{HSS}$ has the following block structure

$$\begin{aligned} \mathscr {P}_{HSS}=\left[ \begin{array}{c@{\quad }c} \alpha I+A &{} B^T+\frac{1}{\alpha }AB^T\\ -B-\frac{1}{\alpha }CB &{} \alpha I+C \end{array} \right] \end{aligned}$$

and the difference between the preconditioner $\mathscr {P}_{HSS}$ and the generalized saddle point matrix $\mathscr {A}$ is given by

$$\begin{aligned} \mathscr {Q}_{HSS}=\mathscr {P}_{HSS}-\mathscr {A}=\left[ \begin{array}{c@{\quad }c} \alpha I &{} \frac{1}{\alpha }AB^T\\ -\frac{1}{\alpha }CB &{} \alpha I \end{array} \right] . \end{aligned}$$

(2.2)

It is observed from (2.2) that when the parameter $\alpha$ tends to zero, the diagonal blocks tend to be zero matrices while the off-diagonal blocks go to infinity. Therefore, we must choose an appropriate parameter $\alpha$ to balance the diagonal and the off-diagonal parts.

According to the theory of preconditioning techniques, we know that the spectral distribution of the preconditioned matrix relates closely to the convergence of Krylov subspace methods and favorable convergence rates are often associated with the eigenvalues of the preconditioned matrix around one and away from zero. Hence, we hope that a preconditioner and the coefficient matrix should be as close as possible. From this point of view, the HSS preconditioner $\mathscr {P}_{HSS}$ in (2.1) may not be a good approximation to the generalized saddle point matrix $\mathscr {A}$. From (2.1) we know that the HSS preconditioner is a scaled product of the block diagonal symmetric positive definite matrix $\alpha I+\mathscr {H}$ and the normal matrix $\alpha I+\mathscr {S}$. In order to get a better approximation to the generalized saddle point matrix $\mathscr {A}$, we propose the following simplified HSS (SHSS) preconditioner

$$\begin{aligned} \mathscr {P}_{SHSS}&=\frac{1}{\alpha }\left[ \begin{array}{c@{\quad }c} A &{} 0\\ 0 &{} \alpha I \end{array} \right] \left[ \begin{array}{c@{\quad }c} \alpha I &{} B^T\\ -B &{} C \end{array} \right] \nonumber \\&=\left[ \begin{array}{c@{\quad }c} A &{} \frac{1}{\alpha }AB^T\\ -B &{} C \end{array} \right] , \end{aligned}$$

(2.3)

which is a scaled product of a block diagonal symmetric positive definite matrix and a block nonsymmetric positive semi-definite matrix. The difference between the SHSS preconditioner $\mathscr {P}_{SHSS}$ and the generalized saddle point matrix $\mathscr {A}$ is

$$\begin{aligned} \mathscr {Q}_{SHSS}=\mathscr {P}_{SHSS}-\mathscr {A} =\left[ \begin{array}{c@{\quad }c} 0 &{} \left( \frac{1}{\alpha }A-I\right) B^T\\ 0 &{} 0 \end{array} \right] . \end{aligned}$$

(2.4)

There is only the (1, 2) block being nonzero in $\mathscr {Q}_{SHSS}$, which shows that the preconditioner $\mathscr {P}_{SHSS}$ is a better approximation to the matrix $\mathscr {A}$ than the preconditioner $\mathscr {P}_{HSS}$ and it may be easier to analyze the eigenvalue distribution of the preconditioned matrix $\mathscr {P}_{SHSS}^{-1}\mathscr {A}$.

For the SHSS preconditioner, there is another advantage that it is easier to implement than the HSS preconditioner. In fact, when the SHSS preconditioner is used to accelerate the convergence of Krylov subspace methods, it is necessary to solve sequences of generalized residual equations of the form

$$\begin{aligned} \left[ \begin{array}{c@{\quad }c} A &{} 0\\ 0 &{} \alpha I \end{array}\right] \left[ \begin{array}{c@{\quad }c} \alpha I &{} B^T\\ -B &{} C \end{array}\right] \left[ \begin{array}{c} z_1\\ z_2 \end{array}\right] =\left[ \begin{array}{c} r_1\\ r_2 \end{array}\right] , \end{aligned}$$

(2.5)

where $[z_1^T, z_2^T]^T$ and $[r_1^T, r_2^T]^T$ are the current and the generalized residual vectors, respectively. Then it follows from (2.5) that

$$\begin{aligned} \left[ \begin{array}{c} z_1\\ z_2\end{array}\right]&= \left[ \begin{array}{c@{\quad }c} \alpha I &{} B^T\\ -B &{} C \end{array}\right] ^{-1}\left[ \begin{array}{c@{\quad }c} A &{} 0\\ 0 &{} \alpha I \end{array}\right] ^{-1} \left[ \begin{array}{c} r_1\\ r_2\end{array}\right] \nonumber \\&=\left[ \begin{array}{c@{\quad }c} I &{} -\frac{1}{\alpha }B^T\\ 0 &{} I\end{array}\right] \left[ \begin{array}{c@{\quad }c} \frac{1}{\alpha }I &{} 0\\ 0 &{} \left( C+\frac{1}{\alpha }BB^T\right) ^{-1} \end{array}\right] \left[ \begin{array}{c@{\quad }c} I &{} 0\\ \frac{1}{\alpha }B &{} I \end{array}\right] \left[ \begin{array}{c@{\quad }c} A^{-1} &{} 0\\ 0 &{} \frac{1}{\alpha }I\end{array}\right] \left[ \begin{array}{c} r_1\\ r_2\end{array}\right] . \end{aligned}$$

(2.6)

Thus, from (2.6) we derive the following algorithm for solving the generalized residual equations (2.5).

Algorithm 2.1

For a given residual vector $[r_1^T, r_2^T]^T$, the current vector $[z_1^T,\ z_2^T]^T$ in (2.5) is computed by the following procedures:

• (1) solve $Av_1=r_1$;

• (2) solve $(C+\frac{1}{\alpha }BB^T)z_2=\frac{1}{\alpha }(Bv_1+r_2)$;

• (3) $z_1=\frac{1}{\alpha }(v_1-B^Tz_2)$.

From Algorithm 2.1, we see that there are two linear subsystems with coefficient matrices A and $C+\frac{1}{\alpha }BB^T$ needed to be solved at steps (1) and (2). Because the matrices A and $C+\frac{1}{\alpha }BB^T$ are symmetric positive definite, at each step we can use the sparse Cholesky decomposition to solve the two linear subsystems. To implement the SHSS preconditioner efficiently, there is an important issue of how to choose the parameter $\alpha$. It is difficult to find the theoretically optimum parameter $\alpha$. However, by an algebraic estimation technique [26] we can find a suitable parameter

$$\begin{aligned} \alpha _{est}=\frac{\Vert BB^T\Vert _2}{\Vert C\Vert _2}, \end{aligned}$$

(2.7)

which balances the matrices C and $BB^T$ in practical computation. It can be found that the estimate (2.7) is a good choice for the parameter $\alpha$ and numerical results in Sect. 4 confirm this.

In the HSS preconditioning process, we need to solve sequences of generalized residual equations of the form

$$\begin{aligned} \left[ \begin{array}{c@{\quad }c} \alpha I+A &{} 0\\ 0 &{} \alpha I+C \end{array}\right] \left[ \begin{array}{c@{\quad }c} \alpha I &{} B^T\\ -B &{} \alpha I \end{array}\right] \left[ \begin{array}{c} z_1\\ z_2 \end{array}\right] =\left[ \begin{array}{c} r_1\\ r_2 \end{array}\right] , \end{aligned}$$

(2.8)

which can be fulfilled by the following algorithm.

Algorithm 2.2

For a given residual vector $[r_1^T, r_2^T]^T$, the current vector $[z_1^T,\ z_2^T]^T$ in (2.8) is computed by the following procedures:

• (1) solve $(\alpha I+A)v_1=r_1$;

• (2) solve $(\alpha I+C)v_2=r_2$;

• (3) solve $(\alpha I+\frac{1}{\alpha }BB^T)z_2=\frac{1}{\alpha }Bv_1+v_2$;

• (4) $z_1=\frac{1}{\alpha }(v_1-B^Tz_2)$.

From Algorithm 2.2, we see that there are three linear subsystems with coefficient matrices $\alpha I+A$, $\alpha I+C$ and $\alpha I+\frac{1}{\alpha }BB^T$ needed to be solved. These linear subsystems can also be solved by the sparse Cholesky decomposition, since the coefficient matrices are symmetric positive definite. The theoretical optimal parameter $\alpha$ for the HSS preconditioner can be found in [2, 6, 13] and a practical choice of $\alpha$ can be found in [28].

Comparing Algorithms 2.1 to 2.2, we observe that the SHSS preconditioner is much easier to implement than the HSS preconditioner, since the former only needs to solve two symmetric positive definite linear subsystems while the latter needs to solve three symmetric positive definite linear subsystems. Therefore, the cost for one iteration of the SHSS preconditioner is much cheaper than that of the HSS preconditioner.

3 Analysis of the SHSS preconditioned matrix

The spectral distribution of the preconditioned matrix relates closely to the convergence rate of Krylov subspace methods. Tightly clustered spectrum or positive real spectrum of the preconditioned matrix are desirable. In this section, we derive some properties of the SHSS preconditioned saddle point matrix $\mathscr {P}_{SHSS}^{-1}\mathscr {A}$. Here and in the sequel, we use $\mathrm{sp}(W)$ to represent the spectrum of the matrix W. The following theorem describes the eigenvalue distribution of the preconditioned matrix $\mathscr {P}_{SHSS}^{-1}\mathscr {A}$.

Theorem 3.1

Assume that $A\in \mathbb {R}^{n\times n}$ is a symmetric positive definite matrix, $B\in \mathbb {R}^{m\times n}$ has full row rank, $C\in \mathbb {R}^{m\times m}$ is a symmetric positive semi-definite matrix, and $\alpha$ is a positive constant. Let the SHSS preconditioner $\mathscr {P}_{SHSS}$ be defined as in (2.3). Let $\mathrm{sp}(C)\subseteq [0, \mu _m]$, $\mathrm{sp}(BB^T)\subseteq [\sigma _1, \sigma _m]$, and $\mathrm{sp}(BA^{-1}B^T)\subseteq [\tau _1, \tau _m]$. Then the preconditioned matrix $\mathscr {P}_{SHSS}^{-1}\mathscr {A}$ has an eigenvalue 1 with multiplicity at least n, and the remaining eigenvalues are real and located in the positive interval

$$\begin{aligned} \Big [\frac{\alpha \tau _1}{\alpha \mu _m+\sigma _m},\ \frac{\alpha (\mu _m+\tau _m)}{\sigma _1}\Big ]. \end{aligned}$$

Proof

From (2.4) and (2.6), we obtain

$$\begin{aligned} \mathscr {P}_{SHSS}^{-1}\mathscr {A}&=\mathscr {P}_{SHSS}^{-1}(\mathscr {P}_{SHSS}-\mathscr {Q}_{SHSS})\nonumber \\&=I-\mathscr {P}_{SHSS}^{-1}\mathscr {Q}_{SHSS}\nonumber \\&=I-\alpha \left[ \begin{array}{c@{\quad }c} \alpha I &{} B^T\\ -B &{} C \end{array}\right] ^{-1} \left[ \begin{array}{c@{\quad }c} A &{} 0\\ 0 &{} \alpha I \end{array}\right] ^{-1} \left[ \begin{array}{c@{\quad }c} 0 &{} \left( \frac{1}{\alpha }A-I\right) B^T\\ 0 &{} 0 \end{array} \right] \nonumber \\&= I-\left[ \begin{array}{c@{\quad }c} I-\frac{1}{\alpha }B^T\left( C+\frac{1}{\alpha }BB^T\right) ^{-1}B &{} -B^T \left( C+\frac{1}{\alpha }BB^T\right) ^{-1}\\ \left( C+\frac{1}{\alpha }BB^T\right) ^{-1}B &{} \alpha \left( C+\frac{1}{\alpha }BB^T\right) ^{-1} \end{array}\right] \left[ \begin{array}{c@{\quad }c} 0 &{} \left( \frac{1}{\alpha }I-A^{-1}\right) B^T\\ 0 &{} 0 \end{array}\right] \nonumber \\&=I-\left[ \begin{array}{c@{\quad }c} 0 &{} \left[ I-\frac{1}{\alpha }B^T \left( C+\frac{1}{\alpha }BB^T\right) ^{-1}B\right] \left( \frac{1}{\alpha }I-A^{-1}\right) B^T\\ 0 &{} \left( C+\frac{1}{\alpha }BB^T\right) ^{-1}B \left( \frac{1}{\alpha }I-A^{-1}\right) B^T \end{array}\right] \nonumber \\&= \left[ \begin{array}{c@{\quad }c} I &{} A^{-1}B^T-\frac{1}{\alpha }B^T \left( C+\frac{1}{\alpha }BB^T\right) ^{-1}(C+BA^{-1}B^T)\\ 0 &{} \left( C+\frac{1}{\alpha }BB^T\right) ^{-1}(C+BA^{-1}B^T)\end{array}\right] . \end{aligned}$$

(3.1)

It then follows from (3.1) that the preconditioned matrix $\mathscr {P}_{SHSS}^{-1}\mathscr {A}$ has an eigenvalue 1 with multiplicity at least n and the remaining eigenvalues are the same as those of the matrix $(C+\frac{1}{\alpha }BB^T)^{-1}(C+BA^{-1}B^T)$.

Since the matrices $BB^T$ and $BA^{-1}B^T$ are symmetric positive definite matrices, and the matrix C is a symmetric positive semi-definite matrix, we know that $\mu _m\ge 0$, $\sigma _m\ge \sigma _1>0$, $\tau _m\ge \tau _1>0$, and

$$\begin{aligned} \mathrm{sp}\left( C+\frac{1}{\alpha }BB^T\right) \subseteq \Big [\frac{\sigma _1}{\alpha },\ \mu _{m}+\frac{1}{\alpha }\sigma _m\Big ] \end{aligned}$$

and

$$\begin{aligned} \mathrm{sp}(C+BA^{-1}B^T)\subseteq [\tau _1,\ \mu _{m}+\tau _{m}]. \end{aligned}$$

As the matrices $C+\frac{1}{\alpha }BB^T$ and $C+BA^{-1}B^T$ are also symmetric positive definite, we obtain

$$\begin{aligned} \mathrm{sp}\left( \left( C+\frac{1}{\alpha }BB^T\right) ^{-1}\right) \subseteq \left[ \frac{\alpha }{\alpha \mu _{m}+\sigma _{m}},\ \frac{\alpha }{\sigma _1}\right] , \end{aligned}$$

and

$$\begin{aligned} \mathrm{sp}\left( \left( C+\frac{1}{\alpha }BB^T\right) ^{-1}(C+BA^{-1}B^T)\right) \subseteq \left[ \frac{\alpha \tau _1}{\alpha \mu _{m}+\sigma _{m}},\ \frac{\alpha (\mu _{m}+\tau _{m})}{\sigma _1}\right] . \end{aligned}$$

Therefore, the remaining eigenvalues of the preconditioned matrix $\mathscr {P}_{SHSS}^{-1}\mathscr {A}$ are real and located in the positive interval $\Big [\frac{\alpha \tau _1}{\alpha \mu _{m}+\sigma _{m}},\ \frac{\alpha (\mu _{m}+\tau _{m})}{\sigma _1}\Big ]$. $\square$

Remark 3.1

Note that the positive interval presented in Theorem 3.1 is not so sharp. In fact, if we take $A=\alpha I$, then all eigenvalues of the preconditioned matrix $\mathscr {P}_{SHSS}^{-1}\mathscr {A}$ are 1. However, the positive interval in Theorem 3.1 is $\Big [\frac{\sigma _1}{\alpha \mu _{m}+\sigma _{m}},\ \frac{\alpha \mu _{m}+\sigma _{m}}{\sigma _1}\Big ]$, which is subject to theories of eigenvalue estimates for the product of two symmetric positive definite matrices [30]. How to find a sharp eigenvalue estimate needs further study. In practical implementation, if we take $\alpha _{est}=\frac{\Vert BB^T\Vert _2}{\Vert C\Vert _2}=\frac{\sigma _m}{\mu _m}$, then the positive interval becomes $\Big [\frac{\tau _1}{2\mu _{m}},\ \frac{\sigma _m(\mu _{m}+\tau _{m})}{\sigma _1\mu _m}\Big ]$. Here, we assume that $\mu _m>0$.

The convergence of Krylov subspace methods is not only related to the eigenvalue distribution of the preconditioned matrix, but also related to the number of corresponding linearly independent eigenvectors. The eigenvector distribution of the preconditioned matrix $\mathscr {P}_{SHSS}^{-1}\mathscr {A}$ is presented in the following theorem.

Theorem 3.2

Let the SHSS preconditioner $\mathscr {P}_{SHSS}$ be defined as in (2.3), then the preconditioned matrix $\mathscr {P}_{SHSS}^{-1}\mathscr {A}$ has $n+i+j$ $(0\le i+j\le m)$ linearly independent eigenvectors. There are

• (1) n eigenvectors $\left[ \begin{array}{c} u_\ell \\ 0 \end{array}\right]$ $(\ell =1,2,\ldots ,n)$ that correspond to the eigenvalue 1, where $u_\ell$ $(\ell =1,2,\ldots ,n)$ are arbitrary linearly independent vectors.

• (2) i $(0\le i\le m)$ eigenvectors $\left[ \begin{array}{c} u^1_\ell \\ v^1_\ell \end{array}\right]$ $(1\le \ell \le i)$ that correspond to the eigenvalue 1, where $v^1_\ell \ne 0$, $(A-\alpha I)B^Tv^1_\ell =0$, $i=\mathrm{dim}\{\mathrm{null}(A-\alpha I)\cap \mathrm{range}(B^T)\}$, and $u^1_\ell$ are arbitrary vectors.

• (3) j $(0\le j\le m)$ eigenvectors $\left[ \begin{array}{c} u^2_\ell \\ v^2_\ell \end{array}\right] (1\le \ell \le j)$ that correspond to eigenvalues $\lambda _\ell \ne 1$, where $v^2_\ell \ne 0$, $(C+BA^{-1}B^T)v^2_\ell =\lambda _\ell (C+\frac{1}{\alpha }BB^T)v^2_\ell$, and $u^2_\ell =\frac{1}{1-\lambda _\ell }(\frac{\lambda _\ell }{\alpha }I-A^{-1})B^Tv^2_\ell$.

Proof

Let $\lambda$ be an eigenvalue of the preconditioned matrix $\mathscr {P}_{SHSS}^{-1}\mathscr {A}$ and $\left[ \begin{array}{c} u\\ v \end{array}\right]$ be the corresponding eigenvector. From (3.1) we have

$$\begin{aligned} \left[ \begin{array}{c@{\quad }c} I &{} A^{-1}B^T-\frac{1}{\alpha }B^TF^{-1}E\\ 0 &{} F^{-1}E \end{array}\right] \left[ \begin{array}{c} u\\ v \end{array}\right] =\lambda \left[ \begin{array}{c} u\\ v \end{array}\right] , \end{aligned}$$

(3.2)

where $E=C+BA^{-1}B^T$ and $F=C+\frac{1}{\alpha }BB^T$. Note that the matrices E and F are symmetric positive definite. It then follows from (3.2) that

$$\begin{aligned} {\left\{ \begin{array}{ll} (1-\lambda )u=\left( \frac{\lambda }{\alpha }I-A^{-1}\right) B^Tv,\\ Ev=\lambda F v. \end{array}\right. } \end{aligned}$$

(3.3)

If $\lambda =1$ holds true, then the Eq. (3.3) become

$$\begin{aligned} {\left\{ \begin{array}{ll} (A-\alpha I)B^Tv=0,\\ Ev=Fv. \end{array}\right. } \end{aligned}$$

(3.4)

When $v=0$, the Eq. (3.4) are always true. Hence, there are n linearly independent eigenvectors $\left[ \begin{array}{c} u_\ell \\ 0 \end{array}\right]$ $(\ell =1,2,\ldots ,n)$ corresponding to the eigenvalue 1, where $u_\ell$ $(\ell =1,2,\ldots ,n)$ are arbitrary linearly independent vectors. Since the second equation in (3.4) is equivalent to

$$\begin{aligned} BA^{-1}(A-\alpha I)B^Tv=0, \end{aligned}$$

(3.5)

if there exists any $v\ne 0$ which satisfies the first equation in (3.4), then it must satisfy (3.5) or the second equation in (3.4). Hence, there will be i ($0\le i\le m$) linearly independent eigenvectors $\left[ \begin{array}{c} u^1_\ell \\ v^1_\ell \end{array}\right]$ $(1\le \ell \le i)$ that correspond to the eigenvalue 1, where $v^1_\ell$ satisfy $(A-\alpha I)B^Tv^1_\ell =0$ and $u^1_\ell$ are arbitrary vectors. Further, we know that $i=\mathrm{dim}\{\mathrm{null}(A-\alpha I)\cap \mathrm{range}(B^T)\}$, where $\mathrm{null}(\cdot )$ and $\mathrm{range}(\cdot )$ denote the null space and range space of the corresponding matrix, respectively.

Next, we consider the case $\lambda \ne 1$. It then follows from (3.3) that the nonunit eigenvalues of the preconditioned matrix $\mathscr {P}_{SHSS}^{-1}\mathscr {A}$ are the same as those of the matrix $F^{-1}E$. From the first equation in (3.3), we have

$$\begin{aligned} u=\frac{1}{1-\lambda }\left( \frac{\lambda }{\alpha }I-A^{-1}\right) B^Tv. \end{aligned}$$

(3.6)

If $v=0$, then $u=0$, which contradicts with $\left[ \begin{array}{c} u\\ v \end{array}\right]$ being an eigenvector. Hence, $v\ne 0$. If there exists $v\ne 0$ which satisfies the second equation in (3.3), then there will be j $(0\le j\le m)$ linearly independent eigenvectors $\left[ \begin{array}{c} u^2_\ell \\ v^2_\ell \end{array}\right] (1\le \ell \le j)$ that correspond to eigenvalues $\lambda \ne 1$. Here, the vectors $v^2_\ell$ $(1\le \ell \le j)$ satisfy $Ev^2_\ell =\lambda Fv^2_\ell$ and the vectors $u^2_\ell$ $(1\le \ell \le j)$ satisfy (3.6). For this case, the vector $u^2_\ell \ne 0$ unless $B^Tv^2_\ell \in \mathrm{null}(\frac{\lambda }{\alpha }A-I)$.

Finally, we show that the $n+i+j$ eigenvectors are linearly independent. Let $c=[c_1, c_2, \ldots , c_n]^T$, $c^1=[c_1^1,c_2^1, \ldots , c_i^1]^T$ and $c^2=[c_1^2,c_2^2, \ldots , c_j^2]^T$ be three vectors with $0\le i,j\le m$. Then we need to show that

$$\begin{aligned} \left[ \begin{array}{c@{\quad }c@{\quad }c} u_1 &{} \cdots &{} u_n\\ 0 &{} \cdots &{} 0 \end{array}\right] \left[ \begin{array}{c} c_1 \\ \vdots \\ c_n \end{array}\right] +\left[ \begin{array}{c@{\quad }c@{\quad }c} u_1^1 &{} \cdots &{} u_i^1\\ v_1^1 &{} \cdots &{} v_i^1 \end{array}\right] \left[ \begin{array}{c} c_1^1 \\ \vdots \\ c_i^1 \end{array}\right] +\left[ \begin{array}{c@{\quad }c@{\quad }c} u_1^2 &{} \cdots &{} u_j^2\\ v_1^2 &{} \cdots &{} v_j^2 \end{array}\right] \left[ \begin{array}{c} c_1^2 \\ \vdots \\ c_j^2 \end{array}\right] =\left[ \begin{array}{c} 0 \\ \vdots \\ 0 \end{array}\right] \end{aligned}$$

(3.7)

holds true if and only if the vectors c, $c^1$ and $c^2$ are all zero vectors, where the first matrix consists of the eigenvectors corresponding to the eigenvalue 1 for the case (1), the second matrix consists of those for the case (2), and the third matrix consists of the eigenvectors corresponding to $\lambda \ne 1$ for the case (3). By multiplying both sides of (3.7) from left with $\mathscr {P}_{SHSS}^{-1}\mathscr {A}$, we obtain

$$\begin{aligned} \left[ \begin{array}{c@{\quad }c@{\quad }c} u_1 &{} \cdots &{} u_n\\ 0 &{} \cdots &{} 0 \end{array}\right] \left[ \begin{array}{c} c_1 \\ \vdots \\ c_n \end{array}\right] +\left[ \begin{array}{c@{\quad }c@{\quad }c} u_1^1 &{} \cdots &{} u_i^1\\ v_1^1 &{} \cdots &{} v_i^1 \end{array}\right] \left[ \begin{array}{c} c_1^1 \\ \vdots \\ c_i^1 \end{array}\right] +\left[ \begin{array}{c@{\quad }c@{\quad }c} u_1^2 &{} \cdots &{} u_j^2\\ v_1^2 &{} \cdots &{} v_j^2 \end{array}\right] \left[ \begin{array}{c} \lambda _1c_1^2 \\ \vdots \\ \lambda _jc_j^2 \end{array}\right] =\left[ \begin{array}{c} 0 \\ \vdots \\ 0 \end{array}\right] . \end{aligned}$$

(3.8)

Then, by subtracting (3.8) from (3.7), it holds that

$$\begin{aligned} \left[ \begin{array}{c@{\quad }c@{\quad }c} u_1^2 &{} \cdots &{} u_j^2\\ v_1^2 &{} \cdots &{} v_j^2 \end{array}\right] \left[ \begin{array}{c} (\lambda _1-1) c_1^2 \\ \vdots \\ (\lambda _j-1) c_j^2 \end{array}\right] =\left[ \begin{array}{c} 0 \\ \vdots \\ 0 \end{array}\right] . \end{aligned}$$

Because the eigenvalues $\lambda _\ell \ne 1$ and $\left[ \begin{array}{c} u_\ell ^2\\ v_\ell ^2 \end{array}\right] (\ell =1,\ldots ,j)$ are linearly independent, we know that $c_\ell ^2=0$ $(\ell =1,\ldots ,j)$. As the vectors $v_\ell ^1 (\ell =1,\ldots ,i)$ are also linearly independent, we have $c_\ell ^1=0$ $(\ell =1,\ldots ,i)$. Thus, the Eq. (3.7) reduces to

$$\begin{aligned} \left[ \begin{array}{c@{\quad }c@{\quad }c} u_1 &{} \cdots &{} u_n\\ 0 &{} \cdots &{} 0 \end{array}\right] \left[ \begin{array}{c} c_1 \\ \vdots \\ c_n \end{array}\right] =\left[ \begin{array}{c} 0 \\ \vdots \\ 0 \end{array}\right] . \end{aligned}$$

Since $u_\ell$ $(\ell =1,\ldots ,n)$ are linearly independent, we have $c_\ell =0$ $(\ell =1,\ldots ,n)$. Therefore, the $n+i+j$ eigenvectors are linearly independent. $\square$

In the following, we study an upper bound of the degree of the minimal polynomial of the preconditioned matrix $\mathscr {P}_{SHSS}^{-1}\mathscr {A}$, which indicates the finite-step termination properties of the preconditioned Krylov subspace iteration methods with an optimal or Galerkin property [34] with respect to the SHSS preconditioner.

Theorem 3.3

Let the SHSS preconditioner $\mathscr {P}_{SHSS}$ be defined as in (2.3). Then the degree of the minimal polynomial of the preconditioned matrix $\mathscr {P}_{SHSS}^{-1}\mathscr {A}$ is at most $m+1$.

Proof

From (3.1) we know that the preconditioned matrix $\mathscr {P}_{SHSS}^{-1}\mathscr {A}$ is a block upper triangular matrix with the (1,1) block being an identity matrix, that is,

$$\begin{aligned} \mathscr {P}_{SHSS}^{-1}\mathscr {A}= \left[ \begin{array}{c@{\quad }c} I &{} \varTheta _2\\ 0 &{} \varTheta _1 \end{array}\right] , \end{aligned}$$

where $\varTheta _1=(C+\frac{1}{\alpha }BB^T)^{-1}(C+BA^{-1}B^T)$ and $\varTheta _2=A^{-1}B^T-\frac{1}{\alpha }B^T(C+\frac{1}{\alpha }BB^T)^{-1}(C+BA^{-1}B^T)$.

Let $\lambda _i$ ($i=1,\ \ldots ,\ m$) be the eigenvalues of the matrix $\varTheta _1$. Then the characteristic polynomial of the matrix $\mathscr {P}_{SHSS}^{-1}\mathscr {A}$ is

$$\begin{aligned} \varPhi _{\mathscr {P}_{SHSS}^{-1}\mathscr {A}}(\lambda ) =\det (\mathscr {P}_{SHSS}^{-1}\mathscr {A}-\lambda I) =(-1)^{m+n}(\lambda -1)^n\prod \limits _{i=1}^{m}(\lambda -\lambda _i). \end{aligned}$$

Let

$$\begin{aligned} \varPsi (\lambda ) =(\lambda -1)\prod \limits _{i=1}^{m}(\lambda -\lambda _i). \end{aligned}$$

Then

$$\begin{aligned} \varPsi (\mathscr {P}_{SHSS}^{-1}\mathscr {A})&=(\mathscr {P}_{SHSS}^{-1}\mathscr {A}-I)\prod \limits _{i=1}^{m}(\mathscr {P}_{SHSS}^{-1}\mathscr {A}-\lambda _i I)\\&=\left[ \begin{array}{c@{\quad }c} 0 &{} \varTheta _2\prod \limits _{i=1}^{m}(\varTheta _1-\lambda _i I)\\ 0 &{} (\varTheta _1-I)\prod \limits _{i=1}^{m}(\varTheta _1-\lambda _i I) \end{array}\right] . \end{aligned}$$

Since $\lambda _i$ ($i=1,\ldots ,m$) are also the eigenvalues of $\varTheta _1\in \mathbb {R}^{m\times m}$, by Hamilton–Cayley theorem we have $\prod \nolimits _{i=1}^{m}(\varTheta _1-\lambda _i I)=0$. Therefore, the degree of the minimal polynomial of the preconditioned matrix $\mathscr {P}_{SHSS}^{-1}\mathscr {A}$ is at most $m+1$. $\square$

According to Theorem 3.3, we easily see that when a Krylov subspace method with an optimal or Galerkin property, like GMRES, is applied to a preconditioned linear system with the coefficient matrix $\mathscr {P}_{SHSS}^{-1}\mathscr {A}$, it will converge to the exact solution of the linear system with the coefficient matrix $\mathscr {A}$ in $m+1$ or fewer iterations, in exact arithmetic.

4 Numerical experiments

In this section, we use numerical experiments to illustrate the effectiveness of the SHSS preconditioner $\mathscr {P}_{SHSS}$ for the generalized saddle point problem (1.1). To this end, we apply the GMRES iteration method incorporated with the SHSS preconditioner $\mathscr {P}_{SHSS}$, the HSS preconditioner $\mathscr {P}_{HSS}$ and no preconditioner (denoted by I), respectively, to solve the saddle point linear system (1.1).

The test generalized saddle point linear systems arise from the Stokes equation:

$$\begin{aligned} \left\{ \begin{array}{l@{\quad }l} -\nu \varDelta u+ \bigtriangledown p=\tilde{f}, &{} \mathrm{in}\,\, \Omega \\ \bigtriangledown \cdot u=\tilde{g},&{} \mathrm{in} \,\,\Omega \\ u=0, &{} \mathrm{on} \,\, \partial \Omega \\ \int _{\Omega }p(x)dx=0. \end{array}\right. \end{aligned}$$

(4.1)

where the velocity $u=(u_x^T,u_y^T)^T$ is a vector-valued function, the pressure p is a scalar function, $\varOmega =(0,1)\times (0,1)\subset \mathbb {R}^2, \partial \varOmega$ is the boundary of $\varOmega$, $\nu$ stands for the viscosity scalar, and $\varDelta$ is the componentwise Laplace operator. The test example is the “leaky” two dimensional lid-driven cavity problem in a square domain ($0\le x\le 1, 0\le y\le 1$). The boundary conditions are $u_x=u_y=0$ on the three fixed walls ($x=0$, $y=0$, $x=1$), and $u_x=1$, $u_y=0$ on the moving wall ($y=1$).

Here, we use the IFISS software package developed by Elman et al. [25] to generate discretizations of the Stokes equation (4.1). In the test problems, finite element subdivisions based on both uniform and stretched grids of square elements are adopted. The mixed finite element is the bilinear-pressure: $Q_1-P_0$ pair with local stabilization (the stabilization parameter is taken as 0.25) [35]. For the case of stretched grids, we use the default stretch factors provided by IFISS. The stretching is done in both the horizontal and vertical directions, which results in rather fine grids near the boundaries. Then we get the discretized linear system of the form

$$\begin{aligned} \left[ \begin{array}{c@{\quad }c} A &{} B^T \\ -B &{} C \end{array}\right] \left[ \begin{array}{c} u \\ p \end{array}\right] = \left[ \begin{array}{c} f \\ -g \end{array}\right] , \end{aligned}$$

where A is the discrete Laplace operator, $B^T$ is the discrete gradient operator, B is the discrete divergence operator, and C is the local stablization matrix. Four grids of increasing sizes (i.e., $8\times 8$, $16\times 16$, $32\times 32$, $64\times 64$) are studied here. In these test problems, we always take $\nu =1$.

We compare these different preconditioned GMRES methods from aspects of the number of iteration steps (denoted by ‘IT’) and elapsed CPU times in seconds (denoted by ‘CPU’). In actual implementations, the initial guess is chosen to be the zero vector and the iteration is terminated if the current iterations satisfy

$$\begin{aligned} \text {ERR} =\frac{\Vert b-\mathscr {A}\bar{u}^k\Vert _2}{\Vert b-\mathscr {A}\bar{u}^0\Vert _2} \le 10^{-6} \end{aligned}$$

or if the number of the prescribed iteration steps $k_{max}=1500$ is exceeded. All runs are performed in MATLAB 2010 on an Intel Core (4G RAM) Windows 7 system. For the SHSS preconditioner, we choose a practical parameter $\alpha$ by the formula (2.7). For the HSS preconditioner, we choose a quasi-optimal parameter $\alpha$ by the formula studied by Huang in [28]. In addition, we solve the linear subsystems in Algorithms 2.1 and 2.2 by means of sparse direct methods, that is, the sparse Cholesky factorization and the sparse incomplete Cholesky factorization. The coefficient matrices of the subsystems are factored once into triangular matrices. The resulting sparse triangular factors are used at each step for the forward and backward substitution. Here, the factorizations are done without reordering.

In Tables 1 and 2, we list the values of the parameter $\alpha$ in the preconditioners $\mathscr {P}_{HSS}$ and $\mathscr {P}_{SHSS}$, the numbers of iteration steps, the CPU times and the corresponding residuals of GMRES method incorporated with preconditioners I, $\mathscr {P}_{HSS}$ and $\mathscr {P}_{SHSS}$. Here, the Cholesky factorization is used as an exact solver for the linear subsystems. The difference of these two tables is that Table 1 lists the numerical results for Stokes problem with different uniform grids, while Table 2 lists those with stretched grids. From Tables 1 and 2, we can see that the GMRES method converges very slowly if no preconditioning technique is used. If the HSS preconditioner or the SHSS preconditioner is employed, the preconditioned GMRES method converges fast. Moreover, the SHSS preconditioned GMRES method uses much less number of iteration steps and CPU time than the HSS preconditioned GMRES method for all these different grids. This shows that our proposed SHSS preconditioner outperforms the HSS preconditioner in accelerating the convergence of the GMRES method for solving the Stokes problem.

Table 1 Numerical results for Stokes problem with different uniform grids by exact solvers

Table 2 Numerical results for Stokes problem with different stretched grids by exact solvers

In order to compare effects of the HSS and the SHSS preconditioners with respect to the parameter $\alpha$, we plot the number of iteration steps of the HSS preconditioned GMRES method with $\alpha$ from 0.0001 to 0.01 and that of the SHSS preconditioned GMRES method with $\alpha$ from 3 to 5 for Stokes problem with uniform $16\times 16$ grids in Fig. 1. Similarly, we plot the number of iteration steps of the HSS preconditioned GMRES method with $\alpha$ from 0.0001 to 0.01 and that of the SHSS preconditioned GMRES method with $\alpha$ from 50 to 80 for Stokes problem with stretched $16\times 16$ grids in Fig. 2. The varying interval of $\alpha$ is chosen according to the estimated values in Tables 1 and 2. In these figures, ‘*’ denotes the corresponding number of iteration steps listed in Tables 1 and 2. From Figs. 1 and 2, we can see that the SHSS preconditioner is not so sensitive to the parameter $\alpha$, while the parameter $\alpha$ influences the HSS preconditioner greatly. From this point, the SHSS preconditioner is more effective and practical than the HSS preconditioner.

Fig. 1

Number of iterations with $\alpha$ for uniform $16\times 16$ grids: HSS preconditioning (left) and SHSS preconditioning (right)

Fig. 2

Number of iterations with $\alpha$ for stretched $16\times 16$ grids: HSS preconditioning (left) and SHSS preconditioning (right)

To further discuss the effectiveness of the HSS and the SHSS preconditioners, we also use the incomplete Cholesky factorization as a direct solver for the subsystems and observe their influence on the convergence rate of the preconditioned GMRES methods. This is essentially the GMRES method incorporated with an inexact HSS preconditioner and an inexact SHSS preconditioner. In Tables 3 and 4, we list the numerical results of the HSS and the SHSS preconditioned GMRES methods with the inexact solver for the Stokes equation with $32\times 32$ uniform grids and stretched grids, respectively. From Tables 3 and 4, we can see that the HSS and the SHSS preconditioned GMRES methods with the inexact solver can also compute satisfactory numerical solutions. The numbers of iteration steps decrease with reduced drop tolerances for these preconditioned GMRES methods. For the HSS preconditioned GMRES method, the elapsed CPU times decrease with reduced drop tolerances for both uniform and stretched grids. On the other hand, for the SHSS preconditioned GMRES method, the elapsed CPU times slightly increase for the uniform grids and vary small for the stretched grids with reduced drop tolerances. Comparing the CPU times in Tables 3 and 4 with these in Tables 1 and 2, we find that the SHSS preconditioned GMRES method with the inexact solver costs less CPU times than that with the exact solver for the given four drop tolerances. Moreover, the SHSS preconditioned GMRES method with the exact and inexact solver both take much less CPU time than the HSS preconditioned GMRES method. Therefore, the SHSS preconditioned GMRES method is effective for solving the Stokes problem.

Table 3 Numerical results for Stokes problem with $32\times 32$ uniform grids by inexact solvers

Table 4 Numerical results for Stokes problem with $32\times 32$ stretched grids by inexact solvers

5 Conclusions

In this paper, based on the Hermitian and skew-Hermitian splitting (HSS) preconditioner and the principle that a preconditioner should be as close as possible to the coefficient matrix and also easy to solve, we propose a new simplified HSS (SHSS) preconditioner for the generalized saddle point problem (1.1). Theoretical analyses show that all eigenvalues of the SHSS preconditioned matrix are located in a positive real interval. We also study the eigenvector distribution of the SHSS preconditioned matrix. Moreover, the degree of the minimal polynomial of the preconditioned matrix $\mathscr {P}_{SHSS}^{-1}\mathscr {A}$ is at most $m+1$, which shows that the SHSS preconditioned GMRES method converges to the exact solution with the coefficient matrix $\mathscr {A}$ in $m+1$ or fewer iterations in exact arithmetic for solving the generalized saddle point problem (1.1). Numerical examples of a model Stokes equation are illustrated to show that our proposed SHSS preconditioner outperforms the HSS preconditioner in accelerating the convergence of the GMRES method. Although the SHSS preconditioner can accelerate the convergence of the GMRES method greatly, it may not have the optimal property, i.e., the iteration number of the SHSS preconditioned GMRES method depends on the problem size. How to improve the SHSS preconditioner and analyze an optimal parameter $\alpha$ should be further studied in depth.