HSS METHOD WITH A COMPLEX PARAMETER FOR THE SOLUTION OF COMPLEX LINEAR SYSTEM

In this paper, a complex parameter is employed in the Hermitian and skew-Hermitian splitting (HSS) method (Bai, Golub and Ng: SIAM J. Matrix Anal. Appl., 24(2003), 603-626) for solving the complex linear system $Ax=f$. The convergence of the resulting method is proved when the spectrum of the matrix $A$ lie in the right upper (or lower) part of the complex plane. We also derive an upper bound of the spectral radius of the HSS iteration matrix, and an estimated optimal parameter $α$(denoted by $α_{est}$) of this upper bound is presented. Numerical experiments on two modified model problems show that the HSS method with $α_{est}$has a smaller spectral radius than that with the real parameter which minimizes the corresponding upper bound. In particular, for the 'dominant' imaginary part of the matrix $A$, this improvement is considerable. We also test the GMRES method preconditioned by the HSS preconditioning matrix with our parameter $α_{est}$.     

On HSS and AHSS iteration methods for nonsymmetric positive definite Toeplitz systems

Two iteration methods are proposed to solve real nonsymmetric positive definite Toeplitz systems of linear equations. These methods are based on Hermitian and skew-Hermitian splitting (HSS) and accelerated Hermitian and skew-Hermitian splitting (AHSS). By constructing an orthogonal matrix and using a similarity transformation, the real Toeplitz linear system is transformed into a generalized saddle point problem. Then the structured HSS and the structured AHSS iteration methods are established by applying the HSS and the AHSS iteration methods to the generalized saddle point problem. We discuss efficient implementations and demonstrate that the structured HSS and the structured AHSS iteration methods have better behavior than the HSS iteration method in terms of both computational complexity and convergence speed. Moreover, the structured AHSS iteration method outperforms the HSS and the structured HSS iteration methods. The structured AHSS iteration method also converges unconditionally to the unique solution of the Toeplitz linear system. In addition, an upper bound for the contraction factor of the structured AHSS iteration method is derived. Numerical experiments are used to illustrate the effectiveness of the structured AHSS iteration method.     

A generalized preconditioned HSS method for non-Hermitian positive definite linear systems

Based on the HSS (Hermitian and skew-Hermitian splitting) and preconditioned HSS methods, we will present a generalized preconditioned HSS method for the large sparse non-Hermitian positive definite linear system. Our method is essentially a two-parameter iteration which can extend the possibility to optimize the iterative process. The iterative sequence produced by our generalized preconditioned HSS method can be proven to be convergent to the unique solution of the linear system. An exact parameter region of convergence for the method is strictly proved. A minimum value for the upper bound of the iterative spectrum is derived, which is relevant to the eigensystem of the products formed by inverse preconditioner and splitting. An efficient preconditioner based on incremental unknowns is presented for the actual implementation of the new method. The optimality and efficiency are effectively testified by some comparisons with numerical results.     

ON HERMITIAN AND SKEW-HERMITIAN SPLITTING ITERATION METHODS FOR CONTINUOUS SYLVESTER EQUATIONS

We present a Hermitian and skew-Hermitian splitting (HSS) iteration method for solving large sparse continuous Sylvester equations with non-Hermitian and positive definite/semi-definite matrices. The unconditional convergence of the HSS iteration method is proved and an upper bound on the convergence rate is derived. Moreover, to reduce the computing cost, we establish an inexact variant of the HSS iteration method and analyze its convergence property in detail. Numerical results show that the HSS iteration method and its inexact variant are efficient and robust solvers for this class of continuous Sylvester equations.     

Lopsided PMHSS iteration method for a class of complex symmetric linear systems

Based on the preconditioned modified Hermitian and skew-Hermitian splitting (PMHSS) iteration method, we introduce a lopsided PMHSS (LPMHSS) iteration method for solving a broad class of complex symmetric linear systems. The convergence properties of the LPMHSS method are analyzed, which show that, under a loose restriction on parameter α, the iterative sequence produced by LPMHSS method is convergent to the unique solution of the linear system for any initial guess. Furthermore, we derive an upper bound for the spectral radius of the LPMHSS iteration matrix, and the quasi-optimal parameter α ^? which minimizes the above upper bound is also obtained. Both theoretical and numerical results indicate that the LPMHSS method outperforms the PMHSS method when the real part of the coefficient matrix is dominant.     

The semi-convergence properties of MHSS method for a class of complex nonsymmetric singular linear systems

We use the modified Hermitian and skew-Hermitian splitting (MHSS) iteration method to solve a class of complex nonsymmetric singular linear systems. The semi-convergence properties of the MHSS method are studied by analyzing the spectrum of the iteration matrix. Moreover, after investigating the semi-convergence factor and estimating its upper bound for the MHSS iteration method, an optimal iteration parameter that minimizes the upper bound of the semi-convergence factor is obtained. Numerical experiments are used to illustrate the theoretical results and examine the effectiveness of the MHSS method served both as a preconditioner for GMRES method and as a solver.     

A class of upper and lower triangular splitting iteration methods for image restoration

Based on the augmented linear system, a class of upper and lower triangular (ULT) splitting iteration methods are established for solving the linear systems arising from image restoration problem. The convergence analysis of the ULT methods is presented for image restoration problem. Moreover, the optimal iteration parameters which minimize the spectral radius of the iteration matrix of these ULT methods and corresponding convergence factors for some special cases are given. In addition, numerical examples from image restoration are employed to validate the theoretical analysis and examine the effectiveness and competitiveness of the proposed methods. Experimental results show that these ULT methods considerably outperform the newly developed methods such as SHSS and RGHSS methods in terms of the numerical performance and image recovering quality. Finally, the SOR acceleration scheme for the ULT iteration method is discussed.     

A special Hermitian and skew-Hermitian splitting method for image restoration

In this paper, we consider an ill-posed image restoration problem with a noise contaminated observation, and a known convolution kernel. A special Hermitian and skew-Hermitian splitting (HSS) iterative method is established for solving the linear systems from image restoration. Our approach is based on an augmented system formulation. The convergence and operation cost of the special HSS iterative method for image restoration problems are discussed. The optimal parameter minimizing the spectral radius of the iteration matrix is derived. We present a detailed algorithm for image restoration problems. Numerical examples are given to demonstrate the performance of the presented method. Finally, the SOR acceleration scheme for the special HSS iterative method is discussed.     

Alternating-directional PMHSS iteration method for a class of two-by-two block linear systems

In Bai et al. (2013), a preconditioned modified HSS (PMHSS) method was proposed for a class of two-by-two block systems of linear equations. In this paper, the PMHSS method is modified by adding one more parameter in the iteration. Convergence of the modified PMHSS method is guaranteed. Theoretic analysis and numerical experiment show that the modification improves the PMHSS method.     

On the convergence of the minimum residual HSS iteration method

Recently, by applying the minimum residual technique to the Hermitian and skew-Hermitian splitting (HSS) iteration scheme, a minimum residual HSS (MRHSS) iteration method was proposed for solving non-Hermitian positive definite linear systems. Although the MRHSS iteration method is very efficient, it is conditionally convergent. In this work, we further study the convergence of the MRHSS iteration method, and show that it can unconditionally convergent if its parameters are determined by minimizing a new norm of the residual. Numerical results verify that the MRHSS method discussed in this work is also very efficient.     

关于广义鞍点问题的HSS迭代方法的收缩因子(英文)

白中治等提出了解非埃尔米特正定线性方程组的埃尔米特和反埃尔米特分裂(HSS)迭代方法(Bai Z Z,Golub G H,Ng M K.Hermitian and skew-Hermitian splitting methodsfor non-Hermitian positive definite linear systems.SIAM J.Matrix Anal.Appl.,2003,24:603-626).本文精确地估计了用HSS迭代方法求解广义鞍点问题时在加权2-范数和2-范数下的收缩因子.在实际的计算中,正是这些收缩因子而不是迭代矩阵的谱半径,本质上控制着HSS迭代方法的实际收敛速度.根据文中的分析,求解广义鞍点问题的HSS迭代方法的收缩因子在加权2-范数下等于1,在2-范数下它会大于等于1,而在某种适当选取的范数之下,它则会小于1.最后,用数值算例说明了理论结果的正确性.     

A splitting preconditioner for saddle point problems

For large sparse systems of linear equations iterative techniques are attractive. In this paper, we study a splitting method for an important class of symmetric and indefinite system. Theoretical analyses show that this method converges to the unique solution of the system of linear equations for all t>0 (t is the parameter). Moreover, all the eigenvalues of the iteration matrix are real and nonnegative and the spectral radius of the iteration matrix is decreasing with respect to the parameter t. Besides, a preconditioning strategy based on the splitting of the symmetric and indefinite coefficient matrices is proposed. The eigensolution of the preconditioned matrix is described and an upper bound of the degree of the minimal polynomials for the preconditioned matrix is obtained. Numerical experiments of a model Stokes problem and a least‐squares problem with linear constraints presented to illustrate the effectiveness of the method. Copyright © 2011 John Wiley & Sons, Ltd.     

Convergence analysis of modified Newton-HSS method for solving systems of nonlinear equations

Hermitian and skew-Hermitian splitting(HSS) method has been proved quite successfully in solving large sparse non-Hermitian positive definite systems of linear equations. Recently, by making use of HSS method as inner iteration, Newton-HSS method for solving the systems of nonlinear equations with non-Hermitian positive definite Jacobian matrices has been proposed by Bai and Guo. It has shown that the Newton-HSS method outperforms the Newton-USOR and the Newton-GMRES iteration methods. In this paper, a class of modified Newton-HSS methods for solving large systems of nonlinear equations is discussed. In our method, the modified Newton method with R-order of convergence three at least is used to solve the nonlinear equations, and the HSS method is applied to approximately solve the Newton equations. For this class of inexact Newton methods, local and semilocal convergence theorems are proved under suitable conditions. Moreover, a globally convergent modified Newton-HSS method is introduced and a basic global convergence theorem is proved. Numerical results are given to confirm the effectiveness of our method.     

A new optimized iterative method for solving M-matrix linear systems

In this paper, we present a new iterative method for solving a linear system, whose coefficient matrix is an M-matrix. This method includes four parameters that are obtained by the accelerated overrelaxation (AOR) splitting and using the Taylor approximation. First, under some standard assumptions, we establish the convergence properties of the new method. Then, by minimizing the Frobenius norm of the iteration matrix, we find the optimal parameters. Meanwhile, numerical results on test examples show the efficiency of the new proposed method in contrast with the Hermitian and skew-Hermitian splitting (HSS), AOR methods and a modified version of the AOR (QAOR) iteration.

     

Fast and improved scaled HSS preconditioner for steady-state space-fractional diffusion equations

Numerical Algorithms - For the discrete linear system resulted from the considered steady-state space-fractional diffusion equations, we propose an improved scaled HSS (ISHSS) iteration method and...     

On an Uzawa smoother in multigrid for poroelasticity equations

A poroelastic saturated medium can be modeled by means of Biot's theory of consolidation. It describes the time‐dependent interaction between the deformation of porous material and the fluid flow inside of it. Here, for the efficient solution of the poroelastic equations, a multigrid method is employed with an Uzawa‐type iteration as the smoother. The Uzawa smoother is an equation‐wise procedure. It shall be interpreted as a combination of the symmetric Gauss‐Seidel smoothing for displacements, together with a Richardson iteration for the Schur complement in the pressure field. The Richardson iteration involves a relaxation parameter which affects the convergence speed, and has to be carefully determined. The analysis of the smoother is based on the framework of local Fourier analysis (LFA) and it allows us to provide an analytic bound of the smoothing factor of the Uzawa smoother as well as an optimal value of the relaxation parameter. Numerical experiments show that our upper bound provides a satisfactory estimate of the exact smoothing factor, and the selected relaxation parameter is optimal. In order to improve the convergence performance, the acceleration of multigrid by iterant recombination is taken into account. Numerical results confirm the efficiency and robustness of the acceleration scheme.     

基于自适应参数校正策略求解SDP的Mehrotra型内点算法

最近,Salahi对线性规划提出了一个基于新的自适应参数校正策略的Mehrotra型预估-校正算法,该策略使其在不使用安全策略的情况下,证明了算法的多项式迭代复杂界.本文将这一算法推广到半定规划的情形.通过利用Zhang的对称化技术,得到了算法的多项式迭代复杂界,这与求解线性规划的相应算法有相同的迭代复杂性阶.     

Erratum to: “On the HSS iteration methods for positive definite Toeplitz linear systems” [J. Comput. Appl. Math. 224 (2009) 709-718]

In [1], Gu and Tian [Chuanqing Gu, Zhaolu Tian, On the HSS iteration methods for positive definite Toeplitz linear systems, J. Comput. Appl. Math. 224 (2009) 709-718] proposed the special HSS iteration methods for positive definite linear systems Ax=b with A∈C^n×n a complex Toeplitz matrix. But we find that the special HSS iteration methods are incorrect. Some examples are given in our paper.     

Multistep matrix splitting iteration preconditioning for singular linear systems

Multistep matrix splitting iterations serve as preconditioning for Krylov subspace methods for solving singular linear systems. The preconditioner is applied to the generalized minimal residual (GMRES) method and the flexible GMRES (FGMRES) method. We present theoretical and practical justifications for using this approach. Numerical experiments show that the multistep generalized shifted splitting (GSS) and Hermitian and skew-Hermitian splitting (HSS) iteration preconditioning are more robust and efficient compared to standard preconditioners for some test problems of large sparse singular linear systems.     

Diagonal and Toeplitz splitting iteration methods for diagonal‐plus‐Toeplitz linear systems from spatial fractional diffusion equations

The finite difference discretization of the spatial fractional diffusion equations gives discretized linear systems whose coefficient matrices have a diagonal‐plus‐Toeplitz structure. For solving these diagonal‐plus‐Toeplitz linear systems, we construct a class of diagonal and Toeplitz splitting iteration methods and establish its unconditional convergence theory. In particular, we derive a sharp upper bound about its asymptotic convergence rate and deduct the optimal value of its iteration parameter. The diagonal and Toeplitz splitting iteration method naturally leads to a diagonal and circulant splitting preconditioner. Analysis shows that the eigenvalues of the corresponding preconditioned matrix are clustered around 1, especially when the discretization step‐size h is small. Numerical results exhibit that the diagonal and circulant splitting preconditioner can significantly improve the convergence properties of GMRES and BiCGSTAB, and these preconditioned Krylov subspace iteration methods outperform the conjugate gradient method preconditioned by the approximate inverse circulant‐plus‐diagonal preconditioner proposed recently by Ng and Pan (M.K. Ng and J.‐Y. Pan, SIAM J. Sci. Comput. 2010;32:1442‐1464). Moreover, unlike this preconditioned conjugate gradient method, the preconditioned GMRES and BiCGSTAB methods show h‐independent convergence behavior even for the spatial fractional diffusion equations of discontinuous or big‐jump coefficients.