An adaptive Chebyshev iterative method\newline for nonsymmetric linear systems based on modified moments

Summary. Large, sparse nonsymmetric systems of linear equations with a matrix whose eigenvalues lie in the right half plane may be solved by an iterative method based on Chebyshev polynomials for an interval in the complex plane. Knowledge of the convex hull of the spectrum of the matrix is required in order to choose parameters upon which the iteration depends. Adaptive Chebyshev algorithms, in which these parameters are determined by using eigenvalue estimates computed by the power method or modifications thereof, have been described by Manteuffel [18]. This paper presents an adaptive Chebyshev iterative method, in which eigenvalue estimates are computed from modified moments determined during the iterations. The computation of eigenvalue estimates from modified moments requires less computer storage than when eigenvalue estimates are computed by a power method and yields faster convergence for many problems. Received May 13, 1992/Revised version received May 13, 1993     

On close eigenvalues of tridiagonal matrices

Summary. A symmetric tridiagonal matrix with a multiple eigenvalue must have a zero subdiagonal element and must be a direct sum of two complementary blocks, both of which have the eigenvalue. Yet it is well known that a small spectral gap does not necessarily imply that some is small, as is demonstrated by the Wilkinson matrix. In this note, it is shown that a pair of close eigenvalues can only arise from two complementary blocks on the diagonal, in spite of the fact that the coupling the two blocks may not be small. In particular, some explanatory bounds are derived and a connection to the Lanczos algorithm is observed. The nonsymmetric problem is also included. Received April 8, 1992 / Revised version received September 21, 1994     

求解大规模Hamilton矩阵特征问题的辛Lanczos算法的误差分析

对求解大规模稀疏Hamilton矩阵特征问题的辛Lanczos算法给出了舍入误差分析.分析表明辛Lanczos算法在无中断时,保Hamilton结构的限制没有破坏非对称Lanczos算法的本质特性.本文还讨论了辛Lanczos算法计算出的辛Lanczos向量的J一正交性的损失与Ritz值收敛的关系.结论正如所料,当某些Ritz值开始收敛时.计算出的辛Lanczos向量的J-正交性损失是必然的.以上结果对辛Lanczos算法的改进具有理论指导意义.     

Error bounds and estimates for eigenvalues of integral equations

Summary Approximate solutions of the linear integral equation eigenvalue problem can be obtained by the replacement of the integral by a numerical quadrature formula and then collocation to obtain a linear algebraic eigenvalue problem. This method is often called the Nyström method and its convergence was discussed in [7]. In this paper computable error bounds and dominant error terms are derived for the approximation of simple eigenvalues of nonsymmetric kernels.     

A SMALLEST SINGULAR VALUE METHOD FOR SOLVING INVERSE EIGENVALUE PROBLEMS

1.IntroductionConsiderthefollowinginverseeigenvalueproblem:ProblemG.LetA(x)ERnxn5earealanalyticmatrix-valuedfunctionofxeR".Findapointx*eR"suchthatthematrixA(x*)ha8agiven8Pectral8etL={Al,'tA.}.HereA1,'1A.aregivencomPlexnum6ersandclosedundercomplexconjugation.Thiskindofproblemarisesofteninvariousareasofapplications(seeFreidlandetal.(1987)andreferencescontainedtherein).ThetwospecialcasesofProblemG,whicharefrequentlyencountered,arethefollowingproblemsproposedbyDowningandHouseholder(19…     

Arnoldi versus nonsymmetric Lanczos algorithms for solving matrix eigenvalue problems

We present theoretical and numerical comparisons between Arnoldi and nonsymmetric Lanczos procedures for computing eigenvalues of nonsymmetric matrices. In exact arithmetic we prove that any type of eigenvalue convergence behavior obtained using a nonsymmetric Lanczos procedure may also be obtained using an Arnoldi procedure but on a different matrix and with a different starting vector. In exact arithmetic we derive relationships between these types of procedures and normal matrices which suggest some interesting questions regarding the roles of nonnormality and of the choice of starting vectors in any characterizations of the convergence behavior of these procedures. Then, through a set of numerical experiments on a complex Arnoldi and on a complex nonsymmetric Lanczos procedure, we consider the more practical question of the behavior of these procedures when they are applied to the same matrices.This work was supported by NSF grant GER-9450081 while the author was visiting the University of Maryland.     

On condition numbers of a nondefective multiple eigenvalue of a nonsymmetric matrix pencil

This paper considers the condition numbers of a nondefective multiple eigenvalue of a nonsymmetric matrix pencil. Based on the directional derivatives of a nondefective multiple eigenvalue of a nonsymmetric matrix pencil analytically dependent on several parameters, different condition numbers of a nondefective multiple eigenvalue are introduced. The computable expressions and bounds of introduced condition numbers are derived. Moreover, some results on the perturbation of a nondefective multiple eigenvalue of a nonsymmetric matrix pencil are given.     

解非对称矩阵特征值问题的一种并行分治算法

１引言考虑矩阵特征值问题其中Ａ是非对称矩阵．通过正交变换（如Ｈｏｕｓｅｈｏｌｄｅｒ变换或Ｇｉｖｅｎｓ变换）,Ａ可化为上Ｈｅｓｓｅｎｂｅｒｇ形．因而,本文假设Ａ为上Ｈｅｓｓｅｎｂｅｒｇ矩阵,表示如下：不失一般性,进一步假设所有的（ｊ＝２,…,ｎ）,即认为Ａ是不可约的关于如何求解上述问题,人们进行了不懈的努力,提出了许多行之有效的算法［１－８］．其中分治算法因具有良好的并行性而引人注目．分治算法的典型代表是基于同伦连续的分治算法［２,３,４］和基于Ｎｅｗｔｏｎ迭代的分治算法［１］．本文提出一种新的分…     

A Two-Level Method for Nonsymmetric Eigenvalue Problems

A two-level discretization method for eigenvalue problems is studied. Compared to the standard Galerkin finite element discretization technique performed on a fine grid this method discretizes the eigenvalue problem on a coarse grid and obtains an improved eigenvector (eigenvalue) approximation by solving only a linear problem on the fine grid (or two linear problems for the case of eigenvalue approximation of nonsymmetric problems). The improved solution has the asymptotic accuracy of the Galerkin discretization solution. The link between the method and the iterated Galerkin method is established. Error estimates for the general nonsymmetric case are derived.     

On some structured inverse eigenvalue problems

This work deals with various finite algorithms that solve two special Structured Inverse Eigenvalue Problems (SIEP). The first problem we consider is the Jacobi Inverse Eigenvalue Problem (JIEP): given some constraints on two sets of reals, find a Jacobi matrix J (real, symmetric, tridiagonal, with positive off-diagonal entries) that admits as spectrum and principal subspectrum the two given sets. Two classes of finite algorithms are considered. The polynomial algorithm which is based on a special Euclid–Sturm algorithm (Householder's terminology) and has been rediscovered several times. The matrix algorithm which is a symmetric Lanczos algorithm with a special initial vector. Some characterization of the matrix ensures the equivalence of the two algorithms in exact arithmetic. The results of the symmetric situation are extended to the nonsymmetric case. This is the second SIEP to be considered: the Tridiagonal Inverse Eigenvalue Problem (TIEP). Possible breakdowns may occur in the polynomial algorithm as it may happen with the nonsymmetric Lanczos algorithm. The connection between the two algorithms exhibits a similarity transformation from the classical Frobenius companion matrix to the tridiagonal matrix. This result is used to illustrate the fact that, when computing the eigenvalues of a matrix, the nonsymmetric Lanczos algorithm may lead to a slow convergence, even for a symmetric matrix, since an outer eigenvalue of the tridiagonal matrix of order n − 1 can be arbitrarily far from the spectrum of the original matrix. This revised version was published online in August 2006 with corrections to the Cover Date.     

A Wilkinson-like multishift QR algorithm for symmetric eigenvalue problems and its global convergence

In 1989, Bai and Demmel proposed the multishift QR algorithm for eigenvalue problems. Although the global convergence property of the algorithm (i.e., the convergence from any initial matrix) still remains an open question for general nonsymmetric matrices, in 1992 Jiang focused on symmetric tridiagonal case and gave a global convergence proof for the generalized Rayleigh quotient shifts. In this paper, we propose Wilkinson-like shifts, which reduce to the standard Wilkinson shift in the single shift case, and show a global convergence theorem.     

Iterative method for a class of nonlinear eigenvalue problems

Let H Be a complex and separable Hilbert space and consider in H the nonlinear eigenvalue problem where A, B, and C belong to the class of unbounded nonsymmetric operators, which are K- positive K-symmetric. Sufficient conditions insuring the existence of the eigenvalues of (i) are investigated. An iterative method for approximating the eigenvalues of (i) is developed and its convergence proved. Some numerical examples are given to illustrate the theory.     

A generalized Rayleigh quotient for eigenvalue problems nonlinear in the parameter

A functional is given which generalizes the Rayleigh quotient to eigenvalue problems for linear operators where the eigenvalue parameter appears nonlinearly. Particular emphasis is given to the development of perturbation-type results for eigenvalues and characteristic values which generalize the classical results. Applications are made to eigenvalue and characteristic value problems for integral and matrix operators and to the critical length problem for integral operators. Both symmetric and nonsymmetric operators are treated.The author would like to acknowledge the work of Gloria Golberg in the preparation of this paper.     

An inverse free parallel spectral divide and conquer algorithm for nonsymmetric eigenproblems

Summary. We discuss an inverse-free, highly parallel, spectral divide and conquer algorithm. It can compute either an invariant subspace of a nonsymmetric matrix , or a pair of left and right deflating subspaces of a regular matrix pencil . This algorithm is based on earlier ones of Bulgakov, Godunov and Malyshev, but improves on them in several ways. This algorithm only uses easily parallelizable linear algebra building blocks: matrix multiplication and QR decomposition, but not matrix inversion. Similar parallel algorithms for the nonsymmetric eigenproblem use the matrix sign function, which requires matrix inversion and is faster but can be less stable than the new algorithm. Received September 20, 1994 / Revised version received February 5, 1996     

Harmonic projection methods for large non-symmetric eigenvalue problems

The problem of finding interior eigenvalues of a large nonsymmetric matrix is examined. A procedure for extracting approximate eigenpairs from a subspace is discussed. It is related to the Rayleigh–Ritz procedure, but is designed for finding interior eigenvalues. Harmonic Ritz values and other approximate eigenvalues are generated. This procedure can be applied to the Arnoldi method, to preconditioning methods, and to other methods for nonsymmetric eigenvalue problems that use the Rayleigh–Ritz procedure. The subject of estimating the boundary of the entire spectrum is briefly discussed, and the importance of preconditioning for interior eigenvalue problems is mentioned. © 1998 John Wiley & Sons, Ltd.     

A-posteriori residual bounds for Arnoldi’s methods for nonsymmetric eigenvalue problems

Convergence of the implicitly restarted Arnoldi (IRA) method for nonsymmetric eigenvalue problems has often been studied by deriving bounds for the angle between a desired eigenvector and the Krylov projection subspace. Bounds for residual norms of approximate eigenvectors have been less studied and this paper derives a new a-posteriori residual bound for nonsymmetric matrices with simple eigenvalues. The residual vector is shown to be a linear combination of exact eigenvectors and a residual bound is obtained as the sum of the magnitudes of the coefficients of the eigenvectors. We numerically illustrate that the convergence of the residual norm to zero is governed by a scalar term, namely the last element of the wanted eigenvector of the projected matrix. Both cases of convergence and non-convergence are illustrated and this validates our theoretical results. We derive an analogous result for implicitly restarted refined Arnoldi (IRRA) and for this algorithm, we numerically illustrate that convergence is governed by two scalar terms appearing in the linear combination which drives the residual norm to zero. We provide a set of numerical results that validate the residual bounds for both variants of Arnoldi methods.     

Realistic error bounds for a simple eigenvalue and its associated eigenvector

Summary An algorithm is described which, given an approximate simple eigenvalue and a corresponding approximate eigenvector, provides rigorous error bounds for improved versions of them. No information is required on the rest of the eigenvalues, which may indeed correspond to non-linear elementary divisors. A second algorithm is described which gives more accurate improved versions than the first but provides only error estimates rather than rigorous bounds. Both algorithms extend immediately to the generalized eigenvalue problem.Dedicated to A.S. Householder on his 75th birthday     

A linear system solver based on a modified Krylov subspace method for breakdown recovery

Despite its usefulness in solving eigenvalue problems and linear systems of equations, the nonsymmetric Lanczos method is known to suffer from a potential breakdown problem. Previous and recent approaches for handling the Lanczos exact and near-breakdowns include, for example, the look-ahead schemes by Parlett-Taylor-Liu [23], Freund-Gutknecht-Nachtigal [9], and Brezinski-Redivo Zaglia-Sadok [4]; the combined look-ahead and restart scheme by Joubert [18]; and the low-rank modified Lanczos scheme by Huckle [17]. In this paper, we present yet another scheme based on a modified Krylov subspace approach for the solution of nonsymmetric linear systems. When a breakdown occurs, our approach seeks a modified dual Krylov subspace, which is the sum of the original subspace and a new Krylov subspaceK _m (w _j ,A ^T ) wherew _j is a newstart vector (this approach has been studied by Ye [26] for eigenvalue computations). Based on this strategy, we have developed a practical algorithm for linear systems called the MLAN/QM algorithm, which also incorporates the residual quasi-minimization as proposed in [12]. We present a few convergence bounds for the method as well as numerical results to show its effectiveness.Research supported by Natural Sciences and Engineering Research Council of Canada.     

On hybrid iterative methods for nonsymmetric systems of linear equations

Summary. Hybrid methods for the solution of systems of linear equations consist of a first phase where some information about the associated coefficient matrix is acquired, and a second phase in which a polynomial iteration designed with respect to this information is used. Most of the hybrid algorithms proposed recently for the solution of nonsymmetric systems rely on the direct use of eigenvalue estimates constructed by the Arnoldi process in Phase I. We will show the limitations of this approach and propose an alternative, also based on the Arnoldi process, which approximates the field of values of the coefficient matrix and of its inverse in the Krylov subspace. We also report on numerical experiments comparing the resulting new method with other hybrid algorithms. Received May 27, 1993 / Revised version received November 14, 1994     

Krylov eigenvalue strategy using the FEAST algorithm with inexact system solves

The FEAST eigenvalue algorithm is a subspace iteration algorithm that uses contour integration to obtain the eigenvectors of a matrix for the eigenvalues that are located in any user‐defined region in the complex plane. By computing small numbers of eigenvalues in specific regions of the complex plane, FEAST is able to naturally parallelize the solution of eigenvalue problems by solving for multiple eigenpairs simultaneously. The traditional FEAST algorithm is implemented by directly solving collections of shifted linear systems of equations; in this paper, we describe a variation of the FEAST algorithm that uses iterative Krylov subspace algorithms for solving the shifted linear systems inexactly. We show that this iterative FEAST algorithm (which we call IFEAST) is mathematically equivalent to a block Krylov subspace method for solving eigenvalue problems. By using Krylov subspaces indirectly through solving shifted linear systems, rather than directly using them in projecting the eigenvalue problem, it becomes possible to use IFEAST to solve eigenvalue problems using very large dimension Krylov subspaces without ever having to store a basis for those subspaces. IFEAST thus combines the flexibility and power of Krylov methods, requiring only matrix–vector multiplication for solving eigenvalue problems, with the natural parallelism of the traditional FEAST algorithm. We discuss the relationship between IFEAST and more traditional Krylov methods and provide numerical examples illustrating its behavior.