Accelerated PMHSS iteration methods for complex symmetric linear systems

In this paper, we introduce and analyze an accelerated preconditioning modification of the Hermitian and skew-Hermitian splitting (APMHSS) iteration method for solving a broad class of complex symmetric linear systems. This accelerated PMHSS algorithm involves two iteration parameters α,β and two preconditioned matrices whose special choices can recover the known PMHSS (preconditioned modification of the Hermitian and skew-Hermitian splitting) iteration method which includes the MHSS method, as well as yield new ones. The convergence theory of this class of APMHSS iteration methods is established under suitable conditions. Each iteration of this method requires the solution of two linear systems with real symmetric positive definite coefficient matrices. Theoretical analyses show that the upper bound σ₁(α,β) of the asymptotic convergence rate of the APMHSS method is smaller than that of the PMHSS iteration method. This implies that the APMHSS method may converge faster than the PMHSS method. Numerical experiments on a few model problems are presented to illustrate the theoretical results and examine the numerical effectiveness of the new method.     

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.     

On preconditioned MHSS iteration methods for complex symmetric linear systems

We propose a preconditioned variant of the modified HSS (MHSS) iteration method for solving a class of complex symmetric systems of linear equations. Under suitable conditions, we prove the convergence of the preconditioned MHSS (PMHSS) iteration method and discuss the spectral properties of the PMHSS-preconditioned matrix. Numerical implementations show that the resulting PMHSS preconditioner leads to fast convergence when it is used to precondition Krylov subspace iteration methods such as GMRES and its restarted variants. In particular, both the stationary PMHSS iteration and PMHSS-preconditioned GMRES show meshsize-independent and parameter-insensitive convergence behavior for the tested numerical examples.     

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}$.     

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.     

MN-DPMHSS iteration method for systems of nonlinear equations with block two-by-two complex Jacobian matrices

Preconditioned modified Hermitian and skew-Hermitian splitting (PMHSS) method is an unconditionally convergent iteration method for solving large sparse complex symmetric systems of linear equation. Motivated by the PMHSS method, we develop a new method of solving a class of linear equations with block two-by-two complex coefficient matrix by introducing two coefficients, noted as DPMHSS. By making use of the DPMHH iteration as the inner solver to approximately solve the Newton equations, we establish modified Newton-DPMHSS (MN-DPMHSS) method for solving large systems of nonlinear equations. We analyze the local convergence properties under the Hölder continuous conditions, which is weaker than Lipschitz assumptions. Numerical results are given to confirm the effectiveness of our method.     

A single-step HSS method for non-Hermitian positive definite linear systems

In this paper, based on the Hermitian and skew-Hermitian splitting (HSS) iteration method, a single-step HSS (SHSS) iteration method is introduced to solve the non-Hermitian positive definite linear systems. Theoretical analysis shows that, under a loose restriction on the iteration parameter, the SHSS method is convergent to the unique solution of the linear system. Furthermore, we derive an upper bound for the spectral radius of the SHSS iteration matrix, and the quasi-optimal parameter is obtained to minimize the above upper bound. Numerical experiments are reported to the efficiency of the SHSS method; numerical comparisons show that the proposed SHSS method is superior to the HSS method under certain conditions.     

On a type of matrix splitting preconditioners for a class of block two-by-two linear systems

Recently, Bai et al. (2013) proposed an effective and efficient matrix splitting iterative method, called preconditioned modified Hermitian/skew-Hermitian splitting (PMHSS) iteration method, for two-by-two block linear systems of equations. The eigenvalue distribution of the iterative matrix suggests that the splitting matrix could be advantageously used as a preconditioner. In this study, the CGNR method is utilized for solving the PMHSS preconditioned linear systems, and the performance of the method is considered by estimating the condition number of the normal equations. Furthermore, the proposed method is compared with other PMHSS preconditioned Krylov subspace methods by solving linear systems arising in complex partial differential equations and a distributed control problem. The numerical results demonstrate the difference in the performance of the methods under consideration.     

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.     

Preconditioned AHSS iteration method for singular saddle point problems

In this paper, for solving the singular saddle point problems, we present a new preconditioned accelerated Hermitian and skew-Hermitian splitting (AHSS) iteration method. The semi-convergence of this method and the eigenvalue distribution of the preconditioned iteration matrix are studied. In addition, we prove that all eigenvalues of the iteration matrix are clustered for any positive iteration parameters α and β. Numerical experiments illustrate the theoretical results and examine the numerical effectiveness of the AHSS iteration method served either as a preconditioner or as a solver.     

A sharp upper bound on the maximal entry in the principal eigenvector of symmetric nonnegative matrix

An upper bound on the maximal entry in the principal eigenvector of a symmetric nonnegative matrix with zero diagonal entries is investigated in [S. Zhao, Y. Hong, On the bounds of maximal entries in the principal eigenvector of symmetric nonnegative matrix, Linear Algebra Appl. 340 (2002) 245-252]. We obtain a sharp upper bound on the maximal entry y^max_p in the principal eigenvector of symmetric nonnegative matrix in terms of order, the spectral radius, the largest and the smallest diagonal entries of that matrix. Our bound is applicable for any symmetric nonnegative matrix and the upper bound of Zhao and Hong (2002) for the maximal entry y^max_p follows as a special case. Moreover, we find an upper bound on maximal entry in the principal eigenvector for the signless Laplacian matrix of a graph.     

A generalized cyclic iterative method for solving variational inequalities over the solution set of a split common fixed point problem

For solving the large-scale linear least-squares problem, we propose a block version of the randomized extended Kaczmarz method, called the two-subspace randomized extended Kaczmarz method, which does not require any row or column paving. Theoretical analysis and numerical results show that the two-subspace randomized extended Kaczmarz method is much more efficient than the randomized extended Kaczmarz method. When the coefficient matrix is of full column rank, the two-subspace randomized extended Kaczmarz method can also outperform the randomized coordinate descent method. If the linear system is consistent, we remove one of the iteration sequences in the two-subspace randomized extended Kaczmarz method, which approximates the projection of the right-hand side vector onto the orthogonal complement space of the range space of the coefficient matrix, and obtain the generalized two-subspace randomized Kaczmarz method, which is actually a generalization of the two-subspace randomized Kaczmarz method without the assumptions of unit row norms and full column rank on the coefficient matrix. We give the upper bound for the convergence rate of the generalized two-subspace randomized Kaczmarz method which also leads to a better upper bound for the convergence rate of the two-subspace randomized Kaczmarz method.

     

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.     

Optimal Parameters for 2-cyclic AOR

Assume A∈C^n×n is a 2-cyclic consistently ordered matrix and J is denoted as its associated block Jacobi iteration matrix. We consider the 2-cyclic AOR method for solving the consistent linear systems Ax=b. In the case that σ(J²) is either nonnegative or nonpositive, we give detailed discussion and derive definite expressions on optimal parameters and spectral radius by efficient method. Moreover, we give some numerical examples.     

Simplified analysis for full-Newton step infeasible interior-point algorithm for semidefinite programming

We present an analysis of the full-Newton step infeasible interior-point algorithm for semidefinite optimization, which is an extension of the algorithm introduced by Roos [C. Roos, A full-Newton step 𝒪(n) infeasible interior-point algorithm for linear optimization, SIAM J. Optim. 16 (2006), pp. 1110–1136] for the linear optimization case. We use the proximity measure σ(V)?=?‖I???V ²‖ to overcome the difficulty of obtaining an upper bound of updated proximity after one full-Newton step, where I is an identity matrix and V is a symmetric positive definite matrix. It turns out that the complexity analysis of the algorithm is simplified and the iteration bound obtained is improved slightly.     

Bifurcation of limit cycles from a 4-dimensional center in 1:n resonance

We study the bifurcation of limit cycles from the periodic orbits of a linear differential system in R⁴ in resonance 1:n perturbed inside a class of piecewise linear differential systems, which appear in a natural way in control theory. Our main result shows that at most 1 limit cycle can bifurcate using expansion of the displacement function up to first order with respect to a small parameter. This upper bound is reached. For proving this result we use the averaging theory in a form where the differentiability of the system is not needed.     

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.     

Error bounds for high-resolution quantization with Rényi-α-entropy constraints

We consider the problem of optimal quantization with norm exponent r > 0 for Borel probability measures on ? ^d under constrained Rényi-α-entropy of the quantizers. If the bound on the entropy becomes large, then sharp asymptotics for the optimal quantization error are well-known in the special cases α = 0 (memory-constrained quantization) and α = 1 (Shannon-entropy-constrained quantization). In this paper we determine sharp asymptotics for the optimal quantization error under large entropy bound with entropy parameter α ∈ [1+r/d,∞]. For α ∈ [0,1 + r/d] we specify the asymptotical order of the optimal quantization error under large entropy bound. The optimal quantization error is decreasing exponentially fast with the entropy bound and the exact rate is determined for all α ∈ [0, ∞].     

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.     

Graph properties for splitting with grounded Laplacian matrices

With any undirected, connected graphG containing no self-loops one can associate the Laplacian matrixL(G). It is also the (singular) admittance matrix of a resistive network with all conductances taken to be unity. While solving the linear system involved, one of the vertices is grounded, so the coefficient matrix is a principal submatrix ofL which we will call the grounded Laplacian matrixL ₁. In this paper we consider iterative solutions of such linear systems using certain regular splittings ofL ₁ and derive an upper bound for the spectral radius of the iteration matrix in terms of the properties of the graphG.This work was supported by the Academy of Finland