Modified Block SSOR Preconditioners for Symmetric Positive Definite Linear Systems

A class of modified block SSOR preconditioners is presented for the symmetric positive definite systems of linear equations, whose coefficient matrices come from the hierarchical-basis finite-element discretizations of the second-order self-adjoint elliptic boundary value problems. These preconditioners include a block SSOR iteration preconditioner, and two inexact block SSOR iteration preconditioners whose diagonal matrices except for the (1,1)-block are approximated by either point symmetric Gauss–Seidel iterations or incomplete Cholesky factorizations, respectively. The optimal relaxation factors involved in these preconditioners and the corresponding optimal condition numbers are estimated in details through two different approaches used by Bank, Dupont and Yserentant (Numer. Math. 52 (1988) 427–458) and Axelsson (Iterative Solution Methods (Cambridge University Press, 1994)). Theoretical analyses show that these modified block SSOR preconditioners are very robust, have nearly optimal convergence rates, and especially, are well suited to difficult problems with rough solutions, discretized using highly nonuniform, adaptively refined meshes.     

Structured preconditioners for nonsingular matrices of block two-by-two structures

For the large sparse block two-by-two real nonsingular matrices, we establish a general framework of practical and efficient structured preconditioners through matrix transformation and matrix approximations. For the specific versions such as modified block Jacobi-type, modified block Gauss-Seidel-type, and modified block unsymmetric (symmetric) Gauss-Seidel-type preconditioners, we precisely describe their concrete expressions and deliberately analyze eigenvalue distributions and positive definiteness of the preconditioned matrices. Also, we show that when these structured preconditioners are employed to precondition the Krylov subspace methods such as GMRES and restarted GMRES, fast and effective iteration solvers can be obtained for the large sparse systems of linear equations with block two-by-two coefficient matrices. In particular, these structured preconditioners can lead to efficient and high-quality preconditioning matrices for some typical matrices from the real-world applications.

     

On SSOR‐like preconditioners for non‐Hermitian positive definite matrices

We construct, analyze, and implement SSOR‐like preconditioners for non‐Hermitian positive definite system of linear equations when its coefficient matrix possesses either a dominant Hermitian part or a dominant skew‐Hermitian part. We derive tight bounds for eigenvalues of the preconditioned matrices and obtain convergence rates of the corresponding SSOR‐like iteration methods as well as the corresponding preconditioned GMRES iteration methods. Numerical implementations show that Krylov subspace iteration methods such as GMRES, when accelerated by the SSOR‐like preconditioners, are efficient solvers for these classes of non‐Hermitian positive definite linear systems. Copyright © 2015 John Wiley & Sons, Ltd.     

A fast LU update for linear programming

This paper discusses sparse matrix kernels of simplex-based linear programming software. State-of-the-art implementations of the simplex method maintain an LU factorization of the basis matrix which is updated at each iteration. The LU factorization is used to solve two sparse sets of linear equations at each iteration. We present new implementation techniques for a modified Forrest-Tomlin LU update which reduce the time complexity of the update and the solution of the associated sparse linear systems. We present numerical results on Netlib and other real-life LP models.     

并行矩阵多分裂块松弛迭代算法

并行矩阵多分裂块松弛迭代算法白中治（复旦大学数学研究所）ＰＡＲＡＬＬＥＬＭＡＴＲＩＸＭＵＬＴＩＳＰＬＩＴＴＩＮＧＢＬＯＣＫＲＥＬＡＸＡＴＩＯＮＩＴＥＲＡＴＩＯＮＭＥＴＨＯＤＳ￥ＢａｔＺｈｏｎｇ－ｚｈｉ（ＩｎｓｔｉｔｕｔｅｏｆＭａｔｈｅｍａｔｉｃｓ，Ｍ...     

On HSS-based iteration methods for weakly nonlinear systems

Based on separable property of the linear and the nonlinear terms and on the Hermitian and skew-Hermitian splitting of the coefficient matrix, we present the Picard-HSS and the nonlinear HSS-like iteration methods for solving a class of large scale systems of weakly nonlinear equations. The advantage of these methods over the Newton and the Newton-HSS iteration methods is that they do not require explicit construction and accurate computation of the Jacobian matrix, and only need to solve linear sub-systems of constant coefficient matrices. Hence, computational workloads and computer memory may be saved in actual implementations. Under suitable conditions, we establish local convergence theorems for both Picard-HSS and nonlinear HSS-like iteration methods. Numerical implementations show that both Picard-HSS and nonlinear HSS-like iteration methods are feasible, effective, and robust nonlinear solvers for this class of large scale systems of weakly nonlinear equations.     

一类弱非线性方程组的Picard-MHSS迭代方法

修正的Hermite/反Hermite分裂(MHSS)迭代方法是一类求解大型稀疏复对称线性代数方程组的无条件收敛的迭代算法.基于非线性代数方程组的特殊结构和性质,我们选取Picard迭代为外迭代方法,MHSS迭代作为内迭代方法,构造了求解大型稀疏弱非线性代数方程组的Picard-MHSS和非线性MHSS-like方法.这两类方法的优点是不需要在每次迭代时均精确计算和存储Jacobi矩阵,仅需要在迭代过程中求解两个常系数实对称正定子线性方程组.除此之外,在一定条件下,给出了两类方法的局部收敛性定理.数值结果证明了这两类方法是可行、有效和稳健的.     

Additive block diagonal preconditioning for block two-by-two linear systems of skew-Hamiltonian coefficient matrices

For a class of block two-by-two systems of linear equations with certain skew-Hamiltonian coefficient matrices, we construct additive block diagonal preconditioning matrices and discuss the eigen-properties of the corresponding preconditioned matrices. The additive block diagonal preconditioners can be employed to accelerate the convergence rates of Krylov subspace iteration methods such as MINRES and GMRES. Numerical experiments show that MINRES preconditioned by the exact and the inexact additive block diagonal preconditioners are effective, robust and scalable solvers for the block two-by-two linear systems arising from the Galerkin finite-element discretizations of a class of distributed control problems.     

三阶线性常微分方程Sinc方程组的结构预处理方法

三阶线性常微分方程在天文学和流体力学等学科的研究中有着广泛的应用.本文介绍求解三阶线性常微分方程由Sinc方法离散所得到的线性方程组的结构预处理方法.首先, 我们利用Sinc方法对三阶线性常微分方程进行离散,证明了离散解以指数阶收敛到原问题的精确解.针对离散后线性方程组的系数矩阵的特殊结构, 提出了结构化的带状预处理子,并证明了预处理矩阵的特征值位于复平面上的一个矩形区域之内.然后, 我们引入新的变量将三阶线性常微分方程等价地转化为由两个二阶线性常微分方程构成的常微分方程组, 并利用Sinc方法对降阶后的常微分方程组进行离散.离散后线性方程组的系数矩阵是分块2×2的, 且每一块都是Toeplitz矩阵与对角矩阵的组合.为了利用Krylov子空间方法有效地求解离散后的线性方程组,我们给出了块对角预处理子, 并分析了预处理矩阵的性质.最后, 我们对降阶后二阶线性常微分方程组进行了一些比较研究.数值结果证实了Sinc方法能够有效地求解三阶线性常微分方程.     

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.     

On a Chebyshev accelerated splitting iteration method with application to two‐by‐two block linear systems

The Chebyshev accelerated preconditioned modified Hermitian and skew‐Hermitian splitting (CAPMHSS) iteration method is presented for solving the linear systems of equations, which have two‐by‐two block coefficient matrices. We derive an iteration error bound to show that the new method is convergent as long as the eigenvalue bounds are not underestimated. Even when the spectral information is lacking, the CAPMHSS iteration method could be considered as an exponentially converging iterative scheme for certain choices of the method parameters. In this case, the convergence rate is independent of the parameters. Besides, the linear subsystems in each iteration can be solved inexactly, which leads to the inexact CAPMHSS iteration method. The iteration error bound of the inexact method is derived also. We discuss in detail the implementation of CAPMHSS for solving two models arising from the Galerkin finite‐element discretizations of distributed control problems and complex symmetric linear systems. The numerical results show the robustness and the efficiency of the new methods.     

A CLASS OF NEW PARALLEL HYBRID ALGEBRAIC MULTILEVEL ITERATIONS

1. IntroductionConsider the large sparse system of linear equationsAx = b, (1.1)where, for a fixed positive integer cr, A e L(R") is a symmetric positive definite (SPD) matrir,having the bloCked formx,b E R" are the uDknwn and the known vectors, respectively, having the correspondingblocked formsni(ni S n, i = 1, 2,', a) are a given positthe integers, satisfying Z ni = n. This systemi= 1of linear equations often arises in sultable finite element discretizations of many secondorderseifad…     

块SSOR迭代法的收敛性

本文在矩阵A为一般非奇方阵的情况下，讨论了解线性方程组AX=b的块SSOR迭代法（SSOR迭代法）的收敛性，得到了几个新的结果．     

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.     

Rotated block triangular preconditioning based on PMHSS

Based on the PMHSS preconditioning matrix, we construct a class of rotated block triangular preconditioners for block two-by-two matrices of real square blocks, and analyze the eigen-properties of the corresponding preconditioned matrices. Numerical experiments show that these rotated block triangular preconditioners can be competitive to and even more efficient than the PMHSS pre-conditioner when they are used to accelerate Krylov subspace iteration methods for solving block two-by-two linear systems with coefficient matrices possibly of nonsymmetric sub-blocks.     

On SSOR iteration method for a class of block two-by-two linear systems

In this paper, the optimal iteration parameters of the symmetric successive overrelaxation (SSOR) method for a class of block two-by-two linear systems are obtained, which result in optimal convergence factor. An accelerated variant of the SSOR (ASSOR) method is presented, which significantly improves the convergence rate of the SSOR method. Furthermore, a more practical way to choose iteration parameters for the ASSOR method has also been proposed. Numerical experiments demonstrate the efficiency of the SSOR and ASSOR methods for solving a class of block two-by-two linear systems with the optimal parameters.     

块Toeplitz方程组的快速块Gauss-Seidel迭代算法

本文研究块Toeplitz方程组的块Gauss-Seidel迭代算法。我们首先讨论了块三角Toeplitz矩阵的一些性质,然后给出了求解块三角Toeplitz矩阵逆的快速算法,由此而得到了求解块Toeplitz方程组的快速块Gauss-Seidel迭代算法,最后证明了当系数矩阵为对称正定和H-矩阵时该方法都收敛,数值例子验证了方法的收敛性。     

几乎各向同性的高维空间分数阶扩散方程的分块快速正则Hermite分裂预处理方法

一类空间分数阶扩散方程经过有限差分离散后所得到的离散线性方程组的系数矩阵是两个对角矩阵与Toeplitz型矩阵的乘积之和.在本文中,对于几乎各向同性的二维或三维空间分数阶扩散方程的离散线性方程组,采用预处理Krylov子空间迭代方法,我们利用其系数矩阵的特殊结构和具体性质构造了一类分块快速正则Hermite分裂预处理子.通过理论分析,我们证明了所对应的预处理矩阵的特征值大部分都聚集于1的附近.数值实验也表明,这类分块快速正则Hermite分裂预处理子可以明显地加快广义极小残量(GMRES)方法和稳定化的双共轭梯度(BiCGSTAB)方法等Krylov子空间迭代方法的收敛速度.     

A CLASS OF ASYNCHRONOUS MATRIX MULTI-SPLITTING MULTI-PARAMETER RELAXATION ITERATIONS

1.IntroductionMultisplittingmethodsforgettingthesolutionoflargesparsesystemoflinearequationsAx=b,A=(and)6L(Rn)nonsingular,x=(x.),b=(b.)eR"(1.1)areefficientparalleliterativemethodswhicharebasedonseveralsplittingsofthecoefficientmatrixAEL(R").Following[11th…     

块AOR迭代法的收敛性

本文推广了解线性方程组的AOR迭代法,给出了块AOR迭代法(BAOR迭代法).文中引进了块M-矩阵,块H-矩阵,块严格对角优势矩阵,块Hermite正定矩阵,块相容次序矩阵和广义块相容次序矩阵等概念.在线性方程组的系数矩阵分别具有上述性质的假设下,讨论了BAOR迭代法的敛散性.