Modulus-Based GSTS Iteration Method for Linear Complementarity Problems

In this paper, a modulus-based generalized skew-Hermitian triangular splitting (MGSTS) iteration method is present for solving a class of linear complementarity problems with the system matrix either being an $H_+$-matrix with non-positive off-diagonal entries or a symmetric positive definite matrix. The convergence of the MGSTS iteration method is studied in detail. By choosing different parameters, a series of existing and new iterative methods are derived, including the modulus-based Jacobi (MJ) and the modulus-based Gauss-Seidel (MGS) iteration methods and so on. Experimental results are given to show the effectiveness and feasibility of the new method when it is employed for solving this class of linear complementarity problems.     

A modified damped Newton method for linear complementarity problems

We present a modified damped Newton method for solving large sparse linear complementarity problems, which adopts a new strategy for determining the stepsize at each Newton iteration. The global convergence of the new method is proved when the system matrix is a nondegenerate matrix. We then apply the matrix splitting technique to this new method, deriving an inexact splitting method for the linear complementarity problems. The global convergence of the resulting inexact splitting method is proved, too. Numerical results show that the new methods are feasible and effective for solving the large sparse linear complementarity problems.     

Skew-Hermitian Triangular Splitting Iteration Methods for Non-Hermitian Positive Definite Linear Systems of Strong Skew-Hermitian Parts

By further generalizing the skew-symmetric triangular splitting iteration method studied by Krukier, Chikina and Belokon (Applied Numerical Mathematics, 41 (2002), pp. 89–105), in this paper, we present a new iteration scheme, called the modified skew-Hermitian triangular splitting iteration method, for solving the strongly non-Hermitian systems of linear equations with positive definite coefficient matrices. We discuss the convergence property and the optimal parameters of this new method in depth. Moreover, when it is applied to precondition the Krylov subspace methods like GMRES, the preconditioning property of the modified skew-Hermitian triangular splitting iteration is analyzed in detail. Numerical results show that, as both solver and preconditioner, the modified skew-Hermitian triangular splitting iteration method is very effective for solving large sparse positive definite systems of linear equations of strong skew-Hermitian parts.     

Two-step modulus-based matrix splitting iteration method for linear complementarity problems

Bai has recently presented a modulus-based matrix splitting iteration method, which is a powerful alternative for solving the large sparse linear complementarity problems. In this paper, we further present a two-step modulus-based matrix splitting iteration method, which consists of a forward and a backward sweep. Its convergence theory is proved when the system matrix is an H ₊-matrix. Moreover, for the two-step modulus-based relaxation iteration methods, more exact convergence domains are obtained without restriction on the Jacobi matrix associated with the system matrix, which improve the existing convergence theory. Numerical results show that the two-step modulus-based relaxation iteration methods are superior to the modulus-based relaxation iteration methods for solving the large sparse linear complementarity problems.     

Two-Stage Multisplitting Iteration Methods Using Modulus-Based Matrix Splitting as Inner Iteration for Linear Complementarity Problems

The matrix multisplitting iteration method is an effective tool for solving large sparse linear complementarity problems. However, at each iteration step we have to solve a sequence of linear complementarity sub-problems exactly. In this paper, we present a two-stage multisplitting iteration method, in which the modulus-based matrix splitting iteration and its relaxed variants are employed as inner iterations to solve the linear complementarity sub-problems approximately. The convergence theorems of these two-stage multisplitting iteration methods are established. Numerical experiments show that the two-stage multisplitting relaxation methods are superior to the matrix multisplitting iteration methods in computing time, and can achieve a satisfactory parallel efficiency.     

关于线性互补问题的模系矩阵分裂迭代方法

模系矩阵分裂迭代方法是求解大型稀疏线性互补问题的有效方法之一.本文的目标是归纳总结模系矩阵分裂迭代方法的最新发展和已有成果,主要内容包括相应的多分裂迭代方法, 二级多分裂迭代方法和两步多分裂迭代方法, 以及这些方法的收敛理论.     

A preconditioned general modulus-based matrix splitting iteration method for linear complementarity problems of <Emphasis Type="Italic">H</Emphasis>-matrices

In this paper, we propose a preconditioned general modulus-based matrix splitting iteration method for solving modulus equations arising from linear complementarity problems. Its convergence theory is proved when the system matrix is an H₊-matrix, from which some new convergence conditions can be derived for the (general) modulus-based matrix splitting iteration methods. Numerical results further show that the proposed methods are superior to the existing methods.     

Skew-symmetric methods for nonsymmetric linear systems with multiple right-hand sides

By transforming nonsymmetric linear systems to the extended skew-symmetric ones, we present the skew-symmetric methods for solving nonsymmetric linear systems with multiple right-hand sides. These methods are based on the block and global Arnoldi algorithm which is formed by implementing orthogonal projections of the initial matrix residual onto a matrix Krylov subspace. The algorithms avoid the tediously long Arnoldi process and highly reduce expensive storage. Numerical experiments show that these algorithms are effective and give better practical performances than global GMRES for solving nonsymmetric linear systems with multiple right-hand sides.     

A two-step modulus-based matrix splitting iteration method for horizontal linear complementarity problems

Numerical Algorithms - In this paper, for solving horizontal linear complementarity problems, a two-step modulus-based matrix splitting iteration method is established. The convergence analysis of...     

Product-type skew-Hermitian triangular splitting iteration methods for strongly non-Hermitian positive definite linear systems

By further generalizing the modified skew-Hermitian triangular splitting iteration methods studied in [L. Wang, Z.-Z. Bai, Skew-Hermitian triangular splitting iteration methods for non-Hermitian positive definite linear systems of strong skew-Hermitian parts, BIT Numer. Math. 44 (2004) 363-386], in this paper, we present a new iteration scheme, called the product-type skew-Hermitian triangular splitting iteration method, for solving the strongly non-Hermitian systems of linear equations with positive definite coefficient matrices. We discuss the convergence property and the optimal parameters of this method. Moreover, when it is applied to precondition the Krylov subspace methods, the preconditioning property of the product-type skew-Hermitian triangular splitting iteration is analyzed in detail. Numerical results show that the product-type skew-Hermitian triangular splitting iteration method can produce high-quality preconditioners for the Krylov subspace methods for solving large sparse positive definite systems of linear equations of strong skew-Hermitian parts.     

一类H矩阵线性互补问题的预处理二步模基矩阵分裂迭代方法

本文我们利用预处理技术推广了求解线性互补问题的二步模基矩阵分裂迭代法,并针对H-矩阵类给出了新方法的收敛性分析,得到的理论结果推广了已有的一些方法.     

Generalized skew‐Hermitian triangular splitting iteration methods for saddle‐point linear systems

A generalized skew‐Hermitian triangular splitting iteration method is presented for solving non‐Hermitian linear systems with strong skew‐Hermitian parts. We study the convergence of the generalized skew‐Hermitian triangular splitting iteration methods for non‐Hermitian positive definite linear systems, as well as spectrum distribution of the preconditioned matrix with respect to the preconditioner induced from the generalized skew‐Hermitian triangular splitting. Then the generalized skew‐Hermitian triangular splitting iteration method is applied to non‐Hermitian positive semidefinite saddle‐point linear systems, and we prove its convergence under suitable restrictions on the iteration parameters. By specially choosing the values of the iteration parameters, we obtain a few of the existing iteration methods in the literature. Numerical results show that the generalized skew‐Hermitian triangular splitting iteration methods are effective for solving non‐Hermitian saddle‐point linear systems with strong skew‐Hermitian parts. Copyright © 2013 John Wiley & Sons, Ltd.     

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.     

Improved convergence theorems of the two-step modulus-based matrix splitting and synchronous multisplitting iteration methods for solving linear complementarity problems

Abstract

In this paper, the convergence conditions of the two-step modulus-based matrix splitting and synchronous multisplitting iteration methods for solving linear complementarity problems of H-matrices are weakened. The convergence domain given by the proposed theorems is larger than the existing ones.     

求解时谐涡流模型鞍点问题的分块交替分裂隐式迭代算法的改进

分块交替分裂隐式迭代方法是求解具有鞍点结构的复线性代数方程组的一类高效迭代法.本文通过预处理技巧得到原方法的一种加速改进方法,称之为预处理分块交替分裂隐式迭代方法·理论分析给出了新方法的收敛性结果.对于一类时谐涡旋电流模型问题,我们给出了若干满足收敛条件的迭代格式.数值实验验证了新型算法是对原方法的有效改进.     

Modified modulus‐based matrix splitting iteration methods for linear complementarity problems

For solving the large sparse linear complementarity problems, we establish modified modulus‐based matrix splitting iteration methods and present the convergence analysis when the system matrices are H₊‐matrices. The optima of parameters involved under some scopes are also analyzed. Numerical results show that in computing efficiency, our new methods are superior to classical modulus‐based matrix splitting iteration methods under suitable conditions. Copyright © 2015 John Wiley & Sons, Ltd.     

求解一类非线性互补问题的松弛two-sweep模系矩阵分裂迭代法

本文构造了求解一类非线性互补问题的松弛two-sweep模系矩阵分裂迭代法. 理论分析建立了新方法在系数矩阵为正定矩阵或H₊矩阵时的收敛性质．数值实验结果表明新方法是行之有效的, 并且在最优参数下松弛two-sweep模系矩阵分裂迭代法在迭代步数和时间上均优于传统的模系矩阵分裂迭代法和two-sweep模系矩阵分裂迭代法.     

Improved convergence theorems of modulus-based matrix splitting iteration methods for linear complementarity problems

We weaken the convergence conditions of modulus-based matrix splitting and matrix two-stage splitting iteration methods for linear complementarity problems. Thus their applied scopes are further extended.     

Inexact non-interior continuation method for monotone semidefinite complementarity problems

Chen and Tseng (Math Program 95:431?C474, 2003) extended non-interior continuation methods for solving linear and nonlinear complementarity problems to semidefinite complementarity problems (SDCP), in which a system of linear equations is exactly solved at each iteration. However, for problems of large size, solving the linear system of equations exactly can be very expensive. In this paper, we propose a version of one of the non-interior continuation methods for monotone SDCP presented by Chen and Tseng that incorporates inexactness into the linear system solves. Only one system of linear equations is inexactly solved at each iteration. The global convergence and local superlinear convergence properties of the method are given under mild conditions.     

Field-of-values analysis of preconditioned iterative methods for nonsymmetric elliptic problems

Summary. The convergence rate of Krylov subspace methods for the solution of nonsymmetric systems of linear equations, such as GMRES or FOM, is studied. Bounds on the convergence rate are presented which are based on the smallest real part of the field of values of the coefficient matrix and of its inverse. Estimates for these quantities are available during the iteration from the underlying Arnoldi process. It is shown how these bounds can be used to study the convergence properties, in particular, the dependence on the mesh-size and on the size of the skew-symmetric part, for preconditioners for finite element discretizations of nonsymmetric elliptic boundary value problems. This is illustrated for the hierarchical basis and multilevel preconditioners which constitute popular preconditioning strategies for such problems. Received May 3, 1996