计算最小奇异组的一个精化调和Lanczos双对角化方法

在很多实际应用中需要计算大规模矩阵的若干个最小奇异组.调和投影方法是计算内部特征对的常用方法,其原理可用于求解大规模奇异值分解问题.本文证明了,当投影空间足够好时,该方法得到的近似奇异值收敛,但近似奇异向量可能收敛很慢甚至不收敛.根据第二作者近年来提出的精化投影方法的原理,本文提出一种精化的调和Lanczos双对角化方法,证明了它的收敛性.然后将该方法与Sorensen提出的隐式重新启动技术相结合,开发出隐式重新启动的调和Lanczos双对角化算法(IRHLB)和隐式重新启动的精化调和Lanczos双对角化算法(IRRHLB).位移的合理选取是算法成功的关键之一,本文对精化算法提出了一种新的位移策略,称之为"精化调和位移".理论分析表明,精化调和位移比IRHLB中所用的调和位移要好,且可以廉价可靠地计算出来.数值实验表明,IRRHLB比IRHLB要显著优越,而且比目前常用的隐式重新启动的Lanczos双对角化方法(IRLB)和精化算法IRRLB更有效.     

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     

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.     

计算部分奇异值分解的隐式重新启动的双对角化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.     

An Implicitly Restarted Block Arnoldi Method in a Vector-Wise Fashion

In this paper, we develop an implicitly restarted block Arnoldi algorithm in a vector-wise fashion. The vector-wise construction greatly simplifies both the detection of necessary deflation and the actual deflation itself, so it is preferable to the block-wise construction. The numerical experiment shows that our algorithm is effective.     

A new framework for implicit restarting of the Krylov–Schur algorithm

This paper introduces a new framework for implicit restarting of the Krylov–Schur algorithm. It is shown that restarting with arbitrary polynomial filter is possible by reassigning some of the eigenvalues of the Rayleigh quotient through a rank‐one correction, implemented using only the elementary transformations (translation and similarity) of the Krylov decomposition. This framework includes the implicitly restarted Arnoldi (IRA) algorithm and the Krylov–Schur algorithm with implicit harmonic restart as special cases. Further, it reveals that the IRA algorithm can be turned into an eigenvalue assignment method. Copyright © 2014 John Wiley & Sons, Ltd.     

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.     

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.     

解大型非对称特征问题的精化块不完全正交化算法

0引言 块Arnoldi方法~[5]是解大型非对称特征值问题的正交投影方法，然而Jia~[3]的分析表     

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.     

调和Arnoldi方法的一种变形

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

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

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

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…     

The implicit application of a rational filter in the RKS method

The implicitly restarted Arnoldi method implicitly applies a polynomial filter to the Arnoldi vectors by use of orthogonal transformations. In this paper, an implicit filtering by rational functions is proposed for the rational Krylov method. This filtering is performed in an efficient way. Two applications are considered. The first one is the filtering of unwanted eigenvalues using exact shifts. This approach is related to the use of exact shifts in the implicitly restarted Arnoldi method. Second, eigenvalue problems can have an infinite eigenvalue without physical relevance. This infinite eigenvalue can corrupt the eigensolution. An implicit filtering is proposed for avoiding such corruptions. The work of Gorik De Samblanx and Adhemar Bultheel was supported by the National Fund for Scientific Research (NFWO), project Lanczos, grant #2.0042.93 and by the Human Capital and Mobility project ROLLS of the European Community under contract ERBCHRXCT930416. The research by Karl Meerbergen was supported by the Belgian programme on Interuniversity Poles of Attraction (IUAP 17), initiated by the Belgian State—Prime Minister's Service—Federal Office for Scientific, Technical and Cultural Affairs and the project Iterative Methods in Scientific Computing, contract number HCM network CHRCCT93-0420, coordinated by CERFACS, Toulouse, France.     

A Power–Arnoldi algorithm for computing PageRank

The PageRank algorithm plays an important role in modern search engine technology. It involves using the classical power method to compute the principle eigenvector of the Google matrix representing the web link graph. However, when the largest eigenvalue is not well separated from the second one, the power method may perform poorly. This happens when the damping factor is sufficiently close to 1. Therefore, it is worth developing new techniques that are more sophisticated than the power method. The approach presented here, called Power–Arnoldi, is based on a periodic combination of the power method with the thick restarted Arnoldi algorithm. The justification for this new approach is presented. Numerical tests illustrate the efficiency and convergence behaviour of the new algorithm. Copyright © 2007 John Wiley & Sons, Ltd.     

A reflection on the implicitly restarted Arnoldi method for computing eigenvalues near a vertical line

In this article, we will study the link between a method for computing eigenvalues closest to the imaginary axis and the implicitly restarted Arnoldi method. The extension to computing eigenvalues closest to a vertical line is straightforward, by incorporating a shift. Without loss of generality we will restrict ourselves here to computing eigenvalues closest to the imaginary axis.In a recent publication, Meerbergen and Spence discussed a new approach for detecting purely imaginary eigenvalues corresponding to Hopf bifurcations, which is of interest for the stability of dynamical systems. The novel method is based on inverse iteration (inverse power method) applied on a Lyapunov-like eigenvalue problem. To reduce the computational overhead significantly a projection was added.This method can also be used for computing eigenvalues of a matrix pencil near a vertical line in the complex plane. We will prove in this paper that the combination of inverse iteration with the projection step is equivalent to Sorensen’s implicitly restarted Arnoldi method utilizing well-chosen shifts.     

IRAM‐based method for eigenpairs and their derivatives of large matrix‐valued functions

Based on the implicitly restarted Arnoldi method for eigenpairs of large matrix, a new method is presented for the computation of a few eigenpairs and their derivatives of large matrix‐valued functions. Eigenpairs and their derivatives are calculated simultaneously. Equation systems that are solved for eigenvector derivatives are greatly reduced from the original matrix size. The left eigenvectors are not required. Hence, the computational cost is saved. The convergence theory of the proposed method is established. Finally, numerical experiments are given to illustrate the efficiency of the proposed method. Copyright © 2010 John Wiley & Sons, Ltd.     

Restarted generalized Krylov subspace methods for solving large-scale polynomial eigenvalue problems

In this paper, we introduce a generalized Krylov subspace based on a square matrix sequence {A _j } and a vector sequence {u _j }. Next we present a generalized Arnoldi procedure for generating an orthonormal basis of . By applying the projection and the refined technique, we derive a restarted generalized Arnoldi method and a restarted refined generalized Arnoldi method for solving a large-scale polynomial eigenvalue problem (PEP). These two methods are applied to solve the PEP directly. Hence they preserve essential structures and properties of the PEP. Furthermore, restarting reduces the storage requirements. Some theoretical results are presented. Numerical tests report the effectiveness of these methods. Yimin Wei is supported by the National Natural Science Foundation of China and Shanghai Education Committee.     

A periodic Krylov-Schur algorithm for large matrix products

Stewart's recently introduced Krylov-Schur algorithm is a modification of the implicitly restarted Arnoldi algorithm which employs reordered Schur decompositions to perform restarts and deflations in a numerically reliable manner. This paper describes a variant of the Krylov-Schur algorithm suitable for addressing eigenvalue problems associated with products of large and sparse matrices. It performs restarts and deflations via reordered periodic Schur decompositions and, by taking the product structure into account, it is capable of achieving qualitatively better approximations to eigenvalues of small magnitude. Supported by DFG Research Center Matheon, Mathematics for key technologies, in Berlin.     

Block Krylov–Schur method for large symmetric eigenvalue problems

Stewart’s Krylov–Schur algorithm offers two advantages over Sorensen’s implicitly restarted Arnoldi (IRA) algorithm. The first is ease of deflation of converged Ritz vectors, the second is the avoidance of the potential forward instability of the QR algorithm. In this paper we develop a block version of the Krylov–Schur algorithm for symmetric eigenproblems. Details of this block algorithm are discussed, including how to handle rank deficient cases and how to use varying block sizes. Numerical results on the efficiency of the block Krylov–Schur method are reported.