A new generalized shift-splitting method for nonsymmetric saddle point problems

Abstract

Recently, Huang and Huang [Journal of Computational and Applied Mathematics, 328 (2018) 381–399] proposed a modified generalized shift-splitting preconditioned (denoted by MGSSP) method for solving large sparse saddle point problems, and gave the corresponding theoretical analysis and numerical experiments. In this paper, based on the modified generalized shift-splitting preconditioned (MGSSP) method, we generalize the MGSSP algorithms and further present the new generalized shift-splitting preconditioned (NGSSP) method for nonsymmetric saddle point problems. Moreover, by similar theoretical analysis, we analyze the convergence conditions of the corresponding matrix splitting iteration methods of the NGSSP preconditioned saddle point matrices. In final, one example is provided to confirm the effectiveness.

MSC: 65F10, 65F15, 65F50

Introduction

Consider the following $2\times 2$ block saddle point problems

$$\mathcal{A}\left(\begin{array}{c}x\hfill \\ \multicolumn{1}{c}{y}\end{array}\right)\equiv \left(\begin{array}{cc}A\hfill & B\hfill \\ \multicolumn{1}{c}{-B^T}& 0\hfill \end{array}\right)\left(\begin{array}{c}x\hfill \\ \multicolumn{1}{c}{y}\end{array}\right)=\left(\begin{array}{c}f\hfill \\ \multicolumn{1}{c}{g}\end{array}\right)=b,$$

(1)

where $A\in R^{n,n}$ is a symmetric positive definite, $B\in R^{n,m},m\le n,$ has full column rank, $B^T\in R^{m,n}$ is the conjugate transpose of $B$ , and $f\in R^n,g\in R^m$ are two given vectors. It appears in many different applications of scientific computing, such as constrained optimization, ¹ the finite element method for solving the Navier-Stokes equation,^2–4 and constrained least squares problems and generalized least squares problems^5–17 and so on.

In recent years, there has been a surge of interest in the saddle point problem of the form (1), and a large number of stationary iterative methods have been proposed. For example, Santos et al. ⁶ studied preconditioned iterative methods for solving the singular augmented system with $A=I$ . Golub et al. ¹⁸ presented SOR-like algorithms for solving linear systems (1). Darvishi and Hessari ⁹ studied SSOR method for solving the augmented systems. Bai and Wang^1,20–22 presented GSOR method, parameterized Uzawa (PU) and the inexact parameterized Uzawa (PIU) methods for solving linear systems (1). Zhang and Lu ²³ showed the generalized symmetric SOR method for augmented systems. Peng and Li ²⁴ studied the unsymmetric block overrelaxation-type methods for saddle point. Bai and Golub^25–31 presented splitting iteration methods such as Hermitian and skew-Hermitian splitting (HSS) iteration scheme and its preconditioned variants, Krylov subspace methods such as preconditioned conjugate gradient (PCG), preconditioned MINRES (PMINRES) and restrictively preconditioned conjugate gradient (RPCG) iteration schemes, and preconditioning techniques related to Krylov subspace methods such as HSS, block-diagonal, block-triangular, and constraint preconditioners and so on.

Recently, based on the modified generalized shift-splitting of the saddle point matrix $\mathcal{A}$ , Huang and Huang ³² constructed a modified generalized shift-splitting preconditioned (denoted by MGSSP) method for solving large sparse saddle point problems. Moreover, theoretical analyses and numerical example show that the corresponding iteration method unconditionally converges to the unique solution of the saddle point problems.

For large, sparse or structure matrices, iterative methods are an attractive option. In particular, Krylov subspace methods apply techniques that involve orthogonal projections onto subspaces of the form

$$\mathcal{K}(\mathcal{A},b)\equiv \mathrm{span}\{b,\mathcal{A}b,{\mathcal{A}}^{2}b,...,{\mathcal{A}}^{n-1}b,...\}.$$

The conjugate gradient method (CG), minimum residual method (MINRES) and generalized minimal residual method (GMRES) are common Krylov subspace methods. The CG method is used for symmetric, positive definite matrices, MINRES for symmetric and possibly indefinite matrices and GMRES for unsymmetric matrices. ³³

In this paper, on the basis of the special shift-splitting by Huang and Huang, ³² we generalize the MGSSP algorithms and further present the new generalized shift-splitting preconditioned (NGSSP) method for nonsymmetric saddle point problems. Moreover, by similar theoretical analysis, we analyze the convergence conditions of the corresponding matrix splitting iteration methods of the NGSSP preconditioned saddle point matrices. In final, one example is provided to confirm the effectiveness.

New generalized shift-splitting preconditioned (NGSSP) method

Recently, for the coefficient matrix of the augmented system (1), Huang and Huang ³² made the following splitting

$$\begin{array}{ccc}\mathcal{A}\hfill & =\hfill & \left(\begin{array}{cc}\alpha I_n+2A\hfill & 2B\hfill \\ \multicolumn{1}{c}{-2B^T}& \beta I_m\hfill \end{array}\right)-\left(\begin{array}{cc}\alpha I_n+A\hfill & B\hfill \\ \multicolumn{1}{c}{-B^T}& \beta I_m\hfill \end{array}\right),\hfill \end{array}$$

(2)

where $\alpha >0,\beta >0$ are two constant numbers, and $I_m$ and $I_n$ are the identity matrix. Based on the iteration methods studied in Huang and Huang, ³² we establish the new generalized shift-splitting preconditioned (NGSSP) method of the saddle point matrix $\mathcal{A}$ , which is as follows:

$$\begin{array}{c}\mathcal{A}={\mathcal{P}}_{\mathrm{NGSSP}}-{\mathcal{R}}_{\mathrm{NGSSP}}\hfill \\ =\left(\begin{array}{cc}\alpha I_n+\gamma A\hfill & \gamma B\hfill \\ \multicolumn{1}{c}{-\gamma B^T}& \beta I_m\hfill \end{array}\right)-\left(\begin{array}{cc}\alpha I_n+(\gamma -1)A\hfill & (\gamma -1)B\hfill \\ \multicolumn{1}{c}{-(\gamma -1)B^T}& \beta I_m\hfill \end{array}\right),\hfill \end{array}$$

(3)

where $\alpha >0,\beta >0,\gamma >0$ are three constant numbers, and $I_m$ and $I_n$ are the identity matrix. By this special splitting, the following mnew generalized shift-splitting preconditioned (NGSSP) method can be defined for solving the saddle point problem (1):

New generalized shift-splitting preconditioned (NGSSP) method: Given initial vectors $u^0\in R^{m+n}$ , and three relaxed parameters $\alpha >0,\beta >0,\gamma >0$ . For $k=0,1,2,...$ until the iteration sequence $\{u^k\}$ converges, compute

$$\begin{array}{c}\left(\begin{array}{c}\alpha I_n+\gamma A\gamma B\hfill \\ \multicolumn{1}{c}{-\gamma B^T}& \beta I_m\hfill \end{array}\right)u^{k+1}\hfill \\ =\left(\begin{array}{cc}\alpha I_n+(\gamma -1)A\hfill & (\gamma -1)B\hfill \\ \multicolumn{1}{c}{-(\gamma -1)B^T}& \beta I_m\hfill \end{array}\right)u^k+\left(\begin{array}{c}f\hfill \\ \multicolumn{1}{c}{g}\end{array}\right)\hfill \end{array}$$

(4)

It is easy to see that the iteration matrix of the NGSSP iteration is

$$\begin{array}{l}{\mathrm{\Gamma }}_{NGSSP}={\mathcal{P}}_{NGSSP}^{-1}{\mathcal{R}}_{NGSSP}=\\ {\left(\begin{array}{cc}\alpha I_n+\gamma A& \gamma B\\ -\gamma B^T& \beta I_m\end{array}\right)}^{-1}\left(\begin{array}{cc}\alpha I_n+(\gamma -1)A& (\gamma -1)B\\ -(\gamma -1)B^T& \beta I_m\end{array}\right).\end{array}$$

(5)

If we use a Krylov subspace method such as GMRES (Generalized Minimal Residual) method or its restarted variant to approximate the solution of this system of linear equations, then

$${\mathcal{P}}_{\mathrm{NGSSP}}=\left(\begin{array}{cc}\alpha I_n+\gamma A\hfill & \gamma B\hfill \\ \multicolumn{1}{c}{-\gamma B^T}& \beta I_m\hfill \end{array}\right),$$

(6)

can be served as a preconditioner. We call the preconditioner ${\mathcal{P}}_{\mathrm{NGSSP}}$ the NGSSP preconditioner for the generalized saddle point matrix $\mathcal{A}$ .

In every iteration of the NGSSP iteration (4) or the preconditioned Krylov subspace method, we need solve a residual equation

$$\left(\begin{array}{cc}\alpha I_n+\gamma A\hfill & \gamma B\hfill \\ \multicolumn{1}{c}{-\gamma B^T}& \beta I_m\hfill \end{array}\right)z=r$$

(7)

needs to be solved for a given vector $r$ at each step. Hence, analogous to Algorithm 2.1 in Cao, ³⁴ we can derive the following algorithmic version of the NGSSP iteration method.

• Algorithm 2.1. For a given vector $r=[r_1^T,r_2^T{]}^T$ , the vector $z=[z_1^T,z_2^T{]}^T$ can be computed by (7) from the following steps:

• Step 1: Computed $t_1=\beta r_1-\beta \gamma B{r}_2;$

• Step 2: Solve $(\alpha \beta I_n+\beta \gamma A+{\gamma }^{2}B{B}^T)z_1=t_1;$

• Step 3: Solve $z_2=\frac{1}{\beta }(\gamma B^T{z}_1+r_2).$

• Remark 2.1. On the new generalized shift-splitting preconditioned (NGSSP) method, when $\gamma =2$ , the NGSSP method reduces to the MGSSP method. So, the NGSSP method is the generalization of existing iterative algorithm.

Convergence of NGSSP method

Now, we turn to study the convergence of the NGSSP iteration for solving saddle point problems (1). It is well known that the iteration method (4) is convergent for every initial guess if and only if $\rho (\mathrm{\Gamma })<1,$ where $\rho (\mathrm{\Gamma })$ denotes the spectral radius of $\mathrm{\Gamma }$ . In Huang and Huang, ³² based on the MGSSP method, Huang and Huang established the spectral properties of the iteration matrix and the preconditioned matrix ${\mathcal{P}}_{\mathrm{MGSSP}}^{-1}\mathcal{A}.$ In this section, we will analyze the spectral properties of the iteration matrix ${\mathcal{P}}_{\mathrm{NGSSP}}^{-1}{\mathcal{R}}_{\mathrm{NGSSP}}$ and obtain that the NGSSP iterative method is convergent under certain conditions.

• Lemma 3.1. Let $A\in R^{n,n}$ be symmetric positive definite, $B\in C^{n,m}$ have full column rank and ${\mathrm{\Gamma }}_{\mathrm{NGSSP}}$ be defined as in (5). Assume $\lambda$ is an eigenvalue of the NGSSP iteration matrix ${\mathrm{\Gamma }}_{\mathrm{NGSSP}}={\mathcal{P}}_{\mathrm{NGSSP}}^{-1}{\mathcal{R}}_{\mathrm{NGSSP}}$ and $(x^T,y^T{)}^T$ the corresponding eigenvector, then

• (1)  $\lambda \ne \pm 1$ .

• (2)  $x\ne 0$ .

• (3) If $y=0$ , then $\rho ({\mathrm{\Gamma }}_{\mathrm{NGSSP}})<1.$

Proof. Similar to the proving process of Lemmas 2.1 and 2.2 in Cao et al., ³⁵ we obviously can get the above Lemma.

• Lemma 3.2. ³⁶ Both roots of the real quadratic equation $x^2+\mathrm{bx}+c=0$ are less than one in modulus if and only if $|c|<1$ and $|b|<1+c$ .

• Theorem 3.3. Let $A\in R^{n,n}$ be symmetric positive definite, $B\in C^{n,m}$ have full column rank and ${\mathrm{\Gamma }}_{\mathrm{NGSSP}}$ be defined as in (5). Then for three positive iteration parameters $\alpha$ , $\beta$ and $\gamma >\frac{\theta +\sigma \beta }{2\theta }$ , the spectral radius of the NGSSP iteration matrix ${\mathrm{\Gamma }}_{\mathrm{NGSSP}}$ satisfies

$$\rho ({\mathrm{\Gamma }}_{\mathrm{NGSSP}})<1,$$

that is, the NGSSP iteration converges to the unique solution of the saddle point problem (1), where $\sigma =\frac{x^T\mathrm{Ax}}{x^{T}x},\theta =\frac{x^{T}B{B}^{T}x}{x^{T}x}.$

Proof. If we let the $u=(x,y{)}^T$ be an eigenvector corresponding to the eigenvalue $\lambda$ of ${\mathrm{\Gamma }}_{\mathrm{NGSSP}}$ , then we get

$${\mathcal{R}}_{\mathrm{NGSSP}}u=\lambda {\mathcal{P}}_{\mathrm{NGSSP}}u,$$

which can be equivalently expanded as follows:

$$\left(\begin{array}{cc}\alpha I_n+(\gamma -1)A\hfill & (\gamma -1)B\hfill \\ \multicolumn{1}{c}{-(\gamma -1)B^T}& \beta I_m\hfill \end{array}\right)u=\lambda \left(\begin{array}{cc}\alpha I_n+\gamma A\hfill & \gamma B\hfill \\ \multicolumn{1}{c}{-\gamma B^T}& \beta I_m\hfill \end{array}\right)u.$$

(8)

Then we have

$$\{\begin{array}{c}[\alpha I_n+(\gamma -1)A]x+(\gamma -1)\mathrm{By}=\lambda (\alpha I_n+\gamma A)x+\gamma \lambda \mathrm{By},\hfill \\ \multicolumn{1}{c}{-(\gamma -1)B^{T}x+\beta y=-\gamma \lambda B^{T}x+\beta \lambda y.}\end{array}$$

(9)

From Lemma 3.1, we know that $\lambda \ne 1$ . From the second formula of equation (9), we have

$$y=\frac{\gamma \lambda -\gamma +1}{\beta (\lambda -1)}{B}^{T}x$$

(10)

By substituting this relationship into the first formula of equation (9), we can obtain

$$\begin{array}{c}\alpha \beta (\lambda -1{)}^{2}x+\beta (\lambda -1)(\lambda \gamma -\gamma +1)\mathrm{Bx}\hfill \\ +(\lambda \gamma -\gamma +1{)}^{2}B{B}^{T}x=0.\hfill \end{array}$$

(11)

Following the spirit of Lemma 3.1, again, we have $x\ne 0$ . Left-multiplying both sides of (11) by $\frac{x^T}{x^{T}x}$ yields

$$\begin{array}{c}\multicolumn{1}{c}{\alpha \beta (\lambda -1{)}^2+\beta (\lambda -1)(\lambda \gamma -\gamma +1)\frac{x^T\mathrm{Bx}}{x^{T}x}}\\ +(\lambda \gamma -\gamma +1{)}^2\frac{x^{T}B{B}^{T}x}{x^{T}x}=0.\hfill \end{array}$$

(12)

For convenience, some labels are given in the forms

$$\sigma =\frac{x^T\mathrm{Ax}}{x^{T}x}>0,\mathrm{and}\tilde{\theta }=\frac{x^{T}B{B}^{T}x}{x^{T}x}\ge 0.$$

with $\tilde{\theta }=0$ or $\tilde{\theta }=\theta >0.$

Note $\lambda \ne 1$ , if $\tilde{\theta }=0$ , then we have from equation (12)

$$\lambda =\frac{\alpha +(\gamma -1)\sigma }{\alpha +\gamma \sigma }.$$

(13)

if $\tilde{\theta }=\theta$ , then equation (12) can be rewritten as

$$\begin{array}{c}\multicolumn{1}{c}{(\alpha \beta +\gamma \sigma \beta +{\gamma }^2\theta ){\lambda }^2-[2\alpha \beta +(2\gamma -1)\sigma \beta }\\ +(2{\gamma }^2-2\gamma )\theta ]\lambda +\alpha \beta +(\gamma -1)\sigma \beta +({\gamma }^2-2\gamma +1)\theta =0.\hfill \end{array}$$

(14)

From Lemma 3.2, it is straightforward to show that $|\lambda |<1$ if and only if

$$\frac{\alpha \beta +(\gamma -1)\sigma \beta +({\gamma }^2-2\gamma +1)\theta }{\alpha \beta +\gamma \sigma \beta +{\gamma }^2\theta }<1$$

(15)

and

$$\begin{array}{c}\frac{2\alpha \beta +(2\gamma -1)\sigma \beta +(2{\gamma }^2-2\gamma )\theta }{\alpha \beta +\gamma \sigma \beta +{\gamma }^2\theta }<1\hfill \\ +\frac{\alpha \beta +(\gamma -1)\sigma \beta +({\gamma }^2-2\gamma +1)\theta }{\alpha \beta +\gamma \sigma \beta +{\gamma }^2\theta }\hfill \end{array}$$

(16)

Obviously, when three iteration parameters $\alpha >0$ , $\beta >0$ and $\gamma >\frac{\theta +\sigma \beta }{2\theta }$ , the above equations (15) and (16) are satisfied.

• Theorem 3.4. Let $\lambda$ be defined as in (13) or (14). If the iteration parameters $\alpha >0$ , $\beta >0$ , $\gamma >0$ satisfy $\frac{\beta }{\alpha }\ge \frac{4\theta }{{\sigma }^2}$ , then all eigenvalues of the NGSSP iteration matrix ${\mathrm{\Gamma }}_{\mathrm{NGSSP}}$ are positive real.

Proof. By some algebra of (14), then it is easy to obtain that the explicit formula of the eigenvalue $\lambda$ satisfies the following form

$$\begin{array}{c}{\lambda }_{\pm }({\mathrm{\Gamma }}_{\mathrm{NGSSP}})=\hfill \\ \frac{[2\alpha \beta +(2\gamma -1)\sigma \beta +(2{\gamma }^2-2\gamma )\theta ]\pm \sqrt{{(\sigma \beta )}^2-4\theta \alpha \beta }}{2(\alpha \beta +\gamma \sigma \beta +{\gamma }^2\theta )}\hfill \end{array}$$

(17)

where ${\lambda }_{+}$ corresponds to the + sign and ${\lambda }_{-}$ associates with the − sign.

So, when $(\sigma \beta {)}^2-4\theta \alpha \beta \ge 0,$ or $\frac{\beta }{\alpha }\ge \frac{4\theta }{{\sigma }^2},$ all eigenvalues of the NGSSP iteration matrix ${\mathrm{\Gamma }}_{\mathrm{NGSSP}}$ are positive real.

• Remark 3.1. On the one hand, the NGSSP method is the generalization of the MGSSP method. On the other hand, when the appropriate parameters are selected, the NGSSP method will have better convergence than the NGSSP method.

Numerical examples

In this section, we verify the above conclusions through numerical experiments. MATLAB 7.1 software was used to conduct numerical experiments, and the numerical experiment matrices were respectively generated based on the mixed two-dimensional time-harmonic Maxwell equations. In all of our runs, the relative residuals have been reduced by at least six orders of magnitude by the time we use zero initial guesses and stop iterating (i.e. when $\parallel b-\mathcal{A}{x}^k{\parallel }_2\le {10}^{-6}\parallel b{\parallel }_2$ ).

• Example 1. In this section, to further evaluate the effectiveness of the new block triangular preconditioned matrix ${\mathcal{P}}_{\mathrm{NGSSP}}^{-1}\mathcal{A}$ combined with Krylov subspace methods, we consider a numerical examples based on a two-dimensional time-harmonic Maxwell equations with constant coefficients: find the vector field $u$ and the multiplier $p$ such that vector field $u$ and the multiplier $p$ such that

$$\begin{array}{ccc}\nabla \times \nabla \times u+\nabla p\hfill & =\hfill & f\mathrm{in}\mathrm{\Omega },\hfill \\ \multicolumn{1}{c}{\nabla ·u}& =\hfill & 0\mathrm{in}\mathrm{\Omega },\hfill \\ \multicolumn{1}{c}{u\times n}& =\hfill & 0\mathrm{on}\partial \mathrm{\Omega },\hfill \\ \multicolumn{1}{c}{p}& =\hfill & 0\mathrm{on}\partial \mathrm{\Omega }.\hfill \end{array}$$

(18)

Here, $\mathrm{\Omega }\in R^3$ is simply connected polyhedron domain with a connected boundary $\partial \mathrm{\Omega }$ and $n$ denotes the outward unit normal on $\partial \mathrm{\Omega }$ . The datum $f$ is a given generic source. We know that finite element discretization using Nédélec elements of the first kind for the approximation of the vector field and standard nodal elements for the multiplier yields the above $2\times 2$ block saddle point problems.

For the simplicity, we take the generic source: $f=1$ and a finite element subdivision such as Figure 2 based on uniform grids of triangle elements. Three mesh sizes are considered: $h=\frac{\sqrt{2}}{8},\frac{\sqrt{2}}{12},\frac{\sqrt{2}}{18}$ , $h=\frac{\sqrt{2}}{4}$ as shown in the Figure 1. The solution of the preprocessing system can be calculated accurately in each iteration. Table 1 shows the sparsity information of correlation matrices on different grids, where nz $(A)$ denote the nonzero elements of matrix $A$ .

Figure 1.

A uniform mesh with $h=\frac{\sqrt{2}}{4}$ .

Table 1.

Datasheet for different grids.

Grid	m	n	nz $(A)$	nz $(B)$	nz $(C)$	order of $\mathcal{A}$
$8\times 8$	176	49	820	462	217	225
$16\times 16$	736	225	3556	2190	1065	961
$32\times 32$	3008	961	14,788	9486	4681	3969
$64\times 64$	12,160	3969	60,292	39,438	19,593	16,129

Since the new preconditioners have three parameters, in numerical experiments we will test different values. Numerical experiments show the spectrum of the NGSSP preconditioned matrix ${\mathcal{P}}_{\mathrm{NGSSP}}^{-1}\mathcal{A}$ and the MGSSP preconditioned matrix ${\mathcal{P}}_{\mathrm{MGSSP}}^{-1}\mathcal{A}$ when choosing different parameters, which coincides with theoretical analysis.

In Figures 2, 4 and 6 we display the eigenvalues of the iteration matrix ${\mathcal{P}}_{\mathrm{NGSSP}}^{-1}{\mathcal{R}}_{\mathrm{NGSSP}}$ in the case of $h=\frac{\sqrt{2}}{8}$ , $h=\frac{\sqrt{2}}{12}$ and $h=\frac{\sqrt{2}}{18}$ for different parameters. In Figures 3, 5, and 7 we display the eigenvalues of the iteration matrix ${\mathcal{P}}_{\mathrm{MGSSP}}^{-1}{\mathcal{R}}_{\mathrm{MGSSP}}$ in the case of $h=\frac{\sqrt{2}}{8}$ , $h=\frac{\sqrt{2}}{12}$ and $h=\frac{\sqrt{2}}{18}$ for different parameters. In Tables $2~3$ we show iteration counts about preconditioned matrices ${\mathcal{P}}_{\mathrm{NGSSP}}^{-1}\mathcal{A}$ and ${\mathcal{P}}_{\mathrm{MGSSP}}^{-1}\mathcal{A}$ , when choosing different parameters and applying to BICGSTAB and GMRES Krylov subspace iterative methods on three meshes, where $I{t}_{\mathrm{BSTAB}({\mathcal{P}}_{\mathrm{NGSSP}}^{-1}\mathcal{A})}$ and $\mathrm{Re}{s}_{\mathrm{BSTAB}({\mathcal{P}}_{\mathrm{NGSSP}}^{-1}\mathcal{A})}$ are the iteration numbers and relative residual of the preconditioned matrices ${\mathcal{P}}_{\mathrm{NGSSP}}^{-1}\mathcal{A}$ when applying to BICGSTAB Krylov subspace iterative methods, respectively. $I{t}_{\mathrm{GMRES}({\mathcal{P}}_{\mathrm{NGSSP}}^{-1}\mathcal{A})}$ and $\mathrm{Re}{s}_{\mathrm{GMRES}({\mathcal{P}}_{\mathrm{NGSSP}}^{-1}\mathcal{A})}$ are the iteration numbers and relative residual of the preconditioned matrices ${\mathcal{P}}_{\mathrm{NGSSP}}^{-1}\mathcal{A}$ when applying to GMRES Krylov subspace iterative methods, respectively. $I{t}_{\mathrm{BSTAB}({\mathcal{P}}_{\mathrm{MGSSP}}^{-1}\mathcal{A})}$ , $\mathrm{Re}{s}_{\mathrm{BSTAB}({\mathcal{P}}_{\mathrm{MGSSP}}^{-1}\mathcal{A})}$ , $I{t}_{\mathrm{GMRES}({\mathcal{P}}_{\mathrm{MGSSP}}^{-1}\mathcal{A})}$ , $\mathrm{Re}{s}_{\mathrm{GMRES}({\mathcal{P}}_{\mathrm{MGSSP}}^{-1}\mathcal{A})}$ are similar definitions.

• Remark 4.1. Figures 2 to 7 show that the distribution of eigenvalues of the iteration matrix confirm our above theoretical analysis.

• Remark 4.2. From Tables 2 and 3, it is very easy to see that the preconditioner ${\mathcal{P}}_{\mathrm{NGSSP}}$ and ${\mathcal{P}}_{\mathrm{MGSSP}}$ will improve the convergence of BICGSTAB and GMRES iteration efficiently when they are applied to the preconditioned BICGSTAB and GMRES to solve two-dimensional time-harmonic Maxwell equations by choosing different parameters.

Figure 2.

The eigenvalue distribution for the NGSSP iteration matrix $\mathrm{\Gamma }={\mathcal{P}}_{\mathrm{NGSSP}}^{-1}{\mathcal{R}}_{\mathrm{NGSSP}}$ when $\alpha =0.3,\beta =0.4,\gamma =2.4$ (the first), $\alpha =0.4,\beta =0.9,\gamma =2.1$ (the second), $\alpha =0.7,\beta =0.3,\gamma =2.6$ (the third) and $\alpha =0.8,\beta =0.4,\gamma =2.3$ (the fourth), respectively. Here, $h=\frac{\sqrt{2}}{8}.$

Figure 3.

The eigenvalue distribution for the MGSSP iteration matrix $\mathrm{\Gamma }={\mathcal{P}}_{\mathrm{MGSSP}}^{-1}{\mathcal{R}}_{\mathrm{MGSSP}}$ when $\alpha =0.3,\beta =0.4$ (the first), $\alpha =0.4,\beta =0.9$ (the second), $\alpha =0.7,\beta =0.3$ (the third) and $\alpha =0.8,\beta =0.4$ (the fourth), respectively. Here, $h=\frac{\sqrt{2}}{8}.$

Figure 4.

The eigenvalue distribution for the NGSSP iteration matrix $\mathrm{\Gamma }={\mathcal{P}}_{\mathrm{NGSSP}}^{-1}{\mathcal{R}}_{\mathrm{NGSSP}}$ when $\alpha =0.3,\beta =0.4,\gamma =2.4$ (the first), $\alpha =0.4,\beta =0.9,\gamma =2.1$ (the second), $\alpha =0.7,\beta =0.3,\gamma =2.6$ (the third) and $\alpha =0.8,\beta =0.4,\gamma =2.3$ (the fourth), respectively. Here, $h=\frac{\sqrt{2}}{12}$ .

Figure 5.

The eigenvalue distribution for the MGSSP iteration matrix $\mathrm{\Gamma }={\mathcal{P}}_{\mathrm{MGSSP}}^{-1}{\mathcal{R}}_{\mathrm{MGSSP}}$ when $\alpha =0.3,\beta =0.4$ (the first), $\alpha =0.4,\beta =0.9$ (the second), $\alpha =0.7,\beta =0.3$ (the third) and $\alpha =0.8,\beta =0.4$ (the fourth), respectively. Here, $h=\frac{\sqrt{2}}{12}.$ .

Figure 6.

The eigenvalue distribution for the NGSSP iteration matrix $\mathrm{\Gamma }={\mathcal{P}}_{\mathrm{NGSSP}}^{-1}{\mathcal{R}}_{\mathrm{NGSSP}}$ when $\alpha =0.3,\beta =0.4,\gamma =2.4$ (the first), $\alpha =0.4,\beta =0.9,\gamma =2.1$ (the second), $\alpha =0.7,\beta =0.3,\gamma =2.6$ (the third) and $\alpha =0.8,\beta =0.4,\gamma =2.3$ (the fourth), respectively. Here, $h=\frac{\sqrt{2}}{18}$ .

Figure 7.

The eigenvalue distribution for the MGSSP iteration matrix $\mathrm{\Gamma }={\mathcal{P}}_{\mathrm{MGSSP}}^{-1}{\mathcal{R}}_{\mathrm{MGSSP}}$ when $\alpha =0.3,\beta =0.4$ (the first), $\alpha =0.4,\beta =0.9$ (the second), $\alpha =0.7,\beta =0.3$ (the third) and $\alpha =0.8,\beta =0.4$ (the fourth), respectively. Here, $h=\frac{\sqrt{2}}{18}.$ .

Table 2.

Iteration counts and relative residual about iteration matrices ${\mathcal{P}}_{\mathrm{NGSSP}}^{-1}{\mathcal{R}}_{\mathrm{NGSSP}}$ and ${\mathcal{P}}_{\mathrm{MGSSP}}^{-1}{\mathcal{R}}_{\mathrm{MGSSP}}$ when choosing different parameters, where the unpreconditioned BICGSTAB and GMRES are divergent, respectively. Here, $h=\frac{\sqrt{2}}{8}$ denotes the size of the corresponding grid.

$\alpha$	$\beta$	$\gamma$	$I{t}_{\mathrm{BSTAB}({\mathcal{P}}_{\mathrm{NGSSP}}^{-1}\mathcal{A})}$	$\mathrm{Re}{s}_{\mathrm{BSTAB}({\mathcal{P}}_{\mathrm{NGSSP}}^{-1}\mathcal{A})}$	$\alpha$	$\beta$	$I{t}_{\mathrm{BSTAB}({\mathcal{P}}_{\mathrm{MGSSP}}^{-1}\mathcal{A})}$	$\mathrm{Re}{s}_{\mathrm{BSTAB}({\mathcal{P}}_{\mathrm{MGSSP}}^{-1}\mathcal{A})}$
0.3	0.4	2.4	8.5	$7.8798\times {10}^{-7}$	0.3	0.4	11	$7.0747\times {10}^{-7}$
0.4	0.9	2.1	18.5	$2.4306\times {10}^{-7}$	0.4	0.9	19.5	$2.0105\times {10}^{-7}$
0.7	0.3	2.6	12.5	$6.1063\times {10}^{-7}$	0.7	0.3	17.5	$1.9656\times {10}^{-7}$
0.8	0.4	2.3	17.5	$2.1479\times {10}^{-7}$	0.8	0.4	21	$9.0702\times {10}^{-7}$
$\alpha$	$\beta$	$\gamma$	$I{t}_{\mathrm{GMRES}({\mathcal{P}}_{\mathrm{NGSSP}}^{-1}\mathcal{A})}$	$\mathrm{Re}{s}_{\mathrm{GMRES}({\mathcal{P}}_{\mathrm{NGSSP}}^{-1}\mathcal{A})}$	$\alpha$	$\beta$	$I{t}_{\mathrm{GMRES}({\mathcal{P}}_{\mathrm{MGSSP}}^{-1}\mathcal{A})}$	$\mathrm{Re}{s}_{\mathrm{GMRES}({\mathcal{P}}_{\mathrm{MGSSP}}^{-1}\mathcal{A})}$
0.3	0.4	2.4	14(1)	$6.3022\times {10}^{-7}$	0.3	0.4	16(1)	$8.0257\times {10}^{-7}$
0.4	0.9	2.1	23(1)	$7.3464\times {10}^{-7}$	0.4	0.9	24(1)	$7.1424\times {10}^{-7}$
0.7	0.3	2.6	17(1)	$8.9272\times {10}^{-7}$	0.7	0.3	22(1)	$6.3090\times {10}^{-7}$
0.8	0.4	2.3	23(1)	$6.3406\times {10}^{-7}$	0.8	0.4	25(1)	$9.7498\times {10}^{-7}$

Table 3.

Iteration counts and relative residual about iteration matrices ${\mathcal{P}}_{\mathrm{NGSSP}}^{-1}{\mathcal{R}}_{\mathrm{NGSSP}}$ and ${\mathcal{P}}_{\mathrm{MGSSP}}^{-1}{\mathcal{R}}_{\mathrm{MGSSP}}$ when choosing different parameters, where the unpreconditioned BICGSTAB and GMRES are divergent, respectively. Here, $h=\frac{\sqrt{2}}{12}$ denotes the size of the corresponding grid.

$\alpha$	$\beta$	$\gamma$	$I{t}_{\mathrm{BSTAB}({\mathcal{P}}_{\mathrm{NGSSP}}^{-1}\mathcal{A})}$	$\mathrm{Re}{s}_{\mathrm{BSTAB}({\mathcal{P}}_{\mathrm{NGSSP}}^{-1}\mathcal{A})}$	$\alpha$	$\beta$	$I{t}_{\mathrm{BSTAB}({\mathcal{P}}_{\mathrm{MGSSP}}^{-1}\mathcal{A})}$	$\mathrm{Re}{s}_{\mathrm{BSTAB}({\mathcal{P}}_{\mathrm{MGSSP}}^{-1}\mathcal{A})}$
0.3	0.4	2.4	21.5	$8.2629\times {10}^{-7}$	0.3	0.4	25.5	$3/9364\times {10}^{-7}$
0.4	0.9	2.1	53.5	$6.7852\times {10}^{-7}$	0.4	0.9	55.5	$6/5531\times {10}^{-7}$
0.7	0.3	2.6	31.5	$9.4124\times {10}^{-7}$	0.7	0.3	40.5	$2.1990\times {10}^{-7}$
0.8	0.4	2.3	43.5	$4.8098\times {10}^{-7}$	0.8	0.4	44	$6/3543\times {10}^{-7}$
$\alpha$	$\beta$	$\gamma$	$I{t}_{\mathrm{GMRES}({\mathcal{P}}_{\mathrm{NGSSP}}^{-1}\mathcal{A})}$	$\mathrm{Re}{s}_{\mathrm{GMRES}({\mathcal{P}}_{\mathrm{NGSSP}}^{-1}\mathcal{A})}$	$\alpha$	$\beta$	$I{t}_{\mathrm{GMRES}({\mathcal{P}}_{\mathrm{MGSSP}}^{-1}\mathcal{A})}$	$\mathrm{Re}{s}_{\mathrm{GMRES}({\mathcal{P}}_{\mathrm{MGSSP}}^{-1}\mathcal{A})}$
0.3	0.4	2.4	27(1)	$8.3413\times {10}^{-7}$	0.3	0.4	32(1)	$6.2737\times {10}^{-7}$
0.4	0.9	2.1	46(1)	$7.6712\times {10}^{-7}$	0.4	0.9	48(1)	$6.6276\times {10}^{-7}$
0.7	0.3	2.6	34(1)	$4.9885\times {10}^{-7}$	0.7	0.3	42(1)	$6.8538\times {10}^{-7}$
0.8	0.4	2.3	44(1)	$6.7671\times {10}^{-7}$	0.8	0.4	49(1)	$9.1834\times {10}^{-7}$

Conclusions

In this paper, based on NGSSP preconditioner, we added an acceleration factor $\gamma$ , carried out theoretical analysis and numerical analysis. The purpose of this paper is to add an acceleration factor and then analyze the conditions of parameter convergence. In the actual numerical simulation, the convergence speed can be improved by selecting appropriate parameters.