New convergence results on the global GMRES method for diagonalizable matrices

In the present paper, we give some new convergence results of the global GMRES method for multiple linear systems. In the case where the coefficient matrix A is diagonalizable, we derive new upper bounds for the Frobenius norm of the residual. We also consider the case of normal matrices and we propose new expressions for the norm of the residual.     

Iterative solutions to coupled Sylvester-transpose matrix equations

This note studies the iterative solutions to the coupled Sylvester-transpose matrix equation with a unique solution. By using the hierarchical identification principle, an iterative algorithm is presented for solving this class of coupled matrix equations. It is proved that the iterative solution consistently converges to the exact solution for any initial values. Meanwhile, sufficient conditions are derived to guarantee that the iterative solutions given by the proposed algorithm converge to the exact solution for any initial matrices. Finally, a numerical example is given to illustrate the efficiency of the proposed approach.     

A class of new iterative methods for general mixed variational inequalities

In this paper, we use the auxiliary principle technique to suggest a class of predictor-corrector methods for solving general mixed variational inequalities. The convergence of the proposed methods only requires the partially relaxed strongly monotonicity of the operator, which is weaker than co-coercivity. As special cases, we obtain a number of known and new results for solving various classes of variational inequalities and related problems.     

Least squares solution with the minimum-norm to general matrix equations via iteration

Two iterative algorithms are presented in this paper to solve the minimal norm least squares solution to a general linear matrix equations including the well-known Sylvester matrix equation and Lyapunov matrix equation as special cases. The first algorithm is based on the gradient based searching principle and the other one can be viewed as its dual form. Necessary and sufficient conditions for the step sizes in these two algorithms are proposed to guarantee the convergence of the algorithms for arbitrary initial conditions. Sufficient condition that is easy to compute is also given. Moreover, two methods are proposed to choose the optimal step sizes such that the convergence speeds of the algorithms are maximized. Between these two methods, the first one is to minimize the spectral radius of the iteration matrix and explicit expression for the optimal step size is obtained. The second method is to minimize the square sum of the F-norm of the error matrices produced by the algorithm and it is shown that the optimal step size exits uniquely and lies in an interval. Several numerical examples are given to illustrate the efficiency of the proposed approach.     

A priori error bounds on invariant subspace approximations by block Krylov subspaces

We derive a priori error bounds for the block Krylov subspace methods in terms of “the sine” between the desired invariant subspace and the block Krylov subspace. The obtained results can be seen as the block analogue of the classical a priori estimates for standard projection methods.     

Computation of matrix functions with deflated restarting

A deflated restarting Krylov subspace method for approximating a function of a matrix times a vector is proposed. In contrast to other Krylov subspace methods, the performance of the method in this paper is better. We further show that the deflating algorithm inherits the superlinear convergence property of its unrestarted counterpart for the entire function and present the results of numerical experiments.     

An iterative algorithm for the least squares bisymmetric solutions of the matrix equations

In this paper, an iterative algorithm is constructed to solve the minimum Frobenius norm residual problem: min over bisymmetric matrices. By this algorithm, for any initial bisymmetric matrix X₀, a solution X^* can be obtained in finite iteration steps in the absence of roundoff errors, and the solution with least norm can be obtained by choosing a special kind of initial matrix. Furthermore, in the solution set of the above problem, the unique optimal approximation solution to a given matrix in the Frobenius norm can be derived by finding the least norm bisymmetric solution of a new corresponding minimum Frobenius norm problem. Given numerical examples show that the iterative algorithm is quite effective in actual computation.     

A note on the efficiency of the conjugate gradient method for a class of time‐dependent problems

We discuss the efficiency of the conjugate gradient (CG) method for solving a sequence of linear systems; Auⁿ⁺¹ = uⁿ, where A is assumed to be sparse, symmetric, and positive definite. We show that under certain conditions the Krylov subspace, which is generated when solving the first linear system Au¹ = u⁰, contains the solutions {uⁿ} for subsequent time steps. The solutions of these equations can therefore be computed by a straightforward projection of the right‐hand side onto the already computed Krylov subspace. Our theoretical considerations are illustrated by numerical experiments that compare this method with the order‐optimal scheme obtained by applying the multigrid method as a preconditioner for the CG‐method at each time step. Copyright © 2007 John Wiley & Sons, Ltd.     

Decreasing solutions and convex solutions of the polynomial-like iterative equation

In this paper we prove the existence and uniqueness of decreasing solutions for the polynomial-like iterative equation so as to answer Problem 2 in [J. Zhang, L. Yang, W. Zhang, Some advances on functional equations, Adv. Math. (China) 24 (1995) 385-405] (or Problem 3 in [W. Zhang, J.A. Baker, Continuous solutions of a polynomial-like iterative equation with variable coefficients, Ann. Polon. Math. 73 (2000) 29-36]). Furthermore, we completely investigate increasing convex (or concave) solutions and decreasing convex (or concave) solutions of this equation so that the results obtained in [W. Zhang, K. Nikodem, B. Xu, Convex solutions of polynomial-like iterative equations, J. Math. Anal. Appl. 315 (2006) 29-40] are improved.     

Construction of continuous solutions and stability for the polynomial-like iterative equation

Most of known results such as existence, uniqueness and stability for polynomial-like iterative equations were given under the assumption that the coefficient of the first order iteration term does not vanish. The existence with a non-zero leading coefficient was therefore raised as an open problem. It was positively answered for local C¹ solutions later. In this paper this problem is answered further by constructing C⁰ solutions. Moreover, we discuss the stability of those C⁰ solutions, which consequently implies a result of the stability for iterative roots.     

Gradient based and least squares based iterative algorithms for matrix equations AXB + CXD = F

This paper develops a gradient based and a least squares based iterative algorithms for solving matrix equation AXB + CX^TD = F. The basic idea is to decompose the matrix equation (system) under consideration into two subsystems by applying the hierarchical identification principle and to derive the iterative algorithms by extending the iterative methods for solving Ax = b and AXB = F. The analysis shows that when the matrix equation has a unique solution (under the sense of least squares), the iterative solution converges to the exact solution for any initial values. A numerical example verifies the proposed theorems.     

Iterative solutions to the Kalman-Yakubovich-conjugate matrix equation

Two operations are introduced for complex matrices. In terms of these two operations an infinite series expression is obtained for the unique solution of the Kalman-Yakubovich-conjugate matrix equation. Based on the obtained explicit solution, some iterative algorithms are given for solving this class of matrix equations. Convergence properties of the proposed algorithms are also analyzed by using some properties of the proposed operations for complex matrices.     

A note on iterative roots of PM functions

In this paper we study iterative roots of PM functions, a special class of non-monotone functions. Problem 2 in [W. Zhang, PM functions, their characteristic intervals and iterative roots, Ann. Polon. Math. LXV (1997) 119-128] is solved partly and Theorem 4 in that paper is generalized.     

A SHIFT-SPLITTING PRECONDITIONER FOR NON-HERMITIAN POSITIVE DEFINITE MATRICES

A shift splitting concept is introduced and, correspondingly, a shift-splitting iteration scheme and a shift-splitting preconditioner are presented, for solving the large sparse system of linear equations of which the coefficient matrix is an ill-conditioned non-Hermitian positive definite matrix. The convergence property of the shift-splitting iteration method and the eigenvalue distribution of the shift-splitting preconditioned matrix are discussed in depth, and the best possible choice of the shift is investigated in detail. Numerical computations show that the shift-splitting preconditioner can induce accurate, robust and effective preconditioned Krylov subspace iteration methods for solving the large sparse non-Hermitian positive definite systems of linear equations.     

A simple strategy for varying the restart parameter in GMRES()

When solving a system of linear equations with the restarted GMRES method, a fixed restart parameter is typically chosen. We present numerical experiments that demonstrate the beneficial effects of changing the value of the restart parameter in each restart cycle on the total time to solution. We propose a simple strategy for varying the restart parameter and provide some heuristic explanations for its effectiveness based on analysis of the symmetric case.     

A new subspace iteration method for the algebraic Riccati equation

We consider the numerical solution of the continuous algebraic Riccati equation A*X + XA ? XFX + G = 0, with F = F*,G = G* of low rank and A large and sparse. We develop an algorithm for the low‐rank approximation of X by means of an invariant subspace iteration on a function of the associated Hamiltonian matrix. We show that the sought‐after approximation can be obtained by a low‐rank update, in the style of the well known Alternating Direction Implicit (ADI) iteration for the linear equation, from which the new method inherits many algebraic properties. Moreover, we establish new insightful matrix relations with emerging projection‐type methods, which will help increase our understanding of this latter class of solution strategies. Copyright © 2014 John Wiley & Sons, Ltd.     

A note on Krylov subspace methods for singular systems

Recently, Calvetti et al. have published an interesting paper [Linear Algebra Appl. 316 (2000) 157–169] concerning the least-squares solution of a singular system by using the so-called range restricted GMRES (RRGMRES) method. However, one of the main results (cf. [loc. cit., Theorem 3.3]) seems to be incomplete. As a complement of paper [loc. cit.], in this note we first make an example to show the incompleteness of that theorem, then we give a modified result.