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…     

调和Arnoldi方法的一种变形

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

The Rayleigh-Ritz method, refinement and Arnoldi process for periodic matrix pairs

We extend the Rayleigh-Ritz method to the eigen-problem of periodic matrix pairs. Assuming that the deviations of the desired periodic eigenvectors from the corresponding periodic subspaces tend to zero, we show that there exist periodic Ritz values that converge to the desired periodic eigenvalues unconditionally, yet the periodic Ritz vectors may fail to converge. To overcome this potential problem, we minimize residuals formed with periodic Ritz values to produce the refined periodic Ritz vectors, which converge under the same assumption. These results generalize the corresponding well-known ones for Rayleigh-Ritz approximations and their refinement for non-periodic eigen-problems. In addition, we consider a periodic Arnoldi process which is particularly efficient when coupled with the Rayleigh-Ritz method with refinement. The numerical results illustrate that the refinement procedure produces excellent approximations to the original periodic eigenvectors.     

Error analysis of symplectic Lanczos method for Hamiltonian eigenvalue problem

A rounding error analysis for the symplectic Lanczos method is given to solve the large-scale sparse Hamiltonian eigenvalue problem. If no breakdown occurs in the method, then it can be shown that the Hamiltonian structure preserving requirement does not destroy the essential feature of the nonsymmetric Lanczos algorithm. The relationship between the loss of J-orthogonality among the symplectic Lanczos vectors and the convergence of the Ritz values in the symmetric Lanczos algorithm is discussed. It is demonstrated that under certain assumptions the computed J-orthogonal Lanczos vectors lose the J-orthogonality when some Ritz values begin to converge. Our analysis closely follows the recent works of Bai and Fabbender. Selected from Journal of Mathematical Research and Exposition, 2004, 24(1): 91–106     

精化的二次残量迭代法

According to the refined projection principle advocated by Jia[8], we improve the residual iteration method of quadratic eigenvalue problems and propose a refined residual iteration method. We study the restarting issue of the method and develop a practical algorithm. Preliminary numerical examples illustrate the efficiency of the method.     

A block inverse-free preconditioned Krylov subspace method for symmetric generalized eigenvalue problems

The inverse-free preconditioned Krylov subspace method of Golub and Ye [G.H. Golub, Q. Ye, An inverse free preconditioned Krylov subspace method for symmetric generalized eigenvalue problems, SIAM J. Sci. Comp. 24 (2002) 312-334] is an efficient algorithm for computing a few extreme eigenvalues of the symmetric generalized eigenvalue problem. In this paper, we first present an analysis of the preconditioning strategy based on incomplete factorizations. We then extend the method by developing a block generalization for computing multiple or severely clustered eigenvalues and develop a robust black-box implementation. Numerical examples are given to illustrate the analysis and the efficiency of the block algorithm.     

An Arnoldi-type algorithm for computing page rank

We consider the problem of computing PageRank. The matrix involved is large and cannot be factored, and hence techniques based on matrix-vector products must be applied. A variant of the restarted refined Arnoldi method is proposed, which does not involve Ritz value computations. Numerical examples illustrate the performance and convergence behavior of the algorithm. AMS subject classification (2000) 65F15, 65C40     

计算部分奇异值分解的隐式重新启动的双对角化Lanczos方法和精化的双对角化Lanczos方法

The singular value decomposition problem is mathematically equivalent to the eigenproblem of an argumented matrix. Golub et al. give a bidiagonalization Lanczos method for computing a number of largest or smallest singular values and corresponding singular vertors, but the method may encounter some convergence problems. In this paper we analyse the convergence of the method and show why it may fail to converge. To correct this possible nonconvergence, we propose a refined bidiagonalization Lanczos method and apply the implicitly restarting technique to it, and we then present an implicitly restarted bidiagonalization Lanczos algorithm(IRBL) and an implicitly restarted refined bidiagonalization Lanczos algorithm (IRRBL). A new implicitly restarting scheme and a reliable and efficient algorithm for computing refined shifts are developed for this special structure eigenproblem.Theoretical analysis and numerical experiments show that IRRBL performs much better than IRBL.     

Some theoretical comparisons of refined Ritz vectors and Ritz vectors

Refined projection methods proposed by the author have received attention internationally. We are concerned with a conventional projection method and its refined counterpart for computing approximations to a simple eigenpair (A, x) of a large matrix A. Given a subspace ω that contains an approximation to x, these two methods compute approximations (μ,x) and (μ,x) to (λ, x), respectively. We establish three results. First, the refined eigenvector approximation or simply the refined Ritz vector x is unique as the     

ARNOLDI TYPE ALGORITHMS FOR LARGE UNSYMMETRIC MULTIPLE EIGENVALUE PROBLEMS

1.IntroductionTheLanczosalgorithm[Zo]isaverypowerfultoolforextractingafewextremeeigenvaluesandassociatedeigenvectorsoflargesymmetricmatrices[4'5'22].Sincethe1980's,considerableattentionhasbeenpaidtogeneralizingittolargeunsymmetricproblems.Oneofitsgen...     

Nested Lanczos: implicitly restarting an unsymmetric Lanczos algorithm

In this text, we present a generalization of the idea of the Implicitly Restarted Arnoldi method to the unsymmetric Lanczos algorithm, using the two-sided Gram-Schmidt process or using a full Lanczos tridiagonalization. The resulting implicitly restarted Lanczos method is called Nested Lanczos. Nested Lanczos can be combined with an implicit filter. It can also be used in case of breakdown and offers an alternative for look-ahead. This revised version was published online in August 2006 with corrections to the Cover Date.     

On common quasi-eigenvector problems

In this paper, we study four types of common quasi-eigenvector problems and two types of eigenvector problems. The existence theorems for the solutions of common quasi-eigenvector problems and eigenvector problems are also established.     

分配格上矩阵的特征向量

设(L,≤,∨,∧)为一分配格。满足Ax=x的向量x称为方阵A的特征向量。本文的主工目的是通过矩阵的伴随有向图来刻画矩阵的特征向量并给出矩阵特征向量的界。同时我们将定义矩阵A的上基本特征向量并讨论它的性质。     

An Investigation of Restarted GMRES Method by Using Flexible Starting Vectors

<正>We discuss a variant of restarted GMRES method that allows changes of the restarting vector at each cycle of iterations.The merit of the variant is that previously generated information can be utilized to select a new starting vector,such that the occurrence of stagnation be mitigated or the convergence be accelerated.The more appealing utilization of the new method is in conjunction with a harmonic Ritz vector as the starting vector,which is discussed in detail.Numerical experiments are carried out to demonstrate that the proposed procedure can effectively mitigate the occurrence of stagnation due to the presence of small eigenvalues in modulus.     

Spectral Variants of Krylov Subspace Methods

Krylov iterative methods usually solve an optimization problem, per iteration, to obtain a vector whose components are the step lengths associated with the previous search directions. This vector can be viewed as the solution of a multiparameter optimization problem. In that sense, Krylov methods can be combined with the spectral choice of step length that has recently been developed to accelerate descent methods in optimization. In this work, we discuss different spectral variants of Krylov methods and present encouraging preliminary numerical experiments, with and without preconditioning.     

A simplex-like method to compute the eigenvalue of an irreducible (max,+)-system

In this paper, we present an alternative method to compute the eigenvalue of an irreducible (max,+)-system. The method resembles the well-known simplex method in linear programming in the sense that the eigenvalue and a corresponding eigenvector are obtained by going along the boundary of a polygon-like set, while increasing the number of equalities in some (max,+)-algebraic eigenvalue–eigenvector expression, until only equalities are left over. The latter is unlike the normal linear programming approach where, going along the boundary of a polygon-like set, a linear functional is optimized.     

A fast minimal residual algorithm for shifted unitary matrices

A new iterative scheme is described for the solution of large linear systems of equations with a matrix of the form A = ρU + ζI, where ρ and ζ are constants, U is a unitary matrix and I is the identity matrix. We show that for such matrices a Krylov subspace basis can be generated by recursion formulas with few terms. This leads to a minimal residual algorithm that requires little storage and makes it possible to determine each iterate with fairly little arithmetic work. This algorithm provides a model for iterative methods for non-Hermitian linear systems of equations, in a similar way to the conjugate gradient and conjugate residual algorithms. Our iterative scheme illustrates that results by Faber and Manteuffel [3,4] on the existence of conjugate gradient algorithms with short recurrence relations, and related results by Joubert and Young [13], can be extended.