Modified Hermitian and skew‐Hermitian splitting methods for non‐Hermitian positive‐definite linear systems

To further study the Hermitian and non‐Hermitian splitting methods for a non‐Hermitian and positive‐definite matrix, we introduce a so‐called lopsided Hermitian and skew‐Hermitian splitting and then establish a class of lopsided Hermitian/skew‐Hermitian (LHSS) methods to solve the non‐Hermitian and positive‐definite systems of linear equations. These methods include a two‐step LHSS iteration and its inexact version, the inexact Hermitian/skew‐Hermitian (ILHSS) iteration, which employs some Krylov subspace methods as its inner process. We theoretically prove that the LHSS method converges to the unique solution of the linear system for a loose restriction on the parameter α. Moreover, the contraction factor of the LHSS iteration is derived. The presented numerical examples illustrate the effectiveness of both LHSS and ILHSS iterations. Copyright © 2007 John Wiley & Sons, Ltd.     

‘Modified Hermitian and skew‐Hermitian splitting methods for non‐Hermitian positive‐definite linear systems’ [Numer. Linear Algebra Appl. 14 (2007) 217–235]

In this note, some errors in the article (Numer. Linear Algebra Appl. 2007; 14 :217–235) are pointed out and some correct results are presented. Copyright © 2011 John Wiley & Sons, Ltd.     

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.

     

Several variants of the Hermitian and skew‐Hermitian splitting method for a class of complex symmetric linear systems

This paper is concerned with several variants of the Hermitian and skew‐Hermitian splitting iteration method to solve a class of complex symmetric linear systems. Theoretical analysis shows that several Hermitian and skew‐Hermitian splitting based iteration methods are unconditionally convergent. Numerical experiments from an n‐degree‐of‐freedom linear system are reported to illustrate the efficiency of the proposed methods. Copyright © 2014 John Wiley & Sons, Ltd.     

Convergence properties of preconditioned Hermitian and skew-Hermitian splitting methods for non-Hermitian positive semidefinite matrices

For the non-Hermitian and positive semidefinite systems of linear equations, we derive necessary and sufficient conditions for guaranteeing the unconditional convergence of the preconditioned Hermitian and skew-Hermitian splitting iteration methods. We then apply these results to block tridiagonal linear systems in order to obtain convergence conditions for the corresponding block variants of the preconditioned Hermitian and skew-Hermitian splitting iteration methods.

     

Preconditioners for non‐Hermitian Toeplitz systems

In this paper, we construct new ω‐circulant preconditioners for non‐Hermitian Toeplitz systems, where we allow the generating function of the sequence of Toeplitz matrices to have zeros on the unit circle. We prove that the eigenvalues of the preconditioned normal equation are clustered at 1 and that for (N, N)‐Toeplitz matrices with spectral condition number 𝒪(N^α) the corresponding PCG method requires at most 𝒪(N log² N) arithmetical operations. If the generating function of the Toeplitz sequence is a rational function then we show that our preconditioned original equation has only a fixed number of eigenvalues which are not equal to 1 such that preconditioned GMRES needs only a constant number of iteration steps independent of the dimension of the problem. Numerical tests are presented with PCG applied to the normal equation, GMRES, CGS and BICGSTAB. In particular, we apply our preconditioners to compute the stationary probability distribution vector of Markovian queuing models with batch arrival. Copyright © 2001 John Wiley & Sons, Ltd.     

Optimal parameters in the HSS‐like methods for saddle‐point problems

For the Hermitian and skew‐Hermitian splitting iteration method and its accelerated variant for solving the large sparse saddle‐point problems, we compute their quasi‐optimal iteration parameters and the corresponding quasi‐optimal convergence factors for the more practical but more difficult case that the (1, 1)‐block of the saddle‐point matrix is not algebraically equivalent to the identity matrix. In addition, the algebraic behaviors and the clustering properties of the eigenvalues of the preconditioned matrices with respect to these two iterations are investigated in detail, and the formulas for computing good iteration parameters are given under certain principle for optimizing the distribution of the eigenvalues. Copyright © 2008 John Wiley & Sons, Ltd.     

Quasi‐optimal preconditioners for finite element approximations of diffusion dominated convection–diffusion equations on (nearly) equilateral triangle meshes

The paper is devoted to the spectral analysis of effective preconditioners for linear systems obtained via a finite element approximation to diffusion‐dominated convection–diffusion equations. We consider a model setting in which the structured finite element partition is made by equilateral triangles. Under such assumptions, if the problem is coercive and the diffusive and convective coefficients are regular enough, then the proposed preconditioned matrix sequences exhibit a strong eigenvalue clustering at unity, the preconditioning matrix sequence and the original matrix sequence are spectrally equivalent, and under the constant coefficients assumption, the eigenvector matrices have a mild conditioning. The obtained results allow to prove the conjugate gradient optimality and the generalized minimal residual quasi‐optimality in the case of structured uniform meshes. The interest of such a study relies on the observation that automatic grid generators tend to construct equilateral triangles when the mesh is fine enough. Numerical tests, both on the model setting and in the non‐structured case, show the effectiveness of the proposal and the correctness of the theoretical findings. Copyright © 2014 John Wiley & Sons, Ltd.     

Bounding the spectrum of large Hermitian matrices

Estimating upper bounds of the spectrum of large Hermitian matrices has long been a problem with both theoretical and practical significance. Algorithms that can compute tight upper bounds with minimum computational cost will have applications in a variety of areas. We present a practical algorithm that exploits k-step Lanczos iteration with a safeguard step. The k is generally very small, say 5-8, regardless of the large dimension of the matrices. This makes the Lanczos iteration economical. The safeguard step can be realized with marginal cost by utilizing the theoretical bounds developed in this paper. The bounds establish the theoretical validity of a previous bound estimator that has been successfully used in various applications. Moreover, we improve the bound estimator which can now provide tighter upper bounds with negligible additional cost.     

A class of modified block SSOR preconditioners for symmetric positive definite systems of linear equations

A class of modified block SSOR preconditioners is presented for solving symmetric positive definite systems of linear equations, which arise in the hierarchical basis finite element discretizations of the second order self‐adjoint elliptic boundary value problems. This class of methods is strongly related to two level methods, standard multigrid methods, and Jacobi‐like hierarchical basis methods. The optimal relaxation factors and optimal condition numbers are estimated in detail. Theoretical analyses show that these methods are very robust, and especially well suited to difficult problems with rough solutions, discretized using highly nonuniform, adaptively refined meshes. This revised version was published online in June 2006 with corrections to the Cover Date.     

矩阵正定性的进一步推广

矩阵的正定性在很多领域中都有广泛的应用,其定义得到了一系列的推广.进一步推广了矩阵的正定性,给出了更广义的正定矩阵的定义,并得到了它的若干性质.     

On the Hermitian positive definite solutions of nonlinear matrix equation X + A∗XA = Q

Nonlinear matrix equation X^s + A∗X^−tA = Q, where A, Q are n × n complex matrices with Q Hermitian positive definite, has widely applied background. In this paper, we consider the Hermitian positive definite solutions of this matrix equation with two cases: s ? 1, 0 < t ? 1 and 0 < s ? 1, t ? 1. We derive necessary conditions and sufficient conditions for the existence of Hermitian positive definite solutions for the matrix equation and obtain some properties of the solutions. We also propose iterative methods for obtaining the extremal Hermitian positive definite solution of the matrix equation. Finally, we give some numerical examples to show the efficiency of the proposed iterative methods.     

Hessenberg matrix for sums of Hermitian positive definite matrices and weighted shifts

In this work, we introduce an algebraic operation between bounded Hessenberg matrices and we analyze some of its properties. We call this operation m-sum and we obtain an expression for it that involves the Cholesky factorization of the corresponding Hermitian positive definite matrices associated with the Hessenberg components.This work extends a method to obtain the Hessenberg matrix of the sum of measures from the Hessenberg matrices of the individual measures, introduced recently by the authors for subnormal matrices, to matrices which are not necessarily subnormal.Moreover, we give some examples and we obtain the explicit formula for the m-sum of a weighted shift. In particular, we construct an interesting example: a subnormal Hessenberg matrix obtained as the m-sum of two not subnormal Hessenberg matrices.     

广义正定矩阵的行列式不等式

研究了广义正定矩阵的行列式理论，给出了一些新的结果，推广了Ky Fan、Openheim、Minkowski、Ostrowski-Taussky等著名行列式不等式，削弱了华罗庚不等式的条件．     

An algebraic preconditioning method for M‐matrices: linear versus non‐linear multilevel iteration

In a recent work, the author introduced a robust multilevel incomplete factorization algorithm using spanning trees of matrix graphs (Proceedings of the 1999 International Conference on Preconditioning Techniques for Large Sparse Matrix Problems in Industrial Applications, Hubert H. Humphrey Center, University of Minnesota, 1999, 251–257). Based on this idea linear and non‐linear algebraic multilevel iteration (AMLI) methods are investigated in the present paper. In both cases, the preconditioner is constructed recursively from the coarsest to finer and finer levels. The considered W‐cycles only need diagonal solvers on all levels and additionally evaluate a second‐degree matrix polynomial (linear case), or, perform ν inner GCG‐type iterations (non‐linear case) on every other level. This involves the same type of preconditioner for the corresponding Schur complement. The non‐linear variant has the additional benefit of being free from any method parameters to be estimated. Based on the same type of approximation property similar convergence rates are obtained for linear and non‐linear AMLI, even for a very small number ν of inner iterations, e.g. ν =2,3. The presented methods are robust with respect to anisotropy and discontinuities in the coefficients of the PDEs and can also be applied to unstructured‐grid problems. Copyright © 2002 John Wiley & Sons, Ltd.     

两个Hermitian矩阵的Hadamard乘积的特征值估计

Schur定理规定了半正定矩阵的Hadamard乘积的所有特征值的整体界限,Eric Iksoon lm在同样的条件下确定了每个特征值的特殊的界限,本文给出了Hermitian矩阵的Hadamard乘积的每个特征值的估计,改进和推广了I.Schur和Eric Iksoon Im的相应结果。     

Two‐level preconditioners for serendipity finite element matrices

In this paper an approach to construct algebraic multilevel preconditioners for serendipity finite element matrices is presented. Two‐level preconditioners constructed in the paper allow to obtain multilevel preconditioners in serendipity case using multilevel preconditioners for linear finite element matrices. Copyright © 2006 John Wiley & Sons, Ltd.     

Improved convergence theorems for new Hermitian and skew-Hermitian splitting methods

In this note, based on the previous work by Pour and Goughery (New Hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems Numer. Algor. 69 (2015) 207–225), we further discuss this new Hermitian and skew-Hermitian splitting (described as NHSS) methods for non-Hermitian positive definite linear systems. Some new convergence conditions of the NHSS method are obtained, which are superior to the results in the above paper.     

On inexact Newton methods based on doubling iteration scheme for non‐symmetric algebraic Riccati equations

Newton iteration method can be used to find the minimal non‐negative solution of a certain class of non‐symmetric algebraic Riccati equations. However, a serious bottleneck exists in efficiency and storage for the implementation of the Newton iteration method, which comes from the use of some direct methods in exactly solving the involved Sylvester equations. In this paper, instead of direct methods, we apply a fast doubling iteration scheme to inexactly solve the Sylvester equations. Hence, a class of inexact Newton iteration methods that uses the Newton iteration method as the outer iteration and the doubling iteration scheme as the inner iteration is obtained. The corresponding procedure is precisely described and two practical methods of monotone convergence are algorithmically presented. In addition, the convergence property of these new methods is studied and numerical results are given to show their feasibility and effectiveness for solving the non‐symmetric algebraic Riccati equations. Copyright © 2010 John Wiley & Sons, Ltd.     

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.