Semiconvergence of block SOR method for singular linear systems with p-cyclic matrices

In this paper, we discuss semiconvergence of the block SOR method for solving singular linear systems with p-cyclic matrices. Some sufficient conditions for the semiconvergence of the block SOR method for solving a general p-cyclic singular system are proved.     

Semiconvergence of nonnegative splittings for singular matrices

Summary. In this paper, we discuss semiconvergence of the matrix splitting methods for solving singular linear systems. The concepts that a splitting of a matrix is regular or nonnegative are generalized and we introduce the terminologies that a splitting is quasi-regular or quasi-nonnegative. The equivalent conditions for the semiconvergence are proved. Comparison theorem on convergence factors for two different quasi-nonnegative splittings is presented. As an application, the semiconvergence of the power method for solving the Markov chain is derived. The monotone convergence of the quasi-nonnegative splittings is proved. That is, for some initial guess, the iterative sequence generated by the iterative method introduced by a quasi-nonnegative splitting converges towards a solution of the system from below or from above. Received August 19, 1997 / Revised version received August 20, 1998 / Published online January 27, 2000     

AOR iterative methods for rank deficient least squares problems

In this paper we study the semiconvergence of accelerated overrelaxation (AOR) iterative methods for the least squares solution of minimal norm of rank deficient linear systems. Necessary and sufficient conditions for the semiconvergence of the AOR and JOR iterative methods are given. The optimum parameters and the associated convergence factor are derived.     

Generalized iterative methods for semidefinite linear systems

We consider iterative methods for semidefinite systems Ax = b based on splittings A = B ? C, where B is not necessarily nonsingular. Necessary and sufficient conditions for convergence are obtained. These are then used to obtain convergence results for block SOR, block SSOR, and block JOR methods for matrices with semidefinite block diagonal.     

A Stein-Rosenberg theorem for rectangular matrices

In the theory of iterative methods, the classical Stein-Rosenberg theorem can be viewed as giving the simultaneous convergence (or divergence) of the extrapolated Jacobi (JOR) matrix $\text{J}$_ω and the successive overrelaxation (SOR) matrix $\text{L}$_ω, in the case when the Jacobi matrix $\text{J}$₁ is nonegative. As has been established by Buoni and Varga, necessary and sufficient conditions for the simultaneous convergence (or divergence) of $\text{J}$_ω and $\text{L}$_ω have been established which do not depend on the assumption that $\text{J}$₁ is nonnegative. More recently, Buoni, Neumann, and Varga extended these results to the singular case, using the notion of semiconvergence. The aim here is to extend these results to consistent rectangular systems.     

Convergence of SSOR methods for linear complementarity problems

In this paper, by applying the SSOR splitting, we propose two new iterative methods for solving the linear complementarity problem LCP (M,q). Convergence results for these two methods are presented when M is an H-matrix (and also an M-matrix). Finally, two numerical examples are given to show the efficiency of the presented methods.     

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.     

An inexact parallel splitting augmented Lagrangian method for large system of linear equations

Parallel iterative methods are powerful in solving large systems of linear equations (LEs). The existing parallel computing research results focus mainly on sparse systems or others with particular structure. Most are based on parallel implementation of the classical relaxation methods such as Gauss-Seidel, SOR, and AOR methods which can be efficiently carried out on multiprocessor system. In this paper, we propose a novel parallel splitting operator method in which we divide the coefficient matrix into two or three parts. Then we convert the original problem (LEs) into a monotone (linear) variational inequality problem (VI) with separable structure. Finally, an inexact parallel splitting augmented Lagrangian method is proposed to solve the variational inequality problem (VI). To avoid dealing with the matrix inverse operator, we introduce proper inexact terms in subproblems such that the complexity of each iteration of the proposed method is O(n²). In addition, the proposed method does not require any special structure of system of LEs under consideration. Convergence of the proposed methods in dealing with two and three separable operators respectively, is proved. Numerical computations are provided to show the applicability and robustness of the proposed methods.     

A new optimized iterative method for solving M-matrix linear systems

In this paper, we present a new iterative method for solving a linear system, whose coefficient matrix is an M-matrix. This method includes four parameters that are obtained by the accelerated overrelaxation (AOR) splitting and using the Taylor approximation. First, under some standard assumptions, we establish the convergence properties of the new method. Then, by minimizing the Frobenius norm of the iteration matrix, we find the optimal parameters. Meanwhile, numerical results on test examples show the efficiency of the new proposed method in contrast with the Hermitian and skew-Hermitian splitting (HSS), AOR methods and a modified version of the AOR (QAOR) iteration.

     

Theorems of Stein-Rosenberg type. III. The singular case

In the theory of iterative methods, the classical Stein-Rosenberg theorem can be viewed as giving the simultaneous convergence (or divergence) of the extrapolated Jacobi (JOR) matrix J_ω and the successive overrelaxation (SOR) matrix

, in the case when the Jacobi matrix J₁ is nonnegative. As has been established recently by Buoni and Varga, necessary and sufficient conditions for the simultaneous convergence (or divergence) of J_ω and

have been established which do not depend on the assumption that J₁ is nonnegative. Our aim here is to extend these results to the singular case, using the notion of semiconvergence. In particular, for a real singular matrix A with nonpositive off-diagonal entries, we find conditions (Theorem 3.4) which imply that J_ω and

simultaneously semiconverge for all ω in the real interval [0,1).     

Two class of synchronous matrix multisplitting schemes for solving linear complementarity problems

Many problems in the areas of scientific computing and engineering applications can lead to the solution of the linear complementarity problem LCP (M,q). It is well known that the matrix multisplitting methods have been found very useful for solving LCP (M,q). In this article, by applying the generalized accelerated overrelaxation (GAOR) and the symmetric successive overrelaxation (SSOR) techniques, we introduce two class of synchronous matrix multisplitting methods to solve LCP (M,q). Convergence results for these two methods are presented when M is an H-matrix (and also an M-matrix). Also the monotone convergence of the new methods is established. Finally, the numerical results show that the introduced methods are effective for solving the large and sparse linear complementary problems.     

On algebraic Riccati equations associated with M-matrices

We consider the algebraic Riccati equation for which the four coefficient matrices form an M-matrix K. When K is a nonsingular M-matrix or an irreducible singular M-matrix, the Riccati equation is known to have a minimal nonnegative solution and several efficient methods are available to find this solution. In this paper we are mainly interested in the case where K is a reducible singular M-matrix. Under a regularity assumption on the M-matrix K, we show that the Riccati equation still has a minimal nonnegative solution. We also study the properties of this particular solution and explain how the solution can be found by existing methods.     

Classes of general H-matrices

Let M(A) denote the comparison matrix of a square H-matrix A, that is, M(A) is an M-matrix. H-matrices such that their comparison matrices are nonsingular are well studied in the literature. In this paper, we study characterizations of H-matrices with either singular or nonsingular comparison matrices. The spectral radius of the Jacobi matrix of M(A) and the generalized diagonal dominance property are used in the characterizations. Finally, a classification of the set of general H-matrices is obtained.     

Convergence of two-stage multisplitting method using AOR or SSOR multisplittings

In this paper, we study the convergence of two-stage multisplitting method using AOR or SSOR multisplittings as inner splittings and an outer splitting for solving a linear system whose coefficient matrix is an H-matrix. We also introduce an application of the two-stage multisplitting method.     

Convergence of SSOR multisplitting method for an M-matrix

In this paper, we study the convergence of both the multisplitting method and the relaxed multisplitting method associated with SOR or SSOR multisplittings for solving a linear system whose coefficient matrix is anM-matrix.     

Modulus-based synchronous two-stage multisplitting iteration methods for linear complementarity problems

In order to solve large sparse linear complementarity problems on parallel multiprocessor systems, we construct modulus-based synchronous two-stage multisplitting iteration methods based on two-stage multisplittings of the system matrices. These iteration methods include the multisplitting relaxation methods such as Jacobi, Gauss–Seidel, SOR and AOR of the modulus type as special cases. We establish the convergence theory of these modulus-based synchronous two-stage multisplitting iteration methods and their relaxed variants when the system matrix is an H _?+?-matrix. Numerical results show that in terms of computing time the modulus-based synchronous two-stage multisplitting relaxation methods are more efficient than the modulus-based synchronous multisplitting relaxation methods in actual implementations.     

Theorems on M-splittings of a singular M-matrix which depend on graph structure

Let $\text{A=M?Nε}\text{R}{}^{\mathrm{n\; n}}$ be a splitting. We investigate the spectral properties of the iteration matrix M^-1N by considering the relationships of the graphs of A, M, N, and M^-1N. We call a splitting an M-splitting if M is a nonsingular M-matrix and N?0. For an M-splitting of an irreducible Z-matrix A we prove that the circuit index of M^-1N is the greatest common divisor of certain sets of integers associated with the circuits of A. For M-splittings of a reducible singular M-matrix we show that the spectral radius of the iteration matrix is 1 and that its multiplicity and index are independent of the splitting. These results hold under somewhat weaker assumptions.     

LU decomposition of M-matrices by elimination without pivoting

It is shown that if A or ?A is a singular M-matrix satisfying the generalized diagonal dominance condition y^TA?0 for some vector y? 0, then A can be factored into A = LU by a certain elimination algorithm, where L is a lower triangular M-matrix with unit diagonal and U is an upper triangular M-matrix. The existence of LU decomposition of symmetric permutations of A and for irreducible M-matrices and symmetric M-matrices follow as colollaries. This work is motivated by applications to the solution of homogeneous systems of linear equations Ax = 0, where A or ?A is an M-matrix. These applications arise, e.g., in the analysis of Markov chains, input-output economic models, and compartmental systems. A converse of the theorem metioned above can be established by considering the reduced normal form of A.     

Nonnegativity of principal minors of generalized inverses of P0-matrices

We derive a necessary and sufficient condition under which a reflexive generalized inverse of a singular P₀-matrix is again a P₀-matrix. Simpler conditions are obtained when the rank of the matrix is n?1, where n is the order of the matrix. We then consider the application of these results to singular M-matrices of order n and rank n?1. In particular, for this case we prove that the Moore-Penrose inverse is a P₀-matrix.     

On the convergence of general stationary iterative methods for range‐Hermitian singular linear systems

General stationary iterative methods with a singular matrix M for solving range‐Hermitian singular linear systems are presented, some convergence conditions and the representation of the solution are also given. It can be verified that the general Ortega–Plemmons theorem and Keller theorem for the singular matrix M still hold. Furthermore, the singular matrix M can act as a good preconditioner for solving range‐Hermitian linear systems. Numerical results have demonstrated the effectiveness of the general stationary iterations and the singular preconditioner M. Copyright © 2009 John Wiley & Sons, Ltd.