Convergence of block iterative methods for linear systems arising in the numerical solution of Euler equations

Summary We discuss block matrices of the formA=[A _ij ], whereA _ij is ak×k symmetric matrix,A _ij is positive definite andA _ij is negative semidefinite. These matrices are natural block-generalizations of Z-matrices and M-matrices. Matrices of this type arise in the numerical solution of Euler equations in fluid flow computations. We discuss properties of these matrices, in particular we prove convergence of block iterative methods for linear systems with such system matrices.     

Some properties of generalized K-centrosymmetric H-matrices

Every n×n$n\times n$ generalized K-centrosymmetric matrix A   can be reduced into a 2×2$2\times 2$ block diagonal matrix (see [Z. Liu, H. Cao, H. Chen, A note on computing matrix–vector products with generalized centrosymmetric (centrohermitian) matrices, Appl. Math. Comput. 169 (2) (2005) 1332–1345]). This block diagonal matrix is called the reduced form of the matrix A. In this paper we further investigate some properties of the reduced form of these matrices and discuss the square roots of these matrices. Finally exploiting these properties, the development of structure-preserving algorithms for certain computations for generalized K-centrosymmetric H-matrices is discussed.     

Convergence theorems for block splitting iterative methods for linear systems

In this paper, we will present the block splitting iterative methods with general weighting matrices for solving linear systems of algebraic equations Ax=b$\mathit{Ax}=b$ when the coefficient matrix A is symmetric positive definite of block form, and establish the convergence theories with respect to the general weighting matrices but special splittings. Finally, a numerical example shows the advantage of this method.     

Convergence of block two-stage iterative methods for symmetric positive definite systems

Summary. We study the convergence of two-stage iterative methods for solving symmetric positive definite (spd) systems. The main tool we used to derive the iterative methods and to analyze their convergence is the diagonally compensated reduction (cf. [1]). Received December 11, 1997 / Revised version received March 25, 1999 / Published online May 30, 2001     

Comparison results on preconditioned SOR-type iterative method for Z-matrices linear systems

In this paper, we present some comparison theorems on preconditioned iterative method for solving Z-matrices linear systems, Comparison results show that the rate of convergence of the Gauss–Seidel-type method is faster than the rate of convergence of the SOR-type iterative method.     

Convergence of generalized AOR iterative method for linear systems with strictly diagonally dominant matrices

In this paper, some improvements on Darvishi and Hessari [On convergence of the generalized AOR method for linear systems with diagonally dominant coefficient matrices, Appl. Math. Comput. 176 (2006) 128–133] are presented for bounds of the spectral radius of _lω,r$l_{\omega ,r}$, which is the iterative matrix of the generalized AOR (GAOR) method. Subsequently, some new sufficient conditions for convergence of GAOR method will be given, which improve some results of Darvishi and Hessari [On convergence of the generalized AOR method for linear systems with diagonally dominant coefficient matrices, Appl. Math. Comput. 176 (2006) 128–133].     

Local convergence of the (exact and inexact) iterative aggregation method for linear systems and Markov operators

Summary. The iterative aggregation method for the solution of linear systems is extended in several directions: to operators on Banach spaces; to the method with inexact correction, i.e., to methods where the (inner) linear system is in turn solved iteratively; and to the problem of finding stationary distributions of Markov operators. Local convergence is shown in all cases. Convergence results apply to the particular case of stochastic matrices. Moreover, an argument is given which suggests why the iterative aggregation method works so well for nearly uncoupled Markov chains, as well as for Markov chains with other zero-nonzero structures. Received May 25, 1991/Revised version received February 23, 1994     

Convergence of a generalized MSSOR method for augmented systems

Recently, Wu et al. [S.-L. Wu, T.-Z. Huang, X.-L. Zhao, A modified SSOR iterative method for augmented systems, J. Comput. Appl. Math. 228 (1) (2009) 424-433] introduced a modified SSOR (MSSOR) method for augmented systems. In this paper, we establish a generalized MSSOR (GMSSOR) method for solving the large sparse augmented systems of linear equations, which is the extension of the MSSOR method. Furthermore, the convergence of the GMSSOR method for augmented systems is analyzed and numerical experiments are carried out, which show that the GMSSOR method with appropriate parameters has a faster convergence rate than the MSSOR method with optimal parameters.     

A comparison of error bounds for linear complementarity problems of H-matrices

We give new error bounds for the linear complementarity problem when the involved matrix is an H-matrix with positive diagonals. We find classes of H-matrices for which the new bounds improve considerably other previous bounds. We also show advantages of these new bounds with respect the computational cost. A new perturbation bound of H-matrices linear complementarity problems is also presented.     

Convergence rates of some iterative methods for nonsymmetric algebraic Riccati equations arising in transport theory

We determine and compare the convergence rates of various fixed-point iterations for finding the minimal positive solution of a class of nonsymmetric algebraic Riccati equations arising in transport theory.     

Convergence of nested classical iterative methods for linear systems

Summary Classical iterative methods for the solution of algebraic linear systems of equations proceed by solving at each step a simpler system of equations. When this system is itself solved by an (inner) iterative method, the global method is called a two-stage iterative method. If this process is repeated, then the resulting method is called a nested iterative method. We study the convergence of such methods and present conditions on the splittings corresponding to the iterative methods to guarantee convergence forany number of inner iterations. We also show that under the conditions presented, the spectral radii of the global iteration matrices decrease when the number of inner iterations increases. The proof uses a new comparison theorem for weak regular splittings. We extend our results to larger classes of iterative methods, which include iterative block Gauss-Seidel. We develop a theory for the concatenation of such iterative methods. This concatenation appears when different numbers of inner interations are performed at each outer step. We also analyze block methods, where different numbers of inner iterations are performed for different diagonal blocks.Dedicated to Richard S. Varga on the occasion of his sixtieth birthdayP.J. Lanzkron was supported by Exxon Foundation Educational grant 12663 and the UNISYS Corporation; D.J. Rose was supported by AT&T Bell Laboratories, the Microelectronic Center of North Carolina and the Office of Naval Research under contract number N00014-85-K-0487; D.B. Szyld was supported by the National Science Foundation grant DMS-8807338.     

An optimum iterative method for solving any linear system with a square matrix

A method is presented to solveAx=b by computing optimum iteration parameters for Richardson's method. It requires some information on the location of the eigenvalues ofA. The algorithm yields parameters well-suited for matrices for which Chebyshev parameters are not appropriate. It therefore supplements the Manteuffel algorithm, developed for the Chebyshev case. Numerical examples are described.     

Application of a block modified Chebyshev algorithm to the iterative solution of symmetric linear systems with multiple right hand side vectors

Summary. An adaptive Richardson iteration method is described for the solution of large sparse symmetric positive definite linear systems of equations with multiple right-hand side vectors. This scheme ``learns' about the linear system to be solved by computing inner products of residual matrices during the iterations. These inner products are interpreted as block modified moments. A block version of the modified Chebyshev algorithm is presented which yields a block tridiagonal matrix from the block modified moments and the recursion coefficients of the residual polynomials. The eigenvalues of this block tridiagonal matrix define an interval, which determines the choice of relaxation parameters for Richardson iteration. Only minor modifications are necessary in order to obtain a scheme for the solution of symmetric indefinite linear systems with multiple right-hand side vectors. We outline the changes required. Received April 22, 1993     

The eigenvalue distribution on Schur complements of H-matrices

The paper studies the eigenvalue distribution of some special matrices. Tong in Theorem 1.2 of [Wen-ting Tong, On the distribution of eigenvalues of some matrices, Acta Math. Sinica (China), 20 (4) (1977) 273-275] gives conditions for an n × n matrix A ∈ SD_n ∪ ID_n to have |J_R+(A)| eigenvalues with positive real part, and |J_R-(A)| eigenvalues with negative real part. A counter-example is given in this paper to show that the conditions of the theorem are not true. A corrected condition is then proposed under which the conclusion of the theorem holds. Then the corrected condition is applied to establish some results about the eigenvalue distribution of the Schur complements of H-matrices with complex diagonal entries. Several conditions on the n × n matrix A and the subset α ⊆ N = {1, 2, … , n} are presented such that the Schur complement matrix A/α of the matrix A has eigenvalues with positive real part and eigenvalues with negative real part.     

A parallel implementation of the restarted GMRES iterative algorithm for nonsymmetric systems of linear equations

We describe the parallelisation of the GMRES(c) algorithm and its implementation on distributed-memory architectures, using both networks of transputers and networks of workstations under the PVM message-passing system. The test systems of linear equations considered are those derived from five-point finite-difference discretisations of partial differential equations. A theoretical model of the computation and communication phases is presented which allows us to decide for which values of the parameterc our implementation executes efficiently. The results show that for reasonably large discretisation grids the implementations are effective on a large number of processors.     

On generalized successive overrelaxation methods for augmented linear systems

For the augmented system of linear equations, Golub, Wu and Yuan recently studied an SOR-like method (BIT 41(2001)71–85). By further accelerating it with another parameter, in this paper we present a generalized SOR (GSOR) method for the augmented linear system. We prove its convergence under suitable restrictions on the iteration parameters, and determine its optimal iteration parameters and the corresponding optimal convergence factor. Theoretical analyses show that the GSOR method has faster asymptotic convergence rate than the SOR-like method. Also numerical results show that the GSOR method is more effective than the SOR-like method when they are applied to solve the augmented linear system. This GSOR method is further generalized to obtain a framework of the relaxed splitting iterative methods for solving both symmetric and nonsymmetric augmented linear systems by using the techniques of vector extrapolation, matrix relaxation and inexact iteration. Besides, we also demonstrate a complete version about the convergence theory of the SOR-like method. Subsidized by The Special Funds For Major State Basic Research Projects (No. G1999032803) and The National Natural Science Foundation (No. 10471146), P.R. China     

On algebraic multi-level methods for non-symmetric systems - Comparison results

We establish theoretical comparison results for algebraic multi-level methods applied to non-singular non-symmetric M-matrices. We consider two types of multi-level approximate block factorizations or AMG methods, the AMLI and the MAMLI method. We compare the spectral radii of the iteration matrices of these methods. This comparison shows, that the spectral radius of the MAMLI method is less than or equal to the spectral radius of the AMLI method. Moreover, we establish how the quality of the approximations in the block factorization effects the spectral radii of the iteration matrices. We prove comparisons results for different approximations of the fine grid block as well as for the used Schur complement. We also establish a theoretical comparison between the AMG methods and the classical block Jacobi and block Gauss-Seidel methods.     

Block-iterative methods for consistent and inconsistent linear equations

Summary We shall in this paper consider the problem of computing a generalized solution of a given linear system of equations. The matrix will be partitioned by blocks of rows or blocks of columns. The generalized inverses of the blocks are then used as data to Jacobi- and SOR-types of iterative schemes. It is shown that the methods based on partitioning by rows converge towards the minimum norm solution of a consistent linear system. The column methods converge towards a least squares solution of a given system. For the case with two blocks explicit expressions for the optimal values of the iteration parameters are obtained. Finally an application is given to the linear system that arises from reconstruction of a two-dimensional object by its one-dimensional projections.     

Limiting accuracy of segregated solution methods for nonsymmetric saddle point problems

Nonsymmetric saddle point problems arise in a wide variety of applications in computational science and engineering. The aim of this paper is to discuss the numerical behavior of several nonsymmetric iterative methods applied for solving the saddle point systems via the Schur complement reduction or the null-space projection approach. Krylov subspace methods often produce the iterates which fluctuate rather strongly. Here we address the question whether large intermediate approximate solutions reduce the final accuracy of these two-level (inner–outer) iteration algorithms. We extend our previous analysis obtained for symmetric saddle point problems and distinguish between three mathematically equivalent back-substitution schemes which lead to a different numerical behavior when applied in finite precision arithmetic. Theoretical results are then illustrated on a simple model example.