An efficient two-step iterative method for solving a class of complex symmetric linear systems

In this paper, a new two-step iterative method called the two-step parameterized (TSP) iteration method for a class of complex symmetric linear systems is developed. We investigate its convergence conditions and derive the quasi-optimal parameters which minimize the upper bound of the spectral radius of the iteration matrix of the TSP iteration method. Meanwhile, some more practical ways to choose iteration parameters for the TSP iteration method are proposed. Furthermore, comparisons of the TSP iteration method with some existing ones are given, which show that the upper bound of the spectral radius of the TSP iteration method is smaller than those of the modified Hermitian and skew-Hermitian splitting (MHSS), the preconditioned MHSS (PMHSS), the combination method of real part and imaginary part (CRI) and the parameterized variant of the fixed-point iteration adding the asymmetric error (PFPAE) iteration methods proposed recently. Inexact version of the TSP iteration (ITSP) method and its convergence properties are also presented. Numerical experiments demonstrate that both TSP and ITSP are effective and robust when they are used either as linear solvers or as matrix splitting preconditioners for the Krylov subspace iteration methods and they have comparable advantages over some known ones for the complex symmetric linear systems.     

广义修正HSS迭代法的超松弛加逮

通过推广修正埃尔米特和反埃尔米特（MHSS）迭代法,我们进一步得到了求解大型稀疏非埃尔米特正定线性方程组的广义MHSS（GMHSS）迭代法．基于不动点方程,我们还将超松弛（SOR）技术运用到了GMHSS迭代法,得到了关于GMHSS迭代法的SOR加速,并分析了它的收敛性．数值算例表明,SOR技术能够大大提高加速GMHSS迭代法的收敛效率．     

非Hermitian正定线性方程组的外推的广义HSS方法

探讨了如何高效求解非Hermitian正定线性方程组,提出了一种外推的广义Hermitian和反Hermitian (EGHSS) 迭代方法。首先,根据矩阵的广义Hermitian和反Hermitian分裂,构造出了一种新的非对称的二步迭代格式。接着,理论分析了新方法的收敛性,并给出了新方法收敛的充要条件。数值实验结果表明,在处理某些问题时,EGHSS迭代方法比GHSS迭代方法和EHSS迭代方法更有效。     

Generalized successive overrelaxation iterative method for a class of complex symmetric linear system of equations

In this paper, to solve a broad class of complex symmetric linear systems, we recast the complex system in a real formulation and apply the generalized successive overrelaxation (GSOR) iterative method to the equivalent real system. We then investigate its convergence properties and determine its optimal iteration parameter as well as its corresponding optimal convergence factor. In addition, the resulting GSOR preconditioner is used to precondition Krylov subspace methods such as the generalized minimal residual method for solving the real equivalent formulation of the system. Finally, we give some numerical experiments to validate the theoretical results and compare the performance of the GSOR method with the modified Hermitian and skew-Hermitian splitting iteration.     

A variant of the HSS preconditioner for complex symmetric indefinite linear systems

Using the equivalent block two-by-two real linear systems, we establish a new variant of the Hermitian and skew-Hermitian splitting (HSS) preconditioner for a class of complex symmetric indefinite linear systems. The new preconditioner is not only a better approximation to the block two-by-two real coefficient matrix than the well-known HSS preconditioner, but also resulting in an unconditional convergent fixed-point iteration. The quasi-optimal parameter, which minimizes an upper bound of the spectral radius of the iteration matrix, is analyzed. Eigen-properties and an upper bound of the degree of the minimal polynomial of the preconditioned matrix are discussed. Finally, two numerical examples are provided to show the efficiency of the new preconditioner.     

Two-parameter generalized Hermitian and skew-Hermitian splitting iteration method

It is known that the Hermitian and skew-Hermitian splitting (HSS) iteration method is an efficient solver for non-Hermitian positive-definite linear system of equations. Benzi [A generalization of the Hermitian and skew-Hermitian splitting iteration, SIAM J. Matrix Anal. Appl. 31 (2009), pp. 360–374] proposed a generalized HSS (GHSS) iteration method. In this paper, we present a two-parameter version of the GHSS (TGHSS) method and investigate its convergence properties. To show the effectiveness of the proposed method the TGHSS iteration method is applied to image restoration and convection–diffusion problems and the results are compared with those of the HSS and GHSS methods.     

On semi-convergence of Hermitian and skew-Hermitian splitting methods for singular linear systems

For the singular, non-Hermitian, and positive semidefinite systems of linear equations, we derive necessary and sufficient conditions for guaranteeing the semi-convergence of the Hermitian and skew-Hermitian splitting (HSS) iteration methods. We then investigate the semi-convergence factor and estimate its upper bound for the HSS iteration method. If the semi-convergence condition is satisfied, it is shown that the semi-convergence rate is the same as that of the HSS iteration method applied to a linear system with the coefficient matrix equal to the compression of the original matrix on the range space of its Hermitian part, that is, the matrix obtained from the original matrix by restricting the domain and projecting the range space to the range space of the Hermitian part. In particular, an upper bound is obtained in terms of the largest and the smallest nonzero eigenvalues of the Hermitian part of the coefficient matrix. In addition, applications of the HSS iteration method as a preconditioner for Krylov subspace methods such as GMRES are investigated in detail, and several examples are used to illustrate the theoretical results and examine the numerical effectiveness of the HSS iteration method served either as a preconditioner for GMRES or as a solver.     

求解鞍点问题的广义正定和反Hermitian分裂方法

探讨了如何求解大型稀疏鞍点问题,给出了一种基于正定分裂的广义正定和反Hermitian分裂(GPSS)方法。该方法首先利用矩阵的正定分裂,构造出鞍点矩阵的2种分裂格式;然后利用这2种分裂格式构造出GPSS迭代;接着给出了迭代收敛的充要条件。最后进行了数值对比实验,实验结果表明,GPSS比正定和反Hermitian分裂(PSS)和Hermitian和反Hermitian分裂(HSS)方法更有效。     

Preconditioned HSS iteration method and its non-alternating variant for continuous Sylvester equations

Bai (2010) proposed an efficient Hermitian and skew-Hermitian splitting (HSS) iteration method for solving a broad class of large sparse continuous Sylvester equations. To further improve the efficiency of the HSS method, in this paper we present a preconditioned HSS (PHSS) iteration method and its non-alternating variant (NPHSS) for this matrix equation. The convergence properties of the PHSS and NPHSS methods are studied in depth and the quasi-optimal values of the iteration parameters for the two methods are also derived. Moreover, to reduce the computational cost, we establish the inexact variants of the two iteration methods. Numerical experiments illustrate the efficiency and robustness of the two iteration methods and their inexact variants.     

On the semi-convergence of preconditioned GLHSS iteration method for non-Hermitian singular saddle point problem

Recently, Fan and Zheng studied the preconditioned generalized local Hermitian and skew-Hermitian splitting (GLHSS) iteration method for non-Hermitian singular saddle point problem, and given its semi-convergence conditions; see Fan and Zheng (2014). In this note, we prove the semi-convergence of preconditioned GLHSS method by another method. The obtained result shows that the conditions for guaranteeing its semi-convergence are easy to check and more weaker.     

The Generalized Modified Hermitian and Skew-Hermitian Splitting Method for the Generalized Lyapunov Equation

In this paper, we propose the generalized modified Hermitian and skew-Hermitian splitting (GMHSS) approach for computing the generalized Lyapunov equation. The GMHSS iteration is convergent to the unique solution of the generalized Lyapunov equation. Moreover, we discuss the convergence analysis of the GMHSS algorithm. Further, the inexact version of the GMHSS (IGMHSS) method is formulated to improve the GMHSS method. Finally, some numerical experiments are carried out to demonstrate the effectiveness and competitiveness of the derived methods

     

On convergence of splitting iteration methods for non-Hermitian positive-definite linear systems

A new splitting iteration method is presented for the system of linear equations when the coefficient matrix is a non-Hermitian positive-definite matrix. The spectral radius, the optimal parameter, and some norm properties of the iteration matrix for the new method are discussed in detail. Based on these results, the new method is convergent under reasonable conditions for any non-Hermitian positive-definite linear system. Finally, the numerical examples show that the new method is more effective than the Hermitian and skew-Hermitian splitting iterative (or positive-definite and skew-Hermitian splitting iterative) method in central processing unit time.     

Modified alternating direction-implicit iteration method for linear systems from the incompressible Navier–Stokes equations

In order to solve the large sparse systems of linear equations arising from numerical solutions of two-dimensional steady incompressible viscous flow problems in primitive variable formulation, Ran and Yuan [On modified block SSOR iteration methods for linear systems from steady incompressible viscous flow problems, Appl. Math. Comput. 217 (2010), pp. 3050–3068] presented the block symmetric successive over-relaxation (BSSOR) and the modified BSSOR iteration methods based on the special structures of the coefficient matrices. In this study, we present the modified alternating direction-implicit (MADI) iteration method for solving the linear systems. Under suitable conditions, we establish convergence theorems for the MADI iteration method. In addition, the optimal parameter involved in the MADI iteration method is estimated in detail. Numerical experiments show that the MADI iteration method is a feasible and effective iterative solver.     

On damped algebraic Riccati equations

In a recent paper, an algorithm was proposed which produces dampening controllers based on damped algebraic Riccati equations (DAREs) derived from a periodic Hamiltonian system. The solution to one of these DAREs is symmetric and the other is skew-symmetric; both of these solutions lead to a dampening feedback, i.e., a stable closed-loop system for which the real parts of the eigenvalues are larger in modulus than the imaginary parts. In this paper, the authors extend these results to include a broader class of damped algebraic Riccati equations which have Hermitian and skew-Hermitian solutions and show that every convex combination of these solutions produces a dampening feedback. This property can be used to vary the feedback with two parameters and thus obtain more flexibility in the controller design process     

并行J-变量块Cholesky分解算法的仿真研究

该文提出一个针对大型实对称正定稠密方程组或复对称非Hermitian稠密方程组线性求解器的并行分布式算法。它使用了不同于ScaLAPACK的J-变量块Cholesky分解算法和一维块循环列数据分配。该算法以MPI作为消息传递库，在最多可达16个处理器的集群上针对实对称正定稠密方程组可提供与ScaLAPACK近似的浮点操作性能，并可解决一些涉及复对称非Hermitian稠密方程组的电磁场散射问题。该算法的优点是执行Cholesky分解所需的存储量只是标准并行库ScaLAPACK的一半。仿真的数值结果表明该算法是正确、有效的。     

Preconditioned accelerated generalized successive overrelaxation method for solving complex symmetric linear systems

In this paper, by adopting the preconditioned technique for the accelerated generalized successive overrelaxation method (AGSOR) proposed by Edalatpour et al. (2015), we establish the preconditioned AGSOR (PAGSOR) iteration method for solving a class of complex symmetric linear systems. The convergence conditions, optimal iteration parameters and corresponding optimal convergence factor of the PAGSOR iteration method are determined. Besides, we prove that the spectral radius of the PAGSOR iteration method is smaller than that of the AGSOR one under proper restrictions, and its optimal convergence factor is smaller than that of the preconditioned symmetric block triangular splitting (PSBTS) one put forward by Zhang et al. (2018) recently. The spectral properties of the preconditioned PAGSOR matrix are also proposed. Numerical experiments illustrate the correctness of the theories and the effectiveness of the proposed iteration method and the preconditioner for the generalized minimal residual (GMRES) method.     

A fast interative method for solving regularized parameter identification problems in elliptic boundary value problems

We study the regularization method applied to the numerical identification of the diffusion coefficienta(x) within a linear two-point boundary value problem of 2nd order. For solving the corresponding regularized discrete nonlinear minimization problems the Gauss-Newton method is analyzed. We describe an effective way for performing one iteration step which requires to solve only two tridiagonal systems of equations.     

On the efficient and accurate solution of the skew-symmetric eigenvalue problem: An arrangement of new and already known algorithmic formulations

Algorithms are presented to solve the special eigenvalue problem $\text{AZ}\text{=}\text{Zλ}$, where $\text{A}$ is skew-symmetric. The effective use of Householder's method, the bisection method and inverse iteration for solving the complete eigen-value problem are described in some detail. Simultaneous vector iteration is formulated for skew-symmetric matrices. The amount of work for the skew-symmetric Jacobi algorithm and the simultaneous vector iteration may be reduced by using the solution of a simplified eigenvalue problem. For Hermitian matrices also quadratic eigenvalue bounds for groups of eigenvalues and linear bounds for groups of eigenvectors are derived. The case where the set of calculated eigenvectors is not orthonormal is considered in some detail. In principle, the skew-symmetric eigenvalue problem may be easily transformed into a symmetric eigenvalue problem; but such a procedure has the following disadvantages: first, the results are in general less accurate, and, second, the eigenvectors which belong to well separated eigenvalues are not uniquely determined.     

An incomplete factorization iterative technique for elliptic equations

This paper describes efficient iterative techniques for solving the large sparse symmetric linear systems that arise from application of finite difference approximations to self-adjoint elliptic equations. We use an incomplete factorization technique with the method of D'Yakonov type, generalized conjugate gradient and Chebyshev semi-iterative methods. We compare these methods with numerical examples. Bounds for the 4-norm of the error vector of the Chebyshev semi-iterative method in terms of the spectral radius of the iteration matrix are derived.