A new splitting and preconditioner for iteratively solving non-Hermitian positive definite systems

A new iteration method for solving a linear system with coefficient matrix being non-Hermitian positive definite is presented in this note. We study the spectral radius and contraction properties of the iteration matrix and then analyze the best possible choice of the parameter. With the results obtained, we show that the new method is convergent for a non-Hermitian positive definite linear system and propose a preconditioner to improve the condition number of the system. The numerical examples show that the new method is much more efficient than the HSS (or PSS) iteration method.     

A general class of shift-splitting preconditioners for non-Hermitian saddle point problems with applications to time-harmonic eddy current models

Based on a general splitting of the (1,1) leading block matrix, we first construct a general class of shift-splitting (GCSS) preconditioners for non-Hermitian saddle point problems. Convergence conditions of the corresponding matrix splitting iteration methods and preconditioning properties of the GCSS preconditioned saddle point matrices are analyzed. Then the GCSS preconditioner is specifically applied to the non-Hermitian saddle point problems arising from the finite element discretizations of the hybrid formulations of the time-harmonic eddy current models. With suitable choices of the splittings, the new GCSS preconditioners are easier to implement and have faster convergence rates than the existing shift-splitting preconditioner and its modified variant. Two numerical examples are presented to verify the theoretical results and show effectiveness of the new proposed preconditioners.     

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.     

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.     

On parameterized matrix splitting preconditioner for the saddle point problems

In this paper, we present a parameterized matrix splitting (PMS) preconditioner for the large sparse saddle point problems. The preconditioner is based on a parameterized splitting of the saddle point matrix, resulting in a fixed-point iteration. The convergence theorem of the new iteration method for solving large sparse saddle point problems is proposed by giving the restrictions imposed on the parameter. Based on the idea of the parameterized splitting, we further propose a modified PMS preconditioner. Some useful properties of the preconditioned matrix are established. Numerical implementations show that the resulting preconditioner leads to fast convergence when it is used to precondition Krylov subspace iteration methods such as generalized minimal residual method.     

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

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

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

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

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.     

The general two-sweep modulus-based matrix splitting iteration method for solving linear complementarity problems

In this paper, we present a general two-sweep modulus-based iteration method to solve a class of linear complementarity problems. Convergence analysis shows that the general two-sweep modulus-based matrix splitting iteration method will converge to the exact solution of linear complementarity problem under appropriate conditions. Numerical experiments further show that the proposed methods are superior to the existing methods in actual implementation.     

Adaptive dynamic programming for discrete-time linear quadratic regulation based on multirate generalised policy iteration

In this paper, we propose two multirate generalised policy iteration (GPI) algorithms applied to discrete-time linear quadratic regulation problems. The proposed algorithms are extensions of the existing GPI algorithm that consists of the approximate policy evaluation and policy improvement steps. The two proposed schemes, named heuristic dynamic programming (HDP) and dual HDP (DHP), based on multirate GPI, use multi-step estimation (M-step Bellman equation) at the approximate policy evaluation step for estimating the value function and its gradient called costate, respectively. Then, we show that these two methods with the same update horizon can be considered equivalent in the iteration domain. Furthermore, monotonically increasing and decreasing convergences, so called value iteration (VI)-mode and policy iteration (PI)-mode convergences, are proved to hold for the proposed multirate GPIs. Further, general convergence properties in terms of eigenvalues are also studied. The data-driven online implementation methods for the proposed HDP and DHP are demonstrated and finally, we present the results of numerical simulations performed to verify the effectiveness of the proposed methods.     

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.     

Rank-two residue iteration method for nonnegative matrix factorization

Rank-one residue iteration (RRI) is a recently developed block coordinate method for nonnegative matrix factorization (NMF). Numerical results show that the decomposed matrices generated by RRI method may have several columns, which are zero vectors. In this paper, by studying two special kinds of quadratic programming, we develop two block coordinate methods for NMF, rank-two residue iteration (RTRI) method and rank-two modified residue iteration (RTMRI) method. In the two algorithms, the exact solution of the subproblem can be obtained directly. We also provide that the consequence generated by our proposed algorithms can converge to a stationary point. Numerical results show that the RTRI method and the RTMRI method can yield better solutions, especially RTMRI method can remedy the limitation of the RRI method.     

Efficient preconditioned NHSS iteration methods for solving complex symmetric linear systems

Based on the new HSS (NHSS) iteration method introduced by Pour and Goughery (2015), we propose a preconditioned variant of NHSS (P*NHSS) and an efficient parameterized P*NHSS (PPNHSS) iteration methods for solving a class of complex symmetric linear systems. The convergence properties of the P*NHSS and the PPNHSS iteration methods show that the iterative sequences are convergent to the unique solution of the linear system for any initial guess when the parameters are properly chosen. Moreover, we discuss the quasi-optimal parameters which minimize the upper bounds for the spectral radius of the iteration matrices. Numerical results show that the PPNHSS iteration method is superior to several iteration methods whether the experimental optimal parameters are used or not.     

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.     

Iteration methods for Fredholm integral equations of the second kind

In this paper, we propose an efficient iteration algorithm for Fredholm integral equations of the second kind. We show that for every step of iteration the coefficient matrix of the linear system to be inverted remains the same as in the original approximation methods, while we obtain the superconvergence rates for every step of iteration. We apply our iteration methods to various approximation methods such as degenerate kernel methods, Galerkin, collocation and new projection methods. We illustrate our results by numerical experiments.     

New high-order convergence iteration methods without employing derivatives for solving nonlinear equations

A family of new iteration methods without employing derivatives is proposed in this paper. We have proved that these new methods are quadratic convergence. Their efficiency is demonstrated by numerical experiments. The numerical experiments show that our algorithms are comparable to well-known methods of Newton and Steffensen. Furthermore, combining the new method with bisection method we construct another new high-order iteration method with nice asymptotic convergence properties of the diameters (b_n − a_n).     

Alternating splitting waveform relaxation method and its successive overrelaxation acceleration

For the large sparse implicit linear initial value problem, we present a block successive overrelaxation scheme for the alternating direction implicit waveform relaxation method to further accelerate its convergence speed, and discuss the convergence property of the resulting iteration method in detail. Numerical implementations about several non-Hermitian implicit linear initial value problems show that the alternating direction implicit waveform relaxation method is very effective, and the block successive overrelaxation technique really accelerates its convergence speed.     

Parameterized generalized shift-splitting preconditioners for nonsymmetric saddle point problems

To solve nonsymmetric saddle point problems, the parameterized generalized shift-splitting (PGSS) preconditioner is presented and analyzed. The corresponding PGSS iteration method can be applied not only to the nonsingular saddle point problems but also to the singular ones. The convergence and semi-convergence of the PGSS iteration method are discussed carefully. Meanwhile, the spectral properties of the preconditioned matrix and the strategy of the choices of the parameters are given. Numerical experiments further demonstrate that the PGSS iteration method and the PGSS preconditioner are efficient and have better performance than some existing iteration methods and newly proposed preconditioners, respectively, for solving both the nonsingular and singular nonsymmetric saddle point problems.     

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.