A two-sweep shift-splitting iterative method for complex symmetric linear systems

1.   Introduction

Consider the linear equations of the form

where $x, b \in \mathcal{C}^{n}$ and $A\in \mathcal{C}^{n\times n}$ is a complex symmetric matrix, whose form is

and $W, T\in \mathcal{R}^{n\times n}$ are real symmetric matrices, with $W$ being positive definite and $T$ positive semidefinite. Here and in the sequel we use $i = \sqrt{-1}$ to denote the imaginary unit. We assume $T\neq 0,$ which implies that $A$ is non-Hermitian. Such kind of linear systems arise in many problems in scientific computing and engineering applications. For more detailed descriptions, we refer to ^[1,8,15,22] and the references therein.

The Hermitian and skew-Hermitian parts of the complex symmetric matrix $A\in \mathcal{C}^{n\times n}$ are given by

respectively, hence, $A\in \mathcal{C}^{n\times n}$ is non-Hermitian, but positive definite matrix. Here $A^{*}$ is used to denote the conjugate transpose of the matrix $A.$ Based on the Hermitian and skew-Hermitian splitting (HSS)

of the matrix $A\in \mathcal{C}^{n\times n}$, Bai et al. ^[2] gave HSS iteration method, which is as follows:

The HSS Iteration Method ^[2]. Let $x^{(0)}\in \mathcal{C}^{n}$ be arbitrary initial guess. For $k = 0, 1, 2, ...$ until the sequence of iterates $\{x^{(k)}\}_{k = 0}^{\infty}\subset \mathcal{C}^{n}$ converges, compute the next iterate $x^{(k+1)}$ according to the following procedure:

where $\alpha$ is a given positive constant and $I$ is the identity matrix.

However, a potential difficulty with the HSS iteration method is the need to solve the shifted skew-Hermitian sub-system of linear equations at each iteration step, which is as difficult as that of the original problem; see ^{[2,3,7,10,12,13,14,16,31]} for more detailed descriptions about the HSS iteration method and its variants. Recently, by making use of the special structure of the coefficient matrix $A\in \mathcal{C}^{n\times n}$, Bai et al. established the following modified HSS iteration (MHSS) method and a preconditioned MHSS (PMHSS) method for solving the complex symmetric linear system (1.1–1.2) in an analogous fashion to the HSS iteration scheme in ^[8] and ^[6], respectively. Concerning the stationary MHSS iteration method and PMHSS iteration method, Bai et al. ^[6,8] analyzed the convergence. In 2013, based on the ideas of ^[6] and ^[26], Li et al. presented a new approach named as the lopsided PMHSS (LPMHSS) iteration method to solve the complex symmetric linear system of linear equation (1–2). In 2015, Wu concerned with several variants of the HSS iterative method in ^[29]. In 2015, Cao et al. studied two variants of the PMHSS iterative method for a class of complex symmetric indefinite linear systems in ^[22]. In 2018, Chen and Ma constructed the generalized shift-splitting (GSS) preconditioner, and gave the corresponding theoretical analysis and numerical experiments in ^[21]. In 2019, Li and Ma gave the efficient parameterized rotated shift-splitting preconditioner and Euler preconditioner SHSS iterative method for a class of complex symmetric linear systems ^[24,25].

Let $u = x+iy$ and $b = p+iq$ where $x, y, p, q\in \mathcal{R}^{n}.$ Then from ^[1,31] we know that the complex linear system (1) can be recast as the following two-by-two block real equivalent formulation

The system of linear equations (1.4) can be seen as a special case of the generalized saddle point problems ^[19].

To further generalize the GSS iteration method and accelerate its convergence rate, based on the generalized shift-splitting (GSS) preconditioner, we generalize their algorithms and further study the two-sweep shift-splitting (TSSS) preconditioner for complex symmetric linear systems.

The organization of the paper is as follows. In Section 2 we provide the two-sweep shift-splitting (TSSS) preconditioner for complex symmetric linear system (1–2). In Section 3, we establish the convergence of the two-sweep shift-splitting iteration method. Finally, in section 4, one example is provided to demonstrate the feasibility and effectiveness of TSSS preconditioner.

2.   The two-sweep shift-splitting preconditioner

In 2018, based on the iterative methods studied in ^[20,22,30], Chen and Ma ^[21] constructed the generalized shift-splitting of the matrix $\mathcal{A}$, which is as follows:

where $\alpha > 0$ and $\beta > 0$ are two real constants and $I$ is the identity matrix (with appropriate dimension). By this special splitting, the following generalized shift-splitting iterative method can be defined for solving the generalized saddle point problems (1.3):

Algorithm 1: The generalized shift-splitting iterative method ^[21] Given an initial guess $u^{0}$, for $k = 0, 1, 2, ...$, until $\{u^{k}\}$ converges, compute

where $\alpha > 0$ and $\beta > 0$ are two given positive constants.

In this paper, to further generalize the GSS iteration method and accelerate its convergence rate, we propose the two-sweep shift-splitting iterative method, which is as follows:

Algorithm 2: The two-sweep shift-splitting iterative (TSSS) method Given an initial guess $u^{0}$, for $k = 0, 1, 2, ...$, until $\{u^{k}\}$ converges, compute

where $\alpha > 0, \beta > 0$ and $\gamma\geq 0$ are three given constants.

Remark 2.1. Obviously, when $\gamma = 0$, the two-sweep shift-splitting iterative (TSSS) method reduces to the generalized shift-splitting iterative (GSS) method. So, TSSS method is the extension of GSS method. When choosing appropriate patameter $\gamma$, TSSS method will have fast convergence speed.

By simple calculation, the iteration format of the two-sweep shift-splitting iteration is

where

Through further analysis, we can find that Algorithm 2 is actually the following splitting:

The splitting preconditioner corresponds to the two-sweep shift-splitting iteration (2.5) is given by

which is called the two-sweep shift-splitting preconditioner for the generalized saddle point matrix $\mathcal{A}$.

3.   Convergence of TSSS method

In this section, we will study the convergence of the two-sweep shift-splitting iteration method, which is motivated by the corresponding results in ^[30]. Let $\rho(\mathcal{T})$ denote the spectral radius of the matrix $\mathcal{T}$. Then the two-sweep shift-splitting iteration converges if and only if $\rho(\mathcal{T}) < 1$. Let $\lambda$ be an eigenvalue of $\mathcal{T}$ and $[\phi^{*}, \psi^{*}]^{T}$ be the corresponding eigenvector. Then we have

To study the convergence of the two-sweep shift-splitting iteration method, two lemmas are given.

Lemma 3.1. Let $W\in \mathcal{R}^{n\times n}$ be a symmetric positive definite matrix, and $T\in \mathcal{R}^{n\times n}$ be a symmetric positive semidefinite matrix. Let $\mathcal{T}$ be defined as in (2.5) with $\alpha > 0, \beta > 0$ and $\gamma\geq 0$. If $\lambda$ is an eigenvalue of the iteration matrix $\mathcal{T}$, then $\lambda\neq\pm 1.$

Proof. At first, we assume that $\gamma\neq1$. If $\lambda = 1$, then from Eq. (3.1), we can obtain

and

By similar proving process to Lemma 2.1 in ^[21], we can get $\lambda\neq1.$

Then, we will prove $\lambda\neq-1$. If $\lambda = -1$, from Eq. (3.1) we can obtain

and

Multiplying both sides of (3.4) and (3.5) by $\phi^{*}$ and $\psi^{*}$, respectively. Then we have

and

Add up the two sides of the Eq. (3.6) and (3.7), we can obtain

Since $W$ is a symmetric positive define matrix and $T$ is a symmetric positive semidefinite matrix, and $\phi^{*}\phi\geq 0, \psi^{*}\psi\geq 0,$ we can get $\psi = 0$ and $\phi = 0.$ Since, the corresponding vector cannot be zero, which a contradiction. So, we can get $\lambda\neq-1.$

Lemma 3.2. Let $W\in \mathcal{R}^{n\times n}$ be a symmetric positive definite matrix, and $T\in \mathcal{R}^{n\times n}$ be a symmetric positive semidefinite matrix. Let $\lambda$ be an eigenvalue of the iteration matrix $\mathcal{T}$ (with $\alpha > 0, \beta > 0, 0\leq\gamma < 1$) and $[\phi^{*}, \psi^{*}]^{T}$ be the corresponding eigenvector with $\phi, \psi\in \mathcal{C}^{n\times n}.$ Then if $\psi = 0,$ we have $|\lambda| < 1.$

Proof. If $\psi = 0,$ then from (3.1) we get

Since $W$ is symmetric positive definite and $0\leq\gamma < 1$, then by ^[12] we can obtain

Theorem 3.3. Let $W\in \mathcal{R}^{n\times n}$ be a symmetric positive definite matrix, and $T\in \mathcal{R}^{n\times n}$ be a symmetric positive semidefinite matrix. Let $\rho(\mathcal{T})$ denote the spectral radius of the two-sweep shift-splitting iteration matrix $\mathcal{T}$. Then it holds that

i.e., the two-sweep shift-splitting iterative method converges to the unique solution of the generalized saddle point problems (1.3).

Proof. Let $\lambda$ be an eigenvalue of the iteration matrix $\mathcal{T}$ (with $\alpha > 0, \beta > 0, 0\leq\gamma < 1$) and $[\phi^{*}, \psi^{*}]^{T}$ be the corresponding eigenvector with $\phi, \psi\in \mathcal{C}^{n\times n}.$

If $\psi = 0$, then from Lemma 3.2 we can obtain $|\lambda| < 1.$

If $\psi\neq0$, without loss of generality let $||\psi||_{2} = 1.$ Multiplying both sides of the second equation in Eq. (3.1) by $\psi^{*}$ yields

If $T\psi = 0,$ then Eq. (3.12) implies

If $T\psi\neq0,$ by Lemma 3.1 we have $\lambda\neq-1.$ Then we can get from the first equation in Eq. (3.1) that $\phi = 0$ and

Substituting (3.14) into (3.12), we can obtain

Here, $\bar{\lambda}$ denotes the conjugate of $\lambda.$ Let $\varsigma = \psi^{*}W\psi, \varphi = \phi^{*}\phi, \chi = \phi^{*}W\phi,$ we can obtain from Eq. (3.15)

where $\omega = \frac{1-\lambda}{\lambda+1-2\gamma}.$ Since $\alpha, \beta, \varsigma, \varphi, \chi > 0$ and $0\leq \gamma < 1$, from Eq. (3.16) we have

where $Re(\omega)$ denotes real part of $\omega.$ So, we can obtain

where $Re(\omega)$ and $Im(\omega)$ denote real part and imaginary part of $\omega,$ respectively.

Remark 3.1. ^[20,22,30] From Theorem 3.3, we know that the two-sweep shift-splitting iterative method is convergent unconditionally. However, the convergence of the stationary iteration is typically too slow for the method to be competitive. For this reason, we propose using the Krylov subspace method to accelerate the convergence of the iteration. In particular, Krylov subspace methods apply techniques that involve orthogonal projections onto subspaces of the form

The conjugate gradient method (CG), minimum residual method (MINRES) and generalized minimal residual method (GMRES) are all common iterative 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.

4.   Numerical examples

In this section, we present one example to illustrate the convergence about the generalized shift-splitting iterative (GSS) method and the two-sweep shift-splitting iterative (TSSS) method to solve the linear systems (1.3) when choosing different parameters. Moreover, we define iteration step as It, relative residual error as Res and spectral radius as $\rho$. All numerical examples are carried out in Matlab 7.0. In our experiments, all runs with respect to both GSS method and PSS method are started from initial vector $((x^{(0)})^{T}, (y^{(0)})^{T})^{T} = 0,$ and terminated if the current iteration satisfy ${\rm RES} < 10^{-6}$.

Example 4.1. ^[8] Consider the linear system of equations (1.1) with

where $V = \rm{tridiag}(-1, 2, -1)\in \mathcal{R}^{l\times l}, V_{C} = V-e_{1}e_{l}^{T}-e_{l}e_{1}^{T}\in\mathcal{R}^{l\times l}$ and $e_{1}$ and $e_{l}$ are the first and last unit vectors in $\mathcal{R}^{l}$, respectively. Here $T$ and $K$ correspond to the five-point centered difference matrices approximating the negative Laplacian operator with homogeneous Dirichlet boundary conditions and periodic boundary conditions, respectively, on a uniform mesh in the unit square $[0, 1]\times [0, 1]$ with the mesh-size $h = \frac{1}{l+1}$.

In Figures 1–3, we report the eigenvalue distribution for the generalized shift-splitting iterative (GSS) method and the two-sweep shift-splitting iterative (TSSS) method for different parameter, respectively. In Tables 1–2, we report iteration counts, relative residual and spectral radius about the generalized shift-splitting iterative (GSS) method and the two-sweep shift-splitting iterative (TSSS) method when choosing different parameters. Figures 1–3 and Tables 1–2 show that PSS iterative method have better convergence than GSS iterative method for Example 4.1. Moreover, we can find that TSSS iterative method will have good convergence when parameters $\gamma$ is selected near 0.5, and have slow convergence or diverge when parameters $\gamma$ is selected near 1.

5.   Conclusion

Based on the generalized shift-splitting (GSS) preconditioner, the authors generalize their algorithms and further study the two-sweep shift-splitting (TSSS) preconditioner for complex symmetric linear systems. Moreover, by similar theoretical analysis, we obtain that the two-sweep shift-splitting iterative method is unconditionally convergent. In finally, we present one example to illustrate the convergence about the generalized shift-splitting iterative (GSS) method and the two-sweep shift-splitting iterative (TSSS) method to solve the linear systems (1.3) when choosing different parameters.

Acknowledgments

We would like to thank the referees and editor for helpful comments and suggestions on the manuscript. This research of this author is supported by the National Natural Science Foundation of China (11226337, 11501525, 11961082, 11801528, 61571104, 41906003), Excellent Youth Foundation of Science Technology Innovation of Henan Province (184100510001, 184100510004), Aeronautical Science Foundation of China (2016ZG55019, 2017ZD55014), Basic Research Projects of Key Scientific Research Projects Plan in Henan Higher Education Institutions(20zx003), Science and Technological Research of Key Projects of Henan Province (182102210242, 182102110065), Project of Youth Backbone Teachers of Colleges and Universities of Henan Province (2019GGJS176), Sichuan Science and Technology Program (2019YJ0357).

Conflict of interest

The authors declare there will be no conflict of interest.