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.     

Generalized consistent orderings and the Accelerated Overrelaxation method

In this paper, the behavior of the block Accelerated Overrelaxation (AOR) iterative method, when applied to linear systems with a generalized consistently ordered coefficient matrix, is investigated. An equation, relating the eigenvalues of the block Jacobi iteration matrix to the eigenvalues of its associated block AOR iteration matrix, as well as sufficient conditions for the convergence of the block AOR method, are obtained.     

Precise domains of convergence for the block SSOR method associated withp-cyclic matrices

We apply Rouché's theorem to the functional equation relating the eigenvalues of theblock symmetric successive overrelaxation (SSOR) matrix with those of the block Jacobi iteration matrix found by Varga, Niethammer, and Cai, in order to obtain precise domains of convergence for the block SSOR iteration method associated withp-cyclic matricesA, p3. The intersection of these domains, taken over all suchp's, is shown to coincide with the exact domain of convergence of thepoint SSOR iteration method associated withH-matricesA. The latter domain was essentially discovered by Neumaier and Varga, but was recently sharpened by Hadjidimos and Neumann.Research supported in part by NSF Grant DMS 870064.     

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     

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     

Some new results on Unsymmetric Successive Overrelaxation method

Summary The Unsymmetric Successive Overrelaxation (USSOR) iterative method is applied to the solution of the system of linear equationsA x=b, whereA is annxn nonsingular matrix. We find the values of the relaxation parameters and for which the USSOR iterative method converges. Then we characterize those matrices which are equimodular toA and for which the USSOR iterative method converges.     

Detecting hyperbolic and definite matrix polynomials

Hyperbolic or more generally definite matrix polynomials are important classes of Hermitian matrix polynomials. They allow for a definite linearization and can therefore be solved by a standard algorithm for Hermitian matrices. They have only real eigenvalues which can be characterized as minmax and maxmin values of Rayleigh functionals, but there is no easy way to test if a given polynomial is hyperbolic or definite or not. Taking advantage of the safeguarded iteration which converges globally and monotonically to extreme eigenvalues we obtain an efficient algorithm that identifies hyperbolic or definite polynomials and enables the transformation to an equivalent definite linear pencil. Numerical examples demonstrate the efficiency of the approach.     

Regions of exact convergence of the USSOR method applied on generalized consistently ordered matrices

Summary. Using the theory of nonnegative matrices and regular splittings, exact convergence and divergence domains of the Unsymmetric Successive Overrelaxation (USSOR) method, as it pertains to the class of Generalized Consistently Ordered (GCO) matrices, are determined. Our recently derived upper bounds, for the convergence of the USSOR method, re also used as effective tools. Received October 17, 1993 / Revised version received December 19, 1994     

Computable eigenvalue bounds for rank-k perturbations

We investigate lower bounds for the eigenvalues of perturbations of matrices. In the footsteps of Weyl and Ipsen & Nadler, we develop approximating matrices whose eigenvalues are lower bounds for the eigenvalues of the perturbed matrix. The number of available eigenvalues and eigenvectors of the original matrix determines how close those approximations can be, and, if the perturbation is of low rank, such bounds are relatively inexpensive to obtain. Moreover, because the process need not be restricted to the eigenvalues of perturbed matrices, lower bounds for eigenvalues of bordered diagonal matrices as well as for singular values of rank-k perturbations and other updates of n×m matrices are given.     

The Lidskii-Mirsky-Wielandt theorem – additive and multiplicative versions

Summary. We use a simple matrix splitting technique to give an elementary new proof of the Lidskii-Mirsky-Wielandt Theorem and to obtain a multiplicative analog of the Lidskii-Mirsky-Wielandt Theorem, which we argue is the fundamental bound in the study of relative perturbation theory for eigenvalues of Hermitian matrices and singular values of general matrices. We apply our bound to obtain numerous bounds on the matching distance between the eigenvalues and singular values of matrices. Our results strengthen and generalize those in the literature. Received November 20, 1996 / Revised version received January 27, 1998     

A note on the eigenvalues of a special class of matrices

In the analysis of stability of a variant of the Crank-Nicolson (C-N) method for the heat equation on a staggered grid a class of non-symmetric matrices appear that have an interesting property: their eigenvalues are all real and lie within the unit circle. In this note we shall show how this class of matrices is derived from the C-N method and prove that their eigenvalues are inside [−1,1] for all values of m (the order of the matrix) and all values of a positive parameter σ, the stability parameter. As the order of the matrix is general, and the parameter σ lies on the positive real line this class of matrices turns out to be quite general and could be of interest as a test set for eigenvalue solvers, especially as examples of very large matrices.     

Solution of finite systems of equations by interval iteration

In actual practice, iteration methods applied to the solution of finite systems of equations yield inconclusive results as to the existence or nonexistence of solutions and the accuracy of any approximate solutions obtained. On the other hand, construction of interval extensions of ordinary iteration operators permits one to carry out interval iteration computationally, with results which can give rigorous guarantees of existence or nonexistence of solutions, and error bounds for approximate solutions. Examples are given of the solution of a nonlinear system of equations and the calculation of eigenvalues and eigenvectors of a matrix by interval iteration. Several ways to obtain lower and upper bounds for eigenvalues are given.Sponsored by the United States Army under Contract No. DAAG29-80-C-0041.     

Current inverse iteration software can fail

Inverse iteration is widley used to compute the eigenvectors of a matrix once accurate eigenvalues are known. We discuss various issues involved in any implementation of inverse iteration for real, symmetric matrices. Current implementations resort to reorthogonalization when eigenvalues agree to more than three digits relative to the norm. Such reorthogonalization can have unexpected consequences. Indeed, as we show in this paper, the implementations in EISPACK and LAPACK may fail. We illustrate with both theoretical and empirical failures. This research was supported, while the author was at the University of California, Berkeley, in part by DARPA Contract No. DAAL03-91-C-0047 through a subcontract with the University of Tennessee, DOE Contract No. DOE-W-31-109-Eng-38 through a subcontract with Argonne National Laboratory, by DOE Grant No. DE-FG03-94ER25219, NSF Grant Nos. ASC-9313958 and CDA-9401156, and DOE Contract DE-AC06-76RLO 1830 through the Environmental Molecular Sciences construction project at Pacific Northwest National Laboraotry (PNNL).     

The spectral properties of the preconditioned matrix for nonsymmetric saddle point problems

In this paper, on the basis of matrix splitting, two preconditioners are proposed and analyzed, for nonsymmetric saddle point problems. The spectral property of the preconditioned matrix is studied in detail. When the iteration parameter becomes small enough, the eigenvalues of the preconditioned matrices will gather into two clusters—one is near (0,0) and the other is near (2,0)—for the PPSS preconditioner no matter whether A is Hermitian or non-Hermitian and for the PHSS preconditioner when A is a Hermitian or real normal matrix. Numerical experiments are given, to illustrate the performances of the two preconditioners.     

On block-circulant preconditioners for high-order compact approximations of convection-diffusion problems

We study some properties of block-circulant preconditioners for high-order compact approximations of convection-diffusion problems. For two-dimensional problems, the approximation gives rise to a nine-point discretisation matrix and in three dimensions, we obtain a nineteen-point matrix. We derive analytical expressions for the eigenvalues of the block-circulant preconditioner and this allows us to establish the invertibility of the preconditioner in both two and three dimensions. The eigenspectra of the preconditioned matrix in the two-dimensional case is described for different test cases. Our numerical results indicate that the block-circulant preconditioning leads to significant reduction in iteration counts and comparisons between the high-order compact and upwind discretisations are carried out. For the unpreconditioned systems, we observe fewer iteration counts for the HOC discretisation but for the preconditioned systems, we find similar iteration counts for both finite difference approximations of constant-coefficient two-dimensional convection-diffusion problems.     

A block Arnoldi-Chebyshev method for computing the leading eigenpairs of large sparse unsymmetric matrices

Summary In this paper we describe a block version of Arnoldi's method for computing a few eigenvalues with largest or smallest real parts. The method is accelerated via Chebyshev iteration and a procedure is developed to identify the optimal ellipse which encloses the spectrum. A parallel implementation of this method is investigated on the eight processor Alliant FX/80. Numerical results and comparisons with simultaneous iteration on some Harwell-Boeing matrices are reported.     

On the modification of an eigenvalue problem that preserves an eigenspace

Eigenvalue problems arise in many application areas ranging from computational fluid dynamics to information retrieval. In these fields we are often interested in only a few eigenvalues and corresponding eigenvectors of a sparse matrix. In this paper, we comment on the modifications of the eigenvalue problem that can simplify the computation of those eigenpairs. These transformations allow us to avoid difficulties associated with non-Hermitian eigenvalue problems, such as the lack of reliable non-Hermitian eigenvalue solvers, by mapping them into generalized Hermitian eigenvalue problems. Also, they allow us to expose and explore parallelism. They require knowledge of a selected eigenvalue and preserve its eigenspace. The positive definiteness of the Hermitian part is inherited by the matrices in the generalized Hermitian eigenvalue problem. The position of the selected eigenspace in the ordering of the eigenvalues is also preserved under certain conditions. The effect of using approximate eigenvalues in the transformation is analyzed and numerical experiments are presented.     

Is modified PSD equivalent to modified SOR for two-cyclic matrices?

In this paper we study the convergence analysis of the Modified Preconditioned Simultaneous Displacement (MPSD) method when A is a two-cyclic matrix. Convergence conditions and optimum values of the parameters are determined in case the eigenvalues of the associated Jacobi iteration matrix are either all real or all imaginary.     

A matrix analysis of Arnoldi and Lanczos methods

Summary. In this paper we propose a matrix analysis of the Arnoldi and Lanczos procedures when used for approximating the eigenpairs of a non-normal matrix. By means of a new relation between the respective representation matrices, we relate the corresponding eigenvalues and eigenvectors. Moreover, backward error analysis is used to theoretically justify some unexpected experimental behaviors of non-normal matrices and in particular of banded Toeplitz matrices. Received June 19, 1996 / Revised version received November 3, 1997