On the analysis of the unsymmetric successive overrelaxation method when applied top-cyclic matrices

Summary A Determinantal Invariance, associated with consistently ordered weakly cyclic matrices, is given. The DI is then used to obtain a new functional equation which relates the eigenvalues of a particular block Jacobi iteration matrix to the eigenvalues of its associated Unsymmetric Successive Overrelaxation (USSOR) iteration matrix. This functional equation as well as the theory of nonnegative matrices and regular splittings are used to obtain convergence and divergence regions of the USSOR method.     

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.     

The convergence of inexact Chebyshev and Richardson iterative methods for solving linear systems

Summary The Chebyshev and second-order Richardson methods are classical iterative schemes for solving linear systems. We consider the convergence analysis of these methods when each step of the iteration is carried out inexactly. This has many applications, since a preconditioned iteration requires, at each step, the solution of a linear system which may be solved inexactly using an inner iteration. We derive an error bound which applies to the general nonsymmetric inexact Chebyshev iteration. We show how this simplifies slightly in the case of a symmetric or skew-symmetric iteration, and we consider both the cases of underestimating and overestimating the spectrum. We show that in the symmetric case, it is actually advantageous to underestimate the spectrum when the spectral radius and the degree of inexactness are both large. This is not true in the case of the skew-symmetric iteration. We show how similar results apply to the Richardson iteration. Finally, we describe numerical experiments which illustrate the results and suggest that the Chebyshev and Richardson methods, with reasonable parameter choices, may be more effective than the conjugate gradient method in the presence of inexactness.This work was supported in part by National Science Foundation Grants DCR-8412314 and DCR-8502014The work of this author was completed while he was on sabbatical leave at the Centre for Mathematical Analysis and Mathematical Sciences Research Institute at the Australian National University, Canberra, Australia     

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     

Optimum stationary and nonstationary iterative methods for the solution of singular linear systems

Summary A number of iterative methods for the solution of the singular linear systemAx=b (det(A)=0 andb in the range ofA) is analyzed and studied. Among them are the Stationaryk-Step, the Accelerated Overrelaxation (AOR) and the Nonstationary Second Order Chebyshev Semi-Iterative ones. It is proved that, under certain assumptions, the corresponding optimum semiconvergent schemes, which present a great resemblance with their analogs for the nonsingular case, can be determined. Finally, a number of numerical examples shows how one can use the theory to obtain the optimum parameters for each applicable semiconvergent method.     

Convergence theory of extrapolated iterative methods for a certain class of non-symmetric linear systems

Summary A variety of iterative methods considered in [3] are applied to linear algebraic systems of the formAu=b, where the matrixA is consistently ordered [12] and the iteration matrix of the Jacobi method is skew-symmetric. The related theory of convergence is developed and the optimum values of the involved parameters for each considered scheme are determined. It reveals that under the aforementioned assumptions the Extrapolated Successive Underrelaxation method attains a rate of convergence which is clearly superior over the Successive Underrelaxation method [5] when the Jacobi iteration matrix is non-singular.     

Tchebychev acceleration technique for large scale nonsymmetric matrices

Summary The acceleration by Tchebychev iteration for solving nonsymmetric eigenvalue problems is dicussed. A simple algorithm is derived to obtain the optimal ellipse which passes through two eigenvalues in a complex plane relative to a reference complex eigenvalue. New criteria are established to identify the optimal ellipse of the eigenspectrum. The algorithm is fast, reliable and does not require a search for all possible ellipses which enclose the spectrum. The procedure is applicable to nonsymmetric linear systems as well.     

Convergent nonnegative matrices and iterative methods for consistent linear systems

Summary In this paper we study linear stationary iterative methods with nonnegative iteration matrices for solving singular and consistent systems of linear equationsAx=b. The iteration matrices for the schemes are obtained via regular and weak regular splittings of the coefficients matrixA. In certain cases when only some necessary, but not sufficient, conditions for the convergence of the iterations schemes exist, we consider a transformation on the iteration matrices and obtain new iterative schemes which ensure convergence to a solution toAx=b. This transformation is parameter-dependent, and in the case where all the eigenvalues of the iteration matrix are real, we show how to choose this parameter so that the asymptotic convergence rate of the new schemes is optimal. Finally, some applications to the problem of computing the stationary distribution vector for a finite homogeneous ergodic Markov chain are discussed.Research sponsored in part by US Army Research Office     

A note on comparison theorems for nonnegative matrices

Summary In a recent paper, [4], Csordas and Varga have unified and extended earlier theorems, of Varga in [10] and Wonicki in [11], on the comparison of the asymptotic rates of convergence of two iteration matrices induced by two regular splittings. The main purpose of this note is to show a connection between the Csordas-Varga paper and a paper by Beauwens, [1], in which a comparison theorem is developed for the asymptotic rate of convergence of two nonnegative iteration matrices induced by two splittings which are not necessarily regular. Monotonic norms already used in [1] play an important role in our work here.Research supported in part by NSF grant number DMS-8400879     

Extrapolated Gauss-Seidel I and SOR methods for least-squares problems

Summary Recently, special attention has been given in the literature, to the problems of accurately computing the least-squares solution of very largescale over-determined systems of linear equations which occur in geodetic applications. In particular, it has been suggested that one can solve such problems iteratively by applying the block SOR (Successive Overrelaxation) and EGS1 (Extrapolated Gauss Seidel 1) plus semi-iterative methods to a linear system with coefficient matrix 2-cyclic or 3-cyclic. The comparison of 2-block SOR and 3-block SOR was made in [1] and showed that the 2-block SOR is better. In [6], the authors also proved that 3-block EGS1-SI is better than 3-block SOR. Here, we first show that the 2-block DJ (Double Jacobi)-SI, GS-SI and EGS1-SI methods are equivalent and all of them are equivalent to the 3-block EGS1-SI method; then, we prove that the composite methods and 2-block SOR have the same asymptotic rate of convergence, but the former has a better average rate of convergence; finally, numerical experiments are reported, and confirm that the 3-block EGS1-SI is better than the 2-block SOR.     

Comparisons of weak regular splittings and multisplitting methods

Summary Comparison results for weak regular splittings of monotone matrices are derived. As an application we get upper and lower bounds for the convergence rate of iterative procedures based on multisplittings. This yields a very simple proof of results of Neumann-Plemmons on upper bounds, and establishes lower bounds, which has in special cases been conjectured by these authors.Dedicated to the memory of Peter Henrici     

An iterative substructuring algorithm for equilibrium equations

Summary The topic of iterative substructuring methods, and more generally domain decomposition methods, has been extensively studied over the past few years, and the topic is well advanced with respect to first and second order elliptic problems. However, relatively little work has been done on more general constrained least squares problems (or equivalent formulations) involving equilibrium equations such as those arising, for example, in realistic structural analysis applications. The potential is good for effective use of iterative algorithms on these problems, but such methods are still far from being competitive with direct methods in industrial codes. The purpose of this paper is to investigate an order reducing, preconditioned conjugate gradient method proposed by Barlow, Nichols and Plemmons for solving problems of this type. The relationships between this method and nullspace methods, such as the force method for structures and the dual variable method for fluids, are examined. Convergence properties are discussed in relation to recent optimality results for Varga's theory ofp-cyclic SOR. We suggest a mixed approach for solving equilibrium equations, consisting of both direct reduction in the substructures and the conjugate gradient iterative algorithm to complete the computations.Dedicated to R. S. Varga on the occasion of his 60th birthdayResearch completed while pursuing graduate studies sponsored by the Department of Mathematical Sciences, US Air Force Academy, CO, and funded by the Air Force Institute of Technology, WPAFB, OHResearch supported by the Air Force under grant no. AFOSR-88-0285 and by the National Science Foundation under grant no. DMS-89-02121     

QR factorization of Toeplitz matrices

Summary This paper presents a new algorithm for computing theQR factorization of anm×n Toeplitz matrix inO(mn) operations. The algorithm exploits the procedure for the rank-1 modification and the fact that both principal (m–1)×(n–1) submatrices of the Toeplitz matrix are identical. An efficient parallel implementation of the algorithm is possible.     

Fast inversion algorithms of Toeplitz-plus-Hankel matrices

Summary The paper deals with the problems of fast inversion of matricesA=T+H, whereT is Toeplitz andH is Hankel. Several algorithms are presented and compared, among them algorithms working for arbitrary strongly nonsingular matricesA=T+H.     

A note on optimal block-scaling of matrices

Summary After pointing out that two recent results on optimal blockscaling are equivalent, a new short and simple proof of both results is given.Dedicated to Prof. Dr. F.L. Bauer on the occasion of his 60th birthday     

Factorization iterative methods,M-operators andH-operators

Summary We set up here a general formalism for describing factorization iterative methods of the first order and we use it to review various methods that have been proposed in the literature; next we introduce the notions ofM- andH-operators which generalize those of block-M- and block-H-matrices; finally we discuss the properties of factorization iterative methods in relation with characteristic properties ofM- andH-operators.     

On conjugate gradient type methods and polynomial preconditioners for a class of complex non-hermitian matrices

Summary We consider conjugate gradient type methods for the solution of large linear systemsA x=b with complex coefficient matrices of the typeA=T+iI whereT is Hermitian and a real scalar. Three different conjugate gradient type approaches with iterates defined by a minimal residual property, a Galerkin type condition, and an Euclidean error minimization, respectively, are investigated. In particular, we propose numerically stable implementations based on the ideas behind Paige and Saunder's SYMMLQ and MINRES for real symmetric matrices and derive error bounds for all three methods. It is shown how the special shift structure ofA can be preserved by using polynomial preconditioning, and results on the optimal choice of the polynomial preconditioner are given. Also, we report on some numerical experiments for matrices arising from finite difference approximations to the complex Helmholtz equation.This work was supported in part by Cooperatives Agreement NCC 2-387 between the National Aeronautics and Space Administration (NASA) and the Universities Space Research Association (USRA) and by National Science Foundation Grant DCR-8412314     

On the convergence of powers of interval matrices (2)

Summary Let be a real irreduciblen×n interval matrix. Then a necessary and sufficient condition is given for the sequence of the powers of an interval matrix to converge to a matrix which is not the null matrix. In addition a criterion for is proved to decide whether the limit matrix satisfies the condition of symmetry .     

The local convergence of ABS methods for nonlinear algebraic equations

Summary In this paper we consider an extension to nonlinear algebraic systems of the class of algorithms recently proposed by Abaffy, Broyden and Spedicato for general linear systems. We analyze the convergence properties, showing that under the usual assumptions on the function and some mild assumptions on the free parameters available in the class, the algorithm is locally convergent and has a superlinear rate of convergence (per major iteration, which is computationally comparable to a single Newton's step). Some particular algorithms satisfying the conditions on the free parameters are considered.     

Domains of divergence of the USSOR method applied onp-cyclic matrices

Summary Using a recently derived classical type general functional equation, relating the eigenvalues of a weakly cyclic Jacobi iteration matrix to the eigenvalues of its associated Unsymmetric Successive Overrelaxation (USSOR) iteration matrix, we obtain bounds for the convergence of the USSOR method, when applied to systems with ap-cyclic coefficient matrix.