A subspace preconditioning algorithm for eigenvector/eigenvalue computation

We consider the problem of computing a modest number of the smallest eigenvalues along with orthogonal bases for the corresponding eigenspaces of a symmetric positive definite operatorA defined on a finite dimensional real Hilbert spaceV. In our applications, the dimension ofV is large and the cost of invertingA is prohibitive. In this paper, we shall develop an effective parallelizable technique for computing these eigenvalues and eigenvectors utilizing subspace iteration and preconditioning forA. Estimates will be provided which show that the preconditioned method converges linearly when used with a uniform preconditioner under the assumption that the approximating subspace is close enough to the span of desired eigenvectors.     

A geometric theory for preconditioned inverse iteration applied to a subspace

The aim of this paper is to provide a convergence analysis for a preconditioned subspace iteration, which is designated to determine a modest number of the smallest eigenvalues and its corresponding invariant subspace of eigenvectors of a large, symmetric positive definite matrix. The algorithm is built upon a subspace implementation of preconditioned inverse iteration, i.e., the well-known inverse iteration procedure, where the associated system of linear equations is solved approximately by using a preconditioner. This step is followed by a Rayleigh-Ritz projection so that preconditioned inverse iteration is always applied to the Ritz vectors of the actual subspace of approximate eigenvectors. The given theory provides sharp convergence estimates for the Ritz values and is mainly built on arguments exploiting the geometry underlying preconditioned inverse iteration.     

Numerical computation of stability and detection of Hopf bifurcations of steady state solutions of delay differential equations

The characteristic equation of a system of delay differential equations (DDEs) is a nonlinear equation with infinitely many zeros. The stability of a steady state solution of such a DDE system is determined by the number of zeros of this equation with positive real part. We present a numerical algorithm to compute the rightmost, i.e., stability determining, zeros of the characteristic equation. The algorithm is based on the application of subspace iteration on the time integration operator of the system or its variational equations. The computed zeros provide insight into the system’s behaviour, can be used for robust bifurcation detection and for efficient indirect calculation of bifurcation points. This revised version was published online in June 2006 with corrections to the Cover Date.     

Eigenvalue bounds for the Schur complement with a pressure convection–diffusion preconditioner in incompressible flow computations

If the stationary Navier–Stokes system or an implicit time discretization of the evolutionary Navier–Stokes system is linearized by a Picard iteration and discretized in space by a mixed finite element method, there arises a saddle point system which may be solved by a Krylov subspace method or an Uzawa type approach. For each of these resolution methods, it is necessary to precondition the Schur complement associated to the saddle point problem in question. In the work at hand, we give upper and lower bounds of the eigenvalues of this Schur complement under the assumption that it is preconditioned by a pressure convection–diffusion matrix.     

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.     

大型不正定陀螺系统本征值问题

陀螺动力系统可以导入哈密顿辛几何体系,在哈密顿陀螺系统的辛子空间迭代法的基础上提出了一种能够有效计算大型不正定哈密顿函数的陀螺系统本征值问题的算法．利用陀螺矩阵既为哈密顿矩阵而本征值又是纯虚数或零的特点,将对应哈密顿函数为负的本征值分离开来,构造出对应哈密顿函数全为正的本征值问题,利用陀螺系统的辛子空间迭代法计算出正定哈密顿矩阵的本征值,从而解决了大型不正定陀螺系统的本征值问题,算例证明,本征解收敛得很快．     

On proximity of Rayleigh quotients for different vectors and Ritz values generated by different trial subspaces

The Rayleigh quotient is unarguably the most important function used in the analysis and computation of eigenvalues of symmetric matrices. The Rayleigh-Ritz method finds the stationary values of the Rayleigh quotient, called Ritz values, on a given trial subspace as optimal, in some sense, approximations to eigenvalues.In the present paper, we derive upper bounds for proximity of the Ritz values in terms of the proximity of the trial subspaces without making an assumption that the trial subspace is close to an invariant subspace. The main result is that the absolute value of the perturbations in the Ritz values is bounded by a constant times the gap between the original trial subspace and its perturbation. The constant is the spread in the matrix spectrum, i.e. the difference between the largest and the smallest eigenvalues of the matrix. It’s shown that the constant cannot be improved. We then generalize this result to arbitrary unitarily invariant norms, but we have to increase the constant by a factor of .Our results demonstrate, in particular, the stability of the Ritz values with respect to a perturbation in the trial subspace.     

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.     

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.     

Numerical study on incomplete orthogonal factorization preconditioners

We design, analyse and test a class of incomplete orthogonal factorization preconditioners constructed from Givens rotations, incorporating some dropping strategies and updating tricks, for the solution of large sparse systems of linear equations. Comprehensive accounts about how the preconditioners are coded, what storage is required and how the computation is executed for a given accuracy are presented. A number of numerical experiments show that these preconditioners are competitive with standard incomplete triangular factorization preconditioners when they are applied to accelerate Krylov subspace iteration methods such as GMRES and BiCGSTAB.     

Deflated block Krylov subspace methods for large scale eigenvalue problems

We discuss a class of deflated block Krylov subspace methods for solving large scale matrix eigenvalue problems. The efficiency of an Arnoldi-type method is examined in computing partial or closely clustered eigenvalues of large matrices. As an improvement, we also propose a refined variant of the Arnoldi-type method. Comparisons show that the refined variant can further improve the Arnoldi-type method and both methods exhibit very regular convergence behavior.     

On the nonlinear domain decomposition method

Any domain decomposition or additive Schwarz method can be put into the abstract framework of subspace iteration. We consider generalizations of this method to the nonlinear case. The analysis shows under relatively weak assumptions that the nonlinear iteration converges locally with the same asymptotic speed as the corresponding linear iteration applied to the linearized problem.     

Riccati-based preconditioner for computing invariant subspaces of large matrices

Summary. This paper introduces and analyzes the convergence properties of a method that computes an approximation to the invariant subspace associated with a group of eigenvalues of a large not necessarily diagonalizable matrix. The method belongs to the family of projection type methods. At each step, it refines the approximate invariant subspace using a linearized Riccati's equation which turns out to be the block analogue of the correction used in the Jacobi-Davidson method. The analysis conducted in this paper shows that the method converges at a rate quasi-quadratic provided that the approximate invariant subspace is close to the exact one. The implementation of the method based on multigrid techniques is also discussed and numerical experiments are reported. Received June 15, 2000 / Revised version received January 22, 2001 / Published online October 17, 2001     

Properties of iteration of toeplitz operators with toeplitz preconditioners

We consider the problems of preconditioning and iterative inversion of Toeplitz operators on sequences of complex numbers. We divide the preconditioned operator into two parts, of which one is compact and the other is regarded as a small perturbartion. It will be shown that the Krylov subspace methods (such as GMRES) will perform initially at superlinear speed when applied to such a preconditioned system. However, with large iteration numbers, the speed will settle down to linear order. Most of our results are stated in terms of the symbol of the Toeplitz operator in question.     

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.     

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.     

A mixed method of subspace iteration for Dirichlet eigenvalue problems

A full multigrid scheme was used in computing some eigenvalues of the Laplace eigenvalue problem with the Dirichlet boundary condition. We get a system of algebraic equations with an aid of finite difference method and apply subspace iteration method to the system to compute first some eigenvalues. The result shows that this is very effective in calculating some eigenvalues of this problem.     

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     

A stable Richardson iteration method for complex linear systems

Summary The Richardson iteration method is conceptually simple, as well as easy to program and parallelize. This makes the method attractive for the solution of large linear systems of algebraic equations with matrices with complex eigenvalues. We change the ordering of the relaxation parameters of a Richardson iteration method proposed by Eiermann, Niethammer and Varga for the solution of such problems. The new method obtained is shown to be stable and to have better convergence properties.Research supported by the National Science Foundation under Grant DMS-8704196     

Bounds on the error of an approximate invariant subspace for non-self-adjoint matrices

Summary. Suppose one approximates an invariant subspace of an matrix in which in not necessarily self--adjoint. Suppose that one also has an approximation for the corresponding eigenvalues. We consider the question of how good the approximations are. Specifically, we develop bounds on the angle between the approximating subspace and the invariant subspace itself. These bounds are functions of the following three terms: (1) the residual of the approximations; (2) singular--value separation in an associated matrix; and (3) the goodness of the approximations to the eigenvalues. Received December 1, 1992 / Revised version received October 20, 1993