On the preconditioned MINRES method for solving singular linear systems

Abstract

Recently, Sugihara et al. (Numer Linear Algebra Appl 27:1-25, 2020) studied the right preconditioned MINRES method for solving symmetric singular linear systems. In this paper, we discuss the left and right preconditioned MINRES method for symmetric singular linear systems with singular preconditioners. The convergence of the preconditioned MINRES method are proved under the condition of proper splitting. Numerical results demonstrate the effectiveness of the preconditioned MINRES with singular preconditioners.

1 Introduction

Consider the following large sparse system of linear equations:

$$\begin{aligned} {\mathscr {A}}x=b, \end{aligned}$$

(1)

where ${\mathscr {A}}\in {\mathbb {R}}^{n\times n}$ is symmetric and singular, i.e., $rank({\mathscr {A}})=m<n$, $x,b\in {\mathbb {R}}^{n}$. ${\mathscr {R}}({\mathscr {A}})$ and ${\mathscr {N}}({\mathscr {A}})$ denote the range and the null space of ${\mathscr {A}}$, respectively. In this paper, we discuss the situation that (1) is consistent, i.e., $b\in {\mathscr {R}}({\mathscr {A}})$.

For the solution of the singular linear systems, Brown and Walker (1997) firstly studied the preconditioned GMRES method. Hayami et al. (2010) and Morikuni and Hayami (2015) discussed the GMRES method for least squares problems. To solve a symmetric linear system, one often use minimum residual (MINRES) method (Paige and Saunders 1975), which is mathematically equivalent to the generalized minimal residual (GMRES) method (Saad and Schultz 1986; Saad 2003; William 2015). For general singular linear systems, Hayami and Sugihara (2011) provided a geometrical view of Krylov subspace methods applied to singular systems by decomposing the algorithm into the ${\mathscr {R}}({\mathscr {A}})$ component and the ${\mathscr {R}}({\mathscr {A}})^{\perp }$ component. For solving symmetric singular linear systems, Sugihara et al. (2020) discussed right preconditioned MINRES method with symmetric positive definite (SPD) preconditioner ${\mathscr {M}}$. When the singular system is consistent and the initial guess $x^{(0)} \in {{\mathscr {R}}({\mathscr {A}})}$, then the right preconditioned MINRES algorithm can be decomposed into the ${\mathscr {R}}({\mathscr {A}})$ component, and the ${\mathscr {R}}({\mathscr {A}})^{\perp _{{\mathscr {M}}^{-1}}}$ component is zero, here ${\mathscr {R}}({\mathscr {A}})^{\perp _{{\mathscr {M}}^{-1}}}$ is the orthogonal complement of ${\mathscr {R}}({\mathscr {A}})$ with respect to the inner product $(,)_{{\mathscr {M}}^{-1}}$.

Generally speaking, when we look for a preconditioner for solving a linear system, we often hope it can approximate the coefficient matrix well. So, when the linear system is nonsingular, we choose a nonsingular matrix as the preconditioner. When the linear system is singular, then taking a singular matrix as the preconditioner may be more reasonable. In Zhang (2010), Zhang and Shen (2013), Zhang and Wei (2010), we studied singular preconditioners for solving singular linear systems. In this paper, we discuss the left and right preconditioned MINRES method for solving (1) with symmetric positive semi-definite (SPSD) preconditioners.

The rest of this paper is organized as follows. In Sect. 2, we present the left preconditioned MINRES algorithm. In Sect. 3, we give the convergence analysis for left preconditioned MINRES method. In Sect. 4, we present the right preconditioned MINRES algorithm. In Sect. 5, we give the convergence analysis for right preconditioned MINRES method. Numerical experiments are presented in Sect. 6. We give two numerical examples to illustrate the effectiveness of MINRES with singular preconditioners. Finally, some conclusions are drawn in Sect. 7.

2 Left preconditioned MINRES method

In this section, we study the left preconditioned MINRES method for solving (1) with singular preconditioners. First we give a brief introduction for MINRES (Paige and Saunders 1975). Let $x^{(0)}$ be the initial guess and $r^{(0)}=b-{\mathscr {A}}x^{(0)}$ be the initial residual. MINRES is an iterative method that finds an approximate solution $x^{(k)}$ which satisfies

$$\begin{aligned} x^{(k)}=\mathop {argmin}\limits _{x\in x^{(0)}+K_{k}({\mathscr {A}},r^{(0)})}||b-{\mathscr {A}}x||_{2}, \end{aligned}$$

where $K_{k}({\mathscr {A}},r^{(0)})=span(r^{(0)},{\mathscr {A}}r^{(0)},...,{\mathscr {A}}^{k-1}r^{(0)})$ is a Krylov subspace.

Definition 2.1

(Lee et al. 2006) For any $x, y\in {\mathbb {R}}^{n}$, we define $(x,y)_{S}=y^{T}Sx$, where S is SPSD. Then we can define a semi-norm by follows:

$$\begin{aligned} ||x||_{S}=\sqrt{(x,x)_{S}}. \end{aligned}$$

(2)

Definition 2.2

(Berman and Plemmons 1974) The splitting ${\mathscr {A}}={\mathscr {M}}-{\mathscr {N}}$ is called a proper splitting of ${\mathscr {A}}$, if ${\mathscr {R}}({\mathscr {A}})={\mathscr {R}}({\mathscr {M}}), {\mathscr {N}}({\mathscr {A}})={\mathscr {N}}({\mathscr {M}})$.

We assume that the preconditioner ${\mathscr {M}}$ is SPSD and ${\mathscr {A}}={\mathscr {M}}-{\mathscr {N}}$ is a proper splitting. Let ${\mathscr {M}}^{+}$ be the Moore-Penrose inverse of ${\mathscr {M}}$, that is

$$\begin{aligned} {\mathscr {M}}^{+}{\mathscr {M}}{\mathscr {M}}^{+}={\mathscr {M}}^{+},{\mathscr {M}}{\mathscr {M}}^{+}{\mathscr {M}}={\mathscr {M}}, ({\mathscr {M}}{\mathscr {M}}^{+})^{T}={\mathscr {M}}{\mathscr {M}}^{+},({\mathscr {M}}^{+}{\mathscr {M}})^{T}={\mathscr {M}}^{+}{\mathscr {M}}, \end{aligned}$$

where $(\cdot )^{T}$ denotes the transpose of a matrix or a vector.

With the preconditioner ${\mathscr {M}}$, we consider to solve the following preconditioned system instead of the original system (1).

$$\begin{aligned} {\mathscr {M}}^{+}{\mathscr {A}}x={\mathscr {M}}^{+}b. \end{aligned}$$

(3)

Notice when ${\mathscr {A}}={\mathscr {M}}-{\mathscr {N}}$ is a proper splitting, then (1) and (3) are equivalent, that is, the solution sets of (1) and (3) are identical (cf. Zhang (2010)).

It is known that ${\mathscr {M}}{\mathscr {M}}^{+}$ is the orthogonal projection onto ${\mathscr {R}}({\mathscr {M}})$ and notice ${\mathscr {R}}({\mathscr {A}})={\mathscr {R}}({\mathscr {M}})$, then ${\mathscr {M}}{\mathscr {M}}^{+}{\mathscr {A}}={\mathscr {A}}$. Since ${\mathscr {A}}$ and ${\mathscr {M}}$ are both symmetric, it holds $({\mathscr {M}}^{+}{\mathscr {A}}x,y)_{{\mathscr {M}}}=y^{T}{\mathscr {A}}x=(x,{\mathscr {M}}^{+}{\mathscr {A}}y)_{{\mathscr {M}}}$. Thus ${\mathscr {M}}^{+}{\mathscr {A}}$ is self-adjoint with respect to $(,)_{{\mathscr {M}}}$, so we can apply MINRES if the semi-norm in Definition 2.1 is taken with respect to ${\mathscr {M}}$. Hence, we can find an approximate solution $x^{(k)}$, which satisfies

$$\begin{aligned} x^{(k)}=\mathop {argmin}\limits _{x\in x^{(0)}+K_{k}({\mathscr {M}}^{+}{\mathscr {A}}, {\mathscr {M}}^{+}r^{(0)})}||{\mathscr {M}}^{+}b-{\mathscr {M}}^{+}{\mathscr {A}}x||_{{\mathscr {M}}}. \end{aligned}$$

We show the left preconditioned MINRES algorithm as follows.

3 Convergence analysis of left preconditioned MINRES method

In this section, we discuss the convergence properties of the left preconditioned MINRES with the preconditioner ${\mathscr {M}}$.

Theorem 3.1

Denote ${\mathscr {R}}({\mathscr {A}})^{\perp }|_{S}=\{z|(z,y)_{S}=0,\forall y\in {{\mathscr {R}}{({\mathscr {A}})}}\}$. If S is a SPSD matrix, ${\mathscr {A}}=S-(S-{\mathscr {A}})$ is a proper splitting, then it holds ${\mathscr {R}}({\mathscr {A}})^{\perp }|_{S}={\mathscr {N}}(S)$.

Proof

First, for any $z\in {{\mathscr {N}}(S)}$, $Sz=0$ holds. Hence, for any $y\in {{\mathscr {R}}{({\mathscr {A}})}}$, $y^{T}Sz=0$, then $z\in {\mathscr {R}}({\mathscr {A}})^{\perp }|_{S}$. So ${\mathscr {N}}(S)\subseteqq {\mathscr {R}}({\mathscr {A}})^{\perp }|_{S}$.

Next, we will prove ${\mathscr {R}}({\mathscr {A}})^{\perp }|_{S}\subseteqq {\mathscr {N}}(S)$. Since S is a SPSD matrix, it holds ${\mathbb {R}}^{n}={\mathscr {R}}(S)\overset{\perp }{\oplus } {\mathscr {N}}(S)$. So there exist $x_{1}\in {\mathscr {N}}(S)$ and $y_{1}\in {\mathscr {R}}(S)$ such that $z=x_{1}+y_{1}$ holds. Therefore, for any $z\in {{\mathscr {R}}({\mathscr {A}})^{\perp }|_{S}}$ and any $y\in {{\mathscr {R}}{({\mathscr {A}})}}$, it holds

$$\begin{aligned} 0 =(z,y)_{S} =y^{T}Sz =y^{T}S(x_{1}+y_{1}) =y^{T}Sx_{1}+y^{T}Sy_{1} =y^{T}Sy_{1}. \end{aligned}$$

(4)

Noticing that $S=U{\hat{\Sigma }}U^{T}$, where ${\hat{\Sigma }}=diag({\hat{\sigma }}_{1},...,{\hat{\sigma }}_{m},0,...,0)\in {\mathbb {R}^{n\times n}}$, $\hat{\sigma }_{i}>0, i=1,2,...,m$ and U is an orthogonal matrix. S can be decomposed as

$$\begin{aligned} S=S^{\frac{1}{2}}S^{\frac{1}{2}} \end{aligned}$$

(5)

in which

$$\begin{aligned} S^{\frac{1}{2}}=U{\hat{\Sigma }}^{\frac{1}{2}}U^{T},\quad {\hat{\Sigma }}^{\frac{1}{2}}=diag({\hat{\sigma }}_{1}^{\frac{1}{2}},...,{\hat{\sigma }}_{m}^{\frac{1}{2}},0,...,0)\in {{\mathbb {R}}^{n\times n}}. \end{aligned}$$

Since ${\hat{\sigma }}_{i}^{\frac{1}{2}}>0$, $i=1,2,...,m$, it holds $S^{\frac{1}{2}}$ is SPSD. It is also easy to see ${\mathscr {N}}(S)={\mathscr {N}}(S^{\frac{1}{2}})$.

Since ${\mathscr {A}}=S-(S-{\mathscr {A}})$ is a proper splitting, by Definition 2.2 we have ${\mathscr {R}}({\mathscr {A}})={\mathscr {R}}(S),{\mathscr {N}}({\mathscr {A}})={\mathscr {N}}(S)$. Then we let $y=y_{1}$ in (4), it holds

$$\begin{aligned} 0=y_{1}^{T}Sy_{1}=y_{1}^{T}S^{\frac{1}{2}}S^{\frac{1}{2}}y_{1}=||S^{\frac{1}{2}}y_{1}||^{2}_{2}. \end{aligned}$$

(6)

Since $y_{1}\in {\mathscr {R}}(S)$ and ${\mathscr {N}}(S)={\mathscr {N}}(S^{\frac{1}{2}})$, then $y_{1}=0$. It follows that $z=x_{1}\in {\mathscr {N}}(S)$. So ${\mathscr {R}}({\mathscr {A}})^{\perp }|_{S}\subseteqq {\mathscr {N}}(S)$. Hence, ${\mathscr {R}}({\mathscr {A}})^{\perp }|_{S}={\mathscr {N}}(S)$ holds, which finishes the proof. $\square$

Lemma 3.2

(Saad and Schultz 1986) If ${\mathscr {A}}\in {{\mathbb {R}}^{n\times n}}$ is nonsingular, then GMRES terminates in at most n steps.

Theorem 3.3

Suppose ${\mathscr {M}}$ is a SPSD matrix and ${\mathscr {A}}={\mathscr {M}}-{\mathscr {N}}$ is a proper splitting, $rank({\mathscr {A}})=m$. Then the left preconditioned MINRES determines a solution x of

$$\begin{aligned} \mathop {min}\limits _{x\in {\mathbb {R}}^{n}}||{\mathscr {M}}^{+}b-{\mathscr {M}}^{+}{\mathscr {A}}x||_{{\mathscr {M}}} \end{aligned}$$

without breakdown, and terminates in at most m steps for all $b\in {\mathscr {R}}({\mathscr {A}})$ and all initial guess $x^{(0)}\in {{\mathscr {R}}({\mathscr {A}})}$.

Proof

Since ${\mathscr {M}}$ is SPSD, it holds ${\mathscr {M}}=V{\Sigma }V^{T}$, where $\Sigma =diag(\sigma _{1},...,\sigma _{m},0,...,0)\in {{\mathbb {R}}^{n\times n}}$, $\sigma _{i}>0, i=1,2,...,m$ and V is an orthogonal matrix. Then we have ${\mathscr {M}}^{+}=V{\Sigma }^{+}V^{T}$, ${\Sigma }^{+}=diag(\sigma _{1}^{-1},...,\sigma _{m}^{-1},0,...,0)$. ${\mathscr {M}}$ and ${\mathscr {M}}^{+}$ can be decomposed as

$$\begin{aligned} {\mathscr {M}}={\mathscr {M}}^{\frac{1}{2}}{\mathscr {M}}^{\frac{1}{2}}, {\mathscr {M}}^{+}={\mathscr {M}}^{+\frac{1}{2}}{\mathscr {M}}^{+\frac{1}{2}} \end{aligned}$$

(7)

in which

$$\begin{aligned} {\mathscr {M}}^{\frac{1}{2}}=V{\Sigma }^{\frac{1}{2}}V^{T},\quad {\Sigma }^{\frac{1}{2}}=diag(\sigma _{1}^{\frac{1}{2}},...,\sigma _{m}^{\frac{1}{2}},0,...,0) \\ {\mathscr {M}}^{+\frac{1}{2}}=V{\Sigma }^{+\frac{1}{2}}V^{T},\quad {\Sigma }^{+\frac{1}{2}}=diag(\sigma _{1}^{-\frac{1}{2}},...,\sigma _{m}^{-\frac{1}{2}},0,...,0). \end{aligned}$$

Since $\sigma _{i}^{\frac{1}{2}}>0$, $\sigma _{i}^{-\frac{1}{2}}>0$, $i=1,2,...,m$, we know ${\mathscr {M}}^{+\frac{1}{2}}$ and ${\mathscr {M}}^{\frac{1}{2}}$ are SPSD. Since ${\mathscr {A}}={\mathscr {M}}-{\mathscr {N}}$ is a proper splitting, then it holds

$$\begin{aligned} {\mathscr {N}}({\mathscr {M}}^{+})={\mathscr {N}}({\mathscr {M}}^{+\frac{1}{2}})={\mathscr {N}}({\mathscr {M}})= {\mathscr {N}}({\mathscr {M}}^{\frac{1}{2}})={\mathscr {N}}({\mathscr {A}}) \end{aligned}$$

(8)

$$\begin{aligned} {\mathscr {R}}({\mathscr {M}}^{+})={\mathscr {R}}({\mathscr {M}}^{+\frac{1}{2}})={\mathscr {R}}({\mathscr {M}})= {\mathscr {R}}({\mathscr {M}}^{\frac{1}{2}})={\mathscr {R}}({\mathscr {A}}) \end{aligned}$$

(9)

and

$$\begin{aligned} {\mathscr {M}}^{+\frac{1}{2}}=({\mathscr {M}}^{\frac{1}{2}})^{+}. \end{aligned}$$

(10)

Let $q_{1}, q_{2},\text {...}, q_{m}$ be the orthonormal basis of ${\mathscr {R}}({\mathscr {A}})$ with respect to the Euclidean inner product, $q_{m+1}, q_{m+2},..., q_{n}$ be the orthonormal basis of ${\mathscr {N}}({\mathscr {A}})$ with respect to the Euclidean inner product .

Let

$$\begin{aligned} \hat{q}_{i}={\mathscr {M}}^{+\frac{1}{2}}q_{i},i=1,2,\text {...},m. \end{aligned}$$

(11)

We define the matrices $Q_{1}, Q_{2}, \hat{Q}_{1}, \hat{Q}$ as follows:

$$\begin{aligned} Q_{1}:=[ q_{1}, q_{2},\text {...}, q_{m}]\in {\mathbb {R}}^{n\times m} \\ Q_{2}:=[ q_{m+1}, q_{m+2},\text {...}, q_{n}]\in {\mathbb {R}}^{n\times (n-m)} \\ \hat{Q}_{1}:=[\hat{q}_{1},\hat{q}_{2},\text {...},\hat{q}_{m}]\in {\mathbb {R}}^{n\times m} \\ {\hat{Q}}:=[\hat{Q}_1, Q_2]\in {\mathbb {R}}^{n\times n}. \end{aligned}$$

We demonstrate ${\hat{q}}_{1},{\hat{q}}_{2},\text {...},{\hat{q}}_{m}$ are the orthonormal basis of ${\mathscr {R}}({\mathscr {A}})$ with respect to $(,)_{{\mathscr {M}}}$ as follows.

From (11), it holds ${\hat{q}}_{i}\in {\mathscr {R}}({\mathscr {M}}^{+\frac{1}{2}})$, $i=1,2,...,m$ and

$$\begin{aligned} {\hat{Q}}_{1}={\mathscr {M}}^{+\frac{1}{2}} Q_{1} \end{aligned}$$

(12)

then we have ${\mathscr {M}}^{\frac{1}{2}}{\hat{Q}}_{1}={\mathscr {M}}^{\frac{1}{2}}{\mathscr {M}}^{+\frac{1}{2}}Q_{1}$. Noticing that ${\mathscr {R}}( Q_{1})={\mathscr {R}}({\mathscr {A}})$, then from (9), it holds ${\mathscr {R}}( Q_{1})={\mathscr {R}}({\mathscr {M}}^{\frac{1}{2}})$. Since ${\mathscr {M}}^{\frac{1}{2}}{\mathscr {M}}^{+\frac{1}{2}}$ is the projection onto ${\mathscr {R}}({\mathscr {M}}^{\frac{1}{2}})$, it holds ${\mathscr {M}}^{\frac{1}{2}}{\mathscr {M}}^{+\frac{1}{2}} Q_{1}= Q_{1}$. Hence,

$$\begin{aligned} Q_{1}={\mathscr {M}}^{\frac{1}{2}}{\hat{Q}}_{1}. \end{aligned}$$

(13)

By (12) and (13), we have $rank({\hat{Q}}_{1})=rank(Q_{1})=m$. This implies ${\hat{q}}_{1},{\hat{q}}_{2},\text {...},{\hat{q}}_{m}$ are the basis of ${\mathscr {R}}({\mathscr {A}})$ and ${\hat{Q}}$ is nonsingular.

Since

$$\begin{aligned} (\hat{q}_{i},\hat{q}_{i})_{{\mathscr {M}}}=({\mathscr {M}}^{+\frac{1}{2}} q_{i})^{T}{\mathscr {M}}{\mathscr {M}}^{+\frac{1}{2}} q_{i}= ({\mathscr {M}}^{\frac{1}{2}}{\mathscr {M}}^{+\frac{1}{2}} q_{i})^{T}{\mathscr {M}}^{\frac{1}{2}}{\mathscr {M}}^{+\frac{1}{2}}q_{i}=( q_{i})^{T} q_{i}=1 \end{aligned}$$

and in the same way, when $i\not =j$, $(\hat{q}_{i},\hat{q}_{j})_{{\mathscr {M}}}=0$, $i, j=1,2,\text {...},m$. Then we have

$$\begin{aligned} \left\{ \begin{aligned}\;&(\hat{q}_{i},\hat{q}_{i})_{{\mathscr {M}}}=1\\&(\hat{q}_{i},\hat{q}_{j})_{{\mathscr {M}}}=0,i\not =j. \end{aligned} \right. \end{aligned}$$

(14)

Therefore, ${\hat{q}}_{1},{\hat{q}}_{2},\text {...},{\hat{q}}_{m}$ are the orthonormal basis of ${\mathscr {R}}({\mathscr {A}})$ with respect to $(,)_{{\mathscr {M}}}$ .

From (14), we obtain

$$\begin{aligned} \hat{Q}_{1}^{T}{\mathscr {M}}\hat{Q}_{1}=I_{m}. \end{aligned}$$

(15)

Evidently,

$$\begin{aligned} \hat{Q}_{1}^{T}{\mathscr {M}}\hat{Q}_{1}\hat{Q}_{1}^{T}{\mathscr {M}}\hat{Q}_{1}=I_{m}. \end{aligned}$$

(16)

By (15) and (16), it holds

$$\begin{aligned} \hat{Q}_{1}^{T}({\mathscr {M}}\hat{Q}_{1}\hat{Q}_{1}^{T}{\mathscr {M}}-{\mathscr {M}})\hat{Q}_{1}=0. \end{aligned}$$

(17)

From (8) and noticing ${\mathscr {R}}(Q_{2})={\mathscr {N}}({\mathscr {A}})$, we have ${\mathscr {M}}Q_{2}=0$. So it holds

$$\begin{aligned} \begin{aligned}&\hat{Q}^{T}({\mathscr {M}}\hat{Q}_{1}\hat{Q}_{1}^{T}{\mathscr {M}}-{\mathscr {M}})\hat{Q}\\&=[\hat{Q}_{1},Q_{2}]^{T}({\mathscr {M}}\hat{Q}_{1}\hat{Q}_{1}^{T}{\mathscr {M}}-{\mathscr {M}})[\hat{Q}_{1},Q_{2}]\\&=\begin{bmatrix} \hat{Q}^{T}_{1}({\mathscr {M}}\hat{Q}_{1}\hat{Q}_{1}^{T}{\mathscr {M}}-{\mathscr {M}})\hat{Q}_{1} &{} \hat{Q}^{T}_{1}({\mathscr {M}}\hat{Q}_{1}\hat{Q}_{1}^{T}{\mathscr {M}}-{\mathscr {M}})Q_{2} \\ Q_{2}^{T}({\mathscr {M}}\hat{Q}_{1}\hat{Q}_{1}^{T}{\mathscr {M}}-{\mathscr {M}})\hat{Q}_{1} &{} Q_{2}^{T}({\mathscr {M}}\hat{Q}_{1}\hat{Q}_{1}^{T}{\mathscr {M}}-{\mathscr {M}})Q_{2} \end{bmatrix}\\&=0\\. \end{aligned} \end{aligned}$$

(18)

Because ${\hat{Q}}$ is nonsingular, we obtain

$$\begin{aligned} {\mathscr {M}}\hat{Q}_{1}\hat{Q}_{1}^{T}{\mathscr {M}}={\mathscr {M}}. \end{aligned}$$

(19)

Noticing ${\mathscr {M}}^{+}{\mathscr {M}}\hat{Q}_{1}=\hat{Q}_{1}$, then it holds

$$\begin{aligned} \hat{Q}_{1}\hat{Q}_{1}^{T}{\mathscr {M}}=\mathscr {M}^{+}{\mathscr {M}}. \end{aligned}$$

(20)

Let $\hat{r}={\mathscr {M}}^{+}b-{\mathscr {M}}^{+}{\mathscr {A}}x$, $\hat{r}\in {\mathscr {R}}({\mathscr {A}})$ holds. Therefore, there exists $\hat{r}_{1}\in {\mathbb {R}}^{m}$ such that

$$\begin{aligned} \hat{r}={\hat{Q}}_{1}\hat{r}_{1}. \end{aligned}$$

(21)

Together with (15), it holds

$$\begin{aligned} ||\hat{r}||_{{\mathscr {M}}}=\sqrt{\hat{r}^{T}{\mathscr {M}}\hat{r}}=\sqrt{\hat{r}_{1}^{T}\hat{Q}_{1}^{T}{\mathscr {M}}\hat{Q}_{1}\hat{r}_{1}} =||\hat{r}_{1}||_{2}. \end{aligned}$$

(22)

By (20) and (21), we have

$$\begin{aligned} \begin{aligned} \hat{r}_{1}&=\hat{Q}^{T}_{1}{\mathscr {M}}\hat{Q}_{1}\hat{r}_{1}\\&=\hat{Q}^{T}_{1}{\mathscr {M}}\hat{r}\\&=\hat{Q}^{T}_{1}{\mathscr {M}}({\mathscr {M}}^{+}b-{\mathscr {M}}^{+}{\mathscr {A}}x)\\&=\hat{Q}^{T}_{1}{\mathscr {M}}{\mathscr {M}}^{+}b-\hat{Q}^{T}_{1}{\mathscr {M}}{\mathscr {M}}^{+}{\mathscr {A}}x\\&=\hat{Q}^{T}_{1}b-\hat{Q}^{T}_{1}({\mathscr {M}}{\mathscr {M}}^{+}{\mathscr {A}})^{T}x\\&=\hat{Q}^{T}_{1}b-\hat{Q}^{T}_{1}{\mathscr {A}}{\mathscr {M}}^{+}{\mathscr {M}}x\\&=\hat{Q}^{T}_{1}b-\hat{Q}^{T}_{1}{\mathscr {A}}\hat{Q}_{1}\hat{Q}^{T}_{1}{\mathscr {M}}x\\. \end{aligned} \end{aligned}$$

(23)

Let

$$\begin{aligned} \hat{b}_{1}:=\hat{Q}^{T}_{1}b,\quad \hat{z}_{1}:=\hat{Q}^{T}_{1}{\mathscr {M}}x,\quad \hat{A}_{1}:=\hat{Q}^{T}_1{\mathscr {A}}\hat{Q}_{1}. \end{aligned}$$

Then

$$\begin{aligned} \hat{r}_{1}=\hat{b}_{1}-\hat{A}_{1}\hat{z}_{1}. \end{aligned}$$

(24)

Noticing ${\mathscr {A}} Q_{2}=0$, it holds

$$\begin{aligned} \begin{aligned} \hat{Q}^{T}{\mathscr {A}}\hat{Q}&=[\hat{Q}_{1},Q_{2}]^{T}{\mathscr {A}}[\hat{Q}_{1},Q_{2}]\\&=\begin{bmatrix} \hat{Q}^{T}_{1}{\mathscr {A}}\hat{Q}_{1} &{} \hat{Q}^{T}_{1}{\mathscr {A}}Q_{2} \\ Q_{2}^{T}{\mathscr {A}}\hat{Q}_{1} &{} Q_{2}^{T}{\mathscr {A}}Q_{2} \end{bmatrix}\\&=\begin{bmatrix} \hat{Q}^{T}_{1}{\mathscr {A}}\hat{Q}_{1} &{} 0 \\ 0 &{} 0 \end{bmatrix}\\ \end{aligned} \end{aligned}$$

(25)

Since $rank({\mathscr {A}})=m$ and $\hat{Q}$ is nonsingular, then $rank(\hat{Q}^{T}{\mathscr {A}}\hat{Q})=m$. Together with (25), we have $rank(\hat{A}_{1})=rank(\hat{Q}^{T}{\mathscr {A}}\hat{Q})=m$. That is, $\hat{A}_{1}$ is nonsingular.

By (22) and (24), we have

$$\begin{aligned} ||{\mathscr {M}}^{+}b-{\mathscr {M}}^{+}{\mathscr {A}}x||_{{\mathscr {M}}}=||\hat{r}_{1}||_{2}=||\hat{b}_{1}-\hat{A}_{1}\hat{z}_{1}||_{2}. \end{aligned}$$

For solving a symmetric linear system, GMRES is mathematical equivalent to MINRES. Since GMRES determines a least squares solution without breakdown for nonsingular systems (Saad and Schultz 1986). So MINRES determines a least squares solution without breakdown for the symmetric nonsingular system $\hat{A}_{1}\hat{z}_{1}=\hat{b}_{1}$. By Lemma 3.2, MINRES converges to the solution of

$$\begin{aligned} \mathop {min}\limits _{\hat{z}_{1}\in {\mathbb {R}}^{m}}||\hat{b}_{1}-\hat{A}_{1}\hat{z}_{1}||_{2} \end{aligned}$$

in at most m iterations.

Therefore, the left preconditioned MINRES determines the solution $x^{(k)}$ of

$$\begin{aligned} \mathop {min}\limits _{x\in {\mathbb {R}}^{n}}||{\mathscr {M}}^{+}b-{\mathscr {M}}^{+}{\mathscr {A}}x||_{{\mathscr {M}}} \end{aligned}$$

without breakdown for all $b\in {\mathscr {R}}({\mathscr {A}})$ and all $x^{(0)}\in { {\mathscr {R}}({\mathscr {A}})}$, and terminates in at most m steps, which finishes the proof. $\square$

Since both b and $x^{(0)}$ are in ${\mathscr {R}}({\mathscr {A}})$, then we can decompose the left preconditioned MINRES (Algorithm 1) into the ${\mathscr {R}}({\mathscr {A}})$ component, and ${\mathscr {R}}({\mathscr {A}})^{\perp }|_{\mathscr {M}^{+}}$ component is zero, see the following decomposed left preconditioned MINRES algorithm (Algorithm 2). Algorithm 2 is equivalent to MINRES applied to ${\hat{A}}_{1}{\hat{z}}_{1}={\hat{b}}_{1}$, and then compute $x={\hat{Q}}_{1}{\hat{z}}_{1}$.

Notice that if the conditions in Theorem 3.3 are satisfied, then $\hat{z}^{(j)}_{1}$ converges to $\hat{A}^{-1}_{1}\hat{Q}^{T}_{1}b$ and $x^{(j)}$ converges to $\hat{Q}_{1}\hat{A}^{-1}_{1}\hat{Q}^{T}_{1}b$.

When the linear system (1) is a SPSD system, we now estimate the convergence rate of left preconditioned MINRES algorithm (Algorithm 1), or equivalently Algorithm 2. Recalling the proof for Theorem 3.3, $\hat{A}_{1}=\hat{Q}^{T}_1{\mathscr {A}}\hat{Q}_{1}$ is nonsingular. Then $\hat{A}_{1}$ is SPD since ${\mathscr {A}}$ is SPSD. So there exist a orthogonal matrix $\Phi$ and a diagonal matrix $\Theta =diag(\theta _1,\theta _2,\cdot \cdot \cdot ,\theta _m)$ with $0<\theta _1\le \theta _2\le \cdot \cdot \cdot \le \theta _m$ such that $\hat{A}_{1}=\Phi \Theta \Phi ^T$.

Theorem 3.4

Assume the conditions in Theorem 3.3 are satisfied and ${\mathscr {A}}$ is SPSD. Then the residual norm $||\hat{r}^{(j)}_{1}||_{2}=||\hat{b}_{1}-\hat{A}_{1}\hat{z}^{(j)}_{1}||_{2}$ achieved by the jth step of Algorithm 2 satisfies the inequality

$$\begin{aligned} ||\hat{r}^{(j)}_{1}||_{2}\le \left( 1-\frac{\theta ^2_1}{\theta ^2_m}\right) ^{\frac{j}{2}}||\hat{r}^{(0)}_{1}||_{2}. \end{aligned}$$

(26)

Proof

Let ${\mathbb {P}}_j$ be the polynomial set of degree not exceeding j that satisfies the constraint ${\mathbb {P}}_j(0)=1$. It is known that it holds

$$\begin{aligned} ||\hat{r}^{(j)}_{1}||_{2}=\mathop {min}\limits _{p\in {\mathbb {P}}_j}||p(\hat{A}_{1})\hat{r}^{(0)}_{1}||_{2}\le \mathop {min}\limits _{p\in {\mathbb {P}}_j} ||p(\hat{A}_{1})||_{2}||\hat{r}^{(0)}_{1}||_{2}. \end{aligned}$$

(27)

Let $p_1(\mu )=1+\alpha \mu \in {\mathbb {P}}_1$. Then $p^j_1(\mu )\in {\mathbb {P}}_j$. Obviously it holds

$$\begin{aligned} \mathop {min}\limits _{p\in {\mathbb {P}}_j} ||p(\hat{A}_{1})||_{2}\le ||p^j_1(\hat{A}_{1})||_{2}\le ||p_1(\hat{A}_{1})||^j_{2}. \end{aligned}$$

(28)

Notice

$$\begin{aligned} ||p_1(\hat{A}_{1})||^2_{2}=\mathop {max}\limits _{0\ne \varphi \in {\mathbb {R}}^{n}}\frac{\varphi ^T(I+\alpha \hat{A}_{1})^2\varphi }{\varphi ^T\varphi } =\mathop {max}\limits _{0\ne \varphi \in {\mathbb {R}}^{n}}\left( 1+2\alpha \frac{\varphi ^T\hat{A}_{1}\varphi }{\varphi ^T\varphi }+\alpha ^2\frac{\varphi ^T\hat{A}_{1}^2\varphi }{\varphi ^T\varphi }\right) \end{aligned}$$

and for any $\alpha <0$ it holds

$$\begin{aligned} 2\alpha \frac{\varphi ^T\hat{A}_{1}\varphi }{\varphi ^T\varphi }\le 2\alpha \theta _1,~~\alpha ^2\frac{\varphi ^T\hat{A}_{1}^2\varphi }{\varphi ^T\varphi }\le \alpha ^2\theta ^2_m. \end{aligned}$$

Then

$$\begin{aligned} ||p_1(\hat{A}_{1})||^2_{2}\le 1+2\alpha \theta _1+\alpha ^2\theta ^2_m \end{aligned}$$

Take $\alpha =-\frac{\theta _1}{\theta ^2_m}$, then we have

$$\begin{aligned} ||p_1(\hat{A}_{1})||^2_{2}\le 1-\frac{\theta ^2_1}{\theta ^2_m} \end{aligned}$$

(29)

Together with (27), (28) and (29) we obtain (26), which finishes the proof. $\square$

4 Right preconditioned MINRES method

Using the preconditioner ${\mathscr {M}}$ defined in Sect. 2, we consider to solve the following system of linear equations.

$$\begin{aligned} \left\{ \begin{aligned}\; {\mathscr {A}}{\mathscr {M}}^{+}z=b\\ x={\mathscr {M}}^{+}z \end{aligned} \right. \end{aligned}$$

(30)

Making use of Definition 2.1, we define a semi-norm

$$\begin{aligned} ||x||_{{\mathscr {M}}^{+}}=\sqrt{(x,x)_{{\mathscr {M}}^{+}}}. \end{aligned}$$

(31)

Notice $({\mathscr {A}}{\mathscr {M}}^{+}x,y)_{{\mathscr {M}}^{+}}=y^{T}{\mathscr {M}}^{+}{\mathscr {A}}{\mathscr {M}}^{+}x= (x,{\mathscr {A}}{\mathscr {M}}^{+}y)_{{\mathscr {M}}^{+}}$, which means ${\mathscr {A}}{\mathscr {M}}^{+}$ is self-adjoint with respect to $(,)_{{\mathscr {M}}^{+}}$. We apply MINRES to solve (30) with the semi-norm $||.||_{{\mathscr {M}}^{+}}$, that is, find an approximate solution $z^{(k)}$ such that

$$\begin{aligned} z^{(k)}=\mathop {argmin}\limits _{z\in z^{(0)}+K_{k}({\mathscr {A}}{\mathscr {M}}^{+},r^{(0)})}||b-{\mathscr {A}}{\mathscr {M}}^{+}z||_{{\mathscr {M}}^{+}} \end{aligned}$$

and then compute the solution $x^{(k)}={\mathscr {M}}^{+}z^{(k)}$.

We show the right preconditioned MINRES algorithm as follows.

5 Convergence analysis of right preconditioned MINRES method

Lemma 5.1

(Zhang 2010) If ${\mathscr {R}}({\mathscr {A}})={\mathscr {R}}({\mathscr {M}})$, then

(1) ${\mathscr {R}}(({\mathscr {M}}^{+}{\mathscr {A}} )^{T})={\mathscr {R}}({\mathscr {A}}^{T})$; (2) ${\mathscr {R}}({\mathscr {M}}^{+}{\mathscr {A}})={\mathscr {R}}({\mathscr {M}}^{T})$.

Theorem 5.2

Suppose ${\mathscr {M}}$ is a SPSD matrix and ${\mathscr {A}}={\mathscr {M}}-{\mathscr {N}}$ is a proper splitting, $rank({\mathscr {A}})=m$. Then right preconditioned MINRES which determines a solution $x={\mathscr {M}}^{+}z$ of

$$\begin{aligned} \mathop {min}\limits _{z\in {\mathbb {R}}^{n}}||b-{\mathscr {A}}{\mathscr {M}}^{+}z||_{{\mathscr {M}}^{+}} \end{aligned}$$

without breakdown, and terminates in at most m steps for all $b\in {\mathscr {R}}({\mathscr {A}})$ and all $z^{(0)}\in {\mathbb {R}}^{n}$.

Proof

Recalling $q_{i}$, $Q_{1}$ and $Q_{2}$ defined in Sect. 3, let

$$\begin{aligned} {\tilde{q}}_{i}={\mathscr {M}}^{\frac{1}{2}} q_{i}, i=1,2,\text {...},m \end{aligned}$$

(32)

Define the matrices $\tilde{Q}_{1}, \tilde{Q}$ as follows:

$$\begin{aligned} {\tilde{Q}}_{1}:=[{\tilde{q}}_{1},{\tilde{q}}_{2},\text {...},{\tilde{q}}_{m}]\in {\mathbb {R}}^{n\times m},\quad {\tilde{Q}}:=[\tilde{Q}_1, Q_2]\in {\mathbb {R}}^{n\times n} \end{aligned}$$

From (32), it holds ${\tilde{q}}_{i}\in {\mathscr {R}}({\mathscr {M}}^{\frac{1}{2}})$, $i=1,2,...,m,$ and we obtain

$$\begin{aligned} {\tilde{Q}}_{1}={\mathscr {M}}^{\frac{1}{2}} Q_{1}. \end{aligned}$$

(33)

Then we have ${\mathscr {M}}^{+\frac{1}{2}}\tilde{Q}_{1}={\mathscr {M}}^{+\frac{1}{2}}{\mathscr {M}}^{\frac{1}{2}}Q_{1}$. Noticing that ${\mathscr {R}}( Q_{1})= {\mathscr {R}}(({\mathscr {M}}^{\frac{1}{2}})^{T})$ and ${\mathscr {M}}^{+\frac{1}{2}}{\mathscr {M}}^{\frac{1}{2}}$ is the projection onto ${\mathscr {R}}(({\mathscr {M}}^{\frac{1}{2}})^{T})$, so it holds ${\mathscr {M}}^{+\frac{1}{2}}{\mathscr {M}}^{\frac{1}{2}} Q_{1}= Q_{1}$. Hence,

$$\begin{aligned} Q_{1}={\mathscr {M}}^{+\frac{1}{2}}{\tilde{Q}}_{1} \end{aligned}$$

(34)

By (33) and (34), we have $rank(\tilde{Q}_{1})=rank(Q_{1})=m$. This implies ${\tilde{q}}_{1},\tilde{q}_{2},\text {...},{\tilde{q}}_{m}$ are the basis of ${\mathscr {R}}({\mathscr {A}})$ and ${\tilde{Q}}$ is nonsingular.

Since

$$\begin{aligned} ({\tilde{q}}_{i},\tilde{q}_{i})_{{\mathscr {M}}^{+}}=({\mathscr {M}}^{\frac{1}{2}}q_{i})^{T}{\mathscr {M}}^{+}{\mathscr {M}}^{\frac{1}{2}}q_{i}= ({\mathscr {M}}^{+\frac{1}{2}}{\mathscr {M}}^{\frac{1}{2}}q_{i})^{T}{\mathscr {M}}^{+\frac{1}{2}}{\mathscr {M}}^{\frac{1}{2}}q_{i}=(q_{i})^{T}q_{i}=1 \end{aligned}$$

and in the same way, when $i\not =j$, $(q_{i},q_{j})_{{\mathscr {M}}^{+}}=0$, $i, j=1,2,\text {...},m.$ Then we have

$$\begin{aligned} \left\{ \begin{aligned}\;&({\tilde{q}}_{i},{\tilde{q}}_{i})_{{\mathscr {M}}^{+}}=1\\&({\tilde{q}}_{i},{\tilde{q}}_{j})_{{\mathscr {M}}^{+}}=0,i\not =j \end{aligned} \right. \end{aligned}$$

(35)

Therefore, ${\tilde{q}}_{1},{\tilde{q}}_{2},\text {...},{\tilde{q}}_{m}$ are the orthonormal basis of ${\mathscr {R}}({\mathscr {A}})$ with respect to $(,)_{{\mathscr {M}}^{+}}$ .

From (35), we obtain

$$\begin{aligned} \tilde{Q}_{1}^{T}{\mathscr {M}}^{+}\tilde{Q}_{1}=I_{m}. \end{aligned}$$

(36)

Evidently,

$$\begin{aligned} \tilde{Q}_{1}^{T}{\mathscr {M}}^{+}\tilde{Q}_{1}\tilde{Q}_{1}^{T}{\mathscr {M}}^{+}\tilde{Q}_{1}=I_{m}. \end{aligned}$$

(37)

By (36) and (37), it holds

$$\begin{aligned} \tilde{Q}_{1}^{T}({\mathscr {M}}^{+}\tilde{Q}_{1}\tilde{Q}_{1}^{T}{\mathscr {M}}^{+}-{\mathscr {M}}^{+})\tilde{Q}_{1}=0. \end{aligned}$$

(38)

Noticing ${\mathscr {M}}^{+}Q_{2}=0$, so it holds

$$\begin{aligned} \begin{aligned}&\tilde{Q}^{T}({\mathscr {M}}^{+}\tilde{Q}_{1}\tilde{Q}_{1}^{T}{\mathscr {M}}^{+}-{\mathscr {M}}^{+})\tilde{Q}\\ {}&=[\tilde{Q}_{1},Q_{2}]^{T}({\mathscr {M}}^{+}\tilde{Q}_{1}\tilde{Q}_{1}^{T}{\mathscr {M}}^{+}-{\mathscr {M}}^{+})[\tilde{Q}_{1},Q_{2}]\\&=\begin{bmatrix} \tilde{Q}^{T}_{1}({\mathscr {M}}^{+}\tilde{Q}_{1}\tilde{Q}_{1}^{T}{\mathscr {M}}^{+}-{\mathscr {M}}^{+})\tilde{Q}_{1} &{} \tilde{Q}^{T}_{1}({\mathscr {M}}^{+}\tilde{Q}_{1}\tilde{Q}_{1}^{T}{\mathscr {M}}^{+}-{\mathscr {M}}^{+})Q_{2} \\ Q_{2}^{T}({\mathscr {M}}^{+}\tilde{Q}_{1}\tilde{Q}_{1}^{T}{\mathscr {M}}^{+}-{\mathscr {M}}^{+})\tilde{Q}_{1} &{} Q_{2}^{T}({\mathscr {M}}^{+}\tilde{Q}_{1}\tilde{Q}_{1}^{T}{\mathscr {M}}^{+}-{\mathscr {M}}^{+})Q_{2} \end{bmatrix}\\&=0.\\ \end{aligned} \end{aligned}$$

(39)

Because ${\tilde{Q}}$ is nonsingular, we have

$$\begin{aligned} {\mathscr {M}}^{+}\tilde{Q}_{1}\tilde{Q}_{1}^{T}{\mathscr {M}}^{+}={\mathscr {M}}^{+}. \end{aligned}$$

(40)

Let ${\tilde{r}}=b-{\mathscr {A}}x$. Since $b\in {\mathscr {R}}({\mathscr {A}})$, ${\tilde{r}}\in {\mathscr {R}}({\mathscr {A}})$ holds. Therefore, there exists ${\tilde{r}}_{1}\in {\mathbb {R}}^{m}$ such that

$$\begin{aligned} {\tilde{r}}={\tilde{Q}}_{1}{\tilde{r}}_{1}. \end{aligned}$$

(41)

Together with (36), we have

$$\begin{aligned} ||{\tilde{r}}||_{{\mathscr {M}}^{+}}=\sqrt{\tilde{r}^{T}{\mathscr {M}}^{+}{\tilde{r}}}=\sqrt{{\tilde{r}}_{1}^{T}\tilde{Q}_{1}^{T}{\mathscr {M}}^{+}{\tilde{Q}}_{1}{\tilde{r}}_{1}} =||\tilde{r}_{1}||_{2}. \end{aligned}$$

(42)

By (40), (41), we have

$$\begin{aligned} \begin{aligned} {\tilde{r}}_{1}&={\tilde{Q}}^{T}_{1}{\mathscr {M}}^{+}{\tilde{Q}}_{1}{\tilde{r}}_{1}\\&={\tilde{Q}}^{T}_{1}{\mathscr {M}}^{+}{\tilde{r}}\\&={\tilde{Q}}^{T}_{1}{\mathscr {M}}^{+}(b-{\mathscr {A}}x)\\&={\tilde{Q}}^{T}_{1}{\mathscr {M}}^{+}b-Q^{T}_{1}{\mathscr {M}}^{+}{\mathscr {A}}x\\&={\tilde{Q}}^{T}_{1}{\mathscr {M}}^{+}b-Q^{T}_{1}{\mathscr {M}}^{+}{\mathscr {A}}{\mathscr {M}}^{+}z\\&={\tilde{Q}}^{T}_{1}{\mathscr {M}}^{+}b-\tilde{Q}^{T}_{1}{\mathscr {M}}^{+}{\mathscr {A}}({\mathscr {M}}^{+}\tilde{Q}_{1}{\tilde{Q}}^{T}_{1}{\mathscr {M}}^{+})z. \end{aligned} \end{aligned}$$

(43)

Let

$$\begin{aligned} {\tilde{b}}_{1}:={\tilde{Q}}^{T}_{1}{\mathscr {M}}^{+}b,\quad \tilde{z}_{1}:={\tilde{Q}}^{T}_{1}{\mathscr {M}}^{+}z,\quad {\tilde{A}}_{1}:=\tilde{Q}^{T}_1{\mathscr {M}}^{+}{\mathscr {A}}{\mathscr {M}}^{+}{\tilde{Q}}_{1}. \end{aligned}$$

Then

$$\begin{aligned} {\tilde{r}}_{1}={\tilde{b}}_{1}-{\tilde{A}}_{1}{\tilde{z}}_{1}. \end{aligned}$$

(44)

Since ${\mathscr {A}}={\mathscr {M}}-{\mathscr {N}}$ is a proper splitting, then from Lemma 5.1, it holds

$$\begin{aligned} {\mathscr {R}}(({\mathscr {M}}^{+}{\mathscr {A}})^{T})={\mathscr {R}}({\mathscr {M}}^{T}). \end{aligned}$$

(45)

Hence, we have

$$\begin{aligned} rank({\mathscr {M}}^{+}{\mathscr {A}}{\mathscr {M}}^{+}{\mathscr {M}}) =rank(({\mathscr {M}}^{+}{\mathscr {A}}{\mathscr {M}}^{+}{\mathscr {M}})^{T}) =rank(({\mathscr {M}}^{+}{\mathscr {M}})^{T}({\mathscr {M}}^{+}{\mathscr {A}})^{T}) =m. \end{aligned}$$

(46)

Since

$$\begin{aligned} m=rank({\mathscr {M}}^{+}{\mathscr {A}}{\mathscr {M}}^{+}{\mathscr {M}})\le rank({\mathscr {M}}^{+}{\mathscr {A}}{\mathscr {M}}^{+})\le rank({\mathscr {M}}^{+}{\mathscr {A}})=m, \end{aligned}$$

then we have $rank({\mathscr {M}}^{+}{\mathscr {A}}{\mathscr {M}}^{+})=m$. Since ${\tilde{Q}}$ is nonsingular, it holds $rank(\tilde{Q}^{T}{\mathscr {M}}^{+}{\mathscr {A}}{\mathscr {M}}^{+}{\tilde{Q}})=m$.

Noticing ${\mathscr {M}}^{+}Q_{2}=0$, it holds

$$\begin{aligned} \begin{aligned}&{\tilde{Q}}^{T}({\mathscr {M}}^{+}{\mathscr {A}}{\mathscr {M}}^{+}){\tilde{Q}}\\&=[{\tilde{Q}}_{1}, Q_{2}]^{T}({\mathscr {M}}^{+}{\mathscr {A}}{\mathscr {M}}^{+})[{\tilde{Q}}_{1},Q_{2}]\\&=\begin{bmatrix} {\tilde{Q}}^{T}_{1}({\mathscr {M}}^{+}{\mathscr {A}}{\mathscr {M}}^{+}){\tilde{Q}}_{1} &{} {\tilde{Q}}^{T}_{1}({\mathscr {M}}^{+}{\mathscr {A}}{\mathscr {M}}^{+}) Q_{2} \\ ( Q_{2})^{T}({\mathscr {M}}^{+}{\mathscr {A}}{\mathscr {M}}^{+}){\tilde{Q}}_{1} &{} ( Q_{2})^{T}({\mathscr {M}}^{+}{\mathscr {A}}{\mathscr {M}}^{+})Q_{2} \end{bmatrix}\\&=\begin{bmatrix} {\tilde{Q}}^{T}_{1}({\mathscr {M}}^{+}{\mathscr {A}}{\mathscr {M}}^{+}){\tilde{Q}}_{1} &{} 0 \\ 0 &{} 0 \end{bmatrix}\\ \end{aligned} \end{aligned}$$

(47)

Then, we have $rank({\tilde{A}}_{1}) =rank(\tilde{Q}^{T}{\mathscr {M}}^{+}{\mathscr {A}}{\mathscr {M}}^{+}{\tilde{Q}})=m$. Therefore, ${\tilde{A}}_{1}$ is nonsingular.

From (42) and (44), we have

$$\begin{aligned} ||b-{\mathscr {A}}x||_{{\mathscr {M}}^{+}}=||\tilde{r}_{1}||_{2}=||\tilde{b}_{1}-\tilde{A}_{1}\tilde{z}_{1}||_{2}. \end{aligned}$$

For solving a symmetric linear system, GMRES is mathematical equivalent to MINRES. Since GMRES determines a least squares solution without breakdown for nonsingular systems (Saad and Schultz 1986). Therefore, MINRES determines a least squares solution without breakdown for symmetric nonsingular systems. From Lemma 3.2, MINRES converges to the solution of

$$\begin{aligned} \mathop {min}\limits _{\tilde{z}_{1}\in {\mathbb {R}}^{m}}||\tilde{b}_{1}-\tilde{A}_{1}\tilde{z}_{1}||_{2} \end{aligned}$$

in at most m iterations.

Therefore, the right preconditioned MINRES which determines a solution $x={\mathscr {M}}^{+}z$ of

$$\begin{aligned} \mathop {min}\limits _{z\in {\mathbb {R}}^{n}}||b-{\mathscr {A}}{\mathscr {M}}^{+}z||_{{\mathscr {M}}^{+}} \end{aligned}$$

without breakdown and terminates in at most m steps for all $b\in {\mathscr {R}}({\mathscr {A}})$ and all $z^{(0)}\in {\mathbb {R}}^{n}$. $\square$

Since both b and $x^{(0)}$ are in ${\mathscr {R}}({\mathscr {A}})$, then we can decompose the right preconditioned MINRES (Algorithm 3) into the ${\mathscr {R}}({\mathscr {A}})$ component, and ${\mathscr {R}}({\mathscr {A}})^{\perp }|_{\mathscr {M}^{+}}$ component is zero, see the following decomposed right preconditioned MINRES algorithm (Algorithm 4). Algorithm 4 is equivalent to MINRES applied to ${\tilde{A}}_{1}{\tilde{z}}_{1}={\tilde{b}}_{1}$, and then compute $x={\mathscr {M}}^{+}{\tilde{Q}}_{1}{\tilde{z}}_{1}$.

Notice that if the conditions in Theorem 5.2 are satisfied, then ${\tilde{z}}^{(j)}_{1}$ converges to $\tilde{A}^{-1}_{1}{\tilde{Q}}^{T}_{1}{\mathscr {M}}^{+}b$ and $x^{(j)}$ converges to ${\mathscr {M}}^{+}{\tilde{Q}}_{1}{\tilde{A}}^{-1}_{1}\tilde{Q}^{T}_{1}{\mathscr {M}}^{+}b$.

Similar to Theorem 3.4 we can estimate the convergence rate of right preconditioned MINRES algorithm, here omitted. In this paper, we use MINRES to solve the left preconditioned system (3) and the right preconditioned system (30), respectively. Hayami et al. (2010) studied BA-GMRES (AB-GMRES), which have similar meanings with left preconditioned MINRES (right preconditioned MINRES). That is, BA-GMRES use GMRES to solve the left preconditioned system (3), AB-GMRES use GMRES to solve the right preconditioned system (30), respectively. AB-GMRES and BA-GMRES both determine the least squares solutions for singular linear systems.

6 Numerical results

In this section, we give three numerical examples of singular saddle point problems to illustrate the effectiveness of MINRES with singular preconditioners. That is, we consider the following system of linear equations:

$$\begin{aligned} {\mathscr {A}}x\equiv \begin{bmatrix} A &{} B^{T} \\ B &{} 0 \end{bmatrix}\begin{bmatrix} u \\ p \end{bmatrix}=b, \end{aligned}$$

(48)

where A is a SPD matrix, B is rank deficient. All the numerical experiments are implemented in MATLAB (version R2018b) on a PC computer with Intel(R) Core(TM) i5-10500 CPU 3.10 GHz, 16.0 GB memory. We denote the elapsed CPU time (in second) by CPU, the iteration numbers by IT, and the norm of the residuals by RES, respectively. In our computations all the initial guesses ${x}^{(0)}$ are taken by zero vectors, and the computations are terminated once the stopping criterion

$$\begin{aligned} RES=\frac{\left\| b-{\mathscr {A}}x\right\| _{2}}{\left\| b\right\| _{2}}\le 10^{-13} \end{aligned}$$

is satisfied.

Example 6.1

(Elman 1999; Zhang 2010) Discretize Navier–Stokes equations by “maker and cell ”(MAC) finite difference scheme, we can obtain the following linear system:

$$\begin{aligned} {\mathscr {A}}x\equiv \begin{bmatrix} {\widetilde{A}} &{} B^{T} \\ B &{} 0 \end{bmatrix}\begin{bmatrix} u \\ p \end{bmatrix}=b, \end{aligned}$$

(49)

where

$$\begin{aligned} {\widetilde{A}}=\begin{bmatrix} F_{1} &{} 0 \\ 0 &{} F2 \end{bmatrix}\in {\mathbb {R}}^{2l(l-1)\times 2l(l-1)}, \quad B=(B_{1},B_{2})\in {\mathbb {R}}^{l^2\times 2l(l-1)} \end{aligned}$$

$$\begin{aligned} F_{i}=vA_{i}+N_{i} \in {\mathbb {R}}^{l(l-1)\times l(l-1)}, i=1,2,\quad u\in { {\mathbb {R}}^{2l(l-1)\times 1}},\quad p\in {{\mathbb {R}}^{l^2\times 1}} \end{aligned}$$

${\widetilde{A}}$ is nonsymmetric and positive definite. We denote $s=2l(l-1)$, $t=l^2$ in this example, $rank(B)=t-1$. To ensure the (1,1)-block matrix be SPD, we take the coefficient matrix as follows:

$$\begin{aligned} {\mathscr {A}}=\begin{bmatrix} A&{} B^{T} \\ B &{} 0 \end{bmatrix}, \end{aligned}$$

where $A=\dfrac{{\widetilde{A}}+{\widetilde{A}}^{T} }{2}, b={\mathscr {A}}e_{s+t}$, $e_{s+t}=(1,1,...,1)^{T}\in R^{s+t}$.

Example 6.2

(Chao and Zhang 2014) Consider the following saddle point problem:

$$\begin{aligned} {\mathscr {A}}x\equiv \begin{bmatrix} A &{} B^{T} \\ B &{} 0 \end{bmatrix}\begin{bmatrix} y \\ z \end{bmatrix}=b, \end{aligned}$$

(50)

where

$$\begin{aligned} A=\begin{bmatrix} I\bigotimes T+ T\bigotimes I &{} 0\\ 0 &{} I\bigotimes T+ T\bigotimes I \end{bmatrix}\in {\mathbb {R}}^{2l^{2}\times 2l^{2}},\quad B^{T}=(E,b_{1},b_{2})\in {\mathbb {R}}^{2l^{2}\times (l^{2}+2)} \end{aligned}$$

in which

$$\begin{aligned} T= \dfrac{1}{h^{2}}tridiag(-1,2,-1)\in {\mathbb {R}}^{l\times l},\quad E=\begin{bmatrix} I\bigotimes F\\ F\bigotimes I \end{bmatrix}\in {\mathbb {R}}^{2l^{2}\times l^{2}} \\ b_{1}=E\begin{bmatrix} e_{l^{2}/2}\\ 0 \end{bmatrix},b_{2}=E\begin{bmatrix} 0\\ e_{l^{2}/2} \end{bmatrix},\quad F= \dfrac{1}{h}tridiag(-1,1,0)\in {\mathbb {R}}^{l\times l}, \end{aligned}$$

where $h=\dfrac{1}{l+1}$, $e_{l^{2}/2}=(1,1,...,1)^{T}\in {\mathbb {R}}^{l^{2}/2}$, $b={\mathscr {A}}e_{s+t}$, where $e_{s+t}=(1,1,...,1)^{T}\in R^{s+t}, s=2l^{2}, t=l^{2}+2$. Then A is SPD, $rank(B)=t-2$.

Example 6.3

(Shen and Huang 2011) Consider the following Stokes equations:

$$\begin{aligned} -\Delta u+gradp=f\quad in ~\Omega \\ -divu=0\quad in ~ \Omega , \end{aligned}$$

where the vector function u is the velocity while the scalar function p is the pressure of the fluid, $\Omega$ is an open bounded domain. We use the IFISS software written by Silvester et al. (2012) to discretize the leaky two-dimensional lid-driven cavity problems in a square domain $(-1, 1)\times (-1, 1)$, and the boundary conditions on the side and bottom are Dirichlet no-flow conditions. A finite element subdivision based on uniform grids of square elements is taken. Then we can obtain a kind of saddle-point problem with the form (50), with the (1,1) block A of the generated coefficient matrix be SPD, and the (1,2) block B be rank deficient, see (Shen and Huang 2011) for detail. We still denote the order of A by $s\times s$ and B by $t\times s$, respectively.

Proposition 6.4

(Zhang 2010) For ${\mathscr {A}}= \begin{bmatrix} A &{} B^{T} \\ B &{} 0 \end{bmatrix}$, where $A\in {{\mathbb {R}}^{s\times s}}$ is SPD, $B\in {{\mathbb {R}}^{t\times s}}, t \le s$, If M is SPD in the block diagonal preconditioner ${\mathscr {M}}=\begin{bmatrix} M &{} 0 \\ 0 &{} BM^{-1}B^{T} \end{bmatrix}$, then ${\mathscr {A}}={\mathscr {M}}-({\mathscr {M}}-{\mathscr {A}})$ is a proper splitting.

Notice if $M_{1}$ and $M_{2}$ are SPD in the preconditioner ${\mathscr {M}}=\begin{bmatrix} M_{1} &{} 0 \\ 0 &{} BM_{2}^{-1}B^{T} \end{bmatrix}$, then ${\mathscr {A}}={\mathscr {M}}-({\mathscr {M}}-{\mathscr {A}})$ is also a proper splitting, and it holds that ${\mathscr {M}}$ is SPSD. We list four suitable singular preconditioners in Table 1, that is ${\mathscr {M}}_I$, ${\mathscr {M}}_{II}$, ${\mathscr {M}}_{III}$ and ${\mathscr {M}}_{IV}$.

Table 1 The choices of preconditioners ${\mathscr {M}}$

Table 2 Numerical results of preconditioned MINRES and preconditioned GMRES for Example 6.1

Table 3 Numerical results of preconditioned MINRES and preconditioned GMRES for Example 6.2

Table 4 Numerical results of preconditioned MINRES and preconditioned GMRES for Example 6.3

We test preconditioned MINRES with different preconditioners, including the SSOR preconditioner ${\mathscr {M}}_{SSOR}$ (Sugihara et al. 2020) and the preconditioners listed in Table 1. We also test the preconditioned GMRES with SSOR preconditioner ${\mathscr {M}}_{SSOR}$, the preconditioners listed in Table 1, and the constraint preconditioner ${\mathscr {M}}_{const}$ (Zhang and Shen 2013), respectively. The drop tolerance of the incomplete Cholesky factorization is 0.001. The SSOR preconditioner ${\mathscr {M}}_{SSOR}$ is defined by follows.

$$\begin{aligned} {\mathscr {M}}_{SSOR}=(L+D)D^{-1}(L^{T}+D), \end{aligned}$$

where L is the strictly lower triangular part of ${\mathscr {A}}$, and $D=\begin{bmatrix} D_{1} &{} O \\ O &{} I_{t} \end{bmatrix}$, $D_{1}$ is the diagonal part of A. The constraint preconditioner ${\mathscr {M}}_{const}$ is defined by follows:

$$\begin{aligned} {\mathscr {M}}_{const}=\begin{bmatrix} M_l &{} B^{T} \\ B &{} O \end{bmatrix}, \end{aligned}$$

where $M_l$=$diag(\beta _1,\beta _2,...,\beta _n)$, where $\beta _{j}$ is 1-norm of the jth row of A, $j=1,2,...,n$.

Numerical results can be found in Tables 2, 3 and 4. LMINRES and RMINRES in these tables denote left preconditioned MINRES and right preconditioned MINRES, respectively. It can be seen that for the same preconditioner, iteration numbers and CPU times of preconditioned MINRES are almost less than that of preconditioned GMRES. Among the four peconditioners in Table 1, ${\mathscr {M}}_{II}$ preconditioned MINRES performs better than that of the other three cases. In addition, ${\mathscr {M}}_{II}$ preconditioned MINRES always performs better than ${\mathscr {M}}_{SSOR}$ preconditioned MINRES and ${\mathscr {M}}_{const}$ preconditioned GMRES. By comparing left preconditioning and right preconditioning techniques with MINRES, we see the iteration number of them are almost the same, but the elapsed CPU time of left preconditioned MINRES are almost less than that of right preconditioned MINRES. Notice in Tables 2, 3 and 4, if CPU>5000s or IT>1500, then the numerical results are replaced by “+”. And “s+t” represents the order of the corresponding coefficient matrices.

7 Conclusions

We have presented the left and right preconditioned MINRES method for solving symmetric singular linear systems. We take the singular preconditioners under the condition of proper splitting, and give the convergence analysis for preconditioned MINRES. It shows that the left and right preconditioned MINRES converges to a solution when the system is consistent. Numerical results have demonstrated the effectiveness of the preconditioned MINRES with singular preconditioners.