Lopsided PMHSS iteration method for a class of complex symmetric linear systems

Based on the preconditioned modified Hermitian and skew-Hermitian splitting (PMHSS) iteration method, we introduce a lopsided PMHSS (LPMHSS) iteration method for solving a broad class of complex symmetric linear systems. The convergence properties of the LPMHSS method are analyzed, which show that, under a loose restriction on parameter α, the iterative sequence produced by LPMHSS method is convergent to the unique solution of the linear system for any initial guess. Furthermore, we derive an upper bound for the spectral radius of the LPMHSS iteration matrix, and the quasi-optimal parameter α ^? which minimizes the above upper bound is also obtained. Both theoretical and numerical results indicate that the LPMHSS method outperforms the PMHSS method when the real part of the coefficient matrix is dominant.     

A generalized variant of the deteriorated PSS preconditioner for nonsymmetric saddle point problems

Based on the variant of the deteriorated positive-definite and skew-Hermitian splitting (VDPSS) preconditioner developed by Zhang and Gu (BIT Numer. Math. 56:587–604, 2016), a generalized VDPSS (GVDPSS) preconditioner is established in this paper by replacing the parameter α in (2,2)-block of the VDPSS preconditioner by another parameter β. This preconditioner can also be viewed as a generalized form of the VDPSS preconditioner and the new relaxed HSS (NRHSS) preconditioner which has been exhibited by Salkuyeh and Masoudi (Numer. Algorithms, 2016). The convergence properties of the GVDPSS iteration method are derived. Meanwhile, the distribution of eigenvalues and the forms of the eigenvectors of the preconditioned matrix are analyzed in detail. We also study the upper bounds on the degree of the minimum polynomial of the preconditioned matrix. Numerical experiments are implemented to illustrate the effectiveness of the GVDPSS preconditioner and verify that the GVDPSS preconditioned generalized minimal residual method is superior to the DPSS, relaxed DPSS, SIMPLE-like, NRHSS, and VDPSS preconditioned ones for solving saddle point problems in terms of the iterations and computational times.     

PMHSS iteration method and preconditioners for Stokes control PDE-constrained optimization problems

Numerical Algorithms - The preconditioned modified Hermitian/skew-Hermitian splitting (PMHSS) iteration method and the corresponding preconditioning technique can achieve satisfactory results for...     

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.     

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.

     

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.     

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

On the Subspace Projected Approximate Matrix method

We provide a comparative study of the Subspace Projected Approximate Matrix method, abbreviated SPAM, which is a fairly recent iterative method of computing a few eigenvalues of a Hermitian matrix A. It falls in the category of inner-outer iteration methods and aims to reduce the costs of matrix-vector products with A within its inner iteration. This is done by choosing an approximation A ₀ of A, and then, based on both A and A ₀, to define a sequence (A _k ) _k=0 ⁿ of matrices that increasingly better approximate A as the process progresses. Then the matrix A _k is used in the kth inner iteration instead of A.In spite of its main idea being refreshingly new and interesting, SPAM has not yet been studied in detail by the numerical linear algebra community. We would like to change this by explaining the method, and to show that for certain special choices for A ₀, SPAM turns out to be mathematically equivalent to known eigenvalue methods. More sophisticated approximations A ₀ turn SPAM into a boosted version of Lanczos, whereas it can also be interpreted as an attempt to enhance a certain instance of the preconditioned Jacobi-Davidson method.Numerical experiments are performed that are specifically tailored to illustrate certain aspects of SPAM and its variations. For experiments that test the practical performance of SPAM in comparison with other methods, we refer to other sources. The main conclusion is that SPAM provides a natural transition between the Lanczos method and one-step preconditioned Jacobi-Davidson.     

Asymptotic quadratic convergence of the parallel block-Jacobi EVD algorithm with dynamic ordering for Hermitian matrices

The proof of the asymptotic quadratic convergence is provided for the parallel two-sided block-Jacobi EVD algorithm with dynamic ordering for Hermitian matrices. The discussion covers the case of well-separated eigenvalues as well as clusters of eigenvalues. Having p processors, each parallel iteration step consists of zeroing 2p off-diagonal blocks chosen by dynamic ordering with the aim to maximize the decrease of the off-diagonal Frobenius norm. Numerical experiments illustrate and confirm the developed theory.     

Special issue: recent progress on iterative methods for large systems of equations

Let A x = b be a large and sparse system of linear equations where A is a nonsingular matrix. An approximate solution is frequently obtained by applying preconditioned iterations. Consider the matrix B = A + P Q ^T where \(P, Q \in \mathbb {R}^{n \times k}\) are full rank matrices. In this work, we study the problem of updating a previously computed preconditioner for A in order to solve the updated linear system B x = b by preconditioned iterations. In particular, we propose a method for updating a Balanced Incomplete Factorization preconditioner. The strategy is based on the computation of an approximate Inverse Sherman-Morrison decomposition for an equivalent augmented linear system. Approximation properties of the preconditioned matrix and an analysis of the computational cost of the algorithm are studied. Moreover, the results of the numerical experiments with different types of problems show that the proposed method contributes to accelerate the convergence.     

Preconditioned Hermitian and skew-Hermitian splitting methods for non-Hermitian positive semidefinite linear systems

Summary. For the positive semidefinite system of linear equations of a block two-by-two structure, by making use of the Hermitian/skew-Hermitian splitting iteration technique we establish a class of preconditioned Hermitian/skew-Hermitian splitting iteration methods. Theoretical analysis shows that the new method converges unconditionally to the unique solution of the linear system. Moreover, the optimal choice of the involved iteration parameter and the corresponding asymptotic convergence rate are computed exactly. Numerical examples further confirm the correctness of the theory and the effectiveness of the method.Mathematics Subject Classification: 65F10, 65F50, CR: G1.3Subsidized by The Special Funds For Major State Basic Research Projects G1999032803Research supported, in part, by DOE-FC02-01ER4177Revised version received November 5, 2003     

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.     

Modified quasi-Chebyshev acceleration to nonoverlapping parallel multisplitting method

In this study, we propose a modified quasi-Chebyshev acceleration to the nonoverlopping multisplitting iteration method for solving the linear systems A x = b where A is a real symmetric positive definite matrix or an H-matrix. In the process of the parallel multisplitting method, the distributive tasks are parallelly computed by each processor, then a global modified acceleration is used to obtain the solution of the system A x = b for every τ steps, such that the efficiency of the computation can be improved. The convergence theory of the new algorithm is given under some reasonable conditions. Finally, numerical experiments show that the method is efficient and effective.     

Zeros of Jacobi polynomials Pn( α, β)$ P_{n}^{(\alpha ,\beta)} $, − 2 < α, β < − 1

The sequence of Jacobi polynomials \(\{P_{n}^{(\alpha ,\beta )}\}_{n = 0}^{\infty }\) is orthogonal on (??1,1) with respect to the weight function (1 ? x)^α(1 + x)^β provided α > ??1,β > ??1. When the parameters α and β lie in the narrow range ??2 < α, β < ??1, the sequence of Jacobi polynomials \(\{P_{n}^{(\alpha ,\beta )}\}_{n = 0}^{\infty }\) is quasi-orthogonal of order 2 with respect to the weight function (1 ? x)^α+?1(1 + x)^β+?1 and each polynomial of degree n,n ≥?2, in such a Jacobi sequence has n real zeros. We show that any sequence of Jacobi polynomials \(\{P_{n}^{(\alpha ,\beta )}\}_{n = 0}^{\infty }\) with ??2 < α, β < ??1, cannot be orthogonal with respect to any positive measure by proving that the zeros of Pn??1(α,β) do not interlace with the zeros of Pn(α,β) for any \(n \in \mathbb {N},\)n ≥?2, and any α,β lying in the range ??2 < α, β < ??1. We also investigate interlacing properties satisfied by the zeros of equal degree Jacobi polynomials Pn(α,β),Pn(α,β+?1) and Pn(α+?1,β+?1) where ??2 < α, β < ??1. Upper and lower bounds for the extreme zeros of quasi-orthogonal order 2 Jacobi polynomials Pn(α,β) with ??2 < α, β < ??1 are derived.     

Jacobi method for symmetric 4 × 4 matrices converges for every cyclic pivot strategy

The paper studies the global convergence of the Jacobi method for symmetric matrices of size 4. We prove global convergence for all 720 cyclic pivot strategies. Precisely, we show that inequality S(A ^[t+3]) ≤ γ S(A ^[t]), t ≥ 1, holds with the constant γ < 1 that depends neither on the matrix A nor on the pivot strategy. Here, A ^[t] stands for the matrix obtained from A after t full cycles of the Jacobi method and S(A) is the off-diagonal norm of A. We show why three consecutive cycles have to be considered. The result has a direct application on the J-Jacobi method.     

A relaxed positive semi-definite and skew-Hermitian splitting preconditioner for non-Hermitian generalized saddle point problems

For non-Hermitian saddle point linear systems, Pan, Ng and Bai presented a positive semi-definite and skew-Hermitian splitting (PSS) preconditioner (Pan et al. Appl. Math. Comput. 172, 762–771 2006), to accelerate the convergence rate of the Krylov subspace iteration methods like the GMRES method. In this paper, a relaxed positive semi-definite and skew-Hermitian (RPSS) splitting preconditioner based on the PSS preconditioner for the non-Hermitian generalized saddle point problems is considered. The distribution of eigenvalues and the form of the eigenvectors of the preconditioned matrix are analyzed. Moreover, an upper bound on the degree of the minimal polynomial is also studied. Finally, numerical experiments of a model Navier-Stokes equation are presented to illustrate the efficiency of the RPSS preconditioner compared to the PSS preconditioner, the block diagonal preconditioner (BD), and the block triangular preconditioner (BT) in terms of the number of iteration and computational time.     

To the Spectral Theory of One-Dimensional Matrix Dirac Operators with Point Matrix Interactions

We investigate one-dimensional (2p × 2p)-matrix Dirac operators D_X,α and D_X,β with point matrix interactions on a discrete set X. Several results of [4] are generalized to the case of (p × p)-matrix interactions with p > 1. It is shown that a number of properties of the operators D_X,α and D_X,β (self-adjointness, discreteness of the spectrum, etc.) are identical to the corresponding properties of some Jacobi matrices B_X,α and B_X,β with (p × p)-matrix entries. The relationship found is used to describe these properties as well as conditions of continuity and absolute continuity of the spectra of the operators D_X,α and D_X,β. Also the non-relativistic limit at the velocity of light c → ∞ is studied.     

Nikol’skii inequality between the uniform norm and <Emphasis Type="Italic">L</Emphasis><Subscript><Emphasis Type="Italic">q</Emphasis></Subscript>-norm with jacobi weight of algebraic polynomials on an interval

We study the Nikol’skii inequality for algebraic polynomials on the interval [?1, 1] between the uniform norm and the norm of the space L _q ^(α,β) , 1 ≤ q < ∞, with the Jacobi weight ?(α,β)(x) = (1 ? x) ^α (1 + x) ^β , α ≥ β > ?1. We prove that, in the case α > β ≥ ?1/2, the polynomial with unit leading coefficient that deviates least from zero in the space L _q ^(α+1,,β) with the Jacobi weight ? ^(α+1,β)(x) = (1?x) ^α+1(1+x) ^β is the unique extremal polynomial in the Nikol’skii inequality. To prove this result, we use the generalized translation operator associated with the Jacobi weight. We describe the set of all functions at which the norm of this operator in the space L _q ^(α,β) for 1 ≤ q < ∞ and α > β ≥ ?1/2 is attained.     

Restarted Q-Arnoldi-type methods exploiting symmetry in quadratic eigenvalue problems

We investigate how to adapt the Q-Arnoldi method for the case of symmetric quadratic eigenvalue problems, that is, we are interested in computing a few eigenpairs \((\lambda ,x)\) of \((\lambda ^2M+\lambda C+K)x=0\) with M, C, K symmetric \(n\times n\) matrices. This problem has no particular structure, in the sense that eigenvalues can be complex or even defective. Still, symmetry of the matrices can be exploited to some extent. For this, we perform a symmetric linearization \(Ay=\lambda By\), where A, B are symmetric \(2n\times 2n\) matrices but the pair (A, B) is indefinite and hence standard Lanczos methods are not applicable. We implement a symmetric-indefinite Lanczos method and enrich it with a thick-restart technique. This method uses pseudo inner products induced by matrix B for the orthogonalization of vectors (indefinite Gram-Schmidt). The projected problem is also an indefinite matrix pair. The next step is to write a specialized, memory-efficient version that exploits the block structure of A and B, referring only to the original problem matrices M, C, K as in the Q-Arnoldi method. This results in what we have called the Q-Lanczos method. Furthermore, we define a stabilized variant analog of the TOAR method. We show results obtained with parallel implementations in SLEPc.