A refined iterative algorithm based on the block arnoldi process for large unsymmetric eigenproblems

When the matrix in question is unsymmetric, the approximate eigenvectors or Ritz vectors obtained by orthogonal projection methods including Arnoldi's method and the block Arnoldi method cannot be guaranteed to converge in theory even if the corresponding approximate eigenvalues or Ritz values do. In order to circumvent this danger, a new strategy has been proposed by the author for Arnoldi's method. The strategy used is generalized to the block Arnoldi method in this paper. It discards Ritz vectors and instead computes refined approximate eigenvectors by small-sized singular-value decompositions. It is proved that the new strategy can guarantee the convergence of refined approximate eigenvectors if the corresponding Ritz values do. The resulting refined iterative algorithm is realized by the block Arnoldi process. Numerical experiments show that the refined algorithm is much more efficient than the iterative block Arnoldi algorithm.     

Variations on Arnoldi's method for computing eigenelements of large unsymmetric matrices

It is shown that the method of Arnoldi can be successfully used for solvinglarge unsymmetric eigenproblems. Like the symmetric Lanczos method, Arnoldi's algorithm realizes a projection process onto the Krylov subspace K_m spanned by v₁,Av₁,...,A^m?1v₁, where v₁ is the initial vector. We therefore study the convergence of the approximate eigenelements obtained by such a process. In particular, when the eigenvalues of A are real, we obtain bounds for the rates of convergence similar to those for the symmetric Lanczos algorithm. Some practical methods are presented in addition to that of Arnoldi, and several numerical experiments are described.     

A global harmonic Arnoldi method for large non-Hermitian eigenproblems with an application to multiple eigenvalue problems

The global Arnoldi method can be used to compute exterior eigenpairs of a large non-Hermitian matrix A, but it does not work well for interior eigenvalue problems. Based on the global Arnoldi process that generates an F-orthonormal basis of a matrix Krylov subspace, we propose a global harmonic Arnoldi method for computing certain harmonic F-Ritz pairs that are used to approximate some interior eigenpairs. We propose computing the F-Rayleigh quotients of the large non-Hermitian matrix with respect to harmonic F-Ritz vectors and taking them as new approximate eigenvalues. They are better and more reliable than the harmonic F-Ritz values. The global harmonic Arnoldi method inherits convergence properties of the harmonic Arnoldi method applied to a larger matrix whose distinct eigenvalues are the same as those of the original given matrix. Some properties of the harmonic F-Ritz vectors are presented. As an application, assuming that A is diagonalizable, we show that the global harmonic Arnoldi method is able to solve multiple eigenvalue problems both in theory and in practice. To be practical, we develop an implicitly restarted global harmonic Arnoldi algorithm with certain harmonic F-shifts suggested. In particular, this algorithm can be adaptively used to solve multiple eigenvalue problems. Numerical experiments show that the algorithm is efficient for the eigenproblem and is reliable for quite ill-conditioned multiple eigenproblems.     

A VARIATION ON THE BLOCK ARNOLDIMETHOD FOR LARGE UNSYMMETRIC MATRIX EIGENPROBLEMS

1.IntroductionLarge-scalematrixeigenproblemsariseinappliedsciencesandmanyengineeringapplications.Arnoldi'smethod[1'2]anditsblockversion[3--6]areverypopularforsolvingthem.Thesemethodshavebeenintensivelyinvestigatedsincethe1980s,bothintheoryandinalgorithms;wereferto[7--17]fordetails.WhenmstepsoftheblockArnoldiprocessareperformed,anorthonormalbasis{K}7=1oftheblockKrylovsubspaceK.(VI,A)spannedbyVI5AVI,'IAm--1VIisgenerated,whereVIisaninitialNxporthogonalmatrix,andtherestrictionofAtoKm(V…     

A modified harmonic block Arnoldi algorithm with adaptive shifts for large interior eigenproblems

The harmonic block Arnoldi method can be used to find interior eigenpairs of large matrices. Given a target point or shift τ$\tau$ to which the needed interior eigenvalues are close, the desired interior eigenpairs are the eigenvalues nearest τ$\tau$ and the associated eigenvectors. However, it has been shown that the harmonic Ritz vectors may converge erratically and even may fail to do so. To do a better job, a modified harmonic block Arnoldi method is coined that replaces the harmonic Ritz vectors by some modified harmonic Ritz vectors. The relationships between the modified harmonic block Arnoldi method and the original one are analyzed. Moreover, how to adaptively adjust shifts during iterations so as to improve convergence is also discussed. Numerical results on the efficiency of the new algorithm are reported.     

计算大规模矩阵最大最小奇异值和奇异向量的两个精化Lanczos算法

1.引言 在科学工程计算中经常需要计算大规模矩阵的少数最大或最小的奇异值及其所对应的奇异子空间。例如图像处理中要计算矩阵端部奇异值之比作为图像的分辨率,诸如此类的问题还存在于最小二乘问题、控制理论、量子化学中等等。然而大多实际问题中的矩阵是大型稀疏矩阵,且需要的是矩阵的部分奇异对。如果计算A的完全奇异值分解(SVD),则运算量和存储量极大,甚至不可能。因此必须寻求其它有效可靠的算法。 假设A的SVD为     

A PROCESS FOR SOLVING A FEW EXTREME EIGENPAIRS OF LARGE SPARSE POSITIVE DEFINITE GENERALIZED EIGENVALUE PROBLEM

1. IntroductionWe are concerned in this work with finding a few extreme eigenvalues and theircorresponding eigenvectors of a generalized large scale eigenvalue problem in which thematrices are sparse and symmetric positive definite.Although finding a few extreme eigenpairs is of interest both in theory and practice,there are only few usable and efficient methods up to now. Reinsch and Baner ([12]),suggested a oR algorithm with Newton shift for the standard eigenproblem which included an ingen…     

Composite orthogonal projection methods for large matrix eigenproblems

For classical orthogonal projection methods for large matrix eigenproblems, it may be much more difficult for a Ritz vector to converge than for its corresponding Ritz value when the matrix in question is non-Hermitian. To this end, a class of new refined orthogonal projection methods has been proposed. It is proved that in some sense each refined method is a composite of two classical orthogonal projections, in which each refined approximate eigenvector is obtained by realizing a new one of some Hermitian semipositive definite matrix onto the same subspace. Apriori error bounds on the refined approximate eigenvector are established in terms of the sine of acute angle of the normalized eigenvector and the subspace involved. It is shown that the sufficient conditions for convergence of the refined vector and that of the Ritz value are the same, so that the refined methods may be much more efficient than the classical ones.     

A harmonic restarted Arnoldi algorithm for calculating eigenvalues and determining multiplicity

A restarted Arnoldi algorithm is given that computes eigenvalues and eigenvectors. It is related to implicitly restarted Arnoldi, but has a simpler restarting approach. Harmonic and regular Rayleigh-Ritz versions are possible.For multiple eigenvalues, an approach is proposed that first computes eigenvalues with the new harmonic restarted Arnoldi algorithm, then uses random restarts to determine multiplicity. This avoids the need for a block method or for relying on roundoff error to produce the multiple copies.     

调和Arnoldi方法的一种变形

讨论求解大规模非对称矩阵内部特征问题的一种方法,与标准的调和A rnold i方法相比,该方法仍用调和R itz值作为特征值的近似,而在近似特征向量选取方面,我们充分利用A rnold i过程所提供的最末一个基向量的信息,在多1维K ry lov子空间中选取一个向量-称之为改进的调和R itz向量-作为所求的特征向量的近似.理论分析和数值试验均表明这种变形的调和A rnold i方法的可行性和有效性.     

Estimation of uTƒ(A)v for large‐scale unsymmetric matrices

Fast algorithms, based on the unsymmetric look‐ahead Lanczos and the Arnoldi process, are developed for the estimation of the functional Φ(?)= u ^T?(A) v for fixed u , v and A, where A∈??^n×n is a large‐scale unsymmetric matrix. Numerical results are presented which validate the comparable accuracy of both approaches. Although the Arnoldi process reaches convergence more quickly in some cases, it has greater memory requirements, and may not be suitable for especially large applications. Copyright © 2003 John Wiley & Sons, Ltd.     

求解大规模非对称矩阵特征问题的精化双正交Lanczos算法

We combine Lanczos algorithm with the thought of the refined projection method using QR factorization and propose the refined biothogonalization Lanczos method for computing the desired eigenvalues of large unsymmetric matrix. With low cost of work space and flops the algorithm cures the disease that the Ritz vectors may not converge when the Ritz values converge usingthe Lanczos method. Numerical experiments show our algorithm is considerably more stable and efficient than its counterpart.     

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.     

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     

Two-sided harmonic subspace extractions for the generalized eigenvalue problem

One crucial step of the solution of large-scale generalized eigenvalue problems with iterative subspace methods, e.g. Arnoldi, Jacobi-Davidson, is a projection of the original large-scale problem onto a low dimensional subspaces. Here we investigate two-sided methods, where approximate eigenvalues together with their right and left eigenvectors of the full-size problem are extracted from the resulting small eigenproblem. The two-sided Ritz-Galerkin projection can be seen as the most basic form of this approach. It usually provides a good convergence towards the extremal eigenvalues of the spectrum. For improving the convergence towards interior eigenvalues, we investigate two approaches based on harmonic subspace extractions for the generalized eigenvalue problem. (© 2011 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

The rational Krylov algorithm for nonsymmetric eigenvalue problems. III: Complex shifts for real matrices

A new algorithm for the computation of eigenvalues of a nonsymmetric matrix pencil is described. It is a generalization of the shifted and inverted Lanczos (or Arnoldi) algorithm, in which several shifts are used in one run. It computes an orthogonal basis and a small Hessenberg pencil. The eigensolution of the Hessenberg pencil, gives Ritz approximations to the solution of the original pencil. It is shown how complex shifts can be used to compute a real block Hessenberg pencil to a real matrix pair.Two applicationx, one coming from an aircraft stability problem and the other from a hydrodynamic bifurcation, have been tested and results are reported.Dedicated to Carl-Erik Fröberg on the occasion of his 75th birthday.     

Composite orthogonal projection methods for large matrix eigenproblems

For classical orthogonal projection methods for large matrix eigenproblems, it may be much more difficult for a Ritz vector to converge than for its corresponding Ritz value when the matrix in question is non-Hermitian. To this end, a class of new refined orthogonal projection methods has been proposed. It is proved that in some sense each refined method is a composite of two classical orthogonal projections, in which each refined approximate eigenvector is obtained by realizing a new one of some Hermitian semipositive definite matrix onto the same subspace. Apriori error bounds on the refined approximate eigenvector are established in terms of the sine of acute angle of the normalized eigenvector and the subspace involved. It is shown that the sufficient conditions for convergence of the refined vector and that of the Ritz value are the same, so that the refined methods may be much more efficient than the classical ones. Project supported by the China State Major Key Projects for Basic Researches, the National Natural Science Foundation of China (Grant No. 19571014), the Doctoral Program (97014113), the Foundation of Excellent Young Scholors of Ministry of Education, the Foundation of Returned Scholars of China and the Liaoning Province Natural Science Foundation.     

Krylov type subspace methods for matrix polynomials

We consider solving eigenvalue problems or model reduction problems for a quadratic matrix polynomial Iλ² − Aλ − B with large and sparse A and B. We propose new Arnoldi and Lanczos type processes which operate on the same space as A and B live and construct projections of A and B to produce a quadratic matrix polynomial with the coefficient matrices of much smaller size, which is used to approximate the original problem. We shall apply the new processes to solve eigenvalue problems and model reductions of a second order linear input-output system and discuss convergence properties. Our new processes are also extendable to cover a general matrix polynomial of any degree.     

IMPROVING EIGENVECTORS IN ARNOLDI''''S METHOD

1. IntroductionArnoldi's method [1, 12] is used for computing.,a few selected eigenpairs of largeunsymmetric matrices. It hajs been investigated since the 1980s; see, e-g., [3--15].It is well known that the m--step Arnoldi processt as described in detail in Section 2,generates an orthonormal basis {yi}7=1 of the Krylov subspace Km(vi, A) spanned byvil Avi,... 5 Am--'v,. Here yi is an initial unit norm vector. The projected matrix ofA onto Km(vi, A) is represented by an m x m upper Hessenb…     

A block incomplete orthogonalization method for large nonsymmetric eigenproblems

The incomplete orthogonalization method (IOM) proposed by Saad for computing a few eigenpairs of large nonsymmetric matrices is generalized into a block incomplete orthogonalization method (BIOM). It is studied how the departure from symmetry A – A ^H affects the conditioning of the block basis vectors generated by BIOM, and some relationships are established between the approximate eigenpairs obtained by BIOM and Ritz pairs. It is proved that BIOM behaves much like generalized block Lanczos methods if the basis vectors of the block Krylov subspace generated by it are strongly linearly independent. However, it is shown that BIOM may generate a nearly linearly dependent basis for a general nonsymmetric matrix. Numerical experiments illustrate the convergence behavior of BIOM.This work was supported in part by the Graduiertenkolleg at the University of Bielefeld, Germany.